Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAP. 14] ORDERED SETS AND LATTICES 361

Fig. 14-18

14.39. LetS={a, b, c, d, e, f}be ordered as in Fig. 14-18(b).

(a) Find all minimal and maximal elements ofS.

(b) DoesShave any first or last element?

(c) List all linearly ordered subsets with three or more elements.

14.40. LetS={a, b, c, d, e, f, g}be ordered as in Fig. 14-11(a). Find the numbernof linearly ordered subsets ofSwith:

(a) four elements; (b) five elements.

14.41. LetS={ 1 , 2 ,..., 7 , 8 }be ordered as in Fig. 14-11(b). Find the numbernof linearly ordered subsets ofSwith:

(a) five elements; (b) six elements.

CONSISTENT ENUMERATIONS

14.42. LetS={a, b, c, d, e}be ordered as in Fig. 14-18(a). List all consistent enumerations ofSinto{ 1 , 2 , 3 , 4 , 5 }.

14.43. LetS={a, b, c, d, e, f}be ordered as in Fig. 14-18(b). Find the numbernof consistent enumerations ofSinto

{ 1 , 2 , 3 , 4 , 5 , 6 }.

14.44. Suppose the following are three consistent enumerations of an ordered setA={a, b, c, d}:

[(a, 1 ), (b, 2 ), (c, 3 ), (d, 4 )], [(a, 1 ), (b, 3 ), (c, 2 ), (d, 4 )], [(a, 1 ), (b, 4 ), (c, 2 ), (d, 3 )]

Assuming the Hasse diagramDofAis connected, drawD.

ORDER AND PRODUCT SETS

14.45. LetM={ 2 , 3 , 4 ,...}and letM^2 =M×Mbe ordered as follows:

(a, b)≺(c, d) if a|candb<d

Find all minimal and maximal elements ofM×M.

14.46. Consider the English alphabetA={a,b,c,...,y,z}with the usual (alphabetical) order. RecallA∗consists of all

words inA. LetLconsist of the following list of elements inA∗:

gone, or, arm, go, an, about, gate, one, at, occur

(a) SortLaccording to the short-lex order, i.e., first by length and then alphabetically.

(b) SortLalphabetically.

14.47. Consider the ordered setsAandBappearing in Fig. 14-17(a) and (b), respectively. SupposeS=A×Bis given the

product order. Insert the correct symbol,≺,.or‖, between each pair of elements ofS:

(a)( 4 ,b)___( 2 ,e); (b)( 3 ,a)___( 6 ,f); (c)( 5 ,d)___( 1 ,a); (d)( 6 ,e)___( 2 ,b).

14.48. SupposeN={ 1 , 2 , 3 ,...}andA={a,b,c,...,y,z}are given the usual orders, andS=N×Ais ordered

lexicographically. Sort the following elements ofS:

( 2 , z), ( 1 ,c), ( 2 , c), ( 1 , y), ( 4 , b), ( 4 , z), ( 3 , b), ( 2 ,a)