Operations on Sets 23DeMorgan's Laws
DeMorgan's Laws are among the most important and useful results about sets. These laws
describe how union, intersection, and complement are related. Figure 1.10 indicates what
the laws tell us.MA BA BAuB=ArB ArB=AuB
Figure 1.10 DeMorgan's Laws.
Theorem 8. (DeMorgan's Laws) Let U be a universal set, and let A and B be subsets
of U. Then:(a) (A U B) = A n B. (DeMorgan's Law for Union)
(b) (A ( B) = A U B. (DeMorgan's Law for Intersection)
Proof.
(a) Show that (i) (A UB) c A WB and (ii) A n B c (A U B).
(i) Pick an arbitrary x E (A U B). Since x e U - (A U B), it follows that x 0 A U B.
For x not to be in this union means it may not be in either of the sets. So, x 0 Aand x 0 B. Hence, since x e U - A = A and x E U - B = B, it follows that x
A (2B.
(ii) Pick an arbitrary X E A n B. Then, x e A, so x 0 A. Also, x E B, so x § B.
Therefore, x g (A U B), and consequently, x e (A U B).
(b) The proof is left for the reader. N
Theorem 8 resembles the ways that and and or interact with not (which are also called
DeMorgan's Laws in logic). For example, "not (x is greater than 3 or x is odd)" is equiva-
lent to "x is not greater than 3, and x is not odd." A more thorough study of logic is given
in Chapter 2.Example 7. Verify DeMorgan's Laws for the sets A = 11, 2, 3, 4} and B = {3, 5, 6, 8}
when the universal set is U = {1, 2, 3, 4, 5, 6, 7, 8).
Solution. AUB={l,2,3,4,5,6,8}={7}. -A={5,6,7,81. B={1,2,4,7}.
An B = {7}. It now follows that A U B = A; B. U
DeMorgan's Laws are important tools for proving results about how union, intersec-
tion, and complementation interact. The notion of the symmetric difference is a particular
instance of this. Symmetric difference identifies the elements of two sets that are not in
their intersection. This set (A U B) - (A n B) is shown in Figure 1.11.
AF BFigure 1.11 Elements in two sets that are not in the intersection: A U B - A n B.