08 · Logical Equivalences
Definition
and are logically equivalent ( or ) if is a tautology — same truth value in every row.
The 10 famous laws
| # | Law | (a) | (b) |
|---|---|---|---|
| 1 | Identity | ||
| 2 | Domination | ||
| 3 | Idempotent | ||
| 4 | Double negation | ||
| 5 | Commutative | ||
| 6 | Associative | ||
| 7 | Distributive | ||
| 8 | De Morgan | ||
| 9 | Absorption | ||
| 10 | Negation |
Distributive edge case
In logic, ∨ distributes over ∧ too (unlike ordinary algebra, where + doesn’t distribute over ×). is valid in Boolean algebra.
Conditional identities (memorise #1 — it unlocks everything)
| # | Equivalence |
|---|---|
| 1 | ⭐ |
| 2 | (contrapositive) |
| 3 | |
| 4 | |
| 5 | ⭐ |
| 6 | |
| 7 | ⭐ |
| 8 | |
| 9 | ⭐ |
Spot the pattern in 6–9
- Same antecedent (6, 8): the connective just moves inside: ∧ stays ∧, ∨ stays ∨.
- Same consequent (7, 9): the connective flips: ∧ outside → ∨ inside, ∨ outside → ∧ inside (because the antecedent gets negated).
Proving #4
✓ Proving #6: ✓
Biconditional identities
| # | Equivalence |
|---|---|
| 1 | |
| 2 | |
| 3 | |
| 4 |
Proof of #3 (from the slides)
Expand like : ✓
🔢 Boolean-algebra shortcut (used in the slide solutions)
Write ∧ as ·, ∨ as +, ¬ as ’ and simplify like a K-map.
| Logic | Boolean |
|---|---|
| Absorption | |
| Useful | ⭐ |
Is equivalent to ?
✅
Prev ← 07 Tautology Contradiction Satisfiability · Next → 09 Rules of Inference