# 投影片 1 - sun.csim.scu.edu.tw

Chapter 8 8.1 Relations and Their Properties 8.2 n-ary Relations and Their Applications 8.3 Representing Relations 8.4 Closures of Relations 8.5 Equivalence Relations 8.6 Partial Orderings 1 8.1 Relations and Their Properties Definition: A binary relation R from a set A to a set B is a subset R A B. .

Note: there are no constraints on relations as there are on functions. We have a common graphical representation of relations: Definition: A Directed graph or a Digraph D from A to B is a collection of vertices V A B and a collection of edges R A B . If there is an ordered pair e = in R then there is an arc or edge from x to y in D. The elements x and y are called the initial and terminal v ertices of the edge e. 2 Relations and Their Properties Examples: Let A = { a, b, c}

B = {1, 2, 3, 4} R is defined by the ordered pairs or edges {, , } can be represented by the digraph D: 3 Relations on a Set Definition: A binary relation R on a set A is a subset of A A or a relation from A to A. Example: A = {a, b, c} , R = {, , }. Then a digraph representation of R is: Note: An arc of the form on a digraph is called a loop.

Example : How many binary relations are there on a set A? Example 4: Let A be the set {1, 2, 3, 4}. Which ordered pairs are in the relation R={(a ,b) | a divides b}? 4 Special Properties of Binary Relations Given: A Universe U A binary relation R on a subset A of U Definition: R is reflexive iff "x [ x U < x, x >R ] Note: if U = then the implication is true vacuously The void relation on a void Universe is reflexive! Note: If U is not void then all vertices in a reflexive relation must have loops!

5 Properties of Relations Example 7: Consider the following relations on {1, 2, 3, 4} : R1:{(1,1) ,(1, 2), (2, 1), (2, 2), (3, 4), (4, 1) ,(4, 4)}. R2:{(1,1) ,(1, 2), (2, 1)}. R3:{(1,1) ,(1, 2), (1, 4), (2, 1), (2, 2), (3, 3) ,(4, 1), (4, 4)}. R4:{(2, 1), (3, 1), (3, 2), (4, 1) ,(4, 2), (4, 3)}. R5:{(1,1) ,(1, 2), (1, 3), (1, 4), (2, 2), (2, 3) ,(2, 4), (3, 3), (3, 4), (4, 4)}. R6:{ (3, 4)}. Which of these relations are reflexive?

6 Properties of Relations Definition: R is symmetric iff "x"y [< x, y > R < y, x > R ] Note:If there is an arc there must be an arc . Definition: R is antisymmetric iff "x"y [ < x, y > R < y, x > R x = y ] Note: If there is an arc from x to y there cannot be one from y to x if x y. You should be able to show that logically:

if is in R and x y then is not in R. 7 Properties of Relations Example 10: Which of the relations from Example 7 are symmetric and which are antisymmetric? R1:{(1,1) ,(1, 2), (2, 1), (2, 2), (3, 4), (4, 1) ,(4, 4)}. R2:{(1,1) ,(1, 2), (2, 1)}. R3:{(1,1) ,(1, 2), (1, 4), (2, 1), (2, 2), (3, 3) ,(4, 1), (4, 4)}. R4:{(2, 1), (3, 1), (3, 2), (4, 1) ,(4, 2), (4, 3)}. R5:{(1,1) ,(1, 2), (1, 3), (1, 4), (2, 2), (2, 3) ,(2, 4), (3, 3), (3, 4), (4, 4)}. R6:{ (3, 4)}.

8 Properties of Relations Definition: R is transitive iff "x"y"z [ < x, y > R < y, z > R < x,z > R ] Note: if there is an arc from x to y and one from y to z then there must be one from x to z. This is the most difficult one to check. We will develop algorithms to check this later. Example 13: Which of the relations in Example 7 are transitive? R1:{(1,1) ,(1, 2), (2, 1), (2, 2), (3, 4), (4, 1) ,(4, 4)}. R2: {(1,1) ,(1, 2), (2, 1)}. R3:{(1,1) ,(1, 2), (1, 4), (2, 1), (2, 2), (3, 3) ,(4, 1), (4, 4)}.

R4:{(2, 1), (3, 1), (3, 2), (4, 1) ,(4, 2), (4, 3)}. R5:{(1,1) ,(1, 2), (1, 3), (1, 4), (2, 2), (2, 3) ,(2, 4), (3, 3), (3, 4), (4,4)}. R6:{ (3, 4)}. 9 Properties of Relations Example: A: not reflexive symmetric antisymmetric transitive

C: not reflexive not symmetric antisymmetric not transitive B: not not not not reflexive symmetric

antisymmetric transitive D: not reflexive not symmetric antisymmetric transitive 10 Combining Relations A very large set of potential questions Let R1 and R2 be binary relations on a set A: If R1 has property 1 and

R2 has property 2, does R1 * R2 have property 3 where * represents an arbitrary binary set operation? 11 Combining Relations Example: If R1 is symmetric , and R2 is antisymmetric, does it follow that, R1R2 is transitive?R2 is transitive? If so, prove it. Otherwise find a counterexample. Example : Let R1 and R2 be transitive on A. Does it follow that

R1 R2 is transitive? R2 is transitive? 12 Composition Definition: Suppose R1 is a relation from A to B R2 is a relation from B to C. Then the composition of R2 with R1, denoted R2 R1 is the relation from A to C: If is a member of R1 and is a member of R2 then is a member of R2 R1. Note:

For to be in the composite relation R2 R1 there must exist a y in B . . . . Note: We read them right to left as in functions. 13 Composition Example: Example 20: What is the composite of the relations R and S, where R is the relation form {1, 2, 3} to {1, 2, 3, 4} with R={(1, 1), (1, 4), (2, 3), (3, 1), (3, 4)} and S is the relation from {1, 2, 3, 4} to {0, 1, 2} with S= {(1, 0), (2, 0), (3, 1), (3, 2), (4,1)}? 14

Composition Definition: Let R be a binary relation on A. Then Basis: R1 = R Induction: Rn + 1= Rn R Note: an ordered pair is in Rn iff there is a path of length n from x to y following the arcs (in the direc tion of the arrows) of R. 15 Composition Example :

16 Composition Theorem: R is transitive iff Rn R for all n > 0 . 17 8.2 n-ary Relations and Their Applications Definition 1: Let A1, A2, . . ., An be sets. An n-ary relation o n these sets is a subset of A1 A2 . . . An The sets A1, A2, . . ., An are called the domains of the rela tion, and n is called its degree. Example 4: Let R be the relation consisting of 5-ruples (A

, N, S, D, T) representing airplane flights, where A is the ai rline, N is the starting point, D is the destination, and T is the departure time, for instance, if Nadir Express Airlines has flight 963 from Newark to Bangor at 15:00, then (Nad ir, 963, Newark, Bangor, 15:00) belongs to R, the degree of this relation is 5, and its domains are the set of all airli nes, the set of flight numbers, the set of cities, the set of cities(again) , and the set of times. 18 Databases and Relations The time required to manipulate information in a dat abase depends on how this information is stored. The operations of adding and deleting records, upda

ting records, searching for records, and combining re cords from overlapping databases are performed mill ions of times each day in a large database. Because of the importance of these operations, vario us methods for representing databases have been de veloped. We will discuss one of these methods, called the rela tional data model, based on the concept of a relatio n. 19 Databases and Relations A database consists of records, which are n-tuples, made u p of fields. For instance, a database of student records may

be made up of fields containing the name, student number, major, and grade point average of the student. Thus , stude nt records are represented as 4-tuples of the form (STUDEN T NAME, ID NUMBER, MAJOR, GPA). A sample database of six such records is (Ackermann, 231455, Computer Science, 3.88) (Adams, 888323, physics, 3.45) (Chou, 102147, Computer Science, 3.49) (Goodfriend, 453876, Mathematics, 3.45) (Rao, 678543, Mathematics, 3.90) (Stevens, 786576, Psychology, 2.99) 20 Databases and Relations

Relations used to represent databases are also called tables. A domain of an n-ary relation is called a primary key when the value of the n-tuple from this domain deter mines the n-tuple. The current collection of n-tuples in a relation is calle d the extension of the relation. The more permanent part of a database , including t he name and attributes of the database, is called its i ntension. 21 Databases and Relations

22 Databases and Relations Example 5: which domains are primary keys for the n-ary relation displayed in Table1, assuming that no n-tuples will be added in the future? Combinations of domains can also uniquely identify n-tuples in an n-ary relation. When the values of a se t of domains determine an n-tuple in a relation, the C artesian product of these domains is called a compos ite key. Example 6: Is the Cartesian product of the domain of major fields of study and the domain of GPAs a com

posite key for the n-ary relation from Table1, assumin g that no n-tuples are ever added? 23 Operations on n-ary Relations Definition 2: Let R be an n-ary relation and C a condition th at elements in R may satisfy. Then the selection operator sC maps the n-ary relation R to the n-ary relation of all n-tupl es from R that satisfy the condition C. Example 7: To find the records of computer science majors i n the n-ary relation R shown in Table 1, we use the operato r sC1, C1 is the condition Major = Computer Science. To find the records of students who have a grade point aver age above 3.5 in this database, we use the operator sC2, wh

ere C2 is the condition GPA > 3.5. To find the records of computer science majors who have a GPA above 3.5, we use the operator sC3 , C3 is the condition (Major=Computer Science GPA > 3.5 ). 24 Operations on n-ary Relations Definition 3: The projection, Pi1, Pi2,. . . , Pim where i1 < i2 <. . .< im , maps the n-tuple (a1, a2,. . ., an) to the m-tuple (ai1 , ai2 , . . ., aim ) , m n. Example 8: what results then the projection P1,3 is applied to t he 4-tuples (2, 3, 0, 4), (Jane Doe, 234111001, Geography, 3.1 4), and (a1, a2, a3, a4)? Example 9: What relation results when the projection

P1,4 is applied to the relation in Table 1? 25 8.3 Representing Relations Connection Matrices Let R be a relation from A = {a1, a2, . . . , am} to B = {b1, b2, . . . , bn}. Definition: An m n connection matrix M for R is defined by Mij = 1 if is in R, = 0 otherwise. Example: We assume the rows are labeled with the elem ents of A and the columns are labeled with the elements of B. Let A = {a, b, c} , 1 0 0 0

B = {e, f, g, h}; R = {, } 0 0 0 0 Then the connection matrix M for R is 0 0 1 0 Note: the order of the elements of A and B matters 26 Representing Relations Theorem: Let R be a binary relation on a set A and let M be its connection matrix. Then R is reflexive iff Mii = 1 for all i. R is symmetric iff M is a symmetric matrix: M = MT

R is antisymetric if Mij = 0 or Mji = 0 for all i j. FIGURE 1 The Zero-One Matrix for a Reflexive FIGURE 2 The Zero-One Matrices for Symmetric and Antisymmetric Relations. 27 Combining Connection Matrices Example 3: Suppose that the relation R on a set is represent ed by the matrix 1 1 0 M R = 1 1 1

0 1 1 Is R reflexive, symmetric and/or antisymmetric? Definition: the join of two matrices M1, M2, denoted M1 M2 , is the component wise boolean or of the two matrices. Fact: If M1 is the connection matrix for R1 and M2 is the connection matrix for R2 then the join of M1 and M2 , M1 M2 is the connection matrix for R1RR2 . 28 Combining Connection Matrices Definition: the meet of two matrices M1, M2, denoted M1 M2 is the componentwise boolean and of the t

wo matrices. Fact: If M1 is the connection matrix for R1 and M2 is th e connection matrix for R2 then the meet of M1 and M 2, M1 M2 is the connection matrix for R1R2 . Example 4: Suppose that the relations R1 and R2 on a set A are represented by the matrices. M R1 1 = 1 0 0 0

1 1 0 0 and , M R 2 1 = 0 1

0 1 0 1 1 0 What are the matrices representing R1RR2 and R1R2 ? 29 The Composition Definition: Let M1 be the connection matrix for R1 M2 be the connection matrix for R2.

The boolean product of two connection matrices M1 and M2, denoted M1 M2 , is the connection matrix for the composition of R2 with R1 , R2 R1. (M1 M2 )ij = k=1n [(M1 )ik (M2 )kj ] Why? 30 The Composition In order for there to be an arc in the composition then there must be and arc in R1 and an arc in R2 for some y ! The Boolean product checkes all possible ys. If at least one such path exists, that is sufficient. Note: the matrices M1 and M2 must be conformable: the

number of columns of M1 must equal the number of rows of M2. If M1 is m n and M2 is n p then M1 M2 is m p. 31 The Composition Example : (M1 M2 )12 = [(M1 )11 (M2 )12 ][(M1 )12 (M2 )22 ] [(M1 )13 (M2 )32 ][(M1)14 (M2 )42 ] = [0 0] [1 1] [0 0] [0 1] = 1 32

The Composition Note: there is an arc in R1 from node 1 in A to node 2 in B there is an arc in R2 from node 2 in B to node 2 in C. Hence there is an arc in R2 R1 from node 1 in A to n ode 2 in C. 33 Representing Relations Using Digraphs Definition 1: A directed graph, or digraph, consists of a set V of vertices (or nodes ) together with a set E of ordered pairs of elements of V called edges (or arcs). The vertex a is called the initial vertex of the edge (a,

b), and the vertex b is called the terminal vertex of thi s edge. An edge of the form (a, a) is represented using an arc from the vertex a back to itself. Such an edge is called a loop. 34 Representing Relations Using Digraphs Example 7: The directed graph with vertices a, b, c, a nd d, and edges (a, b), (a, d), (b, b), (b, d), (c, a), (c, b), and (d, b) is displayed in Figure 3. FIGURE 3 The Directed

Graph. 35 Representing Relations Using Digraphs Example 8: The directed graph of the relation R={(1, 1), (1, 3), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2), (4, 1)} on the set {1, 2, 3, 4} is shown in figure 4. FIGURE 4 The Directed Graph of the Relations R. 36

Representing Relations Using Digraphs Example 9: What are the ordered pairs in the relation R represented by the directed graph shown in figure 5? FIGURE 5 The Directed Graph of the Relations R. 37 Representing Relations Using Digraphs Example 10: Determine whether the relations for the directed graphs shown in figure 6 are reflexive, symm etric, antisymmetric, and/or transitive. FIGURE 6 The Directed Graph of the Relations R and

S. 38 8.4 Closures of Relations Definition: The closure of a relation R with respect to property P is the relation obtained by adding the minim um number of ordered pairs to R to obtain property P. In terms of the digraph representation of R --To find the reflexive closure - add loops. --To find the symmetric closure - add arcs in the opposite direction. --To find the transitive closure - if there is a path from a to b, and a path from b to c, add an arc from a to c.

Note: Reflexive and symmetric closures are easy. Transitive closures can be very complicated. 39 Closures of Relations Definition: Let A be a set and let = { | x in A}. is called the diagonal relation on A (sometimes called the equality relation E). Note that D is the smallest (has the fewest number of ordered pairs) relation which is reflexive on A. Theorem: Let R be a relation on A. The reflexive closure of R, denoted r(R) , is R D. Add loops to all vertices on the digraph representation of R.

Put 1s on the diagonal of the connection matrix of R. 40 Closures of Relations Example 1: What is the reflexive closure of the relatio n R={(a, b) | a< b} on the set of integers? Example 2: What is the symmetric closure of the rela tion R={(a, b) | a> b} on the set of positive integers? 41 Symmetric Closure Definition: Let R be a relation on A. Then R-1 or the inverse of R is the relation R-1 = {< y, x >|< x, y >

R} Note: to get R-1 reverse all the arcs in the digraph representation of R take the transpose MT of the connection matrix M of R. Note: This relation is sometimes denoted as RT or Rc and called the converse of R The composition of the relation with its inverse does not necessarily produce the diagonal relation (recall that the composition of a bijective function with its inverse is the identity). 42 Symmetric Closure Theorem: Let R be a relation on A. The symmetric

closure of R, denoted s(R ), is the relation R R-1 . Example 2: What is the symmetric closure of the relatio n R={(a, b) | a> b} on the set of positive integers? Example : 43 Symmetric Closure Examples: If A = Z, then r( ) = Z Z If A = Z+, then s( < ) = . What is the (infinite) connection matrix of s(<)? If A = Z, then s() = ?) = ?

44 Symmetric Closure Theorem: Let R1 and R2 be relations from A to B. -1 = Then 1 1 = ( R -1) -1 = R R R (R1RR2) -1 = R1-1 R R2-1 (R1 - R2) -1 = R1 -1 - R2 -1

(R1 R2)-1= R1 -1R2 -1 If A = B, then (R1R2) -1 = R2-1R1-1 (A x B) -1 = B x A If R1 R2 then R1-1 R2-1 45 Paths in Directed Graphs Definition 1: A path from a to b in the directed graph G is a sequence of edges (x0, x1), (x1, x2), (x2, x3), . . ., (x

n-1, xn) in G, where n is a nonnegative integer, and x0= a and x1=b . that is , a sequence of edges where the terminal vert ex of an edge is the same as the initial vertex in the n ext edge in the path. This path is denoted by x0, x1, x2, . . .,xn-1 ,xn and has le ngth n. We view the empty set of edges as a path from a to a . a path of length n 1 that begins and ends at the sa1 that begins and ends at the sa me vertex is called a circuit or cycle. 46 Symmetric ClosurePaths in Directed Graphs Examples 3:

Which of the following are paths in the directed grap h show below? What are the lengths of those that ar e paths? Which of the paths in this list are circuits? a,b,e,d; a,e,c,d,b; b,a,c,b,a,a,b; d,c; c,b,a; e,b,a,d,a,b,e; 47 Paths in Directed Graphs Theorem: Let R be a relation on A. There is a path of

length n from a to b iff Rn . Proof: (by induction) Basis: An arc from a to b is a path of length 1. which is in R1 = R. Hence the assertion is true for n = 1. Induction Hypothesis : Assu me the assertion is true for n. Show it must be true for n+1. There is a path of length n+1 f rom a to b iff there is an x in

A such that there is a path of l ength 1 from a to x and a pat h of length n from x to b. From the Induction Hypoth esis, R and since is a path o f length n, Rn. If R And Rn , then Rn R = Rn+1 by the inductive definition o 48 f the powers of R.

Useful Results for Transitive Closure Theorem: Theorem: Corollary: Theorem: If A B and C B, then A C B. If R S and T U then R T S U.

If R S then Rn Sn If R is transitive then so is Rn Theorem: If Rk = Rj for some j > k, then Rj+m = Rn for some n j. We dont get any new relations beyond Rj. As soon as you get a power of R that is the same a s one you had before, STOP. 49 Transitive Closure Recall that the transitive closure of a relation R, t(R), is the smallest transitive relation containing R. Also recall: R is transitive iff Rn is contained in R for all n

. Hence, if there is a path from x to y then there must be an arc from x to y, or is in R. Example: If A = Z and R = {< i, i+1>} then t(R) = < Suppose R: is the following: 50 Transitive Closure Definition: The connectivity relation or the star closu re of the relation R, denoted R*, is the set of ordered pairs such that there is a path (in R) from a to b:

R*=n=1 Rn Examples: Let A = Z and R = {}. R* = < . Let A = the set of people, R = { | person x is a parent of person y}. R* = ? 51 Transitive Closure Theorem 2: t(R) = R*. Proof: Note: this is not the same proof as in the text. We must show that R* 1) is a transitive relation 2) contains R

3) is the smallest transitive relation which contains R. Proof: Part 2): Easy from the definition of R*. Part 1): Suppose and are in R*. Show is in R*. 52 Transitive Closure By definition of R*, is in Rm for some m and is in Rn for some n. Then is in Rn Rm = Rm+n which is contained in R*. Hence, R* must be transitive. Part 3): Now suppose S is any transitive relation that contains R.

We must show S contains R* to show R* is the smallest such relation. R S so R2 S2 S since S is transitive Therefore Rn Sn S for all n. (why?) Hence S must contain R* since it must also contain the union of all the powers of R. 53 Transitive Closure Theorem: If |A| = n, then any path of length > n must c ontain a cycle. Proof: If we write down a list of more than n vertices r epresenting a path in R, some vertex must appear at le

ast twice in the list (by the Pigeon Hole Principle). Thus Rk for k > n doesnt contain any arcs that dont already appear in the first n powers of R. 54 Transitive Closure Lemma 1: Let A be a set with n elements, and let R b e a relation on A . If there is a path of length at least one in R from a to b, then there is such a path with le ngth not exceeding n. Moreover, when a b , if there is a path of length at least one in R from a to b, then t here is such a path with length not exceeding n-1.

55 Transitive Closure Corollary: We can find the connection matrix of t(R) by computing the join of the first n powers of the con nection matrix of R. Powerful Algorithm! Example: 56 Transitive Closure Theorem 3: Let MR be the zero-one matrix of the rela tion R on the relation R on a set with n elements. The

n the zero-one matrix of the transitive closure R* is M R* =M R M [ 2] R M [ 3] R M

[n] R Example: Find the zero-one matrix of the transitive cl osure of the relation R where 1 1 0 M R = 1 0 1 0 1 0 57 Transitive Closure Algorithm 1 : A Procedure for Computing the Transitive Closure procedure transitive closure (MR :zero-one nxn matrix)

A := MR B := A for i :=2 to n begin A := AMMR B := B A end {B is the zero-one matrix for R* } 58 8.5 Equivalence Relations Now we group properties of relations together to de fine new types of important relations. Definition: A relation R on a set A is an equivalence relation iff R is

reflexive symmetric transitive 59 Equivalence Relations It is easy to recognize equivalence relations using digraphs. The subset of all elements related to a particular element forms a universal relation (contains all possible arcs) on that subset. The (sub)digraph representing the subset is called a complete (sub)digraph. All arcs are present.

The number of such subsets is called the rank of the equivalence relation. 60 Equivalence Relations Example: A has 3 elements: 61 Equivalence Relations Each of the subsets is called an equivalence class. A bracket around an element means the equivalence

class in which the element lies. [x] = {y | is in R} The element in the bracket is called a representative of the equivalence class. We could have chosen any one. Example: [a] = {a, c}, [c] = {a, c}, [b] = {b}. rank = 2 62 Equivalence Relations Definition: Let S1, S2, . . ., Sn be a collection of subsets of A. Then the collection forms a partition of A if the subsets are nonempty, disjoint and exhaust

A: Si Si Sj = if i j R2 is transitive?Si = A FIGURE 1 A Partition of a Set. 63 Equivalence Relations Theorem: The equivalence classes of an equivalence relation R partition the set A into disjoint nonempty subsets whose union is the entire set. This partition is denoted A/R and called -- the quotient set, or

-- the partition of A induced by R, or, -- A modulo R. Example : A = [a] [b] = [a] [c] = {a} {b,c} rank = 2 64 Equivalence Relations Theorem: Let R be an equivalence relation on A. The n either [a] = [b] Or [a] [b] =

Theorem: If R1 and R2 are equivalence relations on A then R1 R2 is an equivalence relation on A . 65 Equivalence Relations Definition: Let R be a relation on A. Then the reflexiv e, symmetric, transitive closure of R, tsr(R), is an equi valence relation on A, called the equivalence relation induced by R. Example: tsr(R)

rank = 2 A = [a] [b] = {a} {b, c, d} ; A/R = {{a}, {b, c, d}} 66 Equivalence Relations Theorem: tsr(R) is an equivalence relation Proof: We have to be careful and show that tsr(R) is still sym metric and reflexive. Since we only add arcs vs. deleting arcs when compu ting closures it must be that tsr(R) is reflexive since all loops on the diagraph must be presen t when constructing r(R). If there is an arc then the symmetric closure

of r(R) ensures there is an arc . 67 Equivalence Relations Now argue that if we construct the transitive closure of sr(R) and we add an edge because there is a path from x to z, then there must also exist a path fro m z to x (why?) and hence we also must add an edge . Hence the transitive closure of sr(R) is symmetric. Q.E.D 68

8.6 Partial Orderings Definition: Let R be a relation on A. Then R is a partia l order iff R is reflexive antisymmetric transitive (A, R) is called a partially ordered set or a poset. 69

Partial Orderings Note: It is not required that two things be related un der a partial order. That's the partial part of it. If two objects are always related in a poset, it is calle d a total order or linear order or simple order. In this case (A, R) is called a chain. 70 Partial Orderings Examples: (Z ) is a poset. In this case either a b or b a s o

two things are always related. Hence, is a total ord er and (Z, ) is a chain. If S is a set then (P(S), ) is a poset. It may not be th e case that A B or B A. Hence, is not a total o rder. (Z+, 'divides') is a poset which is not a chain. 71 Partial Orderings Definition 2: The elements a and b of a poset (S, ) are called comparable if either a b or b a . When a and b are elements of S such that neither a b nor b a , a and b are called incomparable. Example 5: In the poset (Z+, |), are the integers 3 and

9 comparable? Are 5 and 7 are incomparable, becaus e 5 7 and 7 5 . 72 Partial Orderings Definition: Let R be a total order on A and suppose S A. An element s in S is a least element of S iff sRb for every b in S. Similarly for greatest element. Note: this implies that is not in R for any a unle ss a = s. (There is nothing smaller than s under the or der R).

73 Partial Orderings A Chain (A,R) is well-ordered iff every subset of A has a l east element. Examples: (Z, ) is a chain but not well-ordered. Z does not have least element. (N, ) is well-ordered. (N, ) is not well-ordered. Theorem 1: The Principle of Well-Ordered Induction Suppose that S is a well-ordered set. Then P(x) is true for all x S, if Inductive Step: For every y S , if P(x) is true for all

x S with x y , then P(y) is true. 74 Lexicographic Order Given two posets (A1, R1) and (A2, R2) we construct an indu ced partial order R on A1A2: < x1, y1> R iff x1 R1 x2 ,Or x1 = x2 and y1 R2 y2. Example: Let A1 = A2 = Z+ and R1 = R2 = 'divides . Then <2, 4> R <2, 8> since x1 = x2 and y1 R2 y2. <2, 4> is not related under R to<2, 6> since x1 = x2 but 4 does not divide 6. <2, 4> R <4, 5> since x1 R1 x2.

(Note that 4 is not related to 5). 75 Lexicographic Order This definition extends naturally to multiple Cartesian products of partially ordered sets: A1 A2 A3 . . . An. Example: Using the same definitions of Ai and Ri as above, < 2, 3, 4, 5> R < 2, 3, 8, 2> since x1 = x2, y1 = y2 and 4 divides 8. <2, 3, 4, 5> is not related to <3, 6, 8, 10> since 2 does not divide 3.

76 Lexicographic Order In Figure 1 the ordered pairs in Z+ Z+ that are less tha n (3, 4) are highlighted. FIGURE 1 The Ordered Pairs Less Than (3,4) in Lexicographic Order. 77

Strings We apply this ordering to strings of symbols where there is an underlying 'alphabetical' or partial order (which is a total order in this case). Example: Let A = { a, b, c} and suppose R is the natural alphabetic al order on A: a R b and b R c. Then Any shorter string is related to any longer string(comes befor e it in the ordering). If two strings have the same length then use the induced par tial order from the alphabetical order:

aabc R abac 78 Hasse or Poset Diagrams To construct a Hasse diagram: 1) Construct a digraph representation of the poset (A, R) so that all arcs point up (except the loops). 2) Eliminate all loops 3) Eliminate all arcs that are redundant because of transitivity 4) eliminate the arrows at the ends of arcs since everything points up.

79 Hasse Diagrams For instance, consider the directed graph for the par tial ordering {(a, b)| a b} on the set {1, 2, 3, 4}. Figu re 2(a). we do not have to show t hese loops because they must be present. Figure 2 (a). We do not have to show t hose edges that must be

present because of transi tivity. Figure 2(c). FIGURE 2 Constructing the Hasse Diagram for ({1,2,3,4},). 80 Hasse Diagrams Example 12: Draw the Hasse diagram representing th e partial ordering {(a, b)| a divides b} on {1, 2, 3, 4, 6, 8, 12}. FIGURE 3 Constructing the Hasse Diagram of ({1,2,3,4,6,8,1 2}, ).

81 Hasse Diagrams Example 13: Draw the Hasse diagram representing th e partial ordering {(A, B)| A B} on the power set S ={a ,b, c}. FIGURE 4 The Hasse Diagram of (P({a,b,c}), ). 82 Maximal and Minimal Elements Definition: Let (A, R) be a poset. Then a in A is a minimal element if there does not exist an element b

in A such that bRa. Similarly for a maximal element. Example: In the above Hasse diagram, is a minimal element and {a, b, c} is a maximal element. 83 Maximal and Minimal Elements Example 14: Which elements of the poset ({2, 4, 5, 10 , 12, 20, 25}, |) are maximal, and which are minimal? FIGURE 5 The Hasse Diagram of a Poset. 84

Least and Greatest Elements Definition: Let (A, R) be a poset. Then a in A is the lea st element if for every element b in A, aRb and b is th e greatest element if for every element a in A, aRb . Theorem: Least and greatest elements are unique. Proof: Assume they are not. . . Example: In the poset above {a, b, c} is the greatest element. is the least element. 85 Maximal and Minimal Elements Example 15: Determine whether the posets represented by

each of the Hasse diagrams in Figure 6 have a greatest elem ent and a least element. FIGURE 6 Hasse Diagrams of Four Posets. 86 Upper and Lower Bounds Definition: Let S be a subset of A in the poset (A, R). I f there exists an element a in A such that sRa for all s in S, then a is called an upper bound . Similarly for lower bounds. Note: to be an upper bound you must be related to e very element in the set. Similarly for lower bounds. Example:

In the poset in Example 13, {a, b, c}, is an upper boun d for all other subsets. is a lower bound for all oth er subsets. 87 Upper and Lower Bounds Example 18: Find the lower and upper bounds of the subsets {a, b, c} , {j, h}, and {a, c, d, f} in the poset wit h the Hasse diagram shown in Figure 7. FIGURE 7 The Hasse Diagram of a Poset. 88

Least Upper and Greatest Lower Bounds Definition: If a is an upper bound for S which is relate d to all other upper bounds then it is the least upper bound, denoted lub(S) . Similarly for the greatest low er bound, glb(S) . Example: Consider the element {a} in Example 13. Sin ce {a, b, c}, {a, b} {a, c} and {a} are upper bounds and {a} is related to all of them, {a} must be the lub. It is a lso the glb. 89 Least Upper and Greatest Lower Bounds

Example 19: Find the greatest lower bound and the l east upper bound of {b, d, g}, if they exist, in the pose t shown in Figure 7. FIGURE 7 The Hasse Diagram of a Poset. 90 Lattices Definition: A poset is a l attice if every pair of ele ments has a lub and a gl b. Examples: In the poset

(P(S), ), lub(A, B) = A B. What is the glb(A, B)? Consider the elements 1 and 3. Upper bounds of 1 are 1, 2, 4 a nd 5. Upper bounds of 3 are 3, 2, 4 a nd 5. 2, 4 and 5 are upper bounds fo r the pair 1 and 3. There is no lub since -- 2 is not related to 4 -- 4 is not related to 2

-- 2 and 4 are both related to 5. There is no glb either. The poset is not a lattice. 91 Lattices Example 30: Determine whether the posets represen ted by each of the Hasse diagrams in Figure 8 are latti ces. FIGURE 8 Hasse Diagrams of Three Posets. 92 Topological Sorting

We impose a total ordering R on a poset compatible wi th the partial order. Useful in PERT charts to determine an ordering of tasks . Useful in rendering in graphics to render objects from back to front to obscure hidden surfaces. A painter uses a topological sort when applying paint t o a canvas - he/she paints parts of the scene furthest from the view first. This definition extends naturally to multiple Cartesian p roducts of partially ordered sets: A1 A2 A3 . . . An. 93

Topological Sorting Example: Consider the rectangles T and the relation R = is more distant than. Then R is a partial order o n the set of rectangles. Two rectangles, Ti and Tj , are related, Ti R Tj, if Ti is more distant from the viewer than Tj . 94 Topological Sorting The Hasse diagram for R is Draw 1 (or 8) and delete 1

from the diagram to get Then 1R2, 1R4, 1R3, 4R9, 4R5, 3R2, 3R9, 3R6, 8R7. Now draw 4 (or 3 or 8) and delete from the diagram. Always choose a minimal element. Any one will do. ...and so forth. 95 Topological Sorting Algorithm 1 Topological Sorting procedure Topological Sorting ((S, ) : finite poset) k :=1 while S

begin ak := a minimal element of S { such an element exists by Lemma 1} S := S - {ak } k := k + 1 end {a1, a2, . . ., an is a compatible total ordering of S} 96 Topological Sorting Example 26: Find a compatible total ordering for the poset ({1, 2, 4, 5, 12, 20}, | ). FIGURE 9 A Topological Sort of ({1,2,4,5,12,20}, ). 97

Topological Sorting Example 27 : A developme nt project at a computer co mpany requires the comple tion of seven tasks. Some of these tasks can be started only after other task s are finished. A partial ordering on tasks i s set up by considering task X task Y if task Y cannot b e started until task X has be en completed.

The Hasse diagram for the s even tasks, with respect to t his partial ordering, is show n in Figure 10 . Find an order in which thes e tasks can be carried out to complete the project. FIGURE 10 The Hasse Diagram for Seven Tasks. 98

Topological Sorting FIGURE 11 A Topological Sort of the Tasks. 99

## Recently Viewed Presentations

• L'acqua risulta bluperché quando la luce del sole, che contiene tutti i colori, vi penetra, alcuni colori vengono assorbiti dalle sue molecole, in particolare esse assimilano maggiormente i colori arancione e rosso, quindi quando la luce arriva ai nostri occhi...
• 7-day hotfix policy. STOP. web site when applying hotfix/upgrade. KIM (Kentico Installation . Manager) Download & apply hotfix/upgrade. READ the instructions . and. follow . them to a T (AND verify , e.g.: 3.1a -> 4.0) CANNOT . be applied...
• APK: Review the Formal/Informal T-chart poster. Tell your ATT buddy one example of a formal language phrase/sentence. Tell your ATT buddy one example of an informal language phrase/sentence. Your ATT buddy is the person directly in front of you. The...
• Chapter Twenty-Nine America Under Stress, 1967-1976
• HUD-VASH Broadcast February 10, 2009 HUD Presentation Portability Two types of portability in HUD-VASH based on which VAMC that will provide case management. Referring VAMC or a VAMC in another part of the country.
• 1) The tracer behaves or interacts with the system to be probed in a known andreproducible fashion. 2) The tracer does not alter or perturb the system in any measurable fashion.
• An Introduction to Sport Education Gary D. Kinchin, PhD School of Education University of Southampton
• Genesis 2:23-25 (NIV) The man said, "This is now bone of my bones and flesh of my flesh; she shall be called 'woman,' for she was taken out of man." 24 For this reason a man will leave his father...