Propositional logic and truth tables

Propositions and connectives

A proposition is a statement that is either true (T) or false (F), never both: “7 is prime” is one; “close the door” is not. Compound propositions are built with connectives: negation ¬p, conjunction p ∧ q (true only when both are true), disjunction p ∨ q (true when at least one is true), implication p → q and the biconditional p ↔ q (true when both sides have the same value). A truth table lists every combination of values of the variables, so a formula with n variables has 2ⁿ rows.

Implication is the connective students get wrong. p → q is false in exactly one row: p true and q false. When p is false the implication is vacuously true, whatever q is. “If it rains, the ground is wet” is not broken on a dry, sunny day. From p → q you may conclude its contrapositive ¬q → ¬p, which is equivalent; you may not conclude the converse q → p or the inverse ¬p → ¬q.

Equivalence, tautology and the laws

Two formulas are logically equivalent (written ≡) when they have the same value in every row. A tautology is true in every row, a contradiction false in every row, and a formula that is true in at least one row is satisfiable. The laws you will use constantly are De Morgan's: ¬(p ∧ q) ≡ ¬p ∨ ¬q and ¬(p ∨ q) ≡ ¬p ∧ ¬q, plus p → q ≡ ¬p ∨ q, double negation, distributivity and absorption. They let you simplify a condition in code or a circuit without drawing the table.

from itertools import product

def implies(a, b):
    # p -> q is false only when p is true and q is false
    return (not a) or b

def is_tautology(f, n):
    # try all 2**n combinations of truth values
    return all(f(*row) for row in product([True, False], repeat=n))

modus_tollens = lambda p, q: implies(implies(p, q) and not q, not p)
de_morgan = lambda p, q: (not (p and q)) == ((not p) or (not q))

print(is_tautology(modus_tollens, 2))  # True
print(is_tautology(de_morgan, 2))      # True

Why it matters in computing

Every if with && and || is a propositional formula, and compilers use the laws above to rewrite and short-circuit it. Hardware is the same algebra in silicon. Deciding whether an arbitrary formula is satisfiable (SAT) was the first problem proved NP-complete, by Stephen Cook in 1971, which is why the 2ⁿ truth table cannot be avoided in general, even though modern SAT solvers handle millions of variables in practice.