Truth Tables
Can a machine with no understanding of meaning still tell you whether an argument is valid? Truth tables answer yes. They do this by reducing the truth or falsity of any compound proposition to a finite mechanical calculation. This matters because logic needs a bedrock method. It must settle disputes about validity without appeal to intuition, rhetoric, or authority. The big picture is simple. Every compound statement built from Logical Connectives is a function of the truth values of its simplest parts. A function on finitely many finite inputs can always be tabulated in full. This article develops the precise definition of a truth table. It proves that the method is both correct and complete for this purpose. It works through two nontrivial examples with three variables. It also shows exactly where the method's power ends. This sets up the later study of The Conditional Statement, Logical Equivalence, and Tautologies and Contradictions.
- A truth table lists every possible assignment of T/F to the atomic propositions in a formula, and the resulting truth value of the whole formula for each assignment.
- A compound proposition with distinct atomic components has exactly rows, since each of the propositions independently takes one of values.
- Truth tables are built column by column, evaluating connectives in order of precedence (¬, then ∧, then ∨, then →, then ↔), reusing previously computed columns.
- The method is a decision procedure: it always terminates and always gives the correct answer for propositional formulas.
- Truth tables let you define new connectives, verify Logical Equivalence between formulas, and detect Tautologies and Contradictions.
- Key idea: truth is a finite function of finitely many inputs, so exhaustive case analysis is not just possible but conclusive.
Where this lives today
Truth tables are the semantic bedrock for the design and verification of digital logic circuits: every AND/OR/NOT gate network implements a truth-functional formula, and engineers use truth tables to specify, simplify (via Karnaugh maps), and verify combinational circuits before fabrication. In computer science, truth tables underlie the definition of Boolean satisfiability (SAT), the canonical NP-complete problem, where the question "does some row make true?" is exactly SAT, and the exponential blow-up of table size in the counterexample discussion is the seed of the vs. question for SAT solvers. In mathematical logic itself, truth tables give the base case for the soundness and completeness theorems connecting syntax and semantics of propositional logic, and they justify the algebraic laws (De Morgan's laws, distributivity, the deduction pattern behind The Conditional Statement) used constantly in proof-writing. In cryptography, truth-functional analysis of Boolean functions (their tables, their nonlinearity, their algebraic degree) is central to designing S-boxes resistant to linear and differential cryptanalysis. In statistics and databases, truth tables underlie query logic and the evaluation of Boolean filter conditions (`AND`/`OR`/`NOT` clauses) over records.
Ask the tutor: Why does checking a handful of rows never suffice to prove a formula is a tautology, and what is the smallest number of rows that could in principle suffice?
Let be distinct atomic propositions (propositional variables), and let be a compound proposition built from them using the connectives . A truth assignment is a function assigning a truth value to each atomic proposition. Every truth assignment extends uniquely to a truth value for the whole formula , defined recursively by:
The truth table of is the array with one row for each of the truth assignments to (listed exhaustively, with no repeats), one column for each of and for each subformula of used in building it up, and entries recording or as computed by the recursion above. The rightmost column, headed by itself, is called the truth table of .
Intuition
Think of a compound proposition as a small machine. It has input switches, one per atomic proposition, each of which can be flipped to T or F. Flip the switches in every possible combination, read off what the machine outputs, and you have completely described the machine — there is nothing more to know. A truth table is simply the log of every switch setting alongside the corresponding output. Because each switch has exactly positions and there are switches, there are exactly settings to check, and checking all of them is always a finite task, however large gets. The subtlety worth internalizing early is that the table is built compositionally: you do not guess the output column directly, you compute intermediate columns for each subformula, in the order dictated by how the formula is parsed, and each new column depends only on columns already computed. This mirrors the recursive definition of itself. The picture below shows the "switch machine" view for a two-variable formula, and a second figure shows how the rows arrange themselves as the vertices of a hypercube of truth assignments — a way of seeing that the table is really an enumeration of the corners of a combinatorial cube.
Let be a compound proposition built from atomic propositions using . Then: 1. (Termination) The truth table of has exactly rows, and can be constructed in finitely many steps. 2. (Well-definedness) For every truth assignment to , the value computed by the table is uniquely determined — it does not depend on the order in which subformulas are evaluated, only on the parse structure of . 3. (Correctness) , as computed via the table, agrees exactly with the semantic truth value of under as defined by the recursive semantics of . 4. (Decidability) The question "is true under every truth assignment?" (i.e. is a tautology) is settled by inspecting the finitely many rows of the table for , so the property of being a tautology is decidable by this procedure.
We argue by structural induction on the formula , using the unique readability of propositional formulas: every compound proposition that is not atomic is of exactly one of the forms , , , , , for unique immediate subformulas (this is a standard fact about the grammar of propositional logic, guaranteed by matched parentheses/precedence conventions in the formal syntax, and assumed here as part of the definition of "compound proposition built from connectives").
(1) Termination. We show by induction on the structure of that has finitely many subformulas, hence finitely many columns, and that the number of rows is where is the number of distinct atomic propositions occurring in . Base case: if is atomic, it has exactly one subformula (itself), and there is atomic proposition, contributing rows: and . Both cases are listed, and no more; the table has finitely many (namely ) rows. Inductive step: suppose or for , where (and ) are shorter formulas each involving finitely many atomic propositions, and each with a finite truth table by the inductive hypothesis. The atomic propositions of are exactly the union of those of and (a finite union of finite sets, hence finite); say this union has size . The subformulas of are itself together with the subformulas of (and of ), a finite set by the inductive hypothesis together with one more element. Hence has finitely many subformulas/columns. For the row count: a truth assignment to the atomic propositions of is precisely a function from an -element set to a -element set . The number of such functions is by the standard counting principle (each of the elements independently has choices, and choices multiply), and listing "every possible assignment with no repeats" means listing exactly this set of functions once each. So the table has exactly rows, a finite number. Construction requires filling in finitely many columns (one inductive step of computation each, per the recursive semantics) across finitely many rows, hence finitely many cells total — a finite procedure.
(2) Well-definedness. By unique readability, has a unique parse tree: a finite rooted tree whose leaves are occurrences of atomic propositions and whose internal nodes are labeled by connectives, each internal node's children being (the roots of the parse trees of) its immediate subformulas, uniquely determined by the form of . Define on this tree by post-order evaluation: assign at leaves, then apply the recursive clause for , , , , or at each internal node using the values already computed at its children. Because the tree is finite (by part 1) and each internal node's value depends only on its children's values via a fixed rule, the value at the root is computed after finitely many steps and is a function purely of the tree structure and the leaf values — not of any choice of evaluation order, since any two orderings that respect the tree's parent-before-child... rather child-before-parent dependency compute the same values at each node (this is immediate: the rule at a node is a fixed function of its children's already-fixed values, so any topological ordering of the tree gives the same result, by a straightforward induction on tree height showing each node's value is uniquely pinned down once its children's are). Hence is well-defined.
(3) Correctness. This is immediate from the definition: is defined to be the value computed by exactly the recursive clauses of the semantics stated in Logical Connectives (restated in the Definition block above). The truth table's entry in row , column , is constructed precisely by applying these clauses at each node of the parse tree in the order guaranteed well-defined by part 2. So there is no gap between "the value the table displays" and "the semantic value " — they are the same computation, verified column by column: the entry for a subformula in row is obtained by flipping the already-computed entry for in that row; the entry for is exactly in rows where both the -column and -column show ; and similarly for per their clauses. Each of these is a direct transcription of the recursive definition of , so by induction on the height of the subformula in the parse tree, the table's column for every subformula agrees with in every row, and in particular this holds for itself.
(4) Decidability. " is a tautology" means: for every truth assignment to the atomic propositions of . By part 1 there are only such assignments, all explicitly enumerated as the rows of the table; by parts 2–3 the table's -column at row correctly and unambiguously reports . Hence " is a tautology" holds if and only if every entry in the -column of the (finite) table equals — a claim checkable by inspecting finitely many entries, in finite time, with a definite yes/no answer. This is exactly what it means for the property to be decided by the table.
∎Worked examples
Example 1 — an asymmetric three-variable formula. Let be atomic propositions and consider
Note the formula is deliberately not symmetric in : swapping variables changes the formula. We build the table column by column: , , , then , then , then , then finally .
| T | T | T | F | F | T | T |
| T | T | F | F | F | T | T |
| T | F | T | T | T | T | T |
| T | F | F | T | T | F | F |
| F | T | T | F | F | T | T |
| F | T | F | F | F | T | T |
| F | F | T | T | F | T | T |
| F | F | F | T | F | F | T |
There are rows, matching part 1 of the theorem. Read row 4 carefully, since it is the only row where is false: gives , so ; meanwhile ; so , matching the -clause ( is the only case making a conditional false). Every other row has either (making the conditional vacuously true) or (making the conditional true regardless of the antecedent). Since is in seven of eight rows and in one, is neither a tautology nor a contradiction — it is a contingency, a notion made precise in Tautologies and Contradictions.
Example 2 — comparing two formulas with a shared variable, to test equivalence. Consider
These look plausible as "equivalent," and we check exhaustively rather than trusting intuition.
| T | T | T | T | T | T | T | T |
| T | T | F | F | F | T | F | F |
| T | F | T | F | F | F | T | F |
| T | F | F | F | F | F | F | F |
| F | T | T | T | T | T | T | T |
| F | T | F | F | T | T | T | T |
| F | F | T | F | T | T | T | T |
| F | F | F | F | T | T | T | T |
Comparing the final columns row by row: for against for — identical in all rows. This is exactly the truth-table criterion for Logical Equivalence: and agree under every truth assignment, so . Note the asymmetry that made this a genuine test: rows 2 and 3 have true but only one of true, which is precisely where a careless guess might fail to notice that a single false conjunct on either side forces both sides false — the table forces you to check it rather than assume it.
The theorem's decidability conclusion rests on there being only rows for a finite number of atomic propositions. Drop this hypothesis — imagine trying to build a "truth table" for a formula built from infinitely many atomic propositions , such as an infinite conjunction
(this is not a legal formula of ordinary propositional logic, which only allows finite formulas, but it illustrates exactly what breaks). A truth assignment to infinitely many atomic propositions is a function from an infinite set to , and there are (uncountably many, by Cantor's theorem) such assignments — no longer finite. There is no way to write down "every row" of a table, because the rows are uncountable; the tabulation procedure from part 1 of the theorem never terminates and cannot even be started as a finite list. Consequently part 4 (decidability by inspection) also fails: one cannot check "true in every row" by looking at finitely many entries, since finitely many rows can never exhaust an uncountable set of assignments. This is precisely why propositional logic is officially built only from finite formulas over a fixed (possibly infinite, but each individual formula uses only finitely many of the) atomic propositions — the finiteness hypothesis in the theorem is not a convenience, it is what makes the method a terminating, correct decision procedure at all.
Scope, edge cases & common traps
| Situation | What to do | Common mistake |
|---|---|---|
| Formula has distinct atomic propositions | Table has exactly rows; list them in a fixed systematic order (e.g. standard binary counting order) | Forgetting a repeated atomic proposition is not a new variable — e.g. has , not |
| Building intermediate columns | Build one column per subformula, following the parse tree from leaves to root | Trying to evaluate the whole formula "by eye" in one step, skipping the or precedence and mis-ordering operations |
| Checking equivalence of | Compare final columns row by row over the same row-ordering, for the union of their atomic propositions | Building each table with a different row order, or with a different variable list, so rows don't line up |
| Testing "is a tautology?" | Confirm every row of the final column is | Concluding tautology from a handful of "obviously true" rows without checking all |
| Large | Method still works, is still correct, but has rows — grows exponentially | Assuming the table is always practical; for that is already over a million rows |
The mathematician behind it
Origins · 1 minCharles Sanders Peirce and how this was discovered
Peirce was an American philosopher, logician, and scientist working largely outside conventional academic posts, who made foundational contributions to symbolic logic, semiotics, and the philosophy of pragmatism. Working through the 1880s, he anticipated the systematic use of truth-value tabulation for evaluating compound logical expressions, alongside independent related work on truth-functional analysis by others in the following decades — most notably the tabular method later popularized and standardized by Emil Post and Ludwig Wittgenstein in the 1920s, which crystallized the truth table into the compact grid form used universally today.
Why does a formula with atomic propositions have exactly rows, not or ?
Each atomic proposition independently can be assigned or — two choices, made independently for each of the propositions. By the basic counting principle, when you make independent choices each with options, the total number of possible combined choices is ( times), which is . This is the same counting fact that tells you a -digit binary string has possibilities, or that a set with elements has subsets (each element independently "in" or "out"). It is genuinely exponential, not linear or quadratic, which is why tables get unwieldy fast: variables already means rows.
Does the order in which I list the rows matter?
Not for correctness — any listing of all assignments with no repeats and no omissions gives a valid table, since the theorem only requires exhausting the assignments, not a particular order. In practice, everyone uses the same standard order: treating T as 1 and F as 0, list assignments as binary counting from up to (or the reverse), so that tables are easy to compare and errors are easy to spot. This convention is what let Example 2 compare and row by row without extra bookkeeping.
Do I need a separate column for every single subformula, or can I skip some?
For correctness you only strictly need enough intermediate columns that each new column's truth values can be read off directly from previous ones using a single connective's rule — skipping straight to the final answer risks silent arithmetic slips, especially with and nested negations. Pedagogically and for error-checking, it is best practice to include one column per subformula appearing in the parse tree, exactly as the proof of the main theorem constructs the table: leaves first, then each connective applied to already-computed columns, ending at the root.
How does a truth table relate to logical equivalence and tautologies, which come later?
A truth table is the tool; equivalence and tautology/contradiction are properties you read off the tool. Two formulas are logically equivalent, as covered in Logical Equivalence, exactly when their truth tables (over the same list of atomic propositions) have identical final columns row by row, as verified directly in Example 2 above. A formula is a tautology if its final column is all , and a contradiction if its final column is all ; these are the subjects of Tautologies and Contradictions. Truth tables are also how one checks, rather than merely asserts, facts about The Conditional Statement such as which rows make false.
Can truth tables handle biconditionals and nested conditionals, or only simple AND/OR formulas?
Truth tables handle every truth-functional connective uniformly, including and and arbitrary nesting, because the recursive semantics in the Definition block specifies a rule for each connective that only ever needs the already-computed values of its immediate subformulas. There is no upper bound on nesting depth that breaks the method — a formula ten connectives deep just means ten (or fewer, if subformulas repeat) intermediate columns, still built the same leaf-to-root way, still finite by the termination part of the theorem.
Is the exponential blow-up in rows ever avoided in practice?
Yes — full truth tables are rarely built by hand past about or variables. Practical tools include Karnaugh maps and Boolean algebra simplification (using laws like De Morgan's and distributivity, themselves justified by truth tables) to shrink formulas before or instead of tabulating them, and, computationally, SAT solvers use clever search (not exhaustive enumeration) to decide satisfiability far faster than in typical cases, even though the worst-case behavior remains exponential for all known general methods.
What exactly does "atomic proposition" mean when counting rows, and can the same proposition appear twice in a formula?
An atomic proposition is a propositional variable with no internal logical structure — etc. — as opposed to a compound proposition built from connectives. Counting rows uses the number of distinct atomic propositions occurring in , not the number of times a symbol is written down; still has (only ), hence rows, even though appears three times in the formula's text.