Ordini Parziali - Reticoli
Insiemi parzialmente ordinati
Nell’analisi di programmi ordini parziali e reticoli giocano un
ruolo importantissimo
Dato un insieme L, un ordine parziale su L è una relazione
: L  L  {vero, falso}
che gode delle proprietà:
riflessiva:
"lL : l l
transitiva:
" l1, l2, l3  L : l1 l2  l2 l3  l1 l3
antisimmetrica:
" l1, l2  L : l1 l2  l2 l1  l1= l2
Un insieme parzialmente ordinato (L, ) è un insieme L sul
quale è definito un ordine parziale .
Tino Cortesi
Tecniche di Analisi di Programmi
2
Esempio
g
c
d
e
a
f
b
L= {a,b,c,d,e,f,g}
 ={(a,c), (a,e), (b,d), (b,f), (c,g), (d,g), (e,g), (f,g)}T
(L, ) è un insieme parzialmente ordinato (finito)
Tino Cortesi
Tecniche di Analisi di Programmi
3
Esempio
NN
b
c
a N  N c
b N  N c
a
(x1,y1) N  N (x2,y2)  x1N x2  y1N y2
(N  N, N  N) è un insieme parzialmente ordinato (infinito)
Tino Cortesi
Tecniche di Analisi di Programmi
4
Esempio
Tutti i possibili insiemi ordinati con tre elementi:
Tino Cortesi
Tecniche di Analisi di Programmi
5
lub e glb
Dato un insieme parzialmente ordinato (L, ),
un insieme Y di L ha un elemento l come upper bound se
" l’  Y : l’  l
un insieme Y di L ha un elemento l come lower bound se
" l’  Y : l  l’
Un least upper bound (lub) di Y è un upper bound l0 di Y che
soddisfa la seguente proprietà:
l’ è un upper bound di Y  l0  l’
Un greatest lower bound (glb) di Y è un lower bound l0 di Y che
soddisfa la seguente proprietà:
l’ è un lower bound di Y  l’  l0
Se un sottoinsieme Y di L ha un least upper bound, questo è
unico (per la proprietà antisimmetrica dell’ordine parziale )
Tino Cortesi
Tecniche di Analisi di Programmi
6
Esempio
NN
upper bounds di Y
Y
lub(Y)
glb(Y)
lower bounds di Y
(x1,y1) N  N (x2,y2)  x1N x2  y1N y2
Tino Cortesi
Tecniche di Analisi di Programmi
7
Esempio
T
lub({b,c})= ?
h
i
e
f
g
a
b
c
^
j
Gli upper bounds dell’insieme {b,c} sono {h,i,T}
T
d
h
i
e questo insieme non ha un minimo elemento:
Il lub non c’è !
Tino Cortesi
Tecniche di Analisi di Programmi
8
Esempio
lub({a,b})= ?
T
Gli upper bounds dell’insieme {a,b} sono {T,h,i,f}
h
i
e
f
g
a
b
c
j
T
h
i
d
f
^
e questo insieme ha un f come minimo elemento:
lub({a,b})= f
Tino Cortesi
Tecniche di Analisi di Programmi
9
Reticoli
Un reticolo è un insieme parzialmente ordinato (L, )
tale che per ogni coppia di elementi di L esiste il least
upper bound ed il greatest lower bound.
Se L è un insieme parzialmente ordinato non vuoto, e
xy, allora
lub({x,y}) = y
glb({x,y}) = x.
Per dimostrare che L è un reticolo basterà quindi
verificare che per ogni coppia di elementi incomparabili
esistano sia lub che glb.
Tino Cortesi
Tecniche di Analisi di Programmi
10
Esempio
Rivediamo tutti i possibili insiemi ordinati con tre elementi: sono
reticoli?
SI
Tino Cortesi
NO
NO
Tecniche di Analisi di Programmi
NO
NO
11
Esempio
g
Y
c
d
e
a
f
b
L= {a,b,c,d,e,f,g}
 ={(a,c), (a,e), (b,d), (b,f), (c,g), (d,g), (e,g), (f,g)}T
(L,) non è un reticolo:
sia a che b sono lower bounds di Y, ma a e b sono incomparabili
Tino Cortesi
Tecniche di Analisi di Programmi
12
Catene
Dato un insieme parzialmente ordinato (L,), un sottoinsieme Y
di L è una catena se
" l1, l2  Y : (l1 l2)  (l2 l1)
ovvero una catena è un sottoinsieme di L totalmente ordinato.
Un insieme parzialmente ordinato (L,) ha altezza finita se e
solo se tutte le catene di L sono finite
Una sequenza (ln)nN di elementi di L è una catena ascendente
se
n  m  ln lm
Tino Cortesi
Tecniche di Analisi di Programmi
13
Esempio: catene
T
h
i
e
f
g
a
b
c
T
j
d
h
i
e
f
g
a
b
c
^
Tino Cortesi
j
d
^
Tecniche di Analisi di Programmi
14
Insiemi Diretti
Sia (P,P) un insieme parzialmente ordinato.
Un sottoinsieme S di P si dice diretto se per ogni
sottoinsieme finito F di S esiste un elemento di S che
appartiene all’insieme degli upper bounds di F.
Tino Cortesi
Tecniche di Analisi di Programmi
15
Esempio
T
F
-4
-3
-2
-1
0
1
2
3
S
4
^
L= Z  {T,^}
"n Z : ^ n T
Tino Cortesi
S non è un insieme diretto:
non esiste un elemento di S che appartiene
all’insieme degli upper bounds di F
Tecniche di Analisi di Programmi
16
Esempio
S
T
F
-4
-3
-2
-1
0
1
2
3
4
^
L= Z  {T,^}
"n Z : ^ n T
Tino Cortesi
S è un insieme diretto: per ogni F finito
esiste un elemento di S che appartiene
all’insieme degli upper bounds di F
Tecniche di Analisi di Programmi
17
Insiemi diretti e catene
T
Sia (P,P) un insieme
parzialmente ordinato. Ogni
catena non vuota di P è un
insieme diretto.
h
e
a
i
f
6
j
5
4
g
b
c
3
2
d
1
0
^
Tino Cortesi
Tecniche di Analisi di Programmi
18
Insiemi diretti
In (N),) l’insieme S={X  N | X è finito} è diretto?
In (N),) l’insieme S={X  N | N-X è finito} è diretto?
Tino Cortesi
Tecniche di Analisi di Programmi
19
CPO
Un insieme parzialmente ordinato (P,P) si dice CPO (insieme
completo parzialmente ordinato) se:
Esiste un elemento minimo (bottom)
Per ogni sottoinsieme diretto S di P esiste lub(S).
Tino Cortesi
Tecniche di Analisi di Programmi
20
Reticoli completi
Un reticolo completo è un insieme parzialmente ordinato
(L, ) tale che tutti i sottoinsiemi di L hanno least upper
bound e greatest lower bound.
Se (L, ) è un reticolo completo, si denotano:
^ = lub()
T = glb(L)
bottom element
top element
Ogni reticolo finito è un reticolo completo
Ogni reticolo completo è un CPO
Tino Cortesi
Tecniche di Analisi di Programmi
21
Esempio
{1,2,3}
L= ({1,2,3})
{1,2}
{1,3}
{2,3}
{1}
{2}
{3}
=
lub(Y) = Y
glb(Y) = Y
Tino Cortesi

Tecniche di Analisi di Programmi
22
Esempio
{1,2,3}
lub(Y)
{1,2}
{1,3}
{2,3}
Y
{1}
{2}
{3}
L= ({1,2,3})
=
lub(Y) = Y
glb(Y) = Y
Tino Cortesi

glb(Y)
Tecniche di Analisi di Programmi
23
Esempio
T
-4
-3
-2
L= Z  {T,^}
-1
0
1
2
3
4
^
"n Z : ^ n T
Tino Cortesi
Tecniche di Analisi di Programmi
24
Esempio
L= Z+
 ordine totale su Z+
lub = max
glb = min
5
4
3
2
E’ un reticolo, ma non completo:
Ad es. l’insieme dei pari non ha lub
Tino Cortesi
6
Tecniche di Analisi di Programmi
1
0
25
Esempio
T
L= Z+  {T}
6
 ordine totale su Z+  {T}
5
lub = max
glb = min
4
3
2
E’ un reticolo completo
Tino Cortesi
Tecniche di Analisi di Programmi
1
0
26
Esempi
L=R (numeri reali) con  ordine totale
(R,  ) non è un reticolo completo:
ad esempio {x  R | x > 2} non ha lub
Per ogni x<y in R, ([x,y],  ) è un reticolo completo
L=Q (numeri razionali) con  ordine totale
(Q,  ) non è un reticolo completo
E non basta aggiungere un top ed un bottom per ottenere la
completezza:
l’insieme {x  Q | x2 < 2} ha upper bounds ma non ha un
least upper bound.
Tino Cortesi
Tecniche di Analisi di Programmi
27
Teorema: Se (L, ) è un insieme parzialmente ordinato, sono
equivalenti:
1. L è un reticolo completo
2. ogni sottoinsieme di L ha un least upper bound
3. ogni sottoinsieme di L ha un greatest lower bound
Dimostrazione:
1  2 e 1  3 seguono immediatamente dalla definizione
Per mostrare che 2  1, basta definire per ogni Y  L
glb(Y) = lub({l L | " l’  Y : l  l’})
Tutti gli elementi dell’insieme a destra sono lower bounds
dell’insieme Y. Quindi lub({...}) definisce un lower bound di Y.
Poiché tutti i lower bound di Y appartengono all’insieme a destra,
lub({...}) definisce il greatest lower bound di Y.
Tino Cortesi
Tecniche di Analisi di Programmi
28
Esempio
{1,2,3}
glb(Y)= lub({l L | " l’  Y : l  l’})
Y
lub(Z)
{1,2}
{1,3}
{2,3}
{1}
{2}
{3}
Z= {l L | " l’  Y : l  l’}
Tino Cortesi
upper bounds di Z
Tecniche di Analisi di Programmi

29