Set Operations and De Morgan's Laws — Mathematics Knowledge System

Overview

Union (A ∪ B), intersection (A ∩ B), and complement (Aᶜ) are the three basic operations for combining and modifying sets, and De Morgan's laws describe exactly how complement interacts with union and intersection: the complement of a union is the intersection of the complements, and the complement of an intersection is the union of the complements. These two identities are not just a curiosity — they are the set-theoretic mirror of the logical De Morgan's laws relating 'and,' 'or,' and 'not' (since x ∈ A∪B means 'x∈A or x∈B,' and negating an 'or' statement turns it into an 'and' of negations). Because every set-builder condition can be rephrased as a logical statement, De Morgan's laws let you systematically rewrite complicated combinations of unions, intersections, and complements into an equivalent but often simpler or more convenient form.

Intuition

Picture the elements NOT in A∪B (the complement of the union): an element avoids the union only by avoiding BOTH A and B individually, so it must be in the complement of A AND the complement of B at once — hence (A∪B)ᶜ = Aᶜ∩Bᶜ. Conversely, an element is NOT in A∩B (the complement of the intersection) if it fails to be in at least one of A or B — it could be missing from A, or missing from B, or both — so it lands in Aᶜ∪Bᶜ. In everyday language: 'not (raining or snowing)' means 'not raining AND not snowing,' while 'not (tall and strong)' means 'not tall OR not strong' (failing on at least one trait). Complementation flips union into intersection and intersection into union — it's a kind of mirror-image duality running through all of set operations.

Formal Definition

Definition

For subsets A, B of a universal set U, with complement Aᶜ = U \ A, De Morgan's laws state that the complement of a union is the intersection of complements, and the complement of an intersection is the union of complements. These identities generalize to arbitrary (even infinite) families of sets.

(A \cup B)^{c} = A^{c} \cap B^{c}

De Morgan's first law

(A \cap B)^{c} = A^{c} \cup B^{c}

De Morgan's second law

\left(\bigcup_{i \in I} A_i\right)^{c} = \bigcap_{i \in I} A_i^{c}

General form (arbitrary index set I)

\left(\bigcap_{i \in I} A_i\right)^{c} = \bigcup_{i \in I} A_i^{c}

General form, intersection case

Notation

Notation	Meaning
$\cup$	Union — elements in A or B (or both)
$\cap$	Intersection — elements in both A and B
$A^{c}$	Complement of A relative to a universal set U, i.e. U \ A
$A \setminus B$	Set difference — elements in A but not in B
$A \subseteq B$	A is a subset of B: every element of A is an element of B

Properties

Commutativity

A \cup B = B \cup A, \qquad A \cap B = B \cap A

Associativity

(A \cup B) \cup C = A \cup (B \cup C), \qquad (A \cap B) \cap C = A \cap (B \cap C)

Distributivity

A \cap (B \cup C) = (A \cap B) \cup (A \cap C)

Double complement

(A^{c})^{c} = A

De Morgan's laws

(A\cup B)^c = A^c \cap B^c, \quad (A \cap B)^c = A^c \cup B^c

Applications

De Morgan's laws are used constantly to simplify boolean expressions and negate conditional statements in code (e.g. !(a && b) is equivalent to !a || !b), and to design digital logic circuits using NAND/NOR gates.

Worked Examples

Compute A∪B = {1,2,3,4,5}, so its complement in U is the elements left out: {6}.
$(A\cup B)^{c} = \{6\}$
Compute Aᶜ = {4,5,6} and Bᶜ = {1,2,6}; their intersection is the elements common to both.
$A^{c} \cap B^{c} = \{4,5,6\} \cap \{1,2,6\} = \{6\}$
Both sides equal {6}, confirming the law for this example.
$(A\cup B)^{c} = A^{c}\cap B^{c} = \{6\}$

Answer: (A∪B)ᶜ = Aᶜ∩Bᶜ = {6} — verified directly by listing elements.

Practice Problems

Difficulty 2/10

Let U={1,...,10}, A={1,3,5,7,9} (odds), B={2,3,5,7} (some primes). Compute (A∩B)ᶜ and Aᶜ∪Bᶜ separately, and confirm they match.

Difficulty 3/10

Which expression is equal to (A ∪ B ∪ C)ᶜ?

Aᶜ ∪ Bᶜ ∪ CᶜAᶜ ∩ Bᶜ ∩ CᶜA ∩ B ∩ C(A∩B∩C)ᶜ

Difficulty 4/10

A system fails if component X fails OR component Y fails. Using De Morgan's laws, express the event 'the system works' in terms of X and Y working.

Common Mistakes

Common Mistake

Thinking (A∪B)ᶜ = Aᶜ∪Bᶜ (keeping the same operation instead of swapping it).

De Morgan's laws SWAP the operation: complementing a union gives an intersection of complements, (A∪B)ᶜ=Aᶜ∩Bᶜ, and complementing an intersection gives a union of complements.

Common Mistake

Applying De Morgan's laws only to two sets and not realizing they generalize to any number (even infinitely many) of sets.

The laws hold for arbitrary families: (⋃ᵢAᵢ)ᶜ = ⋂ᵢAᵢᶜ and (⋂ᵢAᵢ)ᶜ = ⋃ᵢAᵢᶜ, for any index set I, finite or infinite.

Quiz

Historical Background

The logical laws relating negation, conjunction, and disjunction were known in some form to ancient and medieval logicians (traces appear in the work of William of Ockham and other 14th-century scholastics), but they are named after the 19th-century British mathematician Augustus De Morgan, who gave them a rigorous, systematic formulation as part of his broader project of formalizing logic algebraically in the 1840s–1860s. When Georg Cantor and Richard Dedekind developed set theory later in the 19th century, the direct correspondence between logical connectives (and, or, not) and set operations (intersection, union, complement) meant De Morgan's laws transferred immediately into the new language of sets, becoming one of the first identities taught in any basic set theory course.

c. 1350
Logical precursors to De Morgan's laws appear in the work of scholastic logicians such as William of Ockham
William of Ockham
1847
Augustus De Morgan publishes Formal Logic, systematizing the laws relating negation, conjunction, and disjunction
Augustus De Morgan
1874
Cantor's foundational set theory paper establishes the union/intersection/complement framework in which the laws are restated for sets
Georg Cantor

Summary

Union (A∪B), intersection (A∩B), and complement (Aᶜ) are the basic operations for combining/modifying sets.
De Morgan's first law: (A∪B)ᶜ = Aᶜ∩Bᶜ — complementing a union gives the intersection of complements.
De Morgan's second law: (A∩B)ᶜ = Aᶜ∪Bᶜ — complementing an intersection gives the union of complements.
These mirror the logical laws relating negation, 'and,' and 'or,' since set membership in A∪B/A∩B is literally 'or'/'and.'
Both laws generalize to arbitrary (including infinite) families of sets, not just pairs.

References

WebsiteWikipedia — De Morgan's laws
WebsiteWikipedia — Set (mathematics)