Set Identities

Identity Laws

Name	Identity
Identity / Domination Laws	$\begin{array}{r}A\cup \varnothing =AA\cap \varnothing =\varnothing \\ A\cup U=UA\cap U=A\end{array}$
Commutative Laws	$A\cap B=B\cap AA\cup B=B\cup A$
Associative Laws	$\begin{array}{r}(A\cap B)\cap C=A\cap (B\cap C)\\ (A\cup B)\cup C=A\cup (B\cup C)\end{array}$
Distributive Laws	$\begin{array}{r}A\cup (B\cap C)=(A\cup B)\cap (A\cup C)\\ A\cap (B\cup C)=(A\cap B)\cup (A\cap C)\end{array}$
Idempotent Laws	$A\cap A=AA\cup A=A$
Complementation Laws	$\begin{array}{r}A\cap \bar{A}=\varnothing A\cup \bar{A}=U\\ \bar{U}=\varnothing \varnothing =\bar{U}\\ \overline{(\overline{A})}=A\end{array}$
De Morgan’s Laws	$\begin{array}{r}\overline{(A\cap B)}=\bar{A}\cup \bar{B}\\ \overline{(A\cup B)}=\bar{A}\cap \bar{B}\end{array}$
Absorption Laws	$\begin{array}{r}A\cup (A\cap B)=A\\ A\cap (A\cup B)=A\end{array}$
Set Difference Laws	$\begin{array}{rl}& A-B=A\cap (B\oplus A)\\ & A-B=A\cap \bar{B}\end{array}$
Subset Union Laws	$A\subseteq (A\cup B)B\subseteq (A\cup B)$
Subset Intersection Laws	$(A\cap B)\subseteq A(A\cap B)\subseteq B$
Subset Transitive Law	$(A\subseteq B)\wedge (B\subseteq C)⟹(A\subseteq C)$

Proving Set Identities

We can use the identity laws table above to prove set identities.

Example

Show $\overline{A\cup (B\cap C)}=(\bar{C}\cup \bar{B})\cap \bar{A}$

$\begin{array}{r}\overline{A\cup (B\cap C)}=\bar{A}\cap \overline{(B\cap C)}\text{De Morgan’s Law}\\ =\bar{A}\cap (\bar{B}\cup \bar{C})\text{De Morgan’s Law}\\ =(\bar{B}\cup \bar{C})\cap \bar{A}\text{Commutative Law}\\ =(\bar{C}\cup \bar{B})\cap \bar{A}\text{Commutative Law}\end{array}$

Proving With Membership Tables

Set identity can also be proved using membership tables, which is similar to propositional logic, but instead we use 1 to denote that an element is in a set and 0 if not.

Example

Prove $(A\cup B)-B=A-B$

$A$	$B$	$(A\cup B)$	$(A\cup B)-B$	$A-B$
1	1	1	0	0
1	0	1	1	1
0	1	1	0	0
0	0	0	0	0

Since the last two columns have equal values, the equation is true.