Skip to content

De Morgan's laws: (A ∪ B)′ = A′ ∩ B′ and (A ∩ B)′ = A′ ∪ B′

Level: 101 · one law of the algebra of sets, on its own page

One line: Taking the complement swaps ∪ and ∩: not either is neither, and not both is at least one missing; it is the one law worth memorising in words, because it is the one people get wrong in code.

The law

Sets Logic Python
(A ∪ B)′ = A′ ∩ B′, (A ∩ B)′ = A′ ∪ B′ ¬(p ∨ q) = ¬p ∧ ¬q, ¬(p ∧ q) = ¬p ∨ ¬q U - (a | b) == (U - a) & (U - b)

Why it is true

x ∉ A ∪ B means x is in neither, so x ∉ A and x ∉ B; x ∉ A ∩ B means x fails to be in both, so x ∉ A or x ∉ B. Pushing a not through an or turns it into an and, and through an and into an or. A law of sets is decided one member at a time, so checking it on every subset of a four-element universe, every pattern of membership there is, proves it; the program does that and prints the matching truth table.

Where it is used, and the trap

not (a or b) is not a and not b; in SQL, NOT (x = 1 OR y = 2) is x <> 1 AND y <> 2. The classic bug is "not both" written as not (a or b) when it should be not (a and b), that is not a or not b. The same law for quantifiers, ¬∀ is ∃¬, is on predicates and quantifiers, and the version for infinitely many sets is Hrbacek and Jech's exercise 3.11 on the function katas page. Augustus De Morgan stated the laws in 1847; the idea is in William of Ockham.

What the program prints

Verified output of law_de_morgan.py — regenerated by tools/run_examples.py, never hand-typed.

1. THE LAW: (A ∪ B)′ = A′ ∩ B′, (A ∩ B)′ = A′ ∪ B′
   checked on all 256 choices of 2 subset(s) of U = {1, 2, 3, 4}: True

2. ONE INSTANCE, WORKED
   A = {1, 2}, B = {2, 3}, C = {3, 4}, A' = {3, 4}, B' = {1, 4}
   (A ∪ B)' = ({1, 2, 3})' = {4} = A' ∩ B' = {4}
   (A ∩ B)' = ({2})' = {1, 3, 4} = A' ∪ B' = {1, 3, 4}

3. THE SAME LAW IN LOGIC: ¬(p ∨ q) = ¬p ∧ ¬q, ¬(p ∧ q) = ¬p ∨ ¬q
   every row of the truth table agrees, which is why the member-by-member check is a proof:
   p  q   left  right
   T  T   F     F
   T  F   F     F
   F  T   F     F
   F  F   T     T

Po polsku, w skrócie

Prawa De Morgana: dopełnienie zamienia sumę z przekrojem; „nie (któryś)" to „żaden", a „nie (oba)" to „co najmniej jednego brak". To prawo warto umieć na pamięć słowami, bo właśnie je psuje się w kodzie: not (a or b) to not a and not b.

Auf Deutsch: Stichwörter

De-Morgan-Gesetze: das Komplement einer Vereinigung ist der Schnitt der Komplemente, und umgekehrt.

Stichwörter: De-Morgan-Gesetze, Komplement, Negation von „oder“ und „und“, Dualität.

See also