1
The number of rows is 2ⁿ
Each variable doubles the cases. Three variables give 8 rows, five give 32. This growth is why “Logical Equivalence”'s equivalence laws are worth having.
Lesson · Logic and Proof · Propositional logic
Truth Tables
A truth table lists every assignment of truth values to the variables and evaluates the formula at each. It is finite, mechanical and complete — and it is the only tool in this course that can never be wrong.
n variables ⟹ 2ⁿ rows 1 var: 2 2 vars: 4 3 vars: 8
Build inner subexpressions first, then combine them.
The table is COMPLETE: it checks every possible case.
The method, in three lines
Core ideas
What this lesson establishes
Truth tables are the ground truth of propositional logic. Every later shortcut is justified by the fact that a table would agree.
2
Columns go inside out
Evaluate the innermost subexpressions first and build outward, exactly as you would evaluate an arithmetic expression.
3
A table settles the question completely
If two formulas agree in every row they are equivalent, full stop. There is nothing further to check, because the rows are all the cases there are.
The material
Building a truth table
Rows first, then columns, then read the answer off the last one.
A truth table for a formula with variables p₁ … pₙ has one row per assignment of truth values to those variables. Since each variable takes two values independently, there are 2ⁿ rows — a fact that is really the product rule of counting, which Combinatorics and Counting makes explicit.
The conventional row order lists T before F and varies the rightmost variable fastest, so with two variables the rows read TT, TF, FT, FF. Any order works; a consistent one lets two tables be compared line by line.
Definition · Truth table
A table with one row per assignment of truth values to the variables of a formula, and one column per subexpression, ending with the value of the whole formula in that assignment.
The intermediate columns are not decoration. They are where a mistake is caught: if the final column looks wrong, the subexpression columns tell you exactly which step produced it.
Example · Building ¬(p ∧ q) step by step
First a column for p ∧ q (true in one row of four), then negate it (true in three). Compare with the column for ¬p ∨ ¬q: same four values. That agreement is De Morgan's law, and the table is its proof.
Theorem · Truth tables are complete for propositional logic
Any question about a formula built from ¬ ∧ ∨ → ↔ ⊕ — is it always true, is it ever true, is it equivalent to this other one — is answered by its truth table. There is no propositional question a table leaves open.
The catch is size, not correctness. Ten variables give 1024 rows and twenty give over a million; deciding whether a large formula is satisfiable is the canonical hard problem of computer science, and Algorithms and Complexity returns to it by name.
Interactive
Truth table
Every assignment, evaluated
Method
Constructing a table by hand
Five minutes of setup saves the errors that come from improvising.
1
Count the variables and write 2ⁿ rows
Three variables means eight rows. Getting this wrong at the start guarantees a wrong answer at the end.
2
Fill the variable columns systematically
Rightmost alternates every row, next every two rows, next every four. The pattern makes a missing row visible.
3
Add one column per subexpression
Innermost first. Each new column should depend only on columns already written.
4
Read the last column
All T is a tautology, all F a contradiction, a mixture is contingent — the vocabulary of “Tautology, Contradiction, Satisfiability”.
Reading and building tables
Score 0 / 0Choose the answer you can justify.
¬p ∨ (q ∧ r), in full
Three variables, so eight rows, and two subexpression columns: ¬p and q ∧ r, then the disjunction of the two.
p q r | ¬p q∧r | ¬p ∨ (q∧r)
---------------------------------------
T T T | F T | T
T T F | F F | F ← p true, q∧r false
T F T | F F | F
T F F | F F | F
F T T | T T | T
F T F | T F | T ← ¬p alone carries it
F F T | T F | T
F F F | T F | T
Read the shape of the last column. When p is false, ¬p is true and the disjunction is true whatever q and r do — four rows settled by one column. When p is true everything rests on q ∧ r, and only the row where both hold survives. Keep this column: “The Conditional and Its Relatives” introduces a connective, →, whose table is exactly this one, and the rows that surprise people there are the four you have just filled in without surprise.
Common mistakes
1
Writing fewer than 2ⁿ rowsA missing row is a case you have not checked, and it is exactly the case that a counterexample tends to live in.
2
Evaluating outside in¬(p ∧ q) is not ¬p ∧ ¬q. Building the inner column first makes that impossible to get wrong; jumping to the outer connective does not.
3
Reusing a row order inconsistently between two tablesIf you are comparing two formulas, the rows must be in the same order or the comparison is meaningless. The lab pins the order for this reason.
Check your understanding
✓
Finish when you can build a three-variable table without hesitating over the row pattern.
Take (p ∨ q) ∧ ¬(q ∧ r) and produce all eight rows with p ∨ q, q ∧ r and ¬(q ∧ r) as separate columns. If the row pattern is automatic, the rest of this course is bookkeeping.
Note: The lab's subexpression columns are generated from the parsed formula, so they appear in evaluation order rather than in an order someone chose. That is also why an ill-formed formula is rejected rather than guessed at.