Page 153 - Discrete Mathematics and Its Applications

132 2 / Basic Structures: Sets, Functions, Sequences, Sums, and Matrices

TABLE 2 A Membership Table for the Distributive Property.
A B C B ∪ C A ∩ (B ∪ C) A ∩ B A ∩ C (A ∩ B) ∪ (A ∩ C)
1 1 1 1 1 1 1 1
1 1 0 1 1 1 0 1
1 0 1 1 1 0 1 1
1 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0
0 1 0 1 0 0 0 0
0 0 1 1 0 0 0 0
0 0 0 0 0 0 0 0

EXAMPLE 14 Let A, B, and C be sets. Show that

A ∪ (B ∩ C) = (C ∪ B) ∩ A.

Solution: We have

A ∪ (B ∩ C) = A ∩ (B ∩ C) by the first De Morgan law
= A ∩ (B ∪ C) by the second De Morgan law
= (B ∪ C) ∩ A by the commutative law for intersections
▲
= (C ∪ B) ∩ A by the commutative law for unions.

Generalized Unions and Intersections

Because unions and intersections of sets satisfy associative laws, the sets A ∪ B ∪ C and
A ∩ B ∩ C are well defined; that is, the meaning of this notation is unambiguous when A,
B, and C are sets. That is, we do not have to use parentheses to indicate which operation
comes first because A ∪ (B ∪ C) = (A ∪ B) ∪ C and A ∩ (B ∩ C) = (A ∩ B) ∩ C. Note that
A ∪ B ∪ C contains those elements that are in at least one of the sets A, B, and C, and that
A ∩ B ∩ C contains those elements that are in all of A, B, and C. These combinations of the
three sets, A, B, and C, are shown in Figure 5.

U U
A B A B

C C

(a) A U B U C is shaded. (b) A B C is shaded.
U
U
FIGURE 5 The Union and Intersection of A, B, and C.