SET 08 · Set Identities

A, B, C ⊆ U. Each law mirrors a law in 08 Logical Equivalences: swap ∪ ↔ ∨, ∩ ↔ ∧, ’ ↔ ¬, U ↔ T, ϕ ↔ F.

#Law(a)(b)
1Identity
2Domination
3Idempotent
4Complementation (double complement)
5Commutative
6Associative
7Distributive
8De Morgan
9Absorption
10Complement

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

MethodUse when
Algebra (laws + )simplifying to a known form
Region / membership table (SET 07 Set Operations)comparing two 3-set expressions in MCQs
Set-builder + logicproofs / “show that” questions
Counter-example with small setsshowing 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