Truth Tables Explained: From Connectives to Tautologies

Logic & propositions · Updated July 2026

Truth tables are the first tool every discrete math student learns, and one of the most underrated. They turn arguments about logic into a mechanical procedure: list every possible combination of truth values, evaluate, and read off the answer. If you can build a truth table reliably, you can verify equivalences, test arguments for validity, and debug your own reasoning. This guide walks through the connectives, the build procedure, and the classifications that exams love to ask about.

Propositions and the six connectives

A proposition is a statement that is either true (T) or false (F) — no third option. "7 is prime" is a proposition; "close the door" is not. Compound propositions are built from simple ones using connectives:

Programmers have a head start here: ∧, ∨, ¬, and ⊕ behave exactly like &&, ||, !, and ^. The two that trip people up are implication and the biconditional, because everyday English handles "if…then" loosely.

Why is p → q true when p is false?

This is the single most-asked question in introductory logic. Think of p → q as a promise: "if it rains, I will bring an umbrella." If it does not rain, the promise was never tested — you have not broken it, whatever you did with the umbrella. A promise is only broken in one situation: the condition happened (p true) and the commitment failed (q false). So implication is false in exactly one of its four rows, and "vacuously true" in the two rows where p is false. Internalizing this single row is worth several exam points, because implications hide inside almost every proof and every logical equivalence.

How to build a truth table by hand

1. Count the variables. With n variables you need 2ⁿ rows: 2 variables → 4 rows, 3 variables → 8 rows, 4 → 16.
2. Enumerate systematically. The standard pattern: the rightmost variable alternates T, F every row; the next alternates every two rows; the next every four. This guarantees you never miss or duplicate a case.
3. Add one column per subexpression. For (p ∧ q) → ¬r, make columns for p ∧ q, then ¬r, then the whole implication. Evaluating inside-out, one operator at a time, is slower than doing it in your head — and dramatically more accurate.
4. Fill columns top to bottom, not rows left to right. Working a whole column keeps you applying one rule at a time.

Tautology, contradiction, contingency

Once the final column is filled, classify the expression:

• A tautology is true in every row — like p ∨ ¬p. Tautologies are the skeletons of valid arguments.
• A contradiction is false in every row — like p ∧ ¬p. Deriving one is the engine of proof by contradiction.
• A contingency is anything mixed: true in some rows, false in others. Most everyday statements are contingencies.

Two expressions are logically equivalent when their final columns match on every row. That is how you verify the workhorses of the course: De Morgan's laws (¬(p ∧ q) ≡ ¬p ∨ ¬q), the conditional identity (p → q ≡ ¬p ∨ q), and the contrapositive (p → q ≡ ¬q → ¬p). Equivalence via matching columns is also the safety net when an algebraic derivation of an equivalence goes sideways: eight rows of careful evaluation settle the argument.

Where truth tables show up later

Truth tables are not just a week-one topic. They reappear in Boolean algebra, where the same tables describe logic gates and circuit simplification; in proof methods, where the truth table for implication justifies the contrapositive technique; and in computer architecture and digital design courses, where a truth table is the specification a circuit must satisfy. Time invested in fluent, error-free table building pays off for several semesters.

Common mistakes

• Wrong row count or a skipped combination. Cured by the alternating enumeration pattern above.
• Evaluating a big expression in one mental step. One column per operator; the extra ink is cheap insurance.
• Misreading implication. Remember: false premise means the implication is true, full stop.
• Confusing ∨ with ⊕. Inclusive "or" is true when both sides are true; exclusive "or" is not. English usually means ⊕; logic usually means ∨.