Page 652 - Discrete Mathematics and Its Applications

9.6 Partial Orderings 631

21. Draw the Hasse diagram for the “less than or equal to” d) Is there a least element?
relation on {0, 2, 5, 10, 11, 15}.
e) Find all upper bounds of {a, b, c}.
22. Draw the Hasse diagram for divisibility on the set f) Find the least upper bound of {a, b, c}, if it exists.
a) {1, 2, 3, 4, 5, 6}. b) {3, 5, 7, 11, 13, 16, 17}.
g) Find all lower bounds of {f, g, h}.
c) {2, 3, 5, 10, 11, 15, 25}. d) {1, 3, 9, 27, 81, 243}.
h) Find the greatest lower bound of {f, g, h}, if it exists.
23. Draw the Hasse diagram for divisibility on the set
33. Answer these questions for the poset ({3, 5, 9, 15,
a) {1, 2, 3, 4, 5, 6, 7, 8}. b) {1, 2, 3, 5, 7, 11, 13}.
24, 45}, |).
c) {1, 2, 3, 6, 12, 24, 36, 48}. a) Find the maximal elements.
d) {1, 2, 4, 8, 16, 32, 64}.
b) Find the minimal elements.
24. Draw the Hasse diagram for inclusion on the set P(S),
where S ={a, b, c, d}. c) Is there a greatest element?
In Exercises 25–27 list all ordered pairs in the partial ordering d) Is there a least element?
with the accompanying Hasse diagram. e) Find all upper bounds of {3, 5}.
25. 26. f) Find the least upper bound of {3, 5}, if it exists.
c d e d
g) Find all lower bounds of {15, 45}.
b h) Find the greatest lower bound of {15, 45}, if it exists.
b c 34. Answer these questions for the poset ({2, 4, 6, 9, 12,
18, 27, 36, 48, 60, 72}, |).
a
a a) Find the maximal elements.
27. b) Find the minimal elements.
d e f
c) Is there a greatest element?
g d) Is there a least element?
e) Find all upper bounds of {2, 9}.
b a c f) Find the least upper bound of {2, 9}, if it exists.
g) Find all lower bounds of {60, 72}.
28. What is the covering relation of the partial ordering
{(a, b) | a divides b} on {1, 2, 3, 4, 6, 12}? h) Find the greatest lower bound of {60, 72}, if it exists.
29. What is the covering relation of the partial order- 35. Answer these questions for the poset ({{1}, {2}, {4},
ing {(A, B) | A ⊆ B} on the power set of S, where {1, 2}, {1, 4}, {2, 4}, {3, 4}, {1, 3, 4}, {2, 3, 4}}, ⊆).
S ={a, b, c}? a) Find the maximal elements.
30. What is the covering relation of the partial ordering for b) Find the minimal elements.
the poset of security classes defined in Example 25? c) Is there a greatest element?
31. Show that a finite poset can be reconstructed from its cov- d) Is there a least element?
ering relation. [Hint: Show that the poset is the reflexive e) Find all upper bounds of {{2}, {4}}.
transitive closure of its covering relation.]
f) Find the least upper bound of {{2}, {4}}, if it exists.
32. Answer these questions for the partial order represented
g) Find all lower bounds of {{1, 3, 4}, {2, 3, 4}}.
by this Hasse diagram.
h) Find the greatest lower bound of {{1, 3, 4}, {2, 3, 4}},
l m if it exists.
36. Give a poset that has
j k a) a minimal element but no maximal element.
b) a maximal element but no minimal element.
i h g
c) neither a maximal nor a minimal element.
37. Show that lexicographic order is a partial ordering on the
d e f Cartesian product of two posets.

38. Show that lexicographic order is a partial ordering on the
a b c set of strings from a poset.
a) Find the maximal elements.
39. Suppose that (S, 1 ) and (T, 2 ) are posets. Show that
b) Find the minimal elements. (S × T, ) is a poset where (s, t) (u, v) if and only if
c) Is there a greatest element? s 1 u and t 2 v.