Truth tables

Three letters give 2 × 2 × 2 = 8 rows, and a truth table writes out every one of them, so no case is left to guesswork.

One row for every possible situation

The connectives from the last two units have a useful property: once you know whether each simple part is true or false, the truth value of the whole compound is fixed. A truth table uses this. It lists every possible combination of truth values for the simple statements, one combination per row, and then works out the value of the compound statement in each row. Nothing about the meaning of the sentences is needed, only the T and F values.

How many rows? Each simple statement can be T or F, so every new letter doubles the count. One letter gives 2 rows, two letters give 4, three give 8, and n letters give 2 to the power n. A table with five letters already has 32 rows, which is why people who use truth tables a lot keep their formulas short. The usual way to write the rows, used in forall x and most textbooks, is to split the first column into a top half of T and a bottom half of F, the second column into quarters, and so on, until the last column alternates T, F, T, F. That pattern guarantees that no combination is missed or repeated.

Working from the inside out

Take the statement (p ∨ q) ∧ ¬r. After the three input columns, add a column for each piece in the order you would work out brackets in arithmetic: first p ∨ q, then ¬r, then the main connective ∧ that joins them. In each row you only ever apply one small rule from the earlier units. The final column is the answer. Here the whole statement is true in 3 of the 8 rows, the ones where r is false and at least one of p and q is true.

Tautologies, contradictions and equivalence

Some final columns come out all T. The statement p ∨ ¬p (“it is raining or it is not raining”) is true in every row, whatever the weather. A statement like that is called a tautology, or a logical truth. Others come out all F, such as p ∧ ¬p; these are contradictions. Most statements are true in some rows and false in others, and are called contingent: whether they are true depends on how the world is.

Two statements are equivalent when their final columns match row for row. This is how you check De Morgan’s laws or the claim that a conditional matches its contrapositive: build both columns over the same inputs and compare. The table also shows that p → q has the same column as ¬p ∨ q, which is a handy way to rewrite a conditional when a problem only lets you use not, and and or.