Page 658 - Discrete Mathematics and Its Applications

Supplementary Exercises 637

27. Schedule the tasks needed to cook a Chinese meal by ∗ 35. Show that the principle of well-founded induction is valid.
specifying their order, if the Hasse diagram representing
these tasks is as shown here. A relation R on a set A is a quasi-ordering on A if R is
Serve reflexive and transitive.
36. Let R be the relation on the set of all functions from
Z to Z such that (f, g) belongs to R if and only if f
+
+
is O(g). Show that R is a quasi-ordering.
Arrange on platters
37. Let R be a quasi-ordering on a set A. Show that R ∩ R −1
is an equivalence relation.
∗ 38. Let R be a quasi-ordering and let S be the relation on the
Cook in wok −1
set of equivalence classes of R ∩ R such that (C, D)
belongs to S, where C and D are equivalence classes
of R, if and only if there are elements c of C and d of
Steam Make
rice garnishes D such that (c, d) belongs to R. Show that S is a partial
Chop ordering.
water Cut
chestnuts Let L be a lattice. Define the meet (∧) and join (∨) operations
fish
Wash Wash by x ∧ y = glb(x, y) and x ∨ y = lub(x, y).
vegetables
shellfish 39. Show that the following properties hold for all elements
Cut ginger Clean x, y, and z of a lattice L.
and garlic fish
Buy groceries a) x ∧ y = y ∧ x and x ∨ y = y ∨ x (commutative
laws)
Buy seafood
b) (x ∧ y) ∧ z = x ∧ (y ∧ z) and (x ∨ y) ∨ z = x ∨
Find recipe (y ∨ z) (associative laws)
A subset of a poset such that every two elements of this sub- c) x ∧ (x ∨ y) = x and x ∨ (x ∧ y) = x (absorption
set are comparable is called a chain. A subset of a poset is laws)
called an antichain if every two elements of this subset are d) x ∧ x = x and x ∨ x = x (idempotent laws)
incomparable. 40. Show that if x and y are elements of a lattice L, then
x ∨ y = y if and only if x ∧ y = x.
28. Find all chains in the posets with the Hasse diagrams
shown in Exercises 25–27 in Section 9.6. A lattice L is bounded if it has both an upper bound, de-
noted by 1, such that x 1 for all x ∈ L and a lower bound,
29. Find all antichains in the posets with the Hasse diagrams denoted by 0, such that 0 x for all x ∈ L.
shown in Exercises 25–27 in Section 9.6.
41. Show that if L is a bounded lattice with upper bound
30. Find an antichain with the greatest number of elements 1 and lower bound 0 then these properties hold for all
in the poset with the Hasse diagram of Exercise 32 in elements x ∈ L.
Section 9.6.
a) x ∨ 1 = 1 b) x ∧ 1 = x
31. Show that every maximal chain in a finite poset (S, ) c) x ∨ 0 = x d) x ∧ 0 = 0
contains a minimal element of S. (A maximal chain is a 42. Show that every finite lattice is bounded.
chain that is not a subset of a larger chain.)
A lattice is called distributive if x ∨ (y ∧ z) = (x ∨ y) ∧
∗∗ 32. Show that every finite poset can be partitioned into k (x ∨ z) and x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z) for all x, y, and
chains, where k is the largest number of elements in an z in L.
antichain in this poset.
∗ 43. Give an example of a lattice that is not distributive.
∗ 33. Show that in any group of mn + 1 people there is either a 44. Show that the lattice (P(S), ⊆) where P(S) is the power
list of m + 1 people where a person in the list (except for set of a finite set S is distributive.
the first person listed) is a descendant of the previous per- +
son on the list, or there are n + 1 people such that none of 45. Is the lattice (Z , |) distributive?
these people is a descendant of any of the other n people. The complement of an element a of a bounded lattice L with
[Hint: Use Exercise 32.] upper bound 1 and lower bound 0 is an element b such that
Suppose that (S, ) is a well-founded partially ordered set. a ∨ b = 1 and a ∧ b = 0. Such a lattice is complemented if
The principle of well-founded induction states that P(x) is every element of the lattice has a complement.
true for all x ∈ S if ∀x(∀y(y ≺ x → P(y)) → P(x)). 46. Give an example of a finite lattice where at least one el-
ement has more than one complement and at least one
34. Show that no separate basis case is needed for the prin-
ciple of well-founded induction. That is, P(u) is true for element has no complement.
all minimal elements u in S if ∀x(∀y(y ≺ x → P(y)) → 47. Show that the lattice (P(S), ⊆) where P(S) is the power
P(x)). set of a finite set S is complemented.