De Morgan's laws

De Morgan’s laws show how the complement “swaps” union and intersection. They are extremely useful for simplifying complex logical conditions.

Property — De Morgan's laws

The complement of a union is the intersection of the complements, and vice versa: $\overline{A\cup B} = \overline{A}\cap\overline{B}, \qquad \overline{A\cap B} = \overline{A}\cup\overline{B}.$

The same region (in purple) is obtained both as $\overline{A\cup B}$ and as $\overline{A}\cap\overline{B}$.

Example — Decaffeinated black coffee

“I have a decaffeinated black coffee.” Let $A$ = with milk, $B$ = with caffeine. The phrase corresponds to $\overline{A}\cap\overline{B}$.

Its negation (“I do not have a decaffeinated black coffee”) is, by De Morgan, $\overline{\overline{A}\cap\overline{B}} = A\cup B:$ “I have a macchiato or with caffeine (or both)”.

Links

Topics: Set theory
Concepts: Complement · Intersection · De Morgan’s laws · Union
Skills: Using formulae
People: Augustus De Morgan