Discrete Mathematics for Computer Science

Exercises 201

a a Logon

e e Load Text Editor

f f Open File

Dh P h Insert Ext. File

b b b Open Mailer

4P c Reply

g P g Modify File

d P, d Send New Msg.

0 i Save Modified File

Linear order U

In Chapter 6, we will examine and analyze an algorithm called Topological Sort that

carries out the embedding of a partial order in a linear order.

rnExercises

1. (a) Draw the diagram to represent the I (divides) partial order on {1, 2, 3, 4, 5, 6}.
   (b) List all the maximal, maximum, minimal, and minimum elements.


2. (a) Draw a diagram to represent the I (divides) partial order on 10, 1, 2, 3, 4, 5, 6, 7,
   8,9, 10, 111.
   (b) Identify all minimal, minimum, maximal, and maximum elements in the diagram.


3. (a) Draw a diagram to represent the I (divides) partial order on the set {1, 2, 3, 4, 5, 6,

7,8,9,10,11).

(b) Identify all minimal, minimum, maximal, and maximum elements in the diagram.

4. Draw a diagram to represent the I (divides) partial order on the following:
   (a) {1, 111
   (b) 11, 3, 7, 211
   (c) {1, 2, 3, 4, 6, 9, 12, 18, 36)
   (d) {1, 2, 4, 8, 16, 32, 64)


5. Prove that Examples 5(a) and (b) are partial orderings.


6. Let

X = 1-5, -4, -3, -2, -1,0, 1, 2, 3,4, 51

For x, y E X, set x R y if x^2 < y^2 or x = y. Show that R is a partial ordering on X.

Draw a diagram of R.

7. (a) Explain why the relation "is older than or the same age" is a partial order.
   (b) Explain why the relation "is older than" is not a linear order.