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
A complete truth table is a valid proof of a propositional claim. It is also a useful way to audit a small logical transformation. Claims over infinite mathematical domains generally require additional reasoning beyond testing selected values.
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. In a classical contradiction proof, deriving a contradiction from the negated target establishes its double negation; eliminating that double negation yields the target. 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$ |
|---|---|---|---|---|---|
| T | T | T | F | F | T |
| T | F | F | T | F | F |
| F | T | T | F | T | T |
| F | F | T | T | T | T |
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 valid implication chain and an invalid converse.
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
- "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.
- "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.
- "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.
- "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:
- List every variable that appears. Count columns for variables ($n$) and for sub-formulas.
- Enumerate $2^n$ rows, conventionally in descending binary order.
- Fill each sub-formula column by composing from already-filled columns -- never skip steps.
- For equivalence claims, compute both formulas and compare column-by-column.
- For validity claims, highlight the rows where every premise is true and audit the conclusion on exactly those rows.
Transfer to the module project
Use this concept to state, justify or challenge one claim in the workflow project. Name the mathematical model and the execution assumptions separately; software behavior is not established by an analogy alone.
Check Yourself
- Why does one mismatching row show that two formulas are not equivalent?
- What does it mean if a formula is true in every row of its truth table? What about false in every row?
- How many rows does a truth table on $n$ variables have, and why is that growth rate a practical limit?
- Give an argument form that is valid but whose conclusion is false in the real world.
- Is $(P \rightarrow Q) \rightarrow P$ a tautology? If not, on which row does it fail?
- 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:
- $\lnot (P \land Q)$ and $(\lnot P) \lor (\lnot Q)$
- $(P \rightarrow Q) \land (Q \rightarrow R)$ and $P \rightarrow R$
- $P \leftrightarrow Q$ and $(P \land Q) \lor (\lnot P \land \lnot Q)$
- $P \rightarrow (Q \land R)$ and $(P \rightarrow Q) \land (P \rightarrow R)$
- $(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
Use the bounded reading guide to locate this lesson's topic in MCS or Rosen. These links open book indexes. Find the named topic in your edition, read one relevant explanation, then reconstruct the argument with the book closed.
Coverage is part of an exhaustive proof
A truth table is a proof when its rows cover every assignment to all distinct variables and each formula is evaluated correctly. If p occurs five times, it remains one variable, so it contributes a factor of two, not 32. For a constant formula there are zero variables and one empty assignment.
Validity can also be checked by searching for an assignment making all premises true and the conclusion false. A found assignment is a complete countermodel. If no such assignment exists after exhaustive enumeration, the argument is valid for propositional semantics. Unsatisfiable premises make an argument vacuously valid; they do not establish the premises as facts about a system.
Transfer attempt: enumerate the assignments to p,q for premises p→q and q, conclusion p. Identify the invalidating row and explain why the same row cannot invalidate modus ponens with premises p→q and p.
Use Practice Solutions and Feedback after your attempt, and Proof and Model Contracts to audit assumptions.