Skip to content
Tutorials Center
My learning

Topics

Lesson 8 of 38 · Sets and Operations

Laws of Set Algebra and De Morgan

Collect the laws of set algebra, prove De Morgan's laws, and learn to simplify set expressions, checking identities with a membership-table program.

You now know union, intersection, complement, difference and symmetric difference. These operations obey a compact collection of laws. Knowing them lets you simplify messy expressions, prove identities without drawing pictures, and see why set algebra looks exactly like the algebra of logic. The star of this lesson is De Morgan's laws, which tell you how complements interact with union and intersection.

The laws in one place

Let U be the universal set. For all sets A, B, C inside U:

Name Law
Commutative A ∪ B = B ∪ A; A ∩ B = B ∩ A
Associative (A ∪ B) ∪ C = A ∪ (B ∪ C); same for ∩
Distributive A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C); A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
Identity A ∪ ∅ = A; A ∩ U = A
Complement A ∪ Aᶜ = U; A ∩ Aᶜ = ∅
Idempotent A ∪ A = A; A ∩ A = A
Domination A ∪ U = U; A ∩ ∅ = ∅
Absorption A ∪ (A ∩ B) = A; A ∩ (A ∪ B) = A
Double complement (Aᶜ)ᶜ = A
De Morgan (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ; (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ

Notice the duality: if you swap ∪ with ∩ and ∅ with U in a law, you get another true law. This is why the laws come in pairs.

De Morgan's laws

In words:

  • "Not (A or B)" means "not A and not B": (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ.
  • "Not (A and B)" means "not A or not B": (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ.

A real-life reading: if someone says "I don't like tea or coffee", then they don't like tea and they don't like coffee. If they say "I don't like tea and coffee together", it means at least one of the two is disliked.

Proof of the first law, by double inclusion.

  • (⊆) Let x ∈ (A ∪ B)ᶜ. Then x ∉ A ∪ B, which means x is not in A and not in B. So x ∈ Aᶜ and x ∈ Bᶜ, so x ∈ Aᶜ ∩ Bᶜ.
  • (⊇) Let x ∈ Aᶜ ∩ Bᶜ. Then x ∉ A and x ∉ B, so x is not in A ∪ B, so x ∈ (A ∪ B)ᶜ.

The second law follows by applying the first to Aᶜ and Bᶜ and taking complements, or by a similar double inclusion.

Python Membership tables check an identity

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

This membership table method is a genuine proof for any finite number of sets: an element is in or out of each set, and the table lists every possibility. Python's and, or, not correspond to ∩, ∪, ᶜ.

Simplifying expressions

You can use the laws to simplify.

Example 1. Simplify (A ∪ B) ∩ (A ∪ Bᶜ).

By the distributive law (reading it backwards), this is A ∪ (B ∩ Bᶜ). Since B ∩ Bᶜ = ∅, we get A ∪ ∅ = A.

Example 2. Simplify (A ∩ B)ᶜ ∩ A.

By De Morgan, (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ. Then (Aᶜ ∪ Bᶜ) ∩ A = (Aᶜ ∩ A) ∪ (Bᶜ ∩ A) = ∅ ∪ (A ∩ Bᶜ) = A \ B.

Example 3. Show absorption: A ∪ (A ∩ B) = A. Since A ∩ B ⊆ A, adding it to A changes nothing, so the union is A.

Python Checking simplifications on random sets

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Connection to logic

Set operations and logical connectives are two faces of one structure:

Sets Logic Python
A ∪ B p ∨ q (or) a or b
A ∩ B p ∧ q (and) a and b
Aᶜ ¬p (not) not a
A ⊆ B p ⇒ q a <= b

This is why De Morgan's laws for sets and for logic have the same shape. Mathematicians describe both as Boolean algebras. You will meet this structure again in the lessons on lattices.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. Which is De Morgan's law for the complement of a union?

    To be outside A ∪ B you must be outside A and outside B.
  2. 2. Simplify A ∪ (A ∩ B).

    This is absorption: A ∩ B is already inside A.
  3. 3. Simplify (A ∪ B) ∩ (A ∪ Bᶜ).

    By distributivity it equals A ∪ (B ∩ Bᶜ) = A ∪ ∅ = A.
  4. 4. What is the dual of the law A ∪ ∅ = A?

    Swap ∪ with ∩ and ∅ with U to get the identity law A ∩ U = A.

Summary

  • Set operations satisfy commutative, associative, distributive, identity, complement, idempotent, domination and absorption laws.
  • De Morgan: (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ and (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ.
  • Prove identities by double inclusion, by laws, or with a membership table.
  • Sets with these operations form a Boolean algebra, mirroring logic.

Next: Inclusion-Exclusion