Truth tables More about propositional logic

When negation was introduced in chapter 7, the explanation leading to the double negation rules made use of some simple tables recording the effect of negation on truth and falsehood (it switches them). The idea of such truth tables extends naturally to other connectives. Every statement has exactly one of two truth values which we shall symbolise '0' and '1'. Intuitively, true statements have the value 1 and false ones have the value 0. An interpretation of the formal language of propositional logic is simply an assignment of truth values to the sentence letters. This results in a value for each formula. The rules by which these values are calculated are summarised in the truth tables.

For negation, as already foreshadowed, we have

meaning that for any formula A whatsoever, if A has the value 0 on a particular interpretation then NOTA has the value 1 on that interpretation, and vice versa. Because there is only one parameter, A, there are just two cases to consider corresponding to the two values it might have. The dyadic connectives, naturally, have two parameters A and B each of which might have either value, so there are four possible cases to consider corresponding to the various combinations of values:

These tables should be memorised.

Look first at the column under A AND B. This truth table for conjunction says that for A AND B to be true (to take the value 1) it is both necessary and sufficient that each of its two conjuncts should have the value 1. If either of them is false, then the conjunction is false regardless of the value of the other conjunct. I hope this is at least plausible, not to say obvious. Next look at the table for disjunction. According to this, a disjunction is true if at least one disjunct is true and false only in the one case in which both disjuncts are false. This emphasises that we are working with inclusive disjunction, for we have 1 as value on the bottom line.

The table for IMP is less obviously well motivated. We can see why A IMP B should be false (value 0) when A is true and B false, for the conditional says there is an available inference from A to B, and this has to be incorrect if A is true but B is not. But why the value 1 in all other cases regardless of the content of A and B? One answer is given by the (syntactic) provability of the two sequents

q   ⊢   p IMP q

and

NOTp   ⊢   p IMP q

The first of these shows that according to the rules needed to prove it, q entails p IMP q and by substitution of A and B for p and q, B entails A IMP B. That is to say, on our working definition of validity and entailment, if B is true then A IMP B has to be true as well. The second shows similarly that if A is false then A IMP B must be true. Given these facts about entailment, the truth table is forced to be the way it is. So whatever lent plausibility to the rules such as IMPI and RAA can now be enlisted in support of the given truth table for implication.

The connective 'IFF' makes an appearance here, having been neglected during the development of the proof system. It is pretty much a peripheral operation as far as formal logic is concerned, A IFF B simply being defined as (A IMP B) AND (B IMP A). It will be seen from the truth table that this is true if A and B have the same truth value and false if their values are different. An alternative definition of A IFF B, in fact, would be (A AND B) OR (NOTA AND NOTB). You can work through the truth tables to see why these two definitions amount to the same thing. This sameness of truth value is a weak sort of equivalence between A and B known in the literature as material equivalence. Little will be said concerning it here as it is of limited interest, serving mainly as a device to shorten formulas.

Truth tables for complex formulas can be built up from those for their parts. To illustrate, let us compute the value of the formula (p OR q) AND NOT(q IMP NOTr) for an interpretation which assigns 1 to p, 1 to q and 0 to r.

Having filled in the values of the three atoms p, q and r we copy those values under the occurrences of the atoms in the formula. Then we fill in the value of each subformula under its main connective, appealing to the truth tables for connectives to determine the values. Eventually the value of the whole formula appears under its main connective. In this case that means under the 'AND' where there is a 0 because we apply the table for conjunction to the 1 under the 'OR' and the 0 under the 'NOT'.

The process can be repeated for every possible assignment of values to the three atoms, giving the construction in truthTable. The complete truth table for this particular formula is given as the (bold face) column under the main connective. Notice that the construction technique, unlike the process of searching for proofs, is entirely mechanical, requiring no ingenuity or imagination. Truth tables therefore yield an automatic procedure for analysing complex formulas.

Recall that a set X of premises entails a conclusion A iff it is impossible for everything in X to be true while A is false. Accordingly, we say that a sequent X : A is valid iff there is no interpretation giving the value 1 to every formula in X and the value 0 to A. To test a given sequent for validity, therefore, we can in principle just construct its truth table, consisting of the truth tables of its constituent formulas side by side, and look for a row which has '1' under the main connective of each premise and '0' under the main connective of the conclusion. If there is such a row, the sequent is invalid. If there is no such row, it is valid. It is clear that the truth table test gives a purely mechanical procedure for deciding on the validity or invalidity of sequents. We use a double turnstile

X ⊨ A

to claim that a sequent is valid in this semantic sense with respect to truth tables. In the limiting case we write

⊨ A

to claim that A comes out true for every assignment of values to its constituent sentence letters. Such a formula is said to be a tautology.

In practice it is tedious to write out all the rows of a truth table test, and mistakes are easily made especially if there are many atoms in the formula or sequent being tested. To overcome this problem we may devise more efficient testing algorithms based on the observation that the only rows worth considering are those in which refutations occur. To illustrate, consider

(p IMP (q OR r)) IMP (NOT(s AND q) IMP ((p AND s) IMP r))

We are to test this to see whether it is a tautology. Its full truth table has 16 rows because of its 4 atoms, so doing this the stupid way is at best laborious. Instead we note that we are seeking a row—any row—in which there is a 0 under the main connective. The formula is a conditional, so by inspection of the truth table for conditionals we can see that it takes value 0 iff its antecedent takes 1 and its consequent 0. So we can start to fill in the significant row:

Now the whole consequent side is another false conditional, so we can repeat the same reasoning, and repeat again, to reach

But now we have a value of 1 for NOT(s AND q), so clearly s AND q must get 0. Also, since we have 1 for p AND s, both p and s must get 1:

Now we have values for p, r and s which can be copied to their other occurrences in the formula:

We have a true conditional p IMP (q OR r) whose antecedent p is also true, so its consequent q OR r must be true as well. Since r is evaluated as 0, q must therefore get 1. But this is absurd, since s AND q has 0 and s has 1, so q must get 0.

We have therefore reduced the supposition to absurdity. That supposition was that the whole formula could have the value 0 on some interpretation. Hence there can be no such interpretation, so the formula is indeed a tautology.

Click here for a walkthrough of the above argument—complete with background magpie.

The general principle of this kind of test is to begin by writing '1' under the main connective of each premise if there are any, and '0' under the main connective of the conclusion. That is, we suppose there were a refuting interpretation. Then we reason, using the truth tables, about how such an assignment could possibly have got there. This forces more assignments of values to smaller and smaller subformulas. If an absurdity results—for instance, if some subformula gets assigned both values—then the sequent we are testing has been shown valid. If not, we eventually reach a state in which every subformula has a value and nothing clashes with truth tables. This gives us an interpretation which shows the sequent to be invalid. It sometimes happens that no more assignments of values are forced by what we have, even though the line of values is incomplete. When this occurs we must choose a subformula which has no value yet and try the two continuations formed by assigning it 0 and 1 respectively. That is, we look at two potential rows of the truth table instead of one. If either one results in a complete assignment of values free from absurdity then the original sequent was invalid. For a simple example, consider

p OR q,   p IMP q   ⊢   p AND q

The initial assignment of values gives

but now the truth tables do not directly force any more values on subformulas, for there are multiple ways for disjunctions and implications to be true, and for conjunctions to be false. We therefore choose a subformula—q is as good as any—and first try assigning it the value 0:

Absurdity quickly results, since in order to make p OR q true now p must be true, but in order to make p IMP q true p must be false:

The formula q must therefore have the value 1, since assigning it 0 led to a contradiction. So make that assignment:

In order to get p AND q to be false, this forces p to be false:

This is a complete assignment of values which does not violate any truth tables, so we have found an interpretation—the only one in fact—which invalidates the sequent.

It may occur to you that if there were a way to make this kind of reasoning about truth tables fully rigorous and general, we would have a powerful tool for dealing with propositional logic. Well, there is good news regarding this idea, for which please read on!