Skip to content

The distributive laws: each of ∪ and ∩ distributes over the other

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

One line: Unlike numbers, where × distributes over + and not the other way, each of ∪ and ∩ distributes over the other, so set algebra is more symmetric than arithmetic.

The law

Sets Logic Python
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C), A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) p ∧ (q ∨ r) = (p ∧ q) ∨ (p ∧ r), p ∨ (q ∧ r) = (p ∨ q) ∧ (p ∨ r) a & (b | c) == (a & b) | (a & c)

Why it is true

"x ∈ A and (x ∈ B or x ∈ C)" means "(x ∈ A and x ∈ B) or (x ∈ A and x ∈ C)": the and is applied to whichever of the two held. The second law is the first with the roles swapped, and it holds too, which is where the analogy with + and × breaks: a + (b × c) ≠ (a + b) × (a + c). 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

Distributivity is how a condition is put into normal form before a database or a SAT solver sees it, and how WHERE a AND (b OR c) becomes two simpler queries joined by OR. The second law is the surprising one; it is why a Boolean algebra is not a ring in disguise, and why a Venn diagram, which the parent page explains, can prove both at once by shading.

What the program prints

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

1. THE LAW: A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C), A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
   checked on all 4096 choices of 3 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 ∪ C) = {2} = (A ∩ B) ∪ (A ∩ C) = {2}
   A ∪ (B ∩ C) = {1, 2, 3} = (A ∪ B) ∩ (A ∪ C) = {1, 2, 3}

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

Po polsku, w skrócie

Prawa rozdzielności: każde z działań ∪ i ∩ jest rozdzielne względem drugiego, inaczej niż u liczb, gdzie × jest rozdzielne względem +, ale nie odwrotnie. Dowód: „x ∈ A i (x ∈ B lub x ∈ C)" to „(x ∈ A i x ∈ B) lub (x ∈ A i x ∈ C)".

Auf Deutsch: Stichwörter

Distributivgesetze: ∪ und ∩ distribuieren jedes über das andere, anders als + und · bei Zahlen.

Stichwörter: Distributivgesetz, Vereinigung, Schnitt, Vergleich mit Addition und Multiplikation.

See also