Validity and the Indirect Method

Site: Saylor Academy
Course: PHIL102: Introduction to Critical Thinking and Logic
Book: Validity and the Indirect Method
Printed by: Guest user
Date: Wednesday, October 27, 2021, 4:03 PM

Description

Read these two tutorials, which provide information on how to determine if an argument – or sequent – is valid or not in SL. Because using truth-tables to establish validity is time consuming, the second tutorial presents a shortcut version of the method.

Complete the exercises for both tutorials and check your answers.

Validity

§1. The Full Truth-Table Method


In this tutorial we study how to make use of full truth-table method to check the validity of a sequent in SL. Consider this valid sequent:

P, (P→Q) ⊧ Q

To prove that it is valid, we draw a table where the top row contains all the different sentence letters in the argument, followed by the premises, and then the conclusion. Then, using the same method as in drawing complex truth-tables, we list all the possible assignments of truth-values to the sentence letters on the left. In our particular example, since there are only two sentence letters, there should be 4 assignments :

P Q P ( P Q )
T T
T F
F T
F F


The next step is to draw the truth-table for all the premises and also the conclusion: 

P Q P ( P Q ) Q
T T T T



T
T F

T



F



F
F T

F



T



T
F F

F



T F


In the completed truth-table, the first two cells in each row give us the assignment of truth-values, and the next three cells tell us the truth-values of the premises and the conclusion under each of the assignment. If an argument is valid, then every assignment where the premises are all true is also an assignment where the conclusion is true. It so happens that there is only one assignment (the first row) where both premises are true. We can see from the last cell of the row that the conclusion is also true under such an assignment. So this argument has been shown to be valid.

In general, to determine validity, go through every row of the truth-table to find a row where ALL the premises are true AND the conclusion is false. Can you find such a row? If not, the argument is valid. If there is one or more rows, then the argument is not valid.


Exercise #1


§2. More Examples


P Q ( P Q ) ~ P ~ Q
T T T



F


F
T F



F



F


T
F T



T



T


F
F F



T



T


T


To show that a sequent is invalid, we find one or more assignment where all the premises are true and the conclusion is false. Such an assignment is known as an invalidating assignment (a counterexample) for the sequent.

Let's look at a slightly more complex sequent and draw the truth-table:

(~P∨Q), ~(Q→P) ⊧ (Q↔~P)

Again we draw a truth-table for the premises and the conclusion:

P Q ( ~ P Q ) ~ ( Q P ) ( Q ~ P )
T T F T T T


F
T T T



T F F T
T F


F T F F


F
F T T



F T F T
F T


T F T T


T
T F F



T T T F
F F


T F T F


F
F T F



F F T F


To help us calculate the truth-values of the WFFs under each assignment, we use the full truth-table method to write down the truth-values of the sentence letters first, and then work out the truth-values of the whole WFFs step by step. The truth-values of the complete WFFs under each assignment is written beneath the main operator of the WFFs. As you can see, the critical one to check is the third assignment. Since there is no assignment where the premises are true and the conclusion is false, the sequent is valid.



Exercise #2

Examine this table and answer the questions:

P Q ~ Q ( P Q ) ~ P
T T F T T T T F T
T F T F T F F F T
F T F T F F T T F
F F T F F T F T F



Exercise #3

True or false?


Exercise #4

Exercise #5

Confirm for yourself that the WFFs in each pair of WFFs below are logically equivalent to each other :

  • (P→Q), (~Q→~P)
  • (P↔Q), (~P↔~Q)
  • ~(PvQ), (~P&~Q)
  • ~(P&Q), (~Pv~Q)


§3. Some Informal Comments on Decidability


One thing you might notice about the full truth-table method is that it can help us determine the validity of any sequent in SL. A program can be written that, given any finite sequent in SL as input, after a finite number of processing steps, produces an output "Yes" if the sequent is valid, or an output "No" if it is not. Of course, the computer would need to have a lot of memory if the sequent is a long one, but in principle it can be done. This is roughly what logicians mean when they say that validity in SL is decidable. Intuitively, it is a matter of whether there is an algorithm or computer program that can come up with a proof of either the validity or the invalidity of a sequent.

What is interesting and perhaps surprising is that decidability no longer obtains when we are dealing with some more powerful systems of logic. One of the most important discoveries in modern logic is that mathematics is undecidable. In particular, Gödel's first incompleteness theorem says that any consistent systems of mathematics would have to include statements that can neither be proved or disproved. In other words, it is impossible for there to be a computer program that can tell whether these statements are true.



Source: Joe Lau and Jonathan Chan, https://philosophy.hku.hk/think/sl/full.php
Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 License.

The Indirect Method

The full-truth-table method can be used to determine whether any given sequent in SL is valid or not. But as the number of sentence letters in the sequent increases, the number of rows we have to fill in increases exponentially. Here we introduce a more efficient method for determining validity.

Here is the reasoning behind the so-called indirect method (or the reductio method): the full truth-table method shows that an argument is valid by examining all possible assignments of truth-values. However, to show that an argument is not valid, all we need to do is to find one assignment where all the premises are true and the conclusion is false. So in this method we first assume that the argument is invalid, and try to find one invalidating assignment. If we succeed, then the argument has been shown to be invalid. Otherwise it will lead to inconsistency, and we can conclude that the argument is valid after all.


§1. A Valid Sequent


Let us use modus ponens again as a simple example. We start by writing down the premises and the conclusion :

P (P→Q) Q
 


If the sequent is invalid, then there is at least one assignment where both premises are true and the conclusion is false. So let us suppose this is true. So we write T below the premises and F under the conclusion :

P (PQ) Q
T T F


This tells us that if the argument is invalid, “P” is true and “Q” is false. So we write the truth-values of these sentence letters on the second row :

P (P→Q) Q
T T T F F


But now we have discovered a contradiction : If “P” is T and “Q” is F, then “(P→Q)” has to be false, and not T as indicated. Since the original assumption that the sequent is invalid leads to a contradiction, we conclude that the assumption must be false. So the sequent is actually valid.


§2. An Invalid Sequent


Let us now look at the following sequent. Again we assume that it is invalid by writing T below the main operators of the premises and F below that of the conclusion :

(P∨Q) (~P&Q) (Q↔P)
T T F


We now proceed to determine the truth-value of the individual sentence letters under such an assignment. Note that the second premise is a conjunction, so if it is true, then both conjuncts must be true. In other words, Q has to be true and so P has to be false :

(P ∨ Q) (~P & Q) (Q ↔ P)
 F T T T F T T T F F
10 1 8 5 6 2 4 7 3 9


The numbers on the third row shows the order in which the truth-values are filled in, to help you understand how the table is arrived at : Since “(~P&Q)” is T, “Q” is T (step 4) and “~P” is T (step 5), which also means that “P” is F (step 6). We then copy the truth-values of “P” and “Q” to other wffs (steps 7-10). As you can see, this particular assignment of truth-value does not lead to any contradiction. So this assignment shows that it is possible for the premises to be true and the conclusion to be false at the same time. We have therefore come up with an invalidating assignment that proves that the sequent is invalid, and without having to list all the possible assignments.


Exercise #1