1.4 Indirect proof

Truth tables are a decision procedure through which one can always determine whether a formula (or a sentences of such form) is contingent, a tautology, or a contradiction. Another (not decision but) proof procedure, whereby a formula is proven to be a tautology or to be a contradiction, is the indirect proof. This method is sometimes more convenient than the use of truth tables, especially when a formula is too complex and the rows in its truth table are too many. Possibly its disadvantage is that it is not completely mechanical and the success of the proof depends to some extent (in fact not at all a great one) on the ingenuity of the one who is proving.

To indirectly prove that a formula is a tautology, we assume that it has the value F and, based on this assumption, we begin to draw conclusions about the truth values of its subformulas. The goal is to come to a contradiction, i.e. to a subformula having both the value T and the value F. It will follow from the contradiction that the assumption is impossible, i.e. it is impossible for the initial formula to have the value F, which means that it always has the value T, i.e. it is a tautology.

As an example, we will prove that the formula “[(p→q)∧¬q]→¬p” is a tautology. Assume that it has the value F:

A conditional is false only if its antecedent (here “(p→q)∧¬q”) is T and its consequent (here “¬p”) is F. Therefore, from 1. we may conclude the following two things:

On the right in а line of а proof we indicate the line numbers from which follows what is asserted in the line. Since in 2. we have a true conjunction, and a conjunction is true if and only if both its conjuncts are true, then “p→q” and “¬q” must be true:

Since in 3. we have that “¬p” has the value F, so “p” has the value T:

For the same reason from 5. it follows that “q” must have the value F:

Since in 6. we obtained that “p” has the value T, and in 7. that “q” has the value F, from the truth table of the conditional it follows that their conditional “p→q” is false:

However 8. contradicts 4., where we have that “p→q” has the value T. With that, the indirect proof is complete. Due to the contradiction, the initial assumption is impossible – “[(p→q)∧¬q]→¬p” cannot be false and therefore is a tautology.

The proof that a formula is a contradiction rather than a tautology differs only in the initial assumption, which is no longer that it has the value F, but the value T. If this assumption leads to a contradiction, it is impossible for the formula to have the value T, which means that it is a contradiction. As an example, let us prove that “¬[(р∧¬q)∨¬(¬q∨r)]∧(p∧¬r)“ is a contradiction:

In 11. we draw the conclusion that “¬q” is false since we know (from 4. and 8.) that the conjunction “p∧¬q” is false while its constituent “p” is true. For a conjunction to be false, at least one of its constituents has to be false. It is not “p”, so it has to be “¬q”. In 12. we conclude that “r” is true because the disjunction “¬q∨r” is true while its constituent “¬q” is false. For a disjunction to be true, at least one of its disjuncts must be true; “¬q” is false, so “r” has to be true. The other conclusions in the proof are either that the conjuncts of a true conjunction are true (2., 3., 4. and 5.), or that the disjuncts of a false disjunction are false (8. and 9.), or that a negated formula has the opposite truth value from the negation (6., 7. and 10.).

In principle, we can draw a conclusion from the truth value of a formula about the truth values of its constituents only if it is a negation, or true conjunction, or false disjunction, or false conditional, because then there is only one possibility for the truth values of its constituents. On the contrary, for example we cannot draw a conclusion from the truth of the conditional “α→β” about the truth values of α or β, because they may be both true, or both false, or α may be false and β true. In such cases we need additional premises to draw a conclusion (as it is in 11. and 12. above). When there is no such additional information, different cases need to be considered. For example, from the fact that “p∧q” has the value F, we may conclude that either “p” or “q” (or both) have the value F, but since we do not know which of them is false, we have to consider two (non-exclusive) cases: when “p” is false and when “q” is false. Then, in order to prove that the initial formula is a tautology (contradiction), we have to come to a contradiction in both cases.¹ As considering different cases complicates the proof, we should try to do without it. However, this is not always possible. For example, if we want to prove that a biconditional formula is a tautology or a contradiction, we have to examine two cases because “α↔β” is true if and only if α and β are both true or both false.

Indirectly proving that a formula is a tautology or a contradiction, we may come to different forms of contradiction in different ways. Moreover, we can only come to a contradiction if the initial formula is a tautology and we assume that it is false, or if it is a contradiction and we assume that it is true. If the formula is contingent, we cannot come to a contradiction. We cannot come to a contradiction also if the formula is a tautology and we assume that it is true, as well as if it is a contradiction and we assume that it is false. Insofar as we generally do not know in advance what the type of the formula under consideration is, this is a disadvantage that is missing in truth tables. We a going to introduce another method for determining the type of a formula (truth-value analysis) that has the advantages of both methods, without their disadvantages – like truth tables, it is a proof procedure that always gives an answer, and like indirect proof, it is often shorter.

Exercises