Discrete Structures Problems

A. Doerr

1

Week 13 Partial Orderings In your notes for week 11 I have already defined a partial ordering relation. (See Notes section 6.3). http://faculty.uml.edu/klevasseur/ADS2_PartA_Fall2011.pdf For additional information you may wish to read the material in the text section 9.6, examples 1, 2, 3 and 4. Next, if you are not sure what a partial ordering or Hasse diagram is skip to the description of Hasse Diagrams, in the text section 9.6 (page 618) and study examples 12 and 13. Exercise 67, of section 9.6 in the text is an easy and informative problem. Before we begin let’s recall that if A is a set and if R is a relation on A we indicate that the ordered pair (x, y) is an element of R two ways: by simply saying (x, y) ∈R or by saying xRy. Let’s reinforce our knowledge about partial orderings with several simple examples: Example 1. Let A = {1, 2, 3, 6}. Define the relation R on A by m R n iff m | n ( recall, m | n is the notation for m “divides evenly into” n). So R = {(1, 1), (2, 2), (3, 3), (6, 6), (1, 2), (1, 3), (1, 6), (2, 6), (3, 6)}. Take a minute to draw the digraph of this relation. There will be 9 directed edges in the digraph. This relation is reflexive since m | m for all m∈A. This relation is antisymmetric since if m and n are numbers such that m | n and n | m then m must be equal to n. This relation is transitive since if m, n and p are three numbers such that m | n and n | p then m | p. Since this relation is reflexive, antisymmetric and transitive it is a partial ordering and we can draw its partial ordering or Hasse diagram. (Google hasse diagram for a number of interesting diagrams). Hasse diagrams are usually drawn from the “bottom up”. Keep in mind a Hasse diagram is simply a flow chart or a family tree but displayed from the ‘bottom up. Since the number 1 divides all other numbers in the set we start with it. The smaller numbers that 1 divides are 2 and 3 so we indicate those above 1. Next both 2 and 3 divide 6 therefore 6 appears above 2 and 3. If you compare the Hasse diagram of this relation to that of its digraph you will see the Hasse diagram is much simpler to read. The Hasse diagram is

1

2 3

6

A. Doerr

2

Example 2. Let A = {1, 2, 3, 4, 6, 8, 12}. Define the relation R on A by

m R n iff m | n ( recall, | is the notation for m “divides” n. just start to draw the digraph of this relation and you will quickly see it is much too “busy” with way too many directed edges. Its Hasse diagram is:

1

2 3

4 6

8 12

Example 3. To obtain a degree in any field in a university, a person must take a number of required courses. Certain of these courses are prerequisites of others. In the chart below, assume the following are the required mathematics and computer science courses, with perquisites, for a B. S. degree in Computer Science.

Math and CS requirements for a BS degree

C. S. Courses Prerequisites 91.101 Computing I none 16.267 Engineering course none 91.102 Computing II 91.101 91.201 Computing III 91.102 91.203 Computer Organization & Assembly Language 91.101 91.204 Computing IV 91.201, 91.203 91.301 Organization of Programming Languages 91.204 91.304 Foundations of Computer Science 92.322 91.305 Computer Architecture 91.203, 16.267,

91.102 91.308 Introduction to Operating Systems 91.305 91.404 Analysis of Algorithms 91.201, 92.322 Computer Science Project Sequence Senior standing

A. Doerr

3

Mathematics Courses Prerequisites

92.131 Calculus I none 92.132 Calculus II 92.131 92.231 Calculus III 92.132 92.321 Discrete Structures I 92.131 92.322 Discrete Structures II 92.321 92.386 Statistics for Sci/Eng 92.132 A student might ask herself, what is the minimum number of semesters she needs to finish the math and CS required courses for her degree. How many of these courses can one take in a given semester? To answer these questions the student wanted to draw a partially ordered diagram of the math and CS requirements. To do this she must define a relation on the courses which is: reflexive, antisymmetric and transitive. The relation that made sense to her was course x is related to course y iff course x is a prerequisite of course y. More formally. Let A be the set of the required mathematics and computer science courses for a B. S. degree in Computer Science. Define the relation R on a by Course x is related to course y by R iff course x is a prerequisite of course y. We will check each property. Reflexive means (x, x)∈R for all x∈R We will check this property later. Antisymmetric can be defined two ways:

i. If (x, y)∈R and (y, x)∈R then x = y for all x, y ∈R or ii. If (x, y)∈R and x ≠ y then (y, x)∉R for all x, y ∈R

We’ll use definition 2. For this example definition 2 says that if course x and course y are two different courses and if course x is a prerequisite of course y then course y cannot be a perquisite of course x. This is true so this relation is antisymmetric. Transitive means If (x, y)∈R and (y, z)∈R then (x, z)∈R for all x, y and z ∈R For this example if course x is a prerequisite of y and course y is a prerequisite of a third course z then course x must be a prerequisite of course z. This is certainly true so this relation is transitive. Now back to the property of reflexive. A course is not a prerequisite of itself so this relation does not satisfy the mathematical definition of a partial ordering but we can draw a prerequisite graph. See the graph below. We can fix this relation so it satisfies not only the intuition of what the graph should be but the mathematical definition of partial ordering. Let A = {of all the above math and CS courses}. Define the relation R on A by xRy iff course x is a prerequisite of course y or course x = course y. Note: The stipulation “course x = course y” is needed in this example to make the relation reflexive. Why? The readers should, at this point, convince themselves that the relation R now satisfies all parts of the definition of a partial ordering relation.

A. Doerr

4

The Hasse diagram (partial ordering graph) of this relation R is:

Figure 11.1 Can you answer the question posed toward the beginning of this example, namely, ”A student might ask herself, what is the minimum number of semesters she needs to finish the math and CS required courses for her degree. How many of these courses can one take in a given semester?” Examples 4. We can use the idea presented in example 3 of how we made that relation reflexive on family tree. The idea for partial orderings came from that of family trees. The only difference is we ordinarily write family trees from top down. Let’s rewrite this idea so it satisfies the mathematical description of a partial ordering. Let A = {of all your ancestors, say, back to your great grandmother}. Define R on A by person a is related by R to person b iff person a is an ancestor of person b or if person a is = (same person as) person b. The graph of the administrative structure of your business is a partial ordering diagram.

A. Doerr

5

Example 5. The following is a partial ordering of a relation, call it S. List all ordered pairs in S.

a

b c

ed

f

To list the ordered pairs I remind myself that this is a Hasse /Partial Ordering graph of a partial ordering so it must be reflexive, antisymmetric and transitive. I will take each property and list the ordered pairs that that property describes. Let’s call the relation S and use the ordered pair notation for a relation. Reflexive means (x, x)∈S for all x∈S, so (a,a), (b,b), (c,c) etc all belong to S. Note this gives us 6 pairs, one for each node. List them. Antisymmetric can be defined two ways:

i. If (x, y)∈S and (y, x)∈S then x = y for all x, y ∈S or ii. If (x, y)∈S and x ≠ y then (y, x)∉S for all x, y ∈S

Definition 2 says that all lines in this diagram are really directed edges that point up. Think of course prerequisites example. So (a,b), (a,c), (b,d), (c,e) etc are all in the relation. Note this give us 7 pairs, one for each edge. List them. Transitive means If (x, y)∈S and (y, z)∈S then (x, z)∈S for all x, y and z ∈S So since (a,b) ∈S and (b,d) ∈S then, (a,d) ∈S Also since (a,d) ∈S and (d,f) ∈S then, (a,f) ∈S Also since (a,b) ∈S and (b,e) ∈S then, (a,e) ∈S So, so far, transitivity gives us 3 more pairs in the relation. (Did I miss any? Yes, 2 pairs). I claim that Transitivity gives us 5 pairs altogether, so the total Number of pairs in S is 6 + 7 + 5 = 18. Check to see if I am correct. List all pairs in S. A final comment. We can visualize what partial ordering means when we think of our family tree. There are many different levels in a family tree and many people on the same level (brothers, sisters, cousins etc.) A total ordering is when any two elements are comparable in a set. Think of the y-axis and the real numbers on it. For any two real numbers x and y either x ≤ y or y ≤ x.