[SL08] 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 :

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 :

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 :

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 :

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 :

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.