Solved: Let S = {0, 1} and consider the partial order

Problem 51E Suppose the tasks described in Example 8.5.12 require the following performance times: Task Time Needed to Perform Task 1 9 hours 2 7 hours 3 4 hours 4 5 hours 5 7 hours 6 3 hours 7 2 hours 8 4 hours 9 6 hours a. What is the minimum time required to assemble a car? b. Find a critical path for the assembly process.

Problem 1E Each of the following is a relation on {0, 1, 2, 3}. Draw directed graphs for each relation, and indicate which relations are antisymmetric. a. R1 = {(0, 0), (0, 2), (1, 0), (1, 3), (2, 2), (3, 0), (3, 1)} b. R2 = {(0, 1), (0, 2), (1, 1), (1, 2), (1, 3), (2, 2), (3, 2)} c. R3 = {(0, 0), (0, 3), (1, 0), (1, 3), (2, 2), (3, 3), (3, 2)} d. R4 = {(0, 0), (1, 0), (1, 2), (1, 3), (2, 0), (2, 1), (3, 2), (3, 0)}

Problem 3E Let S be the set of all strings of a’s and b’s. Define a relation R on S as follows: For all t ? S, s R t ? l(s) ? l(t), where l(x) denotes the length of a string x. Is R antisymmetric? Prove or give a counterexample.

Problem 4E Let R be the “less than” relation on the set R of all real numbers: For all x, y ? R, x R y ? x < y. Is R antisymmetric? Prove or give a counterexample.

Problem 5E Let R be the set of all real numbers and define a relation R on R × R as follows: For all (a, b) and (c, d) in R × R, ( a , b ) R ( c , d ) ? either a < c or both a = c and b ? d. Is R a partial order relation? Prove or give a counterexample.

Problem 7E Define a relation R on the set Z of all integers as follows: For all m, n ? Z, m R n ? every prime factor of m is a prime factor of n. Is R a partial order relation? Prove or give a counterexample.

Problem 6E Let P be the set of all people who have ever lived and define a relation R on P as follows: For all r, s ? P, r R s ? r is an ancestor of s or r = s. Is R a partial order relation? Prove or give a counterexample.

Problem 8E Define a relation R on the set Z of all integers as follows: For all m, n ? Z, m R n ? m + n is even. Is R a partial order relation? Prove or give a counterexample.

Problem 9E Define a relation R on the set of all real numbers R as follows: For all x, y ? R, x R y ? x2 ? y2. Is R a partial order relation? Prove or give a counterexample.

Problem 10E Suppose R and S are antisymmetric relations on a set A. Must R ? S also be antisymmetric? Explain.

Problem 11E Let A = {a, b}, and suppose A has the partial order relation R where R = {(a, a), (a, b), (b, b)}. Let S be the set of all strings in a’s and b’s and let be the corresponding lexicographic order on S. Indicate which of the following statements are true, and for each true statement cite as a reason part (1), (2), or (3) of the definition of lexicographic order given in Theorem 8.5.1.

Problem 12E Prove Theorem 8.5.1 Reference:

Problem 2E Let P be the set of all people in the world and define a relation R on P as follows: For all x, y ? P, x R y ? x is no older than y. Is R antisymmetric? Prove or give a counterexample.

Problem 13E Let A = {a, b}. Describe all partial order relations on A.

Problem 14E Let A = {a, b, c}. a. Describe all partial order relations on A for which a is a maximal element. b. Describe all partial order relations on A for which a is a minimal element.

Problem 15E Suppose a relation R on a set A is reflexive, symmetric, transitive, and antisymmetric. What can you conclude about R? Prove your answer.

Problem 16E Consider the “divides” relation on each of the following sets A. Draw the Hasse diagram for each relation. a. A = {1, 2, 4, 5, 10, 15, 20} b. A = {2, 3, 4, 6, 8, 9, 12, 18}

Problem 17E Consider the “subset” relation onP(S) for each of the following sets S. Draw the Hasse diagram for each relation. a. S = {0, 1} b. S = {0, 1, 2}

Problem 19E Let S = {0, 1} and consider the partial order relation R defined on S × S as follows: For all ordered pairs (a, b) and (c, d) in S × S, ( a , b ) R ( c , d ) ? a ? c and b ? d, where ? denotes the usual “less than or equal to” relation for real numbers. Draw the Hasse diagram for R.

Problem 20E Let S = {0, 1} and consider the partial order relation R defined on S × S × S as follows: For all ordered triples ( a , b , c ) and (d, e, f ) in S × S × S, ( a , b , c ) R ( d , e , f ) ? a ? d, b ? e, and c ? f, where ? denotes the usual “less than or equal to” relation for real numbers. Draw the Hasse diagram for R.

Problem 18E Let S = {0, 1} and consider the partial order relation R defined on S × S as follows: For all ordered pairs (a, b) and (c, d) in S × S, ( a , b ) R ( c , d ) ? either a < c or both a = c and b ? d, where < denotes the usual “less than” and ? denotes the usual “less than or equal to” relation for real numbers. Draw the Hasse diagram for R.

Problem 21E Consider the “divides” relation defined on the set A={1, 2, 22, 23, . . . , 2n}, where n is a nonnegative integer. a. Prove that this relation is a total order relation on A. b. Draw the Hasse diagram for this relation for n = 4.

Problem 22E In 22–29, find all greatest, least, maximal, and minimal elements for the relations in each of the referenced exercises. Exercise 16(a) Reference: Consider the “divides” relation on each of the following sets A. Draw the Hasse diagram for each relation. a. A = {1, 2, 4, 5, 10, 15, 20}

Problem 23E In 22–29, find all greatest, least, maximal, and minimal elements for the relations in each of the referenced exercises. Exercise 16(b) Reference: Consider the “divides” relation on each of the following sets A. Draw the Hasse diagram for each relation. b. A = {2, 3, 4, 6, 8, 9, 12, 18}

Problem 24E In 22–29, find all greatest, least, maximal, and minimal elements for the relations in each of the referenced exercises. Exercise 17(a) Reference: Consider the “subset” relation onP(S) for each of the following sets S. Draw the Hasse diagram for each relation. a. S = {0, 1}

Problem 25E In 22–29, find all greatest, least, maximal, and minimal elements for the relations in each of the referenced exercises. Exercise 17(b) Reference: Consider the “subset” relation onP(S) for each of the following sets S. Draw the Hasse diagram for each relation. b. S = {0, 1, 2}

Problem 26E In 22–29, find all greatest, least, maximal, and minimal elements for the relations in each of the referenced exercises. Exercise 18 Reference: Let S = {0, 1} and consider the partial order relation R defined on S × S as follows: For all ordered pairs (a, b) and (c, d) in S × S, ( a , b ) R ( c , d ) ? either a < c or both a = c and b ? d, where < denotes the usual “less than” and ? denotes the usual “less than or equal to” relation for real numbers. Draw the Hasse diagram for R.

Problem 27E In 22–29, find all greatest, least, maximal, and minimal elements for the relations in each of the referenced exercises. Exercise 19 Reference: Let S = {0, 1} and consider the partial order relation R defined on S × S as follows: For all ordered pairs (a, b) and (c, d) in S × S, ( a , b ) R ( c , d ) ? a ? c and b ? d, where ? denotes the usual “less than or equal to” relation for real numbers. Draw the Hasse diagram for R.

Problem 29E In 22–29, find all greatest, least, maximal, and minimal elements for the relations in each of the referenced exercises. Exercise 21 Reference: Consider the “divides” relation defined on the set A={1, 2, 22, 23, . . . , 2n}, where n is a nonnegative integer. a. Prove that this relation is a total order relation on A. b. Draw the Hasse diagram for this relation for n = 4.

Problem 28E In 22–29, find all greatest, least, maximal, and minimal elements for the relations in each of the referenced exercises. Exercise 20 Reference: Let S = {0, 1} and consider the partial order relation R defined on S × S × S as follows: For all ordered triples (a, b, c) and (d, e, f ) in S × S × S, ( a , b , c ) R ( d , e , f ) ? a ? d, b ? e, and c ? f, where ? denotes the usual “less than or equal to” relation for real numbers. Draw the Hasse diagram for R.

Problem 30E Each of the following sets is partially ordered with respect to the “less than or equal to” relation, ?, for real numbers. In each case, determine whether the set has a greatest or least element. a. R b. {x ? R| 0 ? x ? 1} c. {x ? R| 0 < x < 1} d. {x ? Z| 0 < x < 10}

Problem 31E Let A = {a, b, c, d}, and let R be the relation R = {(a, a), (b, b), (c, c), (d, d), (c, a), (a, d), (c, d), (b, c), (b, d), (b, a)}. Is R a total order on A? Justify your answer.

Problem 32E Let A = {a, b, c, d}, and let R be the relation R = {(a, a), (b, b), (c, c), (d, d), (c, b), (a, d), (b, a), (b, d), (c, d), (c, a)}. Is R a total order on A? Justify your answer.

Problem 33E Consider the set A = {12, 24, 48, 3, 9} ordered by the “divides” relation. Is A totally ordered with respect to the relation? Justify your answer.

Problem 34E Suppose that R is a partial order relation on a set A and that B is a subset of A. The restriction of R to B is defined as follows: The restriction of R to B = {(x, y) | x ? B, y ? B, and (x, y) ? R}. In other words, two elements of B are related by the restriction of R to B if, and only if, they are related by R. Prove that the restriction of R to B is a partial order relation on B. (In less formal language, this says that a subset of a partially ordered set is partially ordered.)

Problem 35E The set P({w, x, y, z}) is partially ordered with respect to the “subset” relation ?. Find a chain of length 4 in P({w, x, y, z}).

Problem 36E The set A = {2, 4, 3, 6, 12, 18, 24} is partially ordered with respect to the “divides” relation. Find a chain of length 3 in A.

Problem 37E Find a chain of length 2 for the relation defined in exercise 19. Reference: Let S = {0, 1} and consider the partial order relation R defined on S × S as follows: For all ordered pairs (a, b) and (c, d) in S × S, ( a , b ) R ( c , d ) ? a ? c and b ? d, where ? denotes the usual “less than or equal to” relation for real numbers. Draw the Hasse diagram for R.

Problem 38E Prove that a partially ordered set is totally ordered if, and only if, it is a chain.

Problem 39E Suppose that A is a totally ordered set. Use mathematical induction to prove that for any integer n ? 1, every subset of A with n elements has both a least element and a greatest element.

Problem 40E Prove that a nonempty finite partially ordered set has a. at least one minimal element, b. at least one maximal element.

Problem 41E Prove that a finite partially ordered set has a. at most one greatest element, b. at most one least element.

Problem 42E Draw a Hasse diagram for a partially ordered set that has two maximal elements and two minimal elements and is such that each element is comparable to exactly two other elements.

Problem 43E Draw a Hasse diagram for a partially ordered set that has three maximal elements and three minimal elements and is such that each element is either greater than or less than exactly two other elements.

Problem 44E Use the algorithm given in the text to find a topological sorting for the relation of exercise 16(a) that is different from the “less than or equal to” relation ?. Reference: Consider the “subset” relation onP(S) for each of the following sets S. Draw the Hasse diagram for each relation. a. S = {0, 1}

Problem 45E Use the algorithm given in the text to find a topological sorting for the relation of exercise 16(b) that is different from the “less than or equal to” relation ?. Reference: Consider the “subset” relation onP(S) for each of the following sets S. Draw the Hasse diagram for each relation. b. S = {0, 1, 2}

Problem 46E Use the algorithm given in the text to find a topological sorting for the relation of exercise 19. Reference: Let S = {0, 1} and consider the partial order relation R defined on S × S as follows: For all ordered pairs (a, b) and (c, d) in S × S, ( a , b ) R ( c , d ) ? a ? c and b ? d, where ? denotes the usual “less than or equal to” relation for real numbers. Draw the Hasse diagram for R.

Problem 47E Use the algorithm given in the text to find a topological sorting for the relation of exercise 20. Reference: Let S = {0, 1} and consider the partial order relation R defined on S × S × S as follows: For all ordered triples ( a , b , c ) and (d, e, f ) in S × S × S, ( a , b , c ) R ( d , e , f ) ? a ? d, b ? e, and c ? f, where ? denotes the usual “less than or equal to” relation for real numbers. Draw the Hasse diagram for R.

Problem 48E Use the algorithm given in the text to find a topological sorting for the “subset” relation onP({a, b, c, d}).

Problem 50E A set S of jobs can be ordered by writing x y to mean that either x = y or x must be done before y, for all x and y in S. The following is a Hasse diagram for this relation for a particular set S of jobs. a. If one person is to perform all the jobs, one after another, find an order in which the jobs can be done. b. Suppose enough people are available to perform any number of jobs simultaneously. (i) If each job requires one day to perform, what is the least number of days needed to perform all ten jobs? (ii) What is the maximum number of jobs that can be performed at the same time?

Problem 49E Refer to the prerequisite structure shown in Figure 8.5.1. a. Find a list of six noncomparable courses that is different from the list given in the text. b. Find two topological sortings that are different from the one given in the text. Reference: