DOC PREVIEW
TEMPLE CIS 166 - Partial Orderings

This preview shows page 1-2-3-20-21-22-41-42-43 out of 43 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 43 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 43 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 43 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 43 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 43 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 43 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 43 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 43 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 43 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 43 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Partial OrderingsIntroductionPartially Ordered Set (POSET)Example (1)Slide 5ExamplePartial ordering examplesExample (2)Example (3)Comparable/IncomparableSlide 11Slide 12Slide 13Slide 14Slide 15Slide 16Well-ordered sets examplesThe Principle of Well-Ordered InductionLexicographic OrderSlide 20Slide 21Hasse DiagramsHasse Diagrams (continued)Slide 24Slide 25Hasse DiagramSlide 27Assemble an AutomobilePrerequisitesExample – Job Scheduling (PERT chart)Maximal and Minimal ElementsGreatest Element Least ElementUpper bound, Lower boundLeast Upper Bound, Greatest Lower BoundLatticesSlide 36Lattice Model (LinuxSecurity.com)Topological SortingSlide 39Slide 40Slide 41Slide 42Slide 431Partial OrderingsBased on Slides by Chuck Allison fromhttp://uvsc.freshsources.com/Courses/CS_2300/Slides/slides.htmlRosen, Chapter 8.6Modified by Longin Jan Latecki2IntroductionAn equivalence relation is a relation that is reflexive, symmetric, and transitiveA partial ordering (or partial order) is a relation that is reflexive, antisymmetric, and transitive•Recall that antisymmetric means that if (a,b)  R, then (b,a) R unless b = a•Thus, (a,a) is allowed to be in R•But since it’s reflexive, all possible (a,a) must be in R3Partially Ordered Set (POSET)A relation R on a set S is called a partial ordering or partial order if it is reflexive, antisymmetric, and transitive. A set S together with a partial ordering R is called a partially ordered set, or poset, and is denoted by (S, R)4Example (1)Let S = {1, 2, 3} and let R = {(1,1), (2,2), (3,3), (1, 2), (3,1), (3,2)}1235In a poset the notation a b denotes thatThis notation is used because the “less than or equal to” relation is a paradigm for a partial ordering. (Note that the symbol is used to denote the relation in any poset, not just the “less than or equals” relation.) The notation a b denotes thata b, but ( , )a b R�a b�6ExampleLet S = {1, 2, 3} and let R = {(1,1), (2,2), (3,3), (1, 2), (3,1), (3,2)}1232 2 3 27Partial ordering examplesShow that ≥ is a partial order on the set of integers•It is reflexive: a ≥ a for all a  Z•It is antisymmetric: if a ≥ b then the only way that b ≥ a is when b = a•It is transitive: if a ≥ b and b ≥ c, then a ≥ cNote that ≥ is the partial ordering on the set of integers(Z, ≥) is the partially ordered set, or poset8Example (2)Show that ≥ is a partial order on the set of integers•It is reflexive: a ≥ a for all a  Z•It is antisymmetric: if a ≥ b then the only way that b ≥ a is when b = a•It is transitive: if a ≥ b and b ≥ c, then a ≥ cNote that ≥ is the partial ordering on the set of integers(Z, ≥) is the partially ordered set, or poset9Example (3)Consider the power set of {a, b, c} and the subset relation. (P({a,b,c}), ) �10Comparable/IncomparableThe 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.11Example�Consider the power set of {a, b, c} and the subset relation. (P({a,b,c}), ) { , } { , } and { , } { , }a c a b a b a c� �So, {a,c} and {a,b} are incomparable12(S, )If is a poset and every two elements of S are comparable, S is called totally ordered or linearly ordered set, and is called a total order or a linear order. A totally ordered set is also called a chain.Totally Ordered, Chains13In the poset (Z+,≤), are the integers 3 and 9 comparable?•Yes, as 3 ≤ 9Are 7 and 5 comparable?•Yes, as 5 ≤ 7As all pairs of elements in Z+ are comparable, the poset (Z+,≤) is a total order•a.k.a. totally ordered poset, linear order, or chain14In the poset (Z+,|) with “divides” operator |, are the integers 3 and 9 comparable?•Yes, as 3 | 9Are 7 and 5 comparable?•No, as 7 | 5 and 5 | 7Thus, as there are pairs of elements in Z+ that are not comparable, the poset (Z+,|) is a partial order. It is not a chain.1516(S, ) is a well-ordered set if it is a poset such that is a total ordering and such that every nonempty subset of S has a least element.Well-Ordered SetExample: Consider the ordered pairs of positive integers, Z+ x Z+ where 1 2 1 2 1 1 1 1 2 2( , ) ( , ) if , or if and a a b b a b a b a b< = �p17Well-ordered sets examplesExample: (Z,≤)•Is a total ordered poset (every element is comparable to every other element)•It has no least element•Thus, it is not a well-ordered setExample: (S,≤) where S = { 1, 2, 3, 4, 5 }•Is a total ordered poset (every element is comparable to every other element)•Has a least element (1)•Thus, it is a well-ordered set18The Principle of Well-Ordered InductionSuppose that S is a well-ordered set. Then P(x) is true for all x S, if:BASIS STEP: P(x0) is true for the least element of S, andINDUCTION STEP: For every y S if P(x) is true for all x y, then P(y) is true.��19Lexicographic OrderThis ordering is called lexicographical because it is the way that words are ordered in the dictionary.2021For any positive integers m and n and a1a2…am and b1b2…bn in .1. If and ai = bi for all i = 1, 2, , . . ., m, thena1,a2…am b1b2….bn.2. If for some integer k withfor all i = 1,2,…,k-1, and ak R bk but , then a1,a2…am b1b2….bn.3. If is the null string and s is any string inthen s. m n�*�Let be a finite set and suppose R is a partial order relation defined on . Define a relation on , the set of all strings over , as follows:�*���, , and 1, i ik m k n k a b� � � =k ka b�ee*�22Hasse DiagramsGiven any partial order relation defined on a finite set, it is possible to draw the directed graph so that all of these properties are satisfied.This makes it possible to associate a somewhat simpler graph, called a Hasse diagram, with a partial order relation defined on a finite set.23Hasse Diagrams (continued)Start with a directed graph of the relation in which all arrows point upward. Then eliminate:1. the loops at all the vertices,2. all arrows whose existence is implied by the transitive property,3. the direction indicators on the arrows.24ExampleLet A = {1, 2, 3, 9, 19} and consider the “divides” relation on A:For all , , | for some integer .a b A a b b ka k� � =12391825ExampleEliminate the loops at all the vertices.123918Eliminate all arrows


View Full Document
Download Partial Orderings
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Partial Orderings and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Partial Orderings 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?