Introduction to Discrete Mathematics

Operations on Sets

Notes By Pr. El Hadiq Zouhair

1 / 13

Overview

Sets can be combined in many different ways.
Set operations are the main tools to make any combination of sets possible.
Many visualizations of those operations are linked to logic.
In this lesson, you will see how to combine sets computationally and visually, using Python's built-in set and SymPy's FiniteSet.

Python / SymPy — imports (run once) from itertools import product from sympy import FiniteSet, EmptySet, Union, Intersection, Complement, Interval, S from sympy import symbols, Not, And, Or, simplify A, B, C = symbols('A B C')

2 / 13

Union

The union of two sets $A$ and $B$ ($A \cup B$, A | B) is the set obtained by combining the members of each original set.

The closed-form union of sets $A_1$ through $A_n$ is denoted $\displaystyle\bigcup_{i=1}^{n} A_i$.

In Python, | on built-in set returns the union (no duplicates, no order).

Python A = {1, 2, 3} B = {3, 4, 5} print(A | B) # {1, 2, 3, 4, 5} print(sorted(A | B)) # [1, 2, 3, 4, 5]

SymPy from sympy import FiniteSet, Union A = FiniteSet(1, 2, 3) B = FiniteSet(3, 4, 5) print(Union(A, B)) # {1, 2, 3, 4, 5}

3 / 13

Intersection

The intersection of two sets $A$ and $B$ ($A \cap B$, A & B) is the set of elements common to $A$ and $B$.

Intersection is a higher priority operation than union.

The closed-form intersection of $A_1, \dots, A_n$ is $\displaystyle\bigcap_{i=1}^{n} A_i$.

Python A = {1, 2, 3} B = {3, 4, 5} print(A & B) # {3} # n-ary intersection sets = [{1,2,3}, {2,3,4}, {3,4,5}] print(set.intersection(*sets)) # {3}

SymPy from sympy import Intersection print(Intersection(A, B)) # {3}

4 / 13

Complement

The complement ($A'$, $A^c$, $\overline{A}$, $\neg A$) of a set $A$ is the set of all elements of the universe $U$ that are not in $A$.

Complement is a higher-priority operation than intersection or union.

Python — universe-based U = set(range(1, 11)) # universe = {1..10} A = {5, 6, 7, 8, 9, 10} print(U - A) # {1, 2, 3, 4} # difference of two sets: print(set(range(7)) - set(range(5, 10))) # {0,1,2,3,4}

SymPy — Complement from sympy import Complement, FiniteSet U = FiniteSet(*range(1, 11)) A = FiniteSet(5, 6, 7, 8, 9, 10) print(Complement(U, A)) # {1, 2, 3, 4}

5 / 13

Example 1 — combining operations

Consider sets $G = \{1,\dots,7\}$, $H = \{3,\dots,9\}$, $I = \{5,\dots,11\}$.

What elements are in $(G \cup H) \cap I'$ (with universe $U = G \cup H \cup I$)?

Python G = set(range(1, 8)) # {1,2,3,4,5,6,7} H = set(range(3, 10)) # {3,4,5,6,7,8,9} I = set(range(5, 12)) # {5,6,7,8,9,10,11} U = G | H | I answer = (G | H) & (U - I) print(sorted(answer)) # [1, 2, 3, 4]

Output [1, 2, 3, 4]

The result $\{1, 2, 3, 4\}$ matches the orange region of the Venn diagram of $G$, $H$, $I$ (everything in $G$ or $H$ but not in $I$).

6 / 13

Example 2 — empty regions

With $G = \{1..7\}$, $H = \{3..9\}$, $I = \{5..11\}$, ask: which Venn region(s) of $G$, $H$, $I$ contain no elements?

Python — all 8 regions of the 3-set Venn diagram def venn_regions(A, B, C, U=None): U = U or (A | B | C) regions = {} for bits in product([0, 1], repeat=3): sel = [(A, B, C)[i] if b else (U - (A, B, C)[i]) for i, b in enumerate(bits)] regions[bits] = sel[0] & sel[1] & sel[2] return regions G, H, I = set(range(1,8)), set(range(3,10)), set(range(5,12)) for key, region in venn_regions(G, H, I).items(): print(key, "→", sorted(region))

Output (key = (in G, in H, in I)) (0,0,0) → [] # outside all — empty (0,0,1) → [10, 11] (0,1,0) → [] # in H only — empty (0,1,1) → [8, 9] (1,0,0) → [1, 2] (1,0,1) → [] # in G and I but not H — empty (1,1,0) → [3, 4] (1,1,1) → [5, 6, 7]

The empty regions correspond to: $G \cap I \cap H'$, $G' \cap I' \cap H$.

7 / 13

Set Identities

Identity	$A \cap U = A,\quad A \cup \varnothing = A$
Domination	$A \cup U = U,\quad A \cap \varnothing = \varnothing$
Idempotency	$A \cup A = A,\quad A \cap A = A$
Complementation	$(A')' = A$
Commutativity	$A \cup B = B \cup A,\quad A \cap B = B \cap A$
Associativity	$A \cup (B \cup C) = (A \cup B) \cup C,\;\; A \cap (B \cap C) = (A \cap B) \cap C$
Distributivity	$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 \cap B)' = A' \cup B',\quad (A \cup B)' = A' \cap B'$
Absorption	$A \cup (A \cap B) = A,\quad A \cap (A \cup B) = A$
Complement	$A \cup A' = U,\quad A \cap A' = \varnothing$

True ⇔ U | False ⇔ ∅

8 / 13

Proving Identities

You can prove any of these identities using Venn diagrams, or, in Python, by an exhaustive check on a small universe.

Python — exhaustive check of De Morgan's law from itertools import combinations def check_demorgan(U): """Verify (A ∩ B)' == A' ∪ B' for all A, B ⊆ U.""" subsets = [] for r in range(len(U) + 1): subsets += [set(c) for c in combinations(U, r)] for A in subsets: for B in subsets: lhs = U - (A & B) rhs = (U - A) | (U - B) assert lhs == rhs return True print(check_demorgan({1, 2, 3, 4})) # True (2^4 × 2^4 = 256 checks)

Two Venn diagrams are identical if and only if their shaded regions match — that is exactly what the loop above tests.

9 / 13

Membership Tables

Notice the direct correspondence between set identities and logic:

$\cup \;\Leftrightarrow\; \vee$ (or)
$\cap \;\Leftrightarrow\; \wedge$ (and)
$\,'\;\Leftrightarrow\; \neg$ (not)

Any identity can therefore be proven using a truth table. Example: $(A \cap B)' = A' \cup B'$ (De Morgan).

$A$	$B$	$(A \cap B)'$	$A' \cup B'$
T	T	F	F
T	F	T	T
F	T	T	T
F	F	T	T

Python — print a membership table from itertools import product print(f"{'A':>5} {'B':>5} {'(A∩B)\\'':>10} {'A\\'∪B\\'':>10}") for a, b in product([True, False], repeat=2): lhs = not (a and b) rhs = (not a) or (not b) print(f"{a!s:>5} {b!s:>5} {lhs!s:>10} {rhs!s:>10}")

10 / 13

Example — proving an equivalence

Show that $\;(A \cap B \cup C \cup D) \cap B' \cup C \;\equiv\; B' \cap D \cup C$ using a Venn diagram and a membership table.

Python — verify with all 16 truth assignments from itertools import product def lhs(a, b, c, d): return ((a and b) or c or d) and ((not b) or c) def rhs(a, b, c, d): return ((not b) and d) or c ok = all(lhs(*vals) == rhs(*vals) for vals in product([True, False], repeat=4)) print("Equivalent?", ok) # True

Python — SymPy symbolic simplification from sympy import symbols, And, Or, Not, simplify, Equivalent A, B, C, D = symbols('A B C D') lhs = And(Or(And(A, B), C, D), Or(Not(B), C)) rhs = Or(And(Not(B), D), C) print(simplify(Equivalent(lhs, rhs))) # True

11 / 13

Summary

Sets can be combined using union ($\cup$, |), intersection ($\cap$, &), and complement ($'$, -).
Set identities help simplify set expressions (Distributivity, De Morgan, Absorption, …).
There is an equivalence between logic and set identities: $\cup \leftrightarrow \vee,\; \cap \leftrightarrow \wedge,\; ' \leftrightarrow \neg,\; U \leftrightarrow$ True$,\; \varnothing \leftrightarrow$ False.
Visualization is possible using Venn diagrams and membership tables.
All these operations can be combined into more powerful tools, commonly called functions.

Python — key tools for this lesson from itertools import combinations, product from sympy import FiniteSet, Union, Intersection, Complement, simplify, symbols, And, Or, Not

12 / 13

Wolfram → Python Quick Reference

Operation	Wolfram	Python (built-in)	SymPy
Union	`Union[A,B]`	`A \| B`	`Union(A,B)`
Intersection	`Intersection[A,B]`	`A & B`	`Intersection(A,B)`
Complement (B in A)	`Complement[A,B]`	`A - B`	`Complement(A,B)`
Symmetric diff.	`SymmetricDifference`	`A ^ B`	`(A-B) ∪ (B-A)`
N-ary union	`Union @@ list`	`set().union(*L)`	`Union(*L)`
N-ary intersect.	`Intersection @@ L`	`set.intersection(*L)`	`Intersection(*L)`
Membership table	`TruthTable[…]`	`itertools.product`	`truth_table(…)`
Prove identity	`FullSimplify`	brute-force on small U	`simplify(Equivalent(…))`
Venn diagram	`ResourceFunction["VennDiagram"]`	`matplotlib_venn`	—

13 / 13