logo

Hasse Diagrammer

Det er et nyttig verktøy, som fullstendig beskriver den tilhørende delrekkefølgen. Derfor kalles det også et bestillingsdiagram. Det er veldig enkelt å konvertere en rettet graf av en relasjon på et sett A til et ekvivalent Hasse-diagram. Derfor må følgende punkter huskes når du tegner et Hasse-diagram.

  1. Toppunktene i Hasse-diagrammet er angitt med punkter i stedet for med sirkler.
  2. Siden en delrekkefølge er refleksiv, må derfor hvert toppunkt av A være relatert til seg selv, så kantene fra et toppunkt til seg selv blir slettet i Hasse-diagrammet.
  3. Siden en delvis rekkefølge er transitiv, har vi derfor aRc når aRb, bRc. Eliminer alle kanter som er antydet av den transitive egenskapen i Hasse-diagrammet, dvs. Slett kant fra a til c, men behold de to andre kantene.
  4. Hvis et toppunkt 'a' er forbundet med toppunkt 'b' med en kant, dvs. aRb, så vises toppunktet 'b' over toppunkt 'a'. Derfor kan pilen utelates fra kantene i Hasse-diagrammet.

Hasse-diagrammet er mye enklere enn den rettede grafen for delrekkefølgen.

Eksempel: Tenk på settet A = {4, 5, 6, 7}. La R være relasjonen ≦ på A. Tegn den rettede grafen og Hasse-diagrammet til R.

Løsning: Relasjonen ≦ på mengden A er gitt ved

R = {{4, 5}, {4, 6}, {4, 7}, {5, 6}, {5, 7}, {6, 7}, {4, 4}, {5, 5} , {6, 6}, {7, 7}}

Den rettede grafen for relasjonen R er som vist i fig.

Hasse-diagrammer

For å tegne Hasse-diagrammet i delvis rekkefølge, bruk følgende punkter:

  1. Slett alle kanter implisert av refleksiv egenskap, dvs.
    (4, 4), (5, 5), (6, 6), (7, 7)
  2. Slett alle kanter implisert av transitiv egenskap, dvs.
    (4, 7), (5, 7), (4, 6)
  3. Bytt ut sirklene som representerer toppunktene med prikker.
  4. Utelat pilene.

Hasse-diagrammet er som vist i fig.

Hasse-diagrammer

Øvre grense: Betrakt B som en delmengde av et delvis ordnet sett A. Et element x ∈ A kalles en øvre grense for B hvis y ≦ x for hver y ∈ B.

Nedre grense: Betrakt B som en delmengde av et delvis ordnet sett A. Et element z ∈ A kalles en nedre grense av B hvis z ≦ x for hver x ∈ B.

Eksempel: Tenk på at stillingen A = {a, b, c, d, e, f, g} er ordnet vist i fig. La også B = {c, d, e}. Bestem øvre og nedre grense for B.

Hasse Diagrammer

Løsning: Den øvre grensen til B er e, f og g fordi hvert element i B er '≦' e, f og g.

De nedre grensene til B er a og b fordi a og b er '≦' alle elementene i B.

Minste øvre grense (SUPREMUM):

La A være en delmengde av en delvis ordnet mengde S. Et element M i S kalles en øvre grense for A hvis M følger etter hvert element i A, dvs. hvis vi for hver x i A har x<=m< p>

Hvis en øvre grense av A går foran annenhver øvre grense av A, kalles den supremum av A og betegnes med Sup (A)

Største nedre grense (INFIMUM):

Et element m i en posett S kalles en nedre grense for en delmengde A av S hvis m går foran hvert element i A, dvs. hvis vi for hver y i A har m<=y < p>

Hvis en nedre grense av A etterfølger annenhver nedre grense av A, kalles den infimum av A og betegnes med Inf (A)

Eksempel: Bestem den minste øvre grensen og største nedre grensen for B = {a, b, c} hvis de eksisterer, for stillingen hvis Hasse-diagram er vist i fig.

Hasse Diagrammer

Løsning: Den minste øvre grensen er c.

Den største nedre grensen er k.