Discrete Mathematic教学课件（华南理工大学）Ch05-6 PartialOrderings2.pdfVIP

Discrete Mathematic Chapter 5: Relation 5.6 Partial Orderings Dr Patrick Chan School of Computer Science and Engineering South China University of Technology Agenda Partial Order Total Order Lexicographic Order Hasse Diagrams Minimal/Maximal Element Least/Greatest Element Lower/Upper Bound Greatest Lower/Least Upper Bound Chapter 5.6 Partial Orderings 2 What is Order? Chapter 5.6 Partial Orderings 3 What is Order? Equivalence (=) concept is discussed The abstraction of the following relations will be discussed in this chapter Bigger or Equal / Smaller or Equal (≤, ≥) Bigger / Smaller ( , ) Chapter 5.6 Partial Orderings 4 What is Order? What properties “≤” or “≥” should have? Reflexive Irreflexive Transitive Symmetri cAsymmetri cAntisymmetri What properties “” or “” should have? Reflexive Irreflexive Transitive Symmetri cAsymmetri cAntisymmetri Chapter 5.6 Partial Orderings 5 Partially Ordered Set Definition Let R be a relation on A. Then R is a partial order iff R is Reflexive ∀a ( (a, a) ∈ R ) Antisymmetric ∀a ∀b ( ((a, b)∈R ∧ (b, a)∈R) → (a = b) ) Transitive ∀a∀b∀ c( ((a,b)∈R∧(b,c)∈R) → ((a,c)∈R)) a b a b a b d d d Not Partial Order Partial Order Partial Order Chapter 5.6 Partial Orderings 6 Partially Ordered Set When