logo

Diagrammi di Hasse

È uno strumento utile, che descrive completamente l'ordine parziale associato. Pertanto, è anche chiamato diagramma di ordinamento. È molto semplice convertire un grafico orientato di una relazione su un insieme A in un diagramma di Hasse equivalente. Pertanto, mentre si disegna un diagramma di Hasse è necessario ricordare i seguenti punti.

  1. I vertici nel diagramma di Hasse sono indicati da punti anziché da cerchi.
  2. Poiché un ordine parziale è riflessivo, quindi ogni vertice di A deve essere correlato a se stesso, quindi gli spigoli da un vertice a se stesso vengono eliminati nel diagramma di Hasse.
  3. Poiché un ordine parziale è transitivo, quindi ogni volta che aRb, bRc, abbiamo aRc. Elimina tutti gli spigoli implicati dalla proprietà transitiva nel diagramma di Hasse, ovvero elimina lo spigolo da a a c ma mantieni gli altri due spigoli.
  4. Se un vertice 'a' è collegato al vertice 'b' da un bordo, cioè aRb, allora il vertice 'b' appare sopra il vertice 'a'. Pertanto, la freccia può essere omessa dai bordi del diagramma di Hasse.

Il diagramma di Hasse è molto più semplice del grafico orientato dell'ordine parziale.

Esempio: Consideriamo l'insieme A = {4, 5, 6, 7}. Sia R la relazione ≦ su A. Disegna il grafico orientato e il diagramma di Hasse di R.

Soluzione: La relazione ≦ sull'insieme A è data da

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

Il grafico diretto della relazione R è come mostrato in fig:

Diagrammi di Hasse

Per disegnare il diagramma di Hasse dell'ordine parziale, applicare i seguenti punti:

  1. Elimina tutti i bordi implicati dalla proprietà riflessiva, ad es.
    (4, 4), (5, 5), (6, 6), (7, 7)
  2. Elimina tutti i bordi implicati dalla proprietà transitiva, ad es.
    (4, 7), (5, 7), (4, 6)
  3. Sostituisci i cerchi che rappresentano i vertici con punti.
  4. Ometti le frecce.

Il diagramma di Hasse è quello mostrato in figura:

Diagrammi di Hasse

Limite superiore: Consideriamo B un sottoinsieme di un insieme parzialmente ordinato A. Un elemento x ∈ A è detto limite superiore di B se y ≦ x per ogni y ∈ B.

Limite inferiore: Consideriamo B un sottoinsieme di un insieme parzialmente ordinato A. Un elemento z ∈ A è detto limite inferiore di B se z ≦ x per ogni x ∈ B.

Esempio: Considera il poset A = {a, b, c, d, e, f, g} ordinato mostrato in fig. Sia anche B = {c, d, e}. Determinare il limite superiore e inferiore di B.

Diagrammi di Hasse

Soluzione: Il limite superiore di B è e, f e g perché ogni elemento di B è '≦' e, f e g.

I limiti inferiori di B sono a e b perché a e b sono '≦' tutti gli elementi di B.

Limite minimo superiore (SUPREMUM):

Sia A un sottoinsieme di un insieme parzialmente ordinato S. Un elemento M in S è detto limite superiore di A se M succede a ogni elemento di A, cioè se, per ogni x in A, abbiamo x<=m< p>

Se un limite superiore di A precede ogni altro limite superiore di A, allora è chiamato estremo superiore di A ed è indicato con Sup (A)

Limite inferiore massimo (INFIMUM):

Un elemento m in un poset S è detto limite inferiore di un sottoinsieme A di S se m precede ogni elemento di A, cioè se, per ogni y in A, abbiamo m<=y < p>

Se un limite inferiore di A segue ogni altro limite inferiore di A, allora è chiamato estremo inferiore di A ed è indicato con Inf (A)

Esempio: Determina il limite minimo superiore e il limite massimo inferiore di B = {a, b, c} se esistono, del poset il cui diagramma di Hasse è mostrato in fig:

Diagrammi di Hasse

Soluzione: Il limite superiore minimo è c.

Il limite inferiore massimo è k.