Page 637 - Discrete Mathematics and Its Applications

616 9 / Relations

In Exercises 21–23 determine whether the relation with the 35. What is the congruence class [n] 5 (that is, the equiva-
directed graph shown is an equivalence relation. lence class of n with respect to congruence modulo 5)
21. 22. when n is
a) 2? b) 3? c) 6? d) −3?
a b a b
36. What is the congruence class [4] m when m is
a) 2? b) 3? c) 6? d) 8?
37. Give a description of each of the congruence classes
modulo 6.
c d d c
38. What is the equivalence class of each of these strings with
23. respect to the equivalence relation in Exercise 14?
a b a) No b) Yes c) Help
39. a) What is the equivalence class of (1, 2) with respect to
the equivalence relation in Exercise 15?
b) Give an interpretation of the equivalence classes for
the equivalence relation R in Exercise 15. [Hint: Look
at the difference a − b corresponding to (a, b).]
d c
40. a) What is the equivalence class of (1, 2) with respect
24. Determine whether the relations represented by these to the equivalence relation in Exercise 16?
zero–one matrices are equivalence relations.
b) Give an interpretation of the equivalence classes for
⎡ ⎤ ⎡ ⎤
⎡ ⎤ 10 10 1110 the equivalence relation R in Exercise 16. [Hint: Look
111
⎢ 01 01 ⎥ ⎢ 1110 ⎥ at the ratio a/b corresponding to (a, b).]
b) ⎢ ⎥ c) ⎢ ⎥
a) ⎣ 01 1 ⎦
⎣ 10 10 ⎦ ⎣ 1110 ⎦
111 41. Which of these collections of subsets are partitions of
01 01 0001 {1, 2, 3, 4, 5, 6}?
25. Show that the relation R on the set of all bit strings such
a) {1, 2}, {2, 3, 4}, {4, 5, 6} b) {1}, {2, 3, 6}, {4}, {5}
that sR t if and only if s and t contain the same number
c) {2, 4, 6}, {1, 3, 5} d) {1, 4, 5}, {2, 6}
of 1s is an equivalence relation.
42. Which of these collections of subsets are partitions of
26. What are the equivalence classes of the equivalence rela- {−3, −2, −1, 0, 1, 2, 3}?
tions in Exercise 1?
a) {−3, −1, 1, 3}, {−2, 0, 2}
27. What are the equivalence classes of the equivalence rela- b) {−3, −2, −1, 0}, {0, 1, 2, 3}
tions in Exercise 2? c) {−3, 3}, {−2, 2}, {−1, 1}, {0}
28. What are the equivalence classes of the equivalence rela- d) {−3, −2, 2, 3}, {−1, 1}
tions in Exercise 3? 43. Which of these collections of subsets are partitions of the
29. What is the equivalence class of the bit string 011 for the set of bit strings of length 8?
equivalence relation in Exercise 25? a) the set of bit strings that begin with 1, the set of bit
30. What are the equivalence classes of these bit strings for strings that begin with 00, and the set of bit strings
the equivalence relation in Exercise 11? that begin with 01
b) the set of bit strings that contain the string 00, the set
a) 010 b) 1011 c) 11111 d) 01010101
of bit strings that contain the string 01, the set of bit
31. What are the equivalence classes of the bit strings strings that contain the string 10, and the set of bit
in Exercise 30 for the equivalence relation from strings that contain the string 11
Exercise 12?
c) the set of bit strings that end with 00, the set of bit
32. What are the equivalence classes of the bit strings strings that end with 01, the set of bit strings that end
in Exercise 30 for the equivalence relation from with 10, and the set of bit strings that end with 11
Exercise 13? d) the set of bit strings that end with 111, the set of bit
33. What are the equivalence classes of the bit strings in Ex- strings that end with 011, and the set of bit strings that
ercise 30 for the equivalence relation R 4 from Exam- end with 00
ple 5 on the set of all bit strings? (Recall that bit strings s e) the set of bit strings that contain 3k ones for some
and t are equivalent under R 4 if and only if they are equal nonnegative integer k; the set of bit strings that con-
or they are both at least four bits long and agree in their tain 3k + 1 ones for some nonnegative integer k; and
first four bits.) the set of bit strings that contain 3k + 2 ones for some
nonnegative integer k.
34. What are the equivalence classes of the bit strings in Ex-
ercise 30 for the equivalence relation R 5 from Example 5 44. Which of these collections of subsets are partitions of the
on the set of all bit strings? (Recall that bit strings s and set of integers?
t are equivalent under R 5 if and only if they are equal or a) the set of even integers and the set of odd integers
they are both at least five bits long and agree in their first b) the set of positive integers and the set of negative in-
five bits.) tegers