Truth Tables

Overview

Systematic Truth Analysis

A truth table lists every possible combination of truth values for the propositional variables and shows the resulting truth value of the compound proposition. Truth tables are the definitive way to determine whether a compound proposition is a tautology, contradiction, or contingency.

Definition

Truth Table

A truth table for a compound proposition with n propositional variables has 2ⁿ rows - one for every possible combination of T and F. The columns show intermediate results for sub-expressions and the final truth value of the whole expression.

Example

Truth Table for p → q

p | q | p → q ----|----|------ T | T | T T | F | F F | T | T F | F | T

Remember: p → q is false only when p is true and q is false.

Example

Truth Table for ¬(p ∧ q)

p | q | p ∧ q | ¬(p ∧ q) ----|----| ------|-------- T | T | T | F T | F | F | T F | T | F | T F | F | F | T

Notice this matches ¬p ∨ ¬q - that is De Morgan's Law!

Definition

Tautology, Contradiction, Contingency

A tautology is a compound proposition that is always true regardless of the truth values of its variables. Example: p ∨ ¬p.

A contradiction is a compound proposition that is always false. Example: p ∧ ¬p.

A contingency is a compound proposition that is neither a tautology nor a contradiction - its truth value depends on the variables.

Example

Verifying a Tautology

Show that p ∨ ¬p is a tautology:

p | ¬p | p ∨ ¬p ----|-----|------- T | F | T F | T | T

Every row gives T, so p ∨ ¬p is a tautology. This is the Law of the Excluded Middle.

Note

Building Truth Tables Step by Step

To build a truth table: 1. List all propositional variables as columns. 2. Create 2ⁿ rows covering all T/F combinations. 3. Add columns for each sub-expression, evaluating from the innermost parentheses outward. 4. The final column is the truth value of the full expression.

Tip: for the variable columns, alternate T/F with decreasing frequency. The first variable alternates every 2ⁿ⁻¹ rows, the second every 2ⁿ⁻² rows, and so on.