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)
1Identity
2Domination
3Idempotent
4Double negation
5Commutative
6Associative
7Distributive
8De Morgan
9Absorption
10Negation

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.

LogicBoolean
Absorption
Useful ⭐

Is equivalent to ?

✅


Prev ← 07 Tautology Contradiction Satisfiability · Next → 09 Rules of Inference