Truth Tables

Deciding by Exhaustion

A truth table lists every possible assignment of truth values to the atomic sentences and computes the value of the compound in each. Because there are no other possibilities, the table settles the matter completely, propositional logic is decidable, and the truth table is the decision procedure.

The size is fixed by the number of distinct atoms:

$$\text{rows} = 2^n$$

One atom gives 2 rows, two give 4, three give 8. The growth is the method's weakness: ten atoms need 1024 rows, and twenty need over a million. It always works and quickly stops being practical, which is precisely why natural deduction exists.

Building the table has a standard discipline. List the atoms, fill $2^n$ rows so every combination appears exactly once (halving the block size at each column keeps this systematic), then work outward from the smallest subformulas to the main connective. The column under the main connective is the sentence's own column.

The table classifies any sentence into one of three kinds:

Two sentences are logically equivalent when their columns match row for row. The De Morgan equivalences are the ones worth knowing by heart:

$$\neg(P \wedge Q) \equiv \neg P \vee \neg Q, \qquad \neg(P \vee Q) \equiv \neg P \wedge \neg Q$$

Negating a conjunction gives a disjunction, and vice versa. The connective flips.

Tables also test arguments. An argument is valid exactly when no row makes all premises true and the conclusion false, so you build the table and look for that one bad row. Finding none proves validity; finding one is a counterexample and disproves it outright.

Common pitfall: counting rows from the number of letters written rather than the number of distinct atoms. $P \wedge (P \vee Q)$ contains three letter-occurrences but only two distinct atoms, so it needs 4 rows, not 8.