Page 651 - Discrete Mathematics and Its Applications

630 9 / Relations

Exercises

1. Which of these relations on {0, 1, 2, 3} are partial order- 8. Determine whether the relations represented by these
ings? Determine the properties of a partial ordering that zero–one matrices are partial orders.
the others lack. ⎡ 1 0 1 ⎤ ⎡ 1 0 0 ⎤
a) {(0, 0), (1, 1), (2, 2), (3, 3)} a) ⎣ 1 1 0 ⎦ b) ⎣ 0 1 0 ⎦
0 0 1 1 0 1
b) {(0, 0), (1, 1), (2, 0), (2, 2), (2, 3), (3, 2), (3, 3)}
⎡ ⎤
1 0 1 0
c) {(0, 0), (1, 1), (1, 2), (2, 2), (3, 3)}
⎢ 0 1 1 0 ⎥
c) ⎢ ⎥
d) {(0, 0), (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)} ⎣ 0 0 1 1 ⎦
1 1 0 1
e) {(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0),
(2, 2), (3, 3)} In Exercises 9–11 determine whether the relation with the
2. Which of these relations on {0, 1, 2, 3} are partial order- directed graph shown is a partial order.
ings? Determine the properties of a partial ordering that 9. 10.
the others lack. a b a b
a) {(0, 0), (2, 2), (3, 3)}
b) {(0, 0), (1, 1), (2, 0), (2, 2), (2, 3), (3, 3)}
c) {(0, 0), (1, 1), (1, 2), (2, 2), (3, 1), (3, 3)}
c d
d) {(0, 0), (1, 1), (1, 2), (1, 3), (2, 0), (2, 2), (2, 3), c d
(3, 0), (3, 3)} 11.
a b
e) {(0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1), (1, 2),
c d
(1, 3), (2, 0), (2, 2), (3, 3)}
12. Let (S, R) be a poset. Show that (S, R −1 ) is also a poset,
3. Is (S, R) a poset if S is the set of all people in the world where R −1 is the inverse of R. The poset (S, R −1 )is
and (a, b) ∈ R, where a and b are people, if
called the dual of (S, R).
a) a is taller than b?
13. Find the duals of these posets.
b) a is not taller than b?
a) ({0, 1, 2}, ≤) b) (Z, ≥)
c) a = b or a is an ancestor of b? c) (P(Z), ⊇) d) (Z , |)
+
d) a and b have a common friend? 14. Which of these pairs of elements are comparable in the
+
poset (Z , |)?
4. Is (S, R) a poset if S is the set of all people in the world
and (a, b) ∈ R, where a and b are people, if a) 5, 15 b) 6, 9 c) 8, 16 d) 7, 7
a) a is no shorter than b? 15. Find two incomparable elements in these posets.
a) (P({0, 1, 2}), ⊆) b) ({1, 2, 4, 6, 8}, |)
b) a weighs more than b?
16. Let S ={1, 2, 3, 4}. With respect to the lexicographic or-
c) a = b or a is a descendant of b? der based on the usual “less than” relation,
d) a and b do not have a common friend? a) find all pairs in S × S less than (2, 3).
5. Which of these are posets? b) find all pairs in S × S greater than (3, 1).
a) (Z, =) b) (Z, =) c) (Z, ≥) d) (Z, | ) c) draw the Hasse diagram of the poset (S × S, ).
6. Which of these are posets? 17. Find the lexicographic ordering of these n-tuples:
a) (R, =) b) (R,<) c) (R, ≤) d) (R, =) a) (1, 1, 2), (1, 2, 1) b) (0, 1, 2, 3), (0, 1, 3, 2)
7. Determine whether the relations represented by these c) (1, 0, 1, 0, 1), (0, 1, 1, 1, 0)
zero–one matrices are partial orders. 18. Find the lexicographic ordering of these strings of lower-
case English letters:
⎡ ⎤ ⎡ ⎤
1 1 1 1 1 1 a) quack, quick, quicksilver, quicksand, quacking
a) ⎣ 1 1 0 ⎦ b) ⎣ 0 1 0 ⎦ b) open, opener, opera, operand, opened
0 0 1 0 0 1
c) zoo, zero, zoom, zoology, zoological
19. Find the lexicographic ordering of the bit strings 0, 01,
⎡ ⎤
1 1 1 0 11, 001, 010, 011, 0001, and 0101 based on the ordering
⎢ 0 1 1 0 ⎥ 0 < 1.
c) ⎢ ⎥
0 0 1 1
⎣ ⎦
20. Draw the Hasse diagram for the “greater than or equal to”
1 1 0 1
relation on {0, 1, 2, 3, 4, 5}.