Course contentsShow
← Computer Science
Lesson 65 of 2,8722. Discrete Mathematics for CSFree lesson

Set Identities and Laws

Learn commutative, associative, distributive, and De Morgan's laws for set operations.

Set Identities and Laws

What you'll learn: You'll discover the fundamental laws that govern how sets combine and relate to each other—rules that work just like algebra, but for collections.

The Core Idea

Just as arithmetic has laws (like a + b = b + a), set operations follow predictable patterns called identities. These laws let you rearrange and simplify set expressions confidently, knowing the result stays logically equivalent.

The Essential Laws

Commutative Laws

Order doesn't matter:

  • Union: A ∪ B = B ∪ A
  • Intersection: A ∩ B = B ∩ A

(Just like addition: 3 + 5 = 5 + 3)

Associative Laws

Grouping doesn't matter:

  • Union: (A ∪ B) ∪ C = A ∪ (B ∪ C)
  • Intersection: (A ∩ B) ∩ C = A ∩ (B ∩ C)

(Think: (2 + 3) + 4 = 2 + (3 + 4))

Distributive Laws

One operation distributes over another:

  • A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
  • A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)

(Similar to: a × (b + c) = a×b + a×c)

De Morgan's Laws

Complement flips operations:

  • (A ∪ B)' = A' ∩ B' — "NOT (A OR B)" = "NOT A AND NOT B"
  • (A ∩ B)' = A' ∪ B' — "NOT (A AND B)" = "NOT A OR NOT B"

These mirror the De Morgan's Laws you saw with Boolean logic and propositions—the pattern repeats across mathematical structures!

Why They Matter

These laws let you simplify complex set expressions before computing them, prove set equalities algebraically, and write more efficient algorithms that work with collections.

Key Takeaway: Set operations obey commutative, associative, distributive, and De Morgan's laws—algebraic rules that make manipulating and reasoning about sets systematic and predictable.