Skip to content
Tutorials Center
My learning

Topics

Lesson 5 of 68 · Logic

Truth Tables

Build truth tables by hand and with itertools.product, classify formulas as tautologies, contradictions or contingencies, and test equivalence by brute force.

A truth table lists every possible assignment of true and false to the variables of a statement and shows the statement's value for each. It is the most basic decision procedure in logic: it never needs cleverness, only patience, and a computer has plenty of patience. With a truth table you can say for certain whether a formula is always true, never true, or sometimes true, and whether two formulas mean the same thing.

In this lesson you will build tables by hand, generate them with itertools.product, write a small reusable table printer, and use brute force to classify formulas and check equivalence. The connectives used here are explained in Propositional Logic and Implication and Biconditional.

Building a table by hand

Take the formula (p ∨ q) ∧ ¬(p ∧ q). Follow these steps:

  1. List the variables: p and q. With n variables there are 2ⁿ rows, so here 4.
  2. Fill the variable columns with every combination of T and F.
  3. Add one column per sub-formula, working from the inside out: p ∨ q, then p ∧ q, then ¬(p ∧ q), and finally the whole formula.
p q p ∨ q p ∧ q ¬(p ∧ q) whole
T T T T F F
T F T F T T
F T T F T T
F F F F T F

The final column is T when exactly one of p and q is true, so this formula is the exclusive or from the earlier lesson.

Making a truth table

List variables n variables give 2^n rows.
Fill all rows Every combination of T and F once.
Sub-formulas One column per piece, inside out.
Read the last column That column is the answer.
1 / 2

Generating rows with itertools.product

The rows of a truth table are the elements of a Cartesian product: for three variables, every triple of values drawn from [True, False]. itertools.product(values, repeat=n) produces exactly that, in an order with True first, so the table reads like the hand-made one. We can model a formula as a Python function from the variable values to a bool.

Python A generic truth table printer

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The printer works for any number of variables. Doubling the table size with each added variable is a warning: 10 variables mean 1,024 rows, 20 variables about a million, and 30 variables over a billion. This exponential growth is why large problems need smarter methods such as the SAT solvers in Normal Forms and SAT.

Tautology, contradiction, contingency

Looking at the last column of a table tells you what kind of formula you have:

  • A tautology is true in every row. Example: p ∨ ¬p ("it is raining or it is not").
  • A contradiction is false in every row. Example: p ∧ ¬p.
  • A contingency is true in some rows and false in others. Most formulas, such as p ∧ q, are contingencies.

A formula is satisfiable if at least one row makes it true, so tautologies and contingencies are satisfiable and contradictions are not. A formula is valid if it is a tautology. These words come up again in the SAT chapter.

With Python we can classify a formula automatically using all and any over the rows:

Python Classify formulas by brute force

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Two results deserve a pause. (p -> q) or (q -> p) is a tautology: for any two statements, at least one of the implications holds, which feels odd in English but is a direct consequence of the truth table. And ((p -> q) and p) -> q is a tautology: it is modus ponens written as a single formula. A logical argument is valid exactly when the formula "premises imply conclusion" is a tautology.

Checking equivalence

Two formulas are logically equivalent, written A ≡ B, if they have the same value in every row; equivalently, A ↔ B is a tautology. To test it by brute force, evaluate both formulas on every assignment and compare.

Python Are two formulas equivalent?

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

When the formulas differ, returning the first differing row gives a counterexample, the most useful output a checker can give: it tells you exactly where the two statements disagree. Here the converse differs from the original at p = True, q = False: the original is false there, while the converse is true.

Truth tables and their limits

Truth tables are complete and mechanical, but they have limits:

  • Size. The table has 2ⁿ rows, so it is practical only up to roughly 20 to 25 variables on an ordinary computer.
  • Propositional logic only. Statements about "all integers" involve infinitely many cases. These need the quantifiers in Predicates and Quantifiers or a proof.
  • Little insight. A table says that two formulas are equal but not why. Algebraic laws such as De Morgan's, covered next in Logical Equivalences and Laws, give shorter arguments and let you simplify formulas.

Use truth tables for confidence and counterexamples, and algebraic laws for understanding and simplification. Experienced logicians switch between the two without noticing.

Check your understanding

Quick check · 5 questions

of 5 answered You scored / 5 · perfect!

  1. 1. How many rows does a truth table for a formula with 4 variables have?

    Each variable doubles the number of combinations, so 4 variables give 2 to the power 4, which is 16 rows.
  2. 2. What kind of formula is p ∨ ¬p?

    Whatever the value of p, one of p and ¬p is true, so the formula is true in every row.
  3. 3. A formula's truth table has the final column T, F, F, F. What is it?

    The column has both T and F, so it is a contingency. It also matches p ∧ q, not p ∨ q.
  4. 4. Two formulas A and B are equivalent exactly when:

    Equivalent formulas agree in every row, which means A ↔ B is true in every row. A single implication only gives one direction.
  5. 5. Why is brute-force truth-table checking impractical for 60 variables?

    The row count doubles with every variable, so 60 variables need more than a billion billion rows.

Summary

  • A truth table lists all 2ⁿ assignments of n variables and the formula's value in each.
  • itertools.product([True, False], repeat=n) generates the rows; a formula is a Python function of those values.
  • A tautology is always true, a contradiction is always false, and a contingency is sometimes true and sometimes false.
  • Two formulas are equivalent when they agree on every row; return the first disagreeing row as a counterexample.
  • Tables are mechanical but grow exponentially; algebraic laws and SAT methods handle bigger problems.

Next: Logical Equivalences and Laws, the algebra of statements.