Show that the set 5 of security classes (A, C) is a

Problem 1E Which of these relations on (0, 1, 2, 3} are partial orderings? Determine the properties of a partial ordering that the others lack. a) {(0,0), (1, 1), (2, 2), (3, 3)} ________________ b) {(0, 0), (1, 1), (2, 0), (2, 2), (2, 3), (3, 2), (3, 3)} ________________ c) {(0,0), (1, 1), (1,2), (2, 2), (3, 3)} ________________ d) {(0,0), (1, 1), (1,2), (1.3), (2, 2), (2, 3), (3, 3)} ________________ e) {(0,0), (0, 1), (0, 2), (1,0), (1, 1), (1,2), (2,0), (2, 2), (3, 3)}

Problem 2E Which of these relations on {0, 1, 2, 3} are partial orderings? Determine the properties of a partial ordering that the others lack. 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)} ________________ d) {(0, 0), (1, 1), (1, 2), (1, 3), (2, 0), (2, 2), (2,3), (3,0), (3, 3)} ________________ e) {(0,0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1 ), (1,2), (1,3), (2,0), (2, 2), (3, 3)}

Problem 3E 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) a is taller than b? b) a is not taller than b? c) a = b or a is an ancestor of b? d) a and b have a common friend?

Problem 4E 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) a is no shorter than b? b) a weighs more than b? c) a = b or a is a descendant of b? d) a and b do not have a common friend?

Problem 5E Which of these are posets? a) (Z, =) ________________ b) (Z, ?) ________________ c) (Z, ?) ________________ d) (Z, ?)

Problem 6E Which of these are posets? a) (R, =) ________________ b) (R, <) ________________ c) (R, ?) ________________ d) (R, ?)

Determine whether the relations represented by these zero–one matrices are partial orders. a) \(\left[\begin{array}{lll} 1 & 1 & 1 \\ 1 & 1 & 0 \\ 0 & 0 & 1 \end{array}\right]\) b) \(\left[\begin{array}{lll} 1 & 1 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array}\right]\) c) \(\left[\begin{array}{llll} 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \end{array}\right]\) Equation Transcription: [ ] [ ] [] Text Transcription: [ _0 0 1 ^1 1 0 ^^1 1 1 ] [ _0 0 1 ^0 1 0 ^^1 1 1 ] [ _1 1 0 1 ^0 0 1 1 ^^0 1 1 0 ^^^1 1 1 0 ]

In Exercises 9–11 determine whether the relation with the directed graph shown is a partial order.

Determine whether the relations represented by these zero–one matrices are partial orders. a) \(\left[\begin{array}{lll} 1 & 0 & 1 \\ 1 & 1 & 0 \\ 0 & 0 & 1 \end{array}\right]\) b) \(\left[\begin{array}{lll} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 1 \end{array}\right]\) c) \(\left[\begin{array}{llll} 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \end{array}\right]\) Equation Transcription: [ ] [ ] [] Text Transcription: [ _0 0 1 ^1 1 0 ^^1 0 1 ] [ _1 0 1 ^0 1 0 ^^1 0 0 ] [ _1 1 0 1 ^0 0 1 1 ^^0 1 1 0 ^^^1 0 1 0 ]

Problem 10E In Exercises 10 determine whether the relation with the directed graph shown is a partial order.

Problem 11E In Exercises 11 determine whether the relation with the directed graph shown is a partial order. .

Problem 12E Let (S, R) be a poset. Show that (S, R?1) is also a poset. where R?1 is the inverse of R. The poset (S, R?1) is called the dual of (S, R).

Problem 13E Find the duals of these posets. a) ({0,1,2}, ?) b) (Z, ?) ________________ c) (P(Z),?) d) (Z , |)

Problem 15E Find two incomparable elements in these posets. a) (P({0, 1, 2}), ?) ________________ b) ({1,2,4, 6, 8}, |)

Problem 14E Which of these pairs of elements are comparable in the poset (Z+, |)? a) 5, 15 ________________ b) 6,9 ________________ c) 8, 16 ________________ d) 7, 7

Problem 16E Let S = {1, 2, 3, 4), With respect to the lexicographic order based on the usual “less than” relation. a) find all pairs in S × S less than (2, 3). b) find all pairs in S × S greater than (3, 1). c) draw the Hasse diagram of the poset (S × S, ? ).

Problem 20E Draw the Hasse diagram for the “greater than or equal to” relation on {0, 1, 2, 3, 4, 5}.

Problem 21E Draw the Hasse diagram for the “less than or equal to” relation on (0,2,5, 10, 11,15}.

Problem 17E Find the lexicographic ordering of these n-tuples: a) (1, 1,2), (1,2, 1) ________________ b) (0, 1,2,3), (0, 1, 3,2) ________________ c) (1,0, 1,0, 1), (0, 1, 1, 1,0)

Problem 19E Find the lexicographic ordering of the bit strings 0, 01, 11, 001, 010,011,0001, and 0101 based on the ordering 0<1.

Problem 18E Find the lexicographic ordering of these strings of lowercase English letters: a) quack, quick, quicksilver, quicksand, quacking b) open, opener, opera, operand, opened c) zoo, zero, zoom, zoology, zoological

Problem 22E Draw the Hasse diagram for divisibility on the set a) {1,2,3,4,5,6}. ________________ b) {3, 5, 7, 11, 13, 16, 17}. ________________ c) {2,3,5,10,11,15,25}. ________________ d) {1,3,9,27,81,243}.

Problem 23E Draw the Hasse diagram for divisibility on the set a) {1,2,3,4,5,6,7,8}. ________________ b) {1, 2, 3, 5, 7, 11, 13}. ________________ c) {1,2,3,6,12,24,36,48}. ________________ d) {1,2,4,8, 16,32,64}.

Problem 24E Draw the Hasse diagram for inclusion on the set P(S), where S = {a, b, c, d}. In Exercises 25-27 list all ordered pairs in the partial ordering with the accompanying Hasse diagram.

Problem 25E In Exercises 25 list all ordered pairs in the partial ordering with the accompanying Hasse diagram.

Problem 26E In Exercises 26 list all ordered pairs in the partial ordering with the accompanying Hasse diagram.

Problem 28E What is the covering relation of the partial ordering {(a,b) | a divides b} on {1,2, 3,4, 6, 12}?

Problem 29E What is the covering relation of the partial ordering {(A, B) | A ? B} on the power set of S, where S = {a,b,c)?

In Exercises 25–27 list all ordered pairs in the partial ordering with the accompanying Hasse diagram.

Problem 30E What is the covering relation of the partial ordering for the poset of security classes defined in Example 25?

Problem 33E Answer these questions for the poset ({3,5,9,15, 24,45}, |). a) Find the maximal elements. b) Find the minimal elements. c) Is there a greatest element? d) Is there a least element? e) Find all upper bounds of {3, 5}. f) Find the least upper bound of {3, 5}, if it exists. g) Find all lower bounds of {15, 45}. h) Find the greatest lower bound of {15, 45}, if it exists.

Problem 31E Show that a finite poset can be reconstructed from its covering relation. [Hint: Show that the poset is the reflexive transitive closure of its covering relation.)

Problem 34E Answer these questions for the poset ({2,4,6,9, 12, 18,27,36,48,60,72}, |). a) Find the maximal elements. b) Find the minimal elements. c) Is there a greatest element? d) Is there a least element? e) Find all upper bounds of {2, 9}. f) Find the least upper bound of {2, 9}, if it exists. g) Find all lower bounds of {60, 72}. h) Find the greatest lower bound of {60, 72), if it exists.

Answer these questions for the partial order represented by this Hasse diagram. a) Find the maximal elements. b) Find the minimal elements. c) Is there a greatest element? d) Is there a least element? e) Find all upper bounds of \(\{a, b, c\}\). f ) Find the least upper bound of \(\{a, b, c\}\), if it exists. g) Find all lower bounds of \(\{f, g, h\}\). h) Find the greatest lower bound of \(\{f, g, h\}\), if it exists. Equation Transcription: Text Transcription: {a, b, c} {f, g, h}

Problem 35E Answer these questions for the poset ({{1}, {2}, {4}, {1,2}, {1,4}, {2,4}, {3,4}, {1,3,4}, {2,3,4}}, ?). a) Find the maximal elements. b) Find the minimal elements. c) Is there a greatest element? d) Is there a least element? e) Find all upper bounds of {{2}, {4}}. f) Find the least upper bound of ({2}, {4)}, if it exists. g) Find all lower bounds of {{1, 3,4}, {2, 3,4}}. h) Find the greatest lower bound of {{1, 3, 4), {2,3,4}}, if it exists.

Problem 38E Show that lexicographic order is a partial ordering on the set of strings from a poset.

Problem 36E Give a poset that has a) a minimal element but no maximal element. b) a maximal element but no minimal element. c) neither a maximal nor a minimal element.

Problem 37E Show that lexicographic order is a partial ordering on the Cartesian product of two posets.

Problem 39E Suppose that (S, ?1) and (T, ?2) are posets. Show that (S × T, ? ) is a poset where (s, t) ? (u, v) if and only if s ?1 u and t ?2 v.

Problem 42E a) Show that the least upper bound of a set in a poset is unique if it exists. b) Show that the greatest lower bound of a set in a poset is unique if it exists.

Problem 40E a) Show that there is exactly one greatest element of a poset, if such an element exists. b) Show that there is exactly one least element of a poset, if such an element exists.

Problem 43E Determine whether the posets with these Hasse diagrams are lattices. a) b) c)

Problem 41E a) Show that there is exactly one maximal element in a poset with a greatest element. b) Show that there is exactly one minimal element in a poset with a least element.

Problem 44E Determine whether these posets are lattices. a) ({1,3,6,9, 12}, |) ________________ b) ({1,5,25, 125}, |) ________________ c) (Z, ?) ________________ d) (P(S), ?), where P(S) is the power set of a set S

Problem 45E Show that every nonempty finite subset of a lattice has a least upper bound and a greatest lower bound.

Problem 46E Show that if the poset (S, R?1) is a lattice then the dual poset (S, R?1) is also a lattice.

Problem 47E In a company, the lattice model of information flow is used to control sensitive information with security classes represented by ordered pairs (A, C). Here A is an authority level, which may be nonproprietary (0), proprietary (1), restricted (2), or registered (3). A category C is a subset of the set of all projects {Cheetah, Impala, Puma). (Names of animals are often used as code names for projects in companies.)

Problem 48E Show that the set 5 of security classes (A, C) is a lattice, where A is a positive integer representing an authority class and C is a subset of a finite set of compartments, with (A1, C1) ? (A2, C2) if and only if A1 ? A2 and C1 ? C2. [Hint: First show that (S, ? ) is aposet and then show that the least upper bound and greatest lower bound of (A1, C1) and (A2, C2) are (max(A1, A2), C1 U C2) and (min(A1, A2), C1 ? C2). respectively.]

Problem 49E Show that the set of all partitions of a set S with the relation P1 ? P2 if the partition P1 is a refinement of the partition P2 is a lattice. (See the preamble to Exercise 49 of Section 9.5.)

Problem 51E Show that every finite lattice has a least element and a greatest element.

Problem 50E Show that every totally ordered set is a lattice.

Problem 54E Determine whether each of these posets is well-ordered. a) (S, ?), where S = {10, 11, 12,…} b) (Q ? [0, 1 ], ?) (the set of rational numbers between 0 and 1 inclusive) c) (S, ?), where S is the set of positive rational numbers with denominators not exceeding 3 d) (Z?, ?), where Z? is the set of negative integers A poset (R, ? ) is well-founded if there is no infinite decreasing sequence of elements in the poset, that is, elements x1, x2, …, xn such that ? ? xn ? ? ? x2 ? x1. A poset (R, ?) is dense if for all x ? S and y ? S with x ? y, there is an element z ? R such that x ? z ? y.

Problem 52E Give an example of an infinite lattice with a) neither a least nor a greatest element. b) a least but not a greatest element. c) a greatest but not a least element. d) both a least and a greatest element.

Problem 53E Verify that (Z+ × Z+, ? ) is a well-ordered set, where ? is lexicographic order, as claimed in Example 8.

Problem 57E Show that the poset of rational numbers with the usual “less than or equal to” relation. (Q, ?), is a dense poset.

Problem 55E Show that the poset (Z,? ) where x? y if and only if |x|<|y| is well-founded but is not a totally ordered set.

Problem 56E Show that a dense poset with at least two elements that are comparable is not well-founded.

Problem 58E Show that the set of strings of lowercase English letters with lexicographic order is neither well-founded nor dense.

Problem 59E Show that a poset is well-ordered if and only if it is totally ordered and well-founded.

Problem 62E Find a compatible total order for the divisibility relation on the set {1,2, 3, 6, 8, 12,24, 36}.

Problem 61E Find a compatible total order for the poset with the Hasse diagram shown in Exercise 32.

Problem 60E Show that a finite nonempty poset has a maximal element.

Problem 64E Find all compatible total orderings for the poset with the Hasse diagram in Exercise 27.

Problem 63E Find all compatible total orderings for the poset ({1,2,4,5, 12, 20}, |} from Example 26.

Problem 65E Find all possible orders for completing the tasks in the development project in Example 27.

Schedule the tasks needed to build a house, by specifying their order, if the Hasse diagram representing these tasks is as shown in the figure.

Find an ordering of the tasks of a software project if the Hasse diagram for the tasks of the project is as shown.