23.2 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 18.3 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:
Prove that .
We want to draw a table which contains every possible value for and . Note that we want to list the possibilities together, rather than separately (i.e. there are total values to list as there are possible values for and then for each of those possibilities there are possible values for )22 2 See Section 18.1.2 if you are unsure about this.. What about this weird \sayincreasing order of size? First, examine the table
If we set and , and then read the column and that of and concatenate the two values (e.g. in the first row of the table, take and , so their concatenation is the string followed by the string 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 . The same idea extends to larger tables.
Returning to the formula, it must be true, as the column for is the same as the column for .