Partial OrdersOutlineMotivating Example (1)Motivating Example (2)Partial Orderings: DefinitionsPartial Orderings: NotationComparability: DefinitionTotal orders: DefinitionWell Orderings: DefinitionSlide 10Principle of Well-Ordered InductionPrinciple of Well-Ordered Induction: ProofSlide 13Lexicographic Orderings: IdeaLexicographic Orderings on A1A2Lexicographic Ordering on A1A2 … AnLexicographic Ordering on StringsSlide 18Hasse DiagramsHasse Diagram: ExampleHasse Diagrams: Example (1)Hasse Diagram: Example (2)Slide 23Extremal Elements: SummaryExtremal Elements: MaximalExtremal Elements: MinimalExtremal Elements: Upper BoundExtremal Elements: Lower BoundExtremal Elements: Example 1Extremal Elements: Example 2Extremal Elements: Example 3Slide 32LatticesLattices: Example 1Lattices: Example 2A Lattice Or Not a Lattice?Slide 37Topological SortingTopological Sorting: Preliminaries (1)Topological Sorting: Preliminaries (2)Topological Sorting: IntuitionTopological Sorting: AlgorithmTopological Sorting: ExampleSummaryPartial OrdersSection 8.6 of RosenFall 2008CSCE 235 Introduction to Discrete StructuresCourse web-page: cse.unl.edu/~cse235Questions: [email protected] OrdersCSCE 235, Fall 20082Outline•Motivating example•Definitions–Partial ordering, comparability, total ordering, well ordering•Principle of well-ordered induction•Lexicographic orderings•Hasse Diagrams•Extremal elements•Lattices•Topological SortingPartial OrdersCSCE 235, Fall 20083Motivating Example (1)•Consider the renovation of Avery Hall. In this process several tasks were undertaken–Remove Asbestos–Replace windows–Paint walls–Refinish floors–Assign offices–Move in office furniturePartial OrdersCSCE 235, Fall 20084Motivating Example (2)•Clearly, some things had to be done before others could begin–Asbestos had to be removed before anything (except assigning offices)–Painting walls had to be done before refinishing floors to avoid ruining them, etc.•On the other hand, several things could be done concurrently:–Painting could be done while replacing the windows–Assigning offices could be done at anytime before moving in office furniture•This scenario can be nicely modeled using partial orderingsPartial OrdersCSCE 235, Fall 20085Partial Orderings: Definitions •Definitions: –A relation R on a set S is called a partial order if it is•Reflexive•Antisymmetric•Transitive–A set S together with a partial ordering R is called a partially ordered set (poset, for short) and is denote (S,R) •Partial orderings are used to give an order to sets that may not have a natural one•In our renovation example, we could define an ordering such that (a,b)R if ‘a must be done before b can be done’Partial OrdersCSCE 235, Fall 20086Partial Orderings: Notation•We use the notation: –ab, when (a,b)R $\preccurlyeq$–ab, when (a,b)R and ab $\prec$•The notation is not to be mistaken for “less than”•The notation is used to denote any partial orderingPartial OrdersCSCE 235, Fall 20087Comparability: Definition•Definition: –The elements a and b of a poset (S,) are called comparable if either ab or ba. –When for a,bS, we have neither ab nor ba, we say that a,b are incomparable•Consider again our renovation example–Remove Asbestos ai for all activities ai except assign offices–Paint walls Refinish floors–Some tasks are incomparable: Replacing windows can be done before, after, or during the assignment of officesPartial OrdersCSCE 235, Fall 20088Total orders: Definition•Definition: –If (S,) is a poset and every two elements of S are comparable, S is called a totally ordered set. –The relation is said to be a total order•Example–The relation “less than or equal to” over the set of integers (Z, ) since for every a,bZ, it must be the case that ab or ba–What happens if we replace with <?The relation < is not reflexive, and (Z,<) is not a posetPartial OrdersCSCE 235, Fall 20089Well Orderings: Definition•Definition: (S,) is a well-ordered set if–It is a poset–Such that is a total ordering and–Such that every non-empty subset of S has a least element•Example–The natural numbers along with , (N ,), is a well-ordered set since any nonempty subset of N has a least element and is a total ordering on N–However, (Z,) is not a well-ordered set•Why?•Is it totally ordered?Z- Z but does not have a least elementYesPartial OrdersCSCE 235, Fall 200810Outline•Motivating example•Definitions–Partial ordering, comparability, total ordering, well ordering•Principle of well-ordered induction•Lexicographic orderings•Hasse Diagrams•Extremal elements•Lattices•Topological SortingPartial OrdersCSCE 235, Fall 200811Principle of Well-Ordered Induction•Well-ordered sets are the basis of the proof technique known as induction (more when we cover Chapter 3)•Theorem: Principle of Well-Ordered InductionGiven S is a well-ordered set. Then P(x) is true for all xS ifBasis Step: P(x0) is true for the least element in S andInduction Step: For every yS if P(x) is true for all xy, then P(y) is truePartial OrdersCSCE 235, Fall 200812Principle of Well-Ordered Induction: ProofProof: (S well ordered) (Basis Step) (Induction Step) xS, P(x)•Suppose that it is not the case the P(x) holds for all xS y P(y) is false A={ xS | P(x) is false } is not empty•S is well ordered A has a least element a•Since P(x0) is true and P(a) is false ax0•P(x) holds for all xS and xa, then P(a) holds by the induction step•This yields a contradiction QEDPartial OrdersCSCE 235, Fall 200813Outline•Motivating example•Definitions–Partial ordering, comparability, total ordering, well ordering•Principle of well-ordered induction•Lexicographic orderings–Idea, on A1A2, A1A2…An, St (strings)•Hasse Diagrams•Extremal elements•Lattices•Topological SortingPartial OrdersCSCE 235, Fall 200814Lexicographic Orderings: Idea•Lexigraphic ordering is the same as any dictionary or phone-book ordering:–We use alphabetic ordering •Starting with the first character in the string•Then the next character, if the first was equal, etc.–If a word is shorter than the other, than we consider that the ‘no character’ of the shorter word
View Full Document
Unlocking...