SET 08 · Set Identities
A, B, C ⊆ U. Each law mirrors a law in 08 Logical Equivalences: swap ∪ ↔ ∨, ∩ ↔ ∧, ’ ↔ ¬, U ↔ T, ϕ ↔ F.
| # | Law | (a) | (b) |
|---|---|---|---|
| 1 | Identity | ||
| 2 | Domination | ||
| 3 | Idempotent | ||
| 4 | Complementation (double complement) | ||
| 5 | Commutative | ||
| 6 | Associative | ||
| 7 | Distributive | ||
| 8 | De Morgan | ||
| 9 | Absorption | ||
| 10 | Complement |
Slide typo
In the Domination Law proof, part (b) is headed “A ∪ ϕ = ϕ”. That’s wrong: (identity law). The proof below it actually shows A ∩ ϕ = ϕ, which is the correct domination law.
How the proofs work (set-builder method)
Write each side as , apply the matching logic law, convert back.
Identity:
Domination:
Double complement:
De Morgan:
Absorption by double inclusion
⊆: (logic absorption). ⊇: any is in . ∎
Three proof methods — pick the fastest
| Method | Use when |
|---|---|
| Algebra (laws + ) | simplifying to a known form |
| Region / membership table (SET 07 Set Operations) | comparing two 3-set expressions in MCQs |
| Set-builder + logic | proofs / “show that” questions |
| Counter-example with small sets | showing two expressions are NOT equal |
Boolean notation shortcut (used in the slides' GATE 2008 solution)
Write ∩ as ·, ∪ as +, ’ as complement, U as 1, ϕ as 0, and simplify like a K-map. Useful extras: and .
Useful derived identities
- (TIFR 2010)
Prev ← SET 07 Set Operations · Next → SET 09 Symmetric Difference