← Back to Mathematical Logic, Set Theory and Combinatorics
Course: MAT1MN104 — Mathematical Logic, Set Theory and Combinatorics Companion to: Module II — Set Theory, Section 2.1 (The 24 Laws of Sets)
Notation (Koshy’s convention, same as Module II): complement $A’$ (prime), universal set $U$, empty set $\emptyset$, difference $A-B$, symmetric difference $A\oplus B$. Set operations mirror logic exactly: $\cup\leftrightarrow\lor$, $\cap\leftrightarrow\land$, $’\leftrightarrow\sim$, $\emptyset\leftrightarrow f$, $U\leftrightarrow t$.
How to use this page: each example is solved by chaining named laws from the Table 2.2 list in Module II — never by drawing a Venn diagram or picking elements (except Example 9, which is marked as an element-chasing proof, the other standard technique the exam accepts). Quote the law name in brackets at every step, exactly as shown — that’s what full marks looks like in Section B/C of the external exam. A “Verifying Examples 1–10 with Concrete Sets” section near the end re-checks all ten results by roster-listing actual sets, for students who want to see a numeric confirmation alongside the symbolic proof.
For quick reference, the law names used below:
| Law | Statement |
|---|---|
| Idempotent | $A\cup A=A$ $A\cap A=A$ |
| Identity | $A\cup\emptyset=A$ $A\cap U=A$ |
| Inverse | $A\cup A’=U$ $A\cap A’=\emptyset$ |
| Domination | $A\cup U=U$ $A\cap\emptyset=\emptyset$ |
| Commutative | $A\cup B=B\cup A$ $A\cap B=B\cap A$ |
| Double complementation | $(A’)’=A$ |
| Associative | $A\cup(B\cup C)=(A\cup B)\cup C$ $A\cap(B\cap C)=(A\cap B)\cap C$ |
| Distributive | $A\cup(B\cap C)=(A\cup B)\cap(A\cup C)$ $A\cap(B\cup C)=(A\cap B)\cup(A\cap C)$ |
| De Morgan’s | $(A\cup B)’=A’\cap B’$ $(A\cap B)’=A’\cup B’$ |
| Absorption | $A\cup(A\cap B)=A$ $A\cap(A\cup B)=A$ |
| Difference identity | $A-B=A\cap B’$ |
Example 1 — Deriving the Absorption Law
Simplify $A \cup (A \cap B)$.
\[\begin{aligned} &A \cup (A \cap B) \\ &= (A \cap U) \cup (A \cap B) && [\text{identity: } A = A\cap U] \\ &= A \cap (U \cup B) && [\text{distributive}] \\ &= A \cap U && [\text{domination: } U\cup B = U] \\ &= A && [\text{identity}] \end{aligned}\]Answer: $A$. This is exactly the Absorption law — the point of the exercise is to see why it’s true, not just quote it. Once you’ve derived it once, you may cite “Absorption” directly in later proofs.
Example 2 — The Dual Absorption Law
Simplify $A \cap (A \cup B)$.
\[\begin{aligned} &A \cap (A \cup B) \\ &= (A \cup \emptyset) \cap (A \cup B) && [\text{identity: } A = A\cup\emptyset] \\ &= A \cup (\emptyset \cap B) && [\text{distributive}] \\ &= A \cup \emptyset && [\text{domination: } \emptyset\cap B = \emptyset] \\ &= A && [\text{identity}] \end{aligned}\]Answer: $A$. Compare with Example 1 — same skeleton, every law swapped for its dual ($\cup\leftrightarrow\cap$, $U\leftrightarrow\emptyset$). This $\cup/\cap$ duality is the fastest way to remember both halves of every law in the table.
Example 3 — Distributive + Inverse
Simplify $(A \cup B) \cap (A \cup B’)$.
\[\begin{aligned} &(A \cup B) \cap (A \cup B') \\ &= A \cup (B \cap B') && [\text{distributive, in reverse: } A\cup X \text{ form}] \\ &= A \cup \emptyset && [\text{inverse: } B\cap B' = \emptyset] \\ &= A && [\text{identity}] \end{aligned}\]Answer: $A$. Watch the direction of the distributive law here — it’s being used right-to-left, $(A\cup X)\cap(A\cup Y) = A\cup(X\cap Y)$, which is just as valid as the left-to-right form used in Example 1.
Example 4 — Distributive + Inverse (dual)
Simplify $A \cap (A’ \cup B)$.
\[\begin{aligned} &A \cap (A' \cup B) \\ &= (A \cap A') \cup (A \cap B) && [\text{distributive}] \\ &= \emptyset \cup (A \cap B) && [\text{inverse: } A\cap A' = \emptyset] \\ &= A \cap B && [\text{identity}] \end{aligned}\]Answer: $A \cap B$. A common trap is to guess $A$ here by analogy with Example 2 — but $B$ is not the same as $A\cup B$, so absorption doesn’t apply. Always distribute first and simplify honestly.
Example 5 — De Morgan’s Law Distributes Over a Difference
Prove $A - (B \cap C) = (A-B) \cup (A-C)$.
\[\begin{aligned} &A - (B \cap C) \\ &= A \cap (B \cap C)' && [\text{difference identity: } X-Y = X\cap Y'] \\ &= A \cap (B' \cup C') && [\text{De Morgan's}] \\ &= (A \cap B') \cup (A \cap C') && [\text{distributive}] \\ &= (A - B) \cup (A - C) && [\text{difference identity, applied twice}] \end{aligned}\]QED. This is the set-theoretic mirror of the logic identity $p \land \sim(q\land r) \equiv (p\land\sim q) \lor (p\land\sim r)$.
Example 6 — The Other De Morgan Difference Law
Prove $A - (B \cup C) = (A-B) \cap (A-C)$. (This answers Practice Problem 12 from Module II in full.)
\[\begin{aligned} &A - (B \cup C) \\ &= A \cap (B \cup C)' && [\text{difference identity}] \\ &= A \cap (B' \cap C') && [\text{De Morgan's}] \\ &= A \cap A \cap B' \cap C' && [\text{idempotent: } A = A\cap A, \text{ then associative}] \\ &= (A \cap B') \cap (A \cap C') && [\text{associative + commutative, regrouped}] \\ &= (A - B) \cap (A - C) && [\text{difference identity, applied twice}] \end{aligned}\]QED. The key trick — writing $A$ as $A\cap A$ before regrouping — is worth remembering; it’s the standard move whenever you need to “duplicate” a set to distribute it across two bracketed terms.
Example 7 — A Three-Term Simplification
Simplify $(A \cap B) \cup (A \cap B’) \cup (A’ \cap B)$.
\[\begin{aligned} &(A \cap B) \cup (A \cap B') \cup (A' \cap B) \\ &= [A \cap (B \cup B')] \cup (A' \cap B) && [\text{distributive, on the first two terms}] \\ &= (A \cap U) \cup (A' \cap B) && [\text{inverse}] \\ &= A \cup (A' \cap B) && [\text{identity}] \\ &= (A \cup A') \cap (A \cup B) && [\text{distributive}] \\ &= U \cap (A \cup B) && [\text{inverse}] \\ &= A \cup B && [\text{identity}] \end{aligned}\]Answer: $A \cup B$. A useful sanity check: draw a 2-set Venn diagram and shade the three regions on the left ($A$-only, $B$-only, and $A\cap B$) — together they visibly cover all of $A\cup B$. The law-based proof is what you write in the exam; the Venn diagram is how you check your work before you write it.
Example 8 — Simplifying a Union Involving a Complement
Simplify $(A \cup B)’ \cup B$.
\[\begin{aligned} &(A \cup B)' \cup B \\ &= (A' \cap B') \cup B && [\text{De Morgan's}] \\ &= (A' \cup B) \cap (B' \cup B) && [\text{distributive}] \\ &= (A' \cup B) \cap U && [\text{inverse: } B'\cup B = U] \\ &= A' \cup B && [\text{identity}] \end{aligned}\]Answer: $A’ \cup B$. Notice the answer no longer mentions the original bracketed complement $(A\cup B)’$ at all — a sign the simplification is genuine, not cosmetic.
Example 9 — Connecting $\subseteq$ to the Laws (element-chasing)
Prove: $A \subseteq B$ if and only if $A \cap B’ = \emptyset$.
This one can’t be done by chaining laws alone, because $\subseteq$ is a relation between sets, not an operation — so we go back to the definition ($A\subseteq B \leftrightarrow$ every $x\in A$ has $x\in B$) and argue with an arbitrary element, exactly as in Module II §1.1.
($\Rightarrow$) Assume $A \subseteq B$. Suppose, for contradiction, $A \cap B’ \neq \emptyset$. Then there is some $x \in A \cap B’$, so $x \in A$ and $x \in B’$ (i.e. $x \notin B$). But $A \subseteq B$ means $x \in A \to x \in B$, so $x \in B$ — contradicting $x \notin B$. Hence $A \cap B’ = \emptyset$.
($\Leftarrow$) Assume $A \cap B’ = \emptyset$. Let $x \in A$ be arbitrary. If $x \notin B$, then $x \in B’$, so $x \in A \cap B’ = \emptyset$ — impossible. So $x \in B$. Since $x$ was an arbitrary element of $A$, $A \subseteq B$.
QED. This iff is exactly the “unnamed law” row of the Table 2.2 summary in Module II ($A\subseteq B \Leftrightarrow A\cap B=A \Leftrightarrow A\cup B=B \Leftrightarrow B’\subseteq A’$) — $A\cap B’=\emptyset$ is one more equivalent way to say the same thing, and often the fastest one to check numerically.
Example 10 — Deriving the Symmetric Difference Formula
Prove $A \oplus B = (A \cap B’) \cup (A’ \cap B)$, starting only from the definition $A \oplus B = (A \cup B) - (A \cap B)$.
\[\begin{aligned} &A \oplus B \\ &= (A \cup B) - (A \cap B) && [\text{definition}] \\ &= (A \cup B) \cap (A \cap B)' && [\text{difference identity}] \\ &= (A \cup B) \cap (A' \cup B') && [\text{De Morgan's}] \\ &= [(A \cup B) \cap A'] \cup [(A \cup B) \cap B'] && [\text{distributive}] \\ &= [(A \cap A') \cup (B \cap A')] \cup [(A \cap B') \cup (B \cap B')] && [\text{distributive, twice more}] \\ &= [\emptyset \cup (A' \cap B)] \cup [(A \cap B') \cup \emptyset] && [\text{inverse, commutative}] \\ &= (A' \cap B) \cup (A \cap B') && [\text{identity}] \end{aligned}\]QED. This is the “XOR form” of symmetric difference — the set analogue of $p\oplus q \equiv (\sim p\land q)\lor(p\land\sim q)$ in logic — and it’s the version most useful in proofs, since it has no subtraction or bracketed complement in it, only $\cup$, $\cap$, and single complements.
Verifying Examples 1–10 with Concrete Sets
The ten proofs above hold for any sets $A$, $B$, $C$ — that’s the whole point of a law-based proof. But it’s good practice to check a law-chaining proof by plugging in actual sets with actual elements, roster-list both sides, and confirm they come out equal. This is also a legitimate way to disprove a false claim on an exam: one counterexample with concrete sets is enough.
Fix these sets for all ten checks below:
\[\begin{aligned} U &= \{1,2,3,4,5,6,7,8,9,10\} \\ A &= \{1,2,3,4,5,6\} \\ B &= \{4,5,6,7,8\} \\ C &= \{6,7,8,9,10\} \\[0.5em] A' &= U-A = \{7,8,9,10\} \\ B' &= U-B = \{1,2,3,9,10\} \\ C' &= U-C = \{1,2,3,4,5\} \end{aligned}\]1. $A \cup (A \cap B) = A$. $A\cap B = {4,5,6}$. $A\cup{4,5,6} = {1,2,3,4,5,6} = A$. ✓
2. $A \cap (A \cup B) = A$. $A\cup B = {1,2,3,4,5,6,7,8}$. $A\cap(A\cup B) = {1,2,3,4,5,6} = A$. ✓
3. $(A \cup B) \cap (A \cup B’) = A$. $A\cup B = {1,\ldots,8}$. $A\cup B’ = {1,2,3,4,5,6}\cup{1,2,3,9,10} = {1,2,3,4,5,6,9,10}$. Intersection $= {1,2,3,4,5,6} = A$. ✓
4. $A \cap (A’ \cup B) = A \cap B$. $A’\cup B = {7,8,9,10}\cup{4,5,6,7,8} = {4,5,6,7,8,9,10}$. $A\cap(A’\cup B) = {4,5,6}$. And $A\cap B = {4,5,6}$ directly. Equal. ✓
5. $A - (B \cap C) = (A-B) \cup (A-C)$. $B\cap C = {6,7,8}$. LHS: $A - {6,7,8} = {1,2,3,4,5}$. RHS: $A-B = {1,2,3}$; $A-C = {1,2,3,4,5}$; union $= {1,2,3,4,5}$. Equal. ✓
6. $A - (B \cup C) = (A-B) \cap (A-C)$. $B\cup C = {4,5,6,7,8,9,10}$. LHS: $A -$ that $= {1,2,3}$. RHS: $A-B = {1,2,3}$; $A-C = {1,2,3,4,5}$; intersection $= {1,2,3}$. Equal. ✓
7. $(A \cap B) \cup (A \cap B’) \cup (A’ \cap B) = A \cup B$. $A\cap B = {4,5,6}$. $A\cap B’ = {1,2,3,4,5,6}\cap{1,2,3,9,10} = {1,2,3}$. $A’\cap B = {7,8,9,10}\cap{4,5,6,7,8} = {7,8}$. Union of all three: ${1,2,3,4,5,6,7,8}$. And $A\cup B = {1,\ldots,8}$. Equal. ✓
8. $(A \cup B)’ \cup B = A’ \cup B$. $A\cup B = {1,\ldots,8}$, so $(A\cup B)’ = U - {1,\ldots,8} = {9,10}$. LHS: ${9,10}\cup B = {4,5,6,7,8,9,10}$. RHS: $A’\cup B = {7,8,9,10}\cup{4,5,6,7,8} = {4,5,6,7,8,9,10}$. Equal. ✓
9. $A \subseteq B \Leftrightarrow A \cap B’ = \emptyset$. $A$ itself is not a subset of $B$ (1,2,3 $\in A$ but $\notin B$), and indeed $A\cap B’ = {1,2,3,4,5,6}\cap{1,2,3,9,10} = {1,2,3} \neq \emptyset$ — consistent with the iff. Now take $A_2 = {4,5} \subseteq B$: $A_2\cap B’ = {4,5}\cap{1,2,3,9,10} = \emptyset$, confirming the forward direction on a genuine subset. ✓ (both a positive and a negative case checked)
10. $A \oplus B = (A \cap B’) \cup (A’ \cap B)$. By definition $A\oplus B = (A\cup B)-(A\cap B) = {1,\ldots,8} - {4,5,6} = {1,2,3,7,8}$. RHS: $A\cap B’ = {1,2,3}$ (from #7); $A’\cap B = {7,8}$ (from #7); union $= {1,2,3,7,8}$. Equal. ✓
Practice
Try re-deriving these using the same law-chaining technique before checking against the examples above:
- Simplify $B \cup (A \cap B)$ (dual of a case already covered — which one?).
- Simplify $(A \cap B) \cup (A’ \cap B) \cup (A \cap B’)$ (compare with Example 7 — is the answer the same?).
- Prove $(A \oplus B)’ = (A \cap B) \cup (A’ \cap B’)$, using Example 10 and De Morgan’s.
- Prove $A \subseteq B \Leftrightarrow A \cup B = B$, by the element-chasing method of Example 9.
- Simplify $(A \cup B’)’ \cup (A’ \cup B)$.