Truth Tables

Why bother building a table of true/false rows when most arguments only need one example? Because logic compounds: once $P$, $\neg P$, $P \wedge Q$, $P \vee Q$, $P \Rightarrow Q$ are all in play, the rules tangle fast. A truth table is the brute-force ground truth: list every possible world, evaluate the formula in each, and compare. If two formulas agree in every row, they are interchangeable forever. If a formula is true in every row, it is a theorem of pure logic. Truth tables are how mathematicians and computer scientists certify their logical equipment is sound before they trust it on real proofs.

The mechanical idea

A truth table lists every assignment of truth values to the propositional variables and computes the truth value of the compound formula in each row. If the formula has $n$ variables, the table has exactly $2^n$ rows — each variable is either $T$ or $F$, independently of the others.

For two variables $P$ and $Q$ the table has $2^2 = 4$ rows. The basic connectives $\wedge$ (AND), $\vee$ (OR), $\neg$ (NOT), $\Rightarrow$ (implies), and $\Leftrightarrow$ (iff) each have a fixed rule for combining truth values. The widget below lets you toggle $P$ and $Q$ or type your own formula and watch the column appear in real time.

Tautology, contradiction, contingency

The shape of a formula's truth column tells you what kind of statement it is:

• A tautology has a column of all $T$. The classic example is $P \vee \neg P$, the law of excluded middle: no matter what $P$ is, the formula is true.
• A contradiction has a column of all $F$. The classic example is $P \wedge \neg P$: a statement cannot be both true and false at once.
• A contingency has both $T$ and $F$ rows — the formula's truth depends on the world. Most everyday statements are contingencies.

Logical equivalence

Two formulas are logically equivalent — written $\varphi \equiv \psi$ — when they agree in every row of their joint truth table. Equivalent formulas are interchangeable in any proof: each one means exactly the same thing.

The two cornerstone equivalences of elementary logic are De Morgan's laws:

Read aloud: "not (P and Q)" is the same as "not P or not Q." When you negate an AND statement, the negation distributes across the conjuncts and the connective flips. The same move works for OR — negation turns OR into AND. Both laws collapse to a single mental rule: push the negation through, flip the connective.

Another foundational equivalence connects implication to disjunction: $P \Rightarrow Q \equiv \neg P \vee Q$. This one is worth knowing by heart because it lets you rewrite any conditional as a simple OR — the bridge between the language of implication and the language of disjunction.

Pause and think: Why is $P \Rightarrow Q$ logically equivalent to $\neg P \vee Q$? Trace each of the four (P, Q) rows in your head before you continue. (Hint: the only failing row for implication is $P = T$, $Q = F$ — the only row where $\neg P \vee Q$ is also false.)

Try it

• Before opening the widget: how many rows does the truth table for $(P \wedge Q) \vee R$ have? Type the formula in the custom-expression box and count.
• Predict first: is $P \Rightarrow (Q \Rightarrow P)$ a tautology, a contradiction, or a contingency? Verify with the widget.
• De Morgan check: predict the column of $\neg(P \wedge Q)$ for each of the four (P, Q) assignments. Now toggle the inputs through all four and see if your prediction matches.
• Equivalence drill: are $P \Leftrightarrow Q$ and $(P \Rightarrow Q) \wedge (Q \Rightarrow P)$ logically equivalent? Build both columns and compare row by row.

A trap to watch for

Beginners often read $P \Rightarrow Q$ as "if $P$ then $Q$" and instinctively make the conditional false whenever $P$ is false. That is wrong. The conditional $P \Rightarrow Q$ is true whenever $P$ is false, no matter what $Q$ says. The truth table is: $(T,T)\to T$, $(T,F)\to F$, $(F,T)\to T$, $(F,F)\to T$. The only way an implication can fail is if the antecedent is true but the consequent is false. Conditionals with a false antecedent are vacuously true — they make no claim about reality, so by default they are true. This is initially uncomfortable, but it is the only definition that makes the rest of logic (modus ponens, contrapositive, chained reasoning) hang together.

What you now know

You can take any compound propositional formula, enumerate the $2^n$ rows of its truth table, and read off whether it is a tautology, contradiction, or contingency. You can also test whether any two formulas are logically equivalent — the gold-standard equivalence test in propositional logic. In the next section, conditionals and biconditionals, you will use these tables to verify the law of contrapositive and prove that some seemingly different statements are actually the same.

References

• Velleman, D. J. (2019). How to Prove It: A Structured Approach (3rd ed.). Cambridge University Press, ch. 1.
• Enderton, H. B. (2001). A Mathematical Introduction to Logic (2nd ed.). Academic Press, §1.2.
• Smullyan, R. M. (1995). First-Order Logic. Dover Publications, ch. 1.
• Biere, A., Heule, M., van Maaren, H., Walsh, T. (eds.) (2009). Handbook of Satisfiability. IOS Press, ch. 1.
• Knuth, D. E. (2015). The Art of Computer Programming, Vol. 4A: Combinatorial Algorithms, Part 1. Addison-Wesley, §7.1.1.