Page 152 - Discrete Mathematics and Its Applications

2.2 Set Operations 131

EXAMPLE 11 Use set builder notation and logical equivalences to establish the first De Morgan law A ∩ B =
A ∪ B.

Solution: We can prove this identity with the following steps.

A ∩ B ={x | x/∈ A ∩ B} by definition of complement
={x |¬(x ∈ (A ∩ B))} by definition of does not belong symbol
={x |¬(x ∈ A ∧ x ∈ B)} by definition of intersection
={x |¬(x ∈ A) ∨¬(x ∈ B)} by the first De Morgan law for logical equivalences
={x | x/∈ A ∨ x/∈ B} by definition of does not belong symbol
={x | x ∈ A ∨ x ∈ B} by definition of complement
={x | x ∈ A ∪ B} by definition of union
= A ∪ B by meaning of set builder notation

Note that besides the definitions of complement, union, set membership, and set builder
notation, this proof uses the second De Morgan law for logical equivalences. ▲

Proving a set identity involving more than two sets by showing each side of the identity is
a subset of the other often requires that we keep track of different cases, as illustrated by the
proof in Example 12 of one of the distributive laws for sets.
EXAMPLE 12 Prove the second distributive law from Table 1, which states that A ∩ (B ∪ C) = (A ∩ B) ∪
(A ∩ C) for all sets A, B, and C.

Solution: We will prove this identity by showing that each side is a subset of the other side.
Suppose that x ∈ A ∩ (B ∪ C). Then x ∈ A and x ∈ B ∪ C. By the definition of union, it
follows that x ∈ A, and x ∈ B or x ∈ C (or both). In other words, we know that the compound
proposition (x ∈ A) ∧ ((x ∈ B) ∨ (x ∈ C)) is true. By the distributive law for conjunction over
disjunction, it follows that ((x ∈ A) ∧ (x ∈ B)) ∨ ((x ∈ A) ∧ (x ∈ C)).We conclude that either
x ∈ Aandx ∈ B,orx ∈ Aandx ∈ C.Bythedefinitionofintersection,itfollowsthatx ∈ A ∩ B
or x ∈ A ∩ C. Using the definition of union, we conclude that x ∈ (A ∩ B) ∪ (A ∩ C).We
conclude that A ∩ (B ∪ C) ⊆ (A ∩ B) ∪ (A ∩ C).
Now suppose that x ∈ (A ∩ B) ∪ (A ∩ C). Then, by the definition of union, x ∈ A ∩ B or
x ∈ A ∩ C. By the definition of intersection, it follows that x ∈ A and x ∈ B or that x ∈ A and
x ∈ C. From this we see that x ∈ A, and x ∈ B or x ∈ C. Consequently, by the definition of
union we see that x ∈ A and x ∈ B ∪ C. Furthermore, by the definition of intersection, it follows
that x ∈ A ∩ (B ∪ C). We conclude that (A ∩ B) ∪ (A ∩ C) ⊆ A ∩ (B ∪ C). This completes
the proof of the identity. ▲

Set identities can also be proved using membership tables. We consider each combination
of sets that an element can belong to and verify that elements in the same combinations of sets
belong to both the sets in the identity. To indicate that an element is in a set, a 1 is used; to
indicate that an element is not in a set, a 0 is used. (The reader should note the similarity between
membership tables and truth tables.)
EXAMPLE 13 Use a membership table to show that A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).

Solution: The membership table for these combinations of sets is shown in Table 2. This table
has eight rows. Because the columns for A ∩ (B ∪ C) and (A ∩ B) ∪ (A ∩ C) are the same, the
identity is valid. ▲
Additionalsetidentitiescanbeestablishedusingthosethatwehavealreadyproved.Consider
Example 14.