Discrete Mathematics
Unit 2
Question bank
1. Represent each of these relations on {1, 2, 3} with a matrix
a) {(1, 1), (1, 2), (1, 3)}
b) {(1, 3), (3, 1)}
2. List the ordered pairs in the relations on {1, 2, 3} corresponding to these matrices (where the
rows and columns correspond to the integers listed in increasing order).
a)
101
010
101
b)
010
010
010
3. R1 = {(1, 2), (1, 3), (2, 1), (2, 3),), (3, 1), (3, 2)}, R2 = {(1, 1), (1, 2), (1, 3)} On Set A = {1, 2,
3} Represent in matrix form and find
a) R1 ∪ R2. b) R1 ∩ R2.
4. Draw the directed graphs representing each of the relations from Exercise 1
5. Let R be the relation on the set {0, 1, 2, 3} containing the ordered pairs (0, 1), (1, 1), (1, 2), (2,
0), (2, 2), and (3, 0). Find the
a) reflexive closure of R. b) symmetric closure of R
6. Use Warshall’s algorithm to find the transitive closures of these relations on {1, 2, 3, 4}.
b) a) {(1, 2), (2,1), (2,3), (3,4)}
c) b) {(2, 1), (2,3), (3,1), (3,4), (4,1), (4, 3)}
7. Which of these relations on {0, 1, 2, 3} are equivalence relations? Determine the properties of
an equivalence relation that the others lack.
a) {(0, 0), (1, 1), (2, 2), (3, 3)}
b) {(0, 0), (0, 2), (2, 0), (2, 2), (2, 3), (3, 2), (3, 3)}
c) {(0, 0), (1, 1), (1, 2), (2, 1), (2, 2), (3, 3)}
d) {(0, 0), (1, 1), (1, 3), (2, 2), (2, 3), (3, 1), (3, 2),(3, 3)}
8. Which of these relations on the set of all people are equivalence relations? Determine the
properties of an equivalence relation that the others lack.
a) {(a, b) | a and b are the same age}
b) {(a, b) | a and b have the same parents}
c) {(a, b) | a and b share a common parent}
d) {(a, b) | a and b have met}
e) {(a, b) | a and b speak a common language}
9. Let R be the relation on the set of people such that xRy if x and y are people and x is older
than y. Show that R is not a partial ordering.
10. Which of these relations on {0, 1, 2, 3} are partial orderings? Determine the properties of a
partial ordering that the others lack.
11. Which of these are posets?
a) (Z,=) b) (Z, <=)
12. Draw the Hasse diagram for divisibility on the set {1, 3, 9, 27, 81, 243}.
