Mathematics.

propositional logic

Truth Tables

Mathematical Logic15 minDifficulty1 out of 10

You should know: logical connectives

Overview

A truth table is a complete tabular listing of the truth value of a propositional formula for every possible combination of truth values of its variables. A formula with n distinct propositional variables has exactly 2ⁿ rows, since each variable independently takes one of two values. Truth tables provide a mechanical, exhaustive method to determine whether a formula is a tautology (true in every row), a contradiction (false in every row), a contingency (true in some rows and false in others), or logically equivalent to another formula (identical truth-value columns). Because propositional logic's connectives are all truth-functional, truth tables are a complete decision procedure for propositional validity, though the 2ⁿ row count makes them impractical for formulas with many variables.

Intuition

A truth table is simply an exhaustive checklist: since propositional variables only ever take two values, and connectives are entirely mechanical, you can just enumerate every scenario (all TT, TF, FT, FF for two variables) and read off the answer row by row — there's no cleverness required, only patience. This brute-force completeness is exactly what makes truth tables the gold standard for settling any dispute about whether two statements really mean the same thing or whether an argument form is truly valid, even though it becomes impractical once you have more than four or five variables (16 or 32 rows) and named equivalences become the faster tool.

Formal Definition

Definition

For a formula φ with variables p₁,...,pₙ, its truth table lists all 2ⁿ assignments and the resulting value of φ:

φ is a tautology  ⟺  φ is true under every one of the 2n assignments\varphi \text{ is a tautology} \iff \varphi \text{ is true under every one of the } 2^n \text{ assignments}
Tautology
φ is a contradiction  ⟺  φ is false under every assignment\varphi \text{ is a contradiction} \iff \varphi \text{ is false under every assignment}
Contradiction
p≡q  ⟺  the truth-value columns for p and q are identical in every rowp \equiv q \iff \text{the truth-value columns for } p \text{ and } q \text{ are identical in every row}
Equivalence via truth tables
number of rows=2n, n=number of distinct variables\text{number of rows} = 2^{n}, \ n = \text{number of distinct variables}
Row count

Worked Examples

  1. List all four rows for p, q ∈ {T,F} and evaluate p → q, which is false only when p=T, q=F.

    pqp→qTTTTFFFTTFFT\begin{array}{cc|c} p & q & p\to q \\ \hline T&T&T\\ T&F&F\\ F&T&T\\ F&F&T \end{array}

  2. Since row 2 (p=T,q=F) gives False, the formula is not true in every row.

    ∃ row with p→q=F\exists \text{ row with } p\to q = F

Answer: Not a tautology — it is a contingency (true in 3 rows, false in 1).

Practice Problems

Difficulty 1/10

How many rows does the truth table for a formula with 4 distinct propositional variables have?

Difficulty 2/10

Build a truth table to classify p ∧ ¬p as a tautology, contradiction, or contingency.

Difficulty 3/10

Using a truth table, determine whether ((p → q) ∧ p) → q (modus ponens) is a tautology.

Quiz

A formula that is true under every possible assignment of its variables is called a:
How many rows appear in the truth table of a formula with 3 distinct variables?
Two formulas are logically equivalent according to their truth tables when:

Summary

  • A truth table exhaustively lists a formula's truth value across all 2ⁿ assignments of its n propositional variables.
  • Formulas classify as tautologies (always true), contradictions (always false), or contingencies (a mix).
  • Truth tables give a complete, if impractical for large n, decision procedure for validity and logical equivalence in propositional logic.

References

  1. WebsiteWikipedia — Truth table