De Morgan's Laws: The Duality of And and Or

Negate an "and," get an "or." Negate an "or," get an "and."

That's De Morgan's Laws in a sentence. They describe what happens when you take the complement of a union or intersection — the "not" flips the operation.

(A ∪ B)ᶜ = Aᶜ ∩ Bᶜ (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ

The laws reveal a deep symmetry: union and intersection are duals. Each becomes the other under negation.

That's the unlock. Complement swaps ∪ and ∩. This isn't just a rule to memorize — it's a glimpse into the structure of logic itself, where "and" and "or" are mirror images.

The First Law

(A ∪ B)ᶜ = Aᶜ ∩ Bᶜ

Not in A or B = not in A, and not in B.

Left side: "It's false that x is in A or B." Right side: "x is not in A, and x is not in B."

These say the same thing. If x isn't in the union, it must fail to be in both A and B.

The Second Law

(A ∩ B)ᶜ = Aᶜ ∪ Bᶜ

Not in A and B = not in A, or not in B.

Left side: "It's false that x is in both A and B." Right side: "x is not in A, or x is not in B (or both)."

To escape the intersection, you only need to be missing from one set.

Proof of the First Law

We prove (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ by showing mutual containment.

Part 1: (A ∪ B)ᶜ ⊆ Aᶜ ∩ Bᶜ

Let x ∈ (A ∪ B)ᶜ. Then x ∉ (A ∪ B). So x is not in A and x is not in B. Therefore x ∈ Aᶜ and x ∈ Bᶜ. Hence x ∈ Aᶜ ∩ Bᶜ. ✓

Part 2: Aᶜ ∩ Bᶜ ⊆ (A ∪ B)ᶜ

Let x ∈ Aᶜ ∩ Bᶜ. Then x ∈ Aᶜ and x ∈ Bᶜ. So x ∉ A and x ∉ B. Therefore x ∉ (A ∪ B). Hence x ∈ (A ∪ B)ᶜ. ✓

Both directions hold, so (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ. ∎

Visualizing De Morgan's Laws

Draw a Venn diagram with sets A and B inside universal set U.

First law: (A ∪ B)ᶜ

• A ∪ B is both circles.
• The complement is everything outside both circles.
• That's the region where x ∉ A and x ∉ B — which is Aᶜ ∩ Bᶜ.

Second law: (A ∩ B)ᶜ

• A ∩ B is the overlap (the "lens").
• The complement is everything except the lens.
• That includes "only A," "only B," and "neither" — which is Aᶜ ∪ Bᶜ.

De Morgan's Laws in Logic

The same laws apply to logical statements:

¬(P ∨ Q) ≡ ¬P ∧ ¬Q "Not (P or Q)" is equivalent to "not P and not Q."

¬(P ∧ Q) ≡ ¬P ∨ ¬Q "Not (P and Q)" is equivalent to "not P or not Q."

Set complement (ᶜ) corresponds to logical negation (¬). Union (∪) corresponds to logical "or" (∨). Intersection (∩) corresponds to logical "and" (∧).

Example: "Neither"

"Neither Alice nor Bob came to the party."

This means: not (Alice came or Bob came).

By De Morgan: (Alice didn't come) and (Bob didn't come).

To say "neither," you're saying "not this one and not that one."

Example: "Not Both"

"I didn't have both coffee and tea this morning."

This means: not (coffee and tea).

By De Morgan: (no coffee) or (no tea).

At least one was missing — maybe coffee, maybe tea, maybe both.

Extending to More Sets

De Morgan's laws generalize:

(A₁ ∪ A₂ ∪ ... ∪ Aₙ)ᶜ = A₁ᶜ ∩ A₂ᶜ ∩ ... ∩ Aₙᶜ

Not in any = not in the first and not in the second and ... and not in the last.

(A₁ ∩ A₂ ∩ ... ∩ Aₙ)ᶜ = A₁ᶜ ∪ A₂ᶜ ∪ ... ∪ Aₙᶜ

Not in all = not in at least one.

Duality

De Morgan's laws reveal a duality between ∪ and ∩.

Any set identity involving ∪, ∩, and ᶜ has a dual: swap ∪ ↔ ∩, swap ∅ ↔ U, and the identity still holds.

For example:

• A ∪ ∅ = A dualizes to A ∩ U = A
• A ∪ Aᶜ = U dualizes to A ∩ Aᶜ = ∅

This duality pervades mathematics. It appears in logic (∧ ↔ ∨), topology (open ↔ closed), order theory (meet ↔ join), and beyond.

Using De Morgan's Laws

The laws are essential for:

Simplifying expressions: Push negation through to individual sets. (A ∪ B ∪ C)ᶜ = Aᶜ ∩ Bᶜ ∩ Cᶜ

Proving identities: Convert to a form easier to work with.

Negating conditions: In programming, "not (x > 0 or y > 0)" becomes "x ≤ 0 and y ≤ 0."

Common Mistakes

Don't distribute complement like arithmetic: (A ∪ B)ᶜ ≠ Aᶜ ∪ Bᶜ ✗

The complement changes the operation, not just the operands.

Also remember: (Aᶜ)ᶜ = A. Double negation returns to the original.

The Core Insight

De Morgan's laws say: negation inverts the structure.

"Not (or)" becomes "and (not)." "Not (and)" becomes "or (not)."

This inversion is the key to duality. Union and intersection aren't independent operations — they're two faces of the same underlying logic, related by complement.

When you understand De Morgan's laws, you understand that "and" and "or" are symmetric partners. Negate, and they trade places.

Part 7 of the Set Theory series.

Previous: Set Complement and Difference: What Is Not in a Set Next: Cartesian Products: Ordered Pairs and Beyond