Det er et nyttigt værktøj, som fuldstændigt beskriver den tilhørende delrækkefølge. Derfor kaldes det også et bestillingsdiagram. Det er meget nemt at konvertere en rettet graf af en relation på et sæt A til et tilsvarende Hasse-diagram. Derfor skal følgende punkter huskes, når du tegner et Hasse-diagram.
- Toppunkterne i Hasse-diagrammet er angivet med punkter i stedet for med cirkler.
- Da en delrækkefølge er refleksiv, skal hvert hjørne af A derfor være relateret til sig selv, så kanterne fra et hjørne til sig selv slettes i Hasse-diagrammet.
- Da en partiel orden er transitiv, har vi derfor aRc, når som helst aRb, bRc. Eliminer alle kanter, der er underforstået af den transitive egenskab i Hasse-diagrammet, dvs. Slet kant fra a til c, men behold de to andre kanter.
- Hvis et toppunkt 'a' er forbundet med toppunkt 'b' med en kant, dvs. aRb, så vises toppunktet 'b' over toppunkt 'a'. Derfor kan pilen udelades fra kanterne i Hasse-diagrammet.
Hasse-diagrammet er meget enklere end den rettede graf af den delvise rækkefølge.
Eksempel: Overvej mængden A = {4, 5, 6, 7}. Lad R være relationen ≦ på A. Tegn den rettede graf og Hasse-diagrammet for R.
Løsning: Relationen ≦ på mængden A er givet ved
R = {{4, 5}, {4, 6}, {4, 7}, {5, 6}, {5, 7}, {6, 7}, {4, 4}, {5, 5} , {6, 6}, {7, 7}}
Den rettede graf for relationen R er som vist i fig.
For at tegne Hasse-diagrammet i delvis rækkefølge skal du anvende følgende punkter:
- Slet alle kanter underforstået af refleksiv egenskab, dvs.
(4, 4), (5, 5), (6, 6), (7, 7) - Slet alle kanter underforstået af transitiv egenskab, dvs.
(4, 7), (5, 7), (4, 6) - Udskift cirklerne, der repræsenterer hjørnerne, med prikker.
- Udelad pilene.
Hasse-diagrammet er som vist i fig.
Øvre grænse: Betragt B som en delmængde af en delvist ordnet mængde A. Et element x ∈ A kaldes en øvre grænse for B, hvis y ≦ x for hver y ∈ B.
Nedre grænse: Betragt B som en delmængde af en delvist ordnet mængde A. Et element z ∈ A kaldes en nedre grænse for B, hvis z ≦ x for hver x ∈ B.
Eksempel: Betragt sætningen A = {a, b, c, d, e, f, g} som vist i fig. Lad også B = {c, d, e}. Bestem den øvre og nedre grænse for B.
Løsning: Den øvre grænse for B er e, f og g, fordi hvert element i B er '≦' e, f og g.
De nedre grænser for B er a og b, fordi a og b er '≦' alle elementer i B.
Mindste øvre grænse (SUPREMUM):
Lad A være en delmængde af en delvist ordnet mængde S. Et element M i S kaldes en øvre grænse for A, hvis M efterfølger hvert element i A, dvs. hvis vi for hvert x i A har x<=m< p>
Hvis en øvre grænse for A går forud for hver anden øvre grænse af A, så kaldes den supremum af A og betegnes med Sup (A)
Største nedre grænse (INFIMUM):
Et element m i en poset S kaldes en nedre grænse for en delmængde A af S, hvis m går forud for hvert element i A, dvs. hvis vi for hvert y i A har m<=y < p>
Hvis en nedre grænse af A efterfølger hver anden nedre grænse af A, så kaldes den infimum af A og betegnes med Inf (A)
Eksempel: Bestem den mindste øvre grænse og den største nedre grænse for B = {a, b, c}, hvis de findes, for den poset, hvis Hasse-diagram er vist i fig.
Løsning: Den mindste øvre grænse er c.
Den største nedre grænse er k.