Skip to main content

Truth Tables, Validity, and Equivalence

What This Concept Is​

A truth table is an exhaustive enumeration of every possible truth-value assignment to the propositional variables in a formula, together with the resulting truth value of the formula itself. For a formula with $n$ variables, the truth table has $2^n$ rows. Truth tables are the ground-truth semantics for propositional logic: if you want to know whether something is a tautology, a contradiction, or equivalent to another formula, the truth table settles it mechanically.

Three adjacent ideas share this page:

  • A tautology is a formula that is true on every row. Example: $P \lor \lnot P$.
  • A contradiction is a formula that is false on every row. Example: $P \land \lnot P$.
  • A formula that is true on at least one row but not all is contingent.

Validity generalises these ideas to arguments. An argument form "premises $\Gamma$, therefore $C$" is valid when every row that makes all premises in $\Gamma$ true also makes $C$ true. Validity is not about whether the premises are actually true in the world -- it is about whether the conclusion follows.

Logical equivalence ($P \equiv Q$) means $P$ and $Q$ have the same value on every row of a joint truth table. In proof practice, this is the substitution license: equivalent formulas can replace each other anywhere a formula is expected.

The key conceptual move is to stop thinking of propositional formulas as sentences and start thinking of them as functions from assignments to truth values. Two formulas are equivalent iff they are the same function.

Why It Matters Here​

Truth tables are not the final goal of proof writing -- you will almost never hand in a proof that is a truth table. But they are the debugging instrument for propositional reasoning. When you are unsure whether a transformation preserves truth, when you suspect a misremembered identity, when a proof "seems right" but reads suspicious, a truth table gives an audit trail you can check in thirty seconds.

They also underwrite everything in Cluster 2. Contrapositive proofs work because the truth table of $P \rightarrow Q$ matches the table of $\lnot Q \rightarrow \lnot P$ row-for-row. Proof by contradiction works because $P$ and $\lnot \lnot P$ have the same table. When a student asks "why is this method allowed?" the rigorous answer is "because the two formulas are equivalent, and here is their shared table."

Later in the curriculum, truth tables come back as the semantics under Boolean circuit design (Semester 4), as the model-theoretic foundation of SAT and SMT solvers (Semester 9 and beyond), and as the correctness check on every if/else/&&/|| rewrite a compiler performs.

Concrete Examples​

Example 1 -- contrapositive equivalence.

Build the truth table for $P \rightarrow Q$ and $\lnot Q \rightarrow \lnot P$ together:

$P$$Q$$P \rightarrow Q$$\lnot Q$$\lnot P$$\lnot Q \rightarrow \lnot P$
TTTFFT
TFFTFF
FTTFTT
FFTTTT

The third and sixth columns agree on every row. Therefore $P \rightarrow Q \equiv \lnot Q \rightarrow \lnot P$. This is why a "proof by contrapositive" is not a stylistic trick -- it proves an equivalent statement.

Example 2 -- a chain that is almost but not quite a tautology.

Is the following argument form valid?

From $P \rightarrow Q$ and $Q \rightarrow R$, conclude $P \rightarrow R$.

Check: among the eight rows of a $P, Q, R$ table, find every row where both $P \rightarrow Q$ and $Q \rightarrow R$ are true, and verify $P \rightarrow R$ is true on each. It is. The argument form is hypothetical syllogism and it is a valid tautology of the form $((P\rightarrow Q) \land (Q \rightarrow R)) \rightarrow (P \rightarrow R)$.

Now contrast with a nearly identical form:

From $P \rightarrow Q$ and $Q \rightarrow R$, conclude $R \rightarrow P$.

Row with $P = F, Q = F, R = T$ makes both premises true but makes $R \rightarrow P$ false. One bad row is enough -- the argument form is invalid.

Example 3 -- an identity you will reuse.

De Morgan's law for conjunction: $\lnot(P \land Q) \equiv \lnot P \lor \lnot Q$. Build the truth table; all four rows agree. You will cite this identity during set-equality proofs ("an element is not in $A \cap B$ iff it is not in $A$ or not in $B$"), during quantifier negation ("not (for all $x$ both $P$ and $Q$)"), and during Boolean-algebra refactors in code.

Common Confusion / Misconceptions​

  1. "A few example rows are enough." Wrong. Equivalence is a universal claim -- every row must agree. One missed row can be the counterexample that sinks the claim. Discipline move: if your truth table has fewer than $2^n$ rows, you have not yet shown equivalence.
  2. "Equivalence means similar meaning." In logic, equivalence is exact: same truth value on every row. "$P$ and $Q$" feels different from "$Q$ and $P$" in English, but the truth tables match, so they are equivalent.
  3. "Validity of an argument means its conclusion is true." Validity is about form, not fact. "All fish can fly; nemo is a fish; therefore nemo can fly" is a valid argument with a false premise and a false conclusion. Validity only says: if the premises were true, the conclusion would be too.
  4. "Truth tables scale." They do not. For $n = 20$ variables you already need a million rows; realistic logical formulas in software have hundreds of variables. For those cases you hand off to SAT solvers, which use cleverer algorithms than brute enumeration. Truth tables remain a thinking tool for small formulas.

How To Use It​

When a question about propositional formulas is in play, reach for a truth table if:

  • you want to verify a proposed equivalence before citing it;
  • you want to test whether a formula is a tautology, contradiction, or contingent;
  • you want to check the validity of a short argument form;
  • a classmate hands you a "clever" step and you are not sure it preserves truth.

Do not rely on truth tables for:

  • universally quantified statements with infinite domains (those need a proof, not enumeration);
  • set-theoretic claims where elements are not bits;
  • arguments involving more than about 5 variables (use Boolean laws or a solver).

An operational checklist for building a reliable truth table:

  1. List every variable that appears. Count columns for variables ($n$) and for sub-formulas.
  2. Enumerate $2^n$ rows, conventionally in descending binary order.
  3. Fill each sub-formula column by composing from already-filled columns -- never skip steps.
  4. For equivalence claims, compute both formulas and compare column-by-column.
  5. For validity claims, highlight the rows where every premise is true and audit the conclusion on exactly those rows.

Transfer / Where This Shows Up Later​

  • Semester 2 (algorithms). Short-circuit evaluation rules in algorithm pseudocode (e.g., x != null && x.foo()) are truth-table facts; swapping the operands changes behaviour because && is not commutative in call-by-value languages even though it is logically commutative.
  • Semester 4 (systems / hardware). Every combinational circuit is literally a truth table realised in gates; Karnaugh maps are optimised-layout truth tables.
  • Semester 6 (distributed systems). Model checkers exhaustively search state spaces, which for small systems is exactly building a very large truth table of reachable configurations.
  • Semester 9+ (formal methods). SAT/SMT solvers accept formulas and decide satisfiability -- asking whether any row of the implicit truth table makes the formula true. The truth table is the semantic grounding; solvers are the scalable implementation.

Check Yourself​

  1. Why does one mismatching row show that two formulas are not equivalent?
  2. What does it mean if a formula is true in every row of its truth table? What about false in every row?
  3. How many rows does a truth table on $n$ variables have, and why is that growth rate a practical limit?
  4. Give an argument form that is valid but whose conclusion is false in the real world.
  5. Is $(P \rightarrow Q) \rightarrow P$ a tautology? If not, on which row does it fail?
  6. Why is $P \rightarrow Q$ equivalent to $\lnot P \lor Q$, and where would you use this identity in code?

Mini Drill or Application​

Build full truth tables for each pair, then state whether the two formulas are equivalent. If not, identify the row where they disagree:

  1. $\lnot (P \land Q)$ and $(\lnot P) \lor (\lnot Q)$
  2. $(P \rightarrow Q) \land (Q \rightarrow R)$ and $P \rightarrow R$
  3. $P \leftrightarrow Q$ and $(P \land Q) \lor (\lnot P \land \lnot Q)$
  4. $P \rightarrow (Q \land R)$ and $(P \rightarrow Q) \land (P \rightarrow R)$
  5. $(P \lor Q) \rightarrow R$ and $(P \rightarrow R) \lor (Q \rightarrow R)$

For each pair, note whether you could have predicted the answer from a known identity (De Morgan, distributive, implication-as-disjunction).

Read This Only If Stuck​