Normal forms

Disjunctive normal form (DNF): push negation and conjunction inward, add missing variables:

  (¬(p ∨ q) ∧ r) ∨ p
≡ (¬p ∧ ¬q ∧ r) ∨ p
≡ (¬p ∧ ¬q ∧ r) ∨ (p ∧ (q ∨ ¬q) ∧ (r ∨ ¬r))
≡ (¬p ∧ ¬q ∧ r) ∨ (p ∧ q ∧ r) ∨ (p ∧ q ∧ ¬r) ∨ (p ∧ ¬q ∧ r) ∨ (p ∧ ¬q ∧ ¬r)

Conjunctive normal form (CNF): push negation and disjunction inward, add missing variables:

  (¬(p ∨ q) ∧ r) ∨ p
≡ (¬p ∧ ¬q ∧ r) ∨ p
≡ (¬p ∨ p) ∧ (p ∨ ¬q) ∧ (p ∨ r)
≡ (p ∨ ¬q ∨ (r ∧ ¬r)) ∧ (p ∨ (q ∧ ¬q) ∨ r)
≡ (p ∨ ¬q ∨ r) ∧ (p ∨ ¬q ∨ ¬r) ∧ (p ∨ q ∨ r) ∧ (p ∨ ¬q ∨ r)
≡ (p ∨ ¬q ∨ r) ∧ (p ∨ ¬q ∨ ¬r) ∧ (p ∨ q ∨ r)