Page 157 - Discrete Mathematics and Its Applications

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

Exercises

1. Let A be the set of students who live within one mile b) using a membership table.
of school and let B be the set of students who walk to 16. Let A and B be sets. Show that
classes. Describe the students in each of these sets.
a) (A ∩ B) ⊆ A. b) A ⊆ (A ∪ B).
a) A ∩ B b) A ∪ B c) A − B ⊆ A. d) A ∩ (B − A) =∅.
c) A − B d) B − A e) A ∪ (B − A) = A ∪ B.
2. Suppose that A is the set of sophomores at your school 17. Show that if A, B, and C are sets, then A ∩ B ∩ C =
and B is the set of students in discrete mathematics at A ∪ B ∪ C
your school. Express each of these sets in terms of A and a) by showing each side is a subset of the other side.
B. b) using a membership table.
a) the set of sophomores taking discrete mathematics in
18. Let A, B, and C be sets. Show that
your school
a) (A ∪ B) ⊆ (A ∪ B ∪ C).
b) the set of sophomores at your school who are not tak-
b) (A ∩ B ∩ C) ⊆ (A ∩ B).
ing discrete mathematics c) (A − B) − C ⊆ A − C.
c) the set of students at your school who either are sopho- d) (A − C) ∩ (C − B) =∅.
mores or are taking discrete mathematics e) (B − A) ∪ (C − A) = (B ∪ C) − A.
d) the set of students at your school who either are not
sophomores or are not taking discrete mathematics 19. Show that if A and B are sets, then
a) A − B = A ∩ B.
3. Let A ={1, 2, 3, 4, 5} and B ={0, 3, 6}. Find
b) (A ∩ B) ∪ (A ∩ B) = A.
a) A ∪ B. b) A ∩ B.
c) A − B. d) B − A. 20. Show that if A and B are sets with A ⊆ B, then
a) A ∪ B = B.
4. Let A ={a, b, c, d, e} and B ={a, b, c, d, e, f, g, h}.
Find b) A ∩ B = A.
21. Prove the first associative law from Table 1 by show-
a) A ∪ B. b) A ∩ B.
ing that if A, B, and C are sets, then A ∪ (B ∪ C) =
c) A − B. d) B − A.
(A ∪ B) ∪ C.
In Exercises 5–10 assume that A is a subset of some underly- 22. Prove the second associative law from Table 1 by show-
ing universal set U.
ing that if A, B, and C are sets, then A ∩ (B ∩ C) =
5. Prove the complementation law in Table 1 by showing (A ∩ B) ∩ C.
that A = A. 23. Prove the first distributive law from Table 1 by show-
6. Prove the identity laws in Table 1 by showing that ing that if A, B, and C are sets, then A ∪ (B ∩ C) =
a) A ∪⊆ =A. b) A ∩ U = A. (A ∪ B) ∩ (A ∪ C).
7. Prove the domination laws in Table 1 by showing that 24. Let A, B, and C be sets. Show that (A − B) − C =
(A − C) − (B − C).
a) A ∪ U = U. b) A ∩ ∅=∅.
25. Let A ={0, 2, 4, 6, 8, 10}, B ={0, 1, 2, 3, 4, 5, 6}, and
8. Prove the idempotent laws in Table 1 by showing that
C ={4, 5, 6, 7, 8, 9, 10}. Find
a) A ∪ A = A. b) A ∩ A = A.
a) A ∩ B ∩ C. b) A ∪ B ∪ C.
9. Prove the complement laws in Table 1 by showing that
c) (A ∪ B) ∩ C. d) (A ∩ B) ∪ C.
a) A ∪ A = U. b) A ∩ A =∅.
26. Draw the Venn diagrams for each of these combinations
10. Show that of the sets A, B, and C.
a) A −∩ = A. b) ∅− A =∅. a) A ∩ (B ∪ C) b) A ∩ B ∩ C
11. Let A and B be sets. Prove the commutative laws from c) (A − B) ∪ (A − C) ∪ (B − C)
Table 1 by showing that 27. Draw the Venn diagrams for each of these combinations
a) A ∪ B = B ∪ A. of the sets A, B, and C.
b) A ∩ B = B ∩ A. a) A ∩ (B − C) b) (A ∩ B) ∪ (A ∩ C)
12. Prove the first absorption law from Table 1 by showing c) (A ∩ B) ∪ (A ∩ C)
that if A and B are sets, then A ∪ (A ∩ B) = A. 28. Draw the Venn diagrams for each of these combinations
13. Prove the second absorption law from Table 1 by showing of the sets A, B, C, and D.
that if A and B are sets, then A ∩ (A ∪ B) = A. a) (A ∩ B) ∪ (C ∩ D) b) A ∪ B ∪ C ∪ D
14. Find the sets A and B if A − B ={1, 5, 7, 8}, B − A = c) A − (B ∩ C ∩ D)
{2, 10}, and A ∩ B ={3, 6, 9}. 29. What can you say about the sets A and B if we know that
15. Prove the second De Morgan law in Table 1 by showing a) A ∪ B = A? b) A ∩ B = A?
that if A and B are sets, then A ∪ B = A ∩ B c) A − B = A? d) A ∩ B = B ∩ A?
a) by showing each side is a subset of the other side. e) A − B = B − A?