A calculus of the absurd

17.2 Propositional logic

17.2.1 Truth tables

One very powerful (but perhaps not very elegant) way to reason about propositions is by writing a big table. The advantage of this is that it’s easy to ensure that we’ve considered every case (provided that we list every possible value). To do this, we must list them systematically. The convention is to combine the approach in Section 6.1.1 with the constraint that we want to list all variables possibilities in increasing order of size. I realise this probably makes no sense, so it’s best to proceed with an example:

  • Example 30 Prove that \(A \land (A \lor B) \equiv A\).

We want to draw a table which contains every possible value for \(A\) and \(B\). Note that we want to list the possibilities together, rather than separately (i.e. there are \(4\) total values to list as there are \(2\) possible values for \(A\) and then for each of those possibilities there are \(2\) possible values for \(B\))125125 See Section 6.1.3 if you are unsure about this.. What about this weird “increasing order of size”? First, examine the table

.
\(A\) \(B\) \(A \lor B\) \(A \land (A \lor B)\)
F F F F
F T T F
T F T T
T T T T

If we set \(F=0\) and \(T=1\), and then read the column \(A\) and that of \(B\) and concatenate the two values (e.g. in the first row of the table, take \(A=F=0\) and \(B=F=0\), so their concatenation is the string \(0\) followed by the string \(0\) again), then we wish to list them in increasing value (this just makes everything much clearer, and also makes it harder to make mistakes). In the table above we have \(00 < 01 < 10 < 11\). The same idea extends to larger tables.

Returning to the formula, it must be true, as the column for \(A\) is the same as the column for \(A \land (A \lor B)\).