Page 158 - Discrete Mathematics and Its Applications

2.2 Set Operations 137

30. Can you conclude that A = B if A, B, and C are sets such 49. Let A i be the set of all nonempty bit strings (that is, bit
that strings of length at least one) of length not exceeding i.
a) A ∪ C = B ∪ C? b) A ∩ C = B ∩ C? Find
n n
c) A ∪ C = B ∪ C and A ∩ C = B ∩ C?
a) A i . b) A i .
31. Let A and B be subsets of a universal set U. Show that
i=1 i=1
A ⊆ B if and only if B ⊆ A. ∞ ∞
50. Find i=1 A i and i=1 A i if for every positive integer i,
The symmetric difference of A and B, denoted by A ⊕ B,is a) A i ={i, i + 1,i + 2,...}.
the set containing those elements in either A or B, but not in
both A and B. b) A i ={0,i}.
c) A i = (0,i), that is, the set of real numbers x with
32. Find the symmetric difference of {1, 3, 5} and {1, 2, 3}.
0 <x <i.
33. Find the symmetric difference of the set of computer sci- d) A i = (i, ∞), that is, the set of real numbers x with
ence majors at a school and the set of mathematics majors x> i.
at this school. ∞ ∞
51. Find A i and A i if for every positive integer i,
i=1 i=1
34. Draw a Venn diagram for the symmetric difference of the a) A i ={−i, −i + 1,..., −1, 0, 1,...,i − 1,i}.
sets A and B.
b) A i ={−i, i}.
35. Show that A ⊕ B = (A ∪ B) − (A ∩ B). c) A i =[−i, i], that is, the set of real numbers x with
36. Show that A ⊕ B = (A − B) ∪ (B − A). −i ≤ x ≤ i.
d) A i =[i, ∞), that is, the set of real numbers x with
37. Show that if A is a subset of a universal set U, then
x ≥ i.
a) A ⊕ A =∅. b) A ⊕⊆ =A.
52. Suppose that the universal set is U ={1, 2, 3, 4,
c) A ⊕ U = A. d) A ⊕ A = U.
5, 6, 7, 8, 9, 10}. Express each of these sets with bit
38. Show that if A and B are sets, then
strings where the ith bit in the string is 1 if i is in the
a) A ⊕ B = B ⊕ A. b) (A ⊕ B) ⊕ B = A. set and 0 otherwise.
39. What can you say about the sets A and B if A ⊕ B = A? a) {3, 4, 5}
∗ 40. Determine whether the symmetric difference is associa- b) {1, 3, 6, 10}
tive; that is, if A, B, and C are sets, does it follow that c) {2, 3, 4, 7, 8, 9}
A ⊕ (B ⊕ C) = (A ⊕ B) ⊕ C?
53. Using the same universal set as in the last problem, find
∗ 41. Suppose that A, B, and C are sets such that A ⊕ C = the set specified by each of these bit strings.
B ⊕ C. Must it be the case that A = B? a) 11 1100 1111
42. If A, B, C, and D are sets, does it follow that (A ⊕ B) ⊕ b) 01 0111 1000
(C ⊕ D) = (A ⊕ C) ⊕ (B ⊕ D)? c) 10 0000 0001

43. If A, B, C, and D are sets, does it follow that (A ⊕ B) ⊕ 54. What subsets of a finite universal set do these bit strings
(C ⊕ D) = (A ⊕ D) ⊕ (B ⊕ C)? represent?
44. Show that if A and B are finite sets, then A ∪ B is a finite a) the string with all zeros
set. b) the string with all ones
45. Show that if A is an infinite set, then whenever B is a set, 55. What is the bit string corresponding to the difference of
A ∪ B is also an infinite set. two sets?
∗ 46. Show that if A, B, and C are sets, then 56. What is the bit string corresponding to the symmetric dif-
ference of two sets?
|A ∪ B ∪ C|=|A|+|B|+|C|−|A ∩ B| 57. Show how bitwise operations on bit strings can be
−|A ∩ C|−|B ∩ C|+|A ∩ B ∩ C|. used to find these combinations of A ={a, b, c, d, e},
B ={b, c, d, g, p, t, v}, C ={c, e, i, o, u, x, y, z}, and
D ={d, e, h, i, n, o, t, u, x, y}.
(This is a special case of the inclusion–exclusion princi-
ple, which will be studied in Chapter 8.) a) A ∪ B b) A ∩ B
c) (A ∪ D) ∩ (B ∪ C) d) A ∪ B ∪ C ∪ D
47. Let A i ={1, 2, 3,...,i} for i = 1, 2, 3,.... Find
n n 58. How can the union and intersection of n sets that all are

a) A i . b) A i . subsets of the universal set U be found using bit strings?
i=1 i=1 The successor of the set A is the set A ∪{A}.
48. Let A i ={..., −2, −1, 0, 1,...,i}. Find
n n 59. Find the successors of the following sets.

a) A i . b) A i . a) {1, 2, 3} b) ∅
i=1 i=1 c) {∅} d) {∅, {∅}}