Logical Equivalences & Normal Forms

Two formulas are logically equivalent, written P ≡ Q, if they have the same truth value in every row of the truth table — equivalently, if P ↔ Q is a tautology.

#The laws

Equivalences involving implication:

#Proving equivalences by the laws

Show ¬(p ∨ (¬p ∧ q)) ≡ ¬p ∧ ¬q:

Check any equivalence instantly — compare both columns:

#Normal forms

Every formula can be rewritten in a standard shape:

• Disjunctive normal form (DNF): an OR of AND-terms — a "sum of products". Example: (p ∧ ¬q) ∨ (¬p ∧ q).
• Conjunctive normal form (CNF): an AND of OR-clauses — a "product of sums". Example: (p ∨ q) ∧ (¬p ∨ ¬q).

DNF from a truth table: for each row where the formula is T, write the AND of the literals that make that row (p if p is T, ¬p if p is F); OR them together.

CNF from a truth table: for each row where the formula is F, write the OR of the negated literals; AND them together.

from itertools import product

def formula(p, q, r):
    return (p or q) and not r             # the function we want in normal form

names = "pqr"
minterms, maxterms = [], []
for row in product([True, False], repeat=3):
    lits = [n if v else "¬" + n for n, v in zip(names, row)]
    if formula(*row):
        minterms.append("(" + " ∧ ".join(lits) + ")")
    else:
        maxterms.append("(" + " ∨ ".join("¬" + n if v else n for n, v in zip(names, row)) + ")")
print("DNF:", " ∨ ".join(minterms))
print("CNF:", " ∧ ".join(maxterms))

DNF: (p ∧ q ∧ ¬r) ∨ (p ∧ ¬q ∧ ¬r) ∨ (¬p ∧ q ∧ ¬r)
CNF: (¬p ∨ ¬q ∨ ¬r) ∧ (¬p ∨ q ∨ ¬r) ∧ (p ∨ ¬q ∨ ¬r) ∧ (p ∨ q ∨ ¬r) ∧ (p ∨ q ∨ r)

CNF matters in computer science because SAT solvers work on CNF formulas; DNF and CNF also correspond to sum-of-products and product-of-sums circuits in Boolean algebra.

#Functionally complete sets

{¬, ∧, ∨} can express every Boolean function. So can {¬, ∧} (by De Morgan), and so can NAND alone or NOR alone — which is why chips can be built from a single gate type.