Logical equivalences
Two formulas are equivalent (≡) when they have the same truth value under every assignment.
A few classical equivalences rewrite any formula without changing its meaning:
- Involution (double negation): ¬¬p ≡ p
- De Morgan: ¬(p ∧ q) ≡ ¬p ∨ ¬q and ¬(p ∨ q) ≡ ¬p ∧ ¬q
- Distributivity: p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) and p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
- Law of excluded middle (LEM): p ∨ ¬p always holds, so q ∧ (p ∨ ¬p) ≡ q
- Law of non-contradiction (LNC): p ∧ ¬p never holds, so q ∨ (p ∧ ¬p) ≡ q
De Morgan and involution push negation inward to the variables.
Distributivity expands the formula into a conjunction of disjunctions (or the reverse).
LEM and LNC add missing variables.
Distributivity expands the formula into a conjunction of disjunctions (or the reverse).
LEM and LNC add missing variables.