Date post: | 01-May-2015 |
Category: |
Documents |
Upload: | luciano-dolce |
View: | 222 times |
Download: | 3 times |
Ordini Parziali - Reticoli
Tino Cortesi Tecniche di Analisi di Programmi 2
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 3
Esempio
a b
c d e f
g
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 4
Esempio
(x1,y1) N N (x2,y2) x1N x2 y1N y2
(N N, N N) è un insieme parzialmente ordinato (infinito)
N N
a
b cb N N c
a N N c
Tino Cortesi Tecniche di Analisi di Programmi 5
EsempioTutti i possibili insiemi ordinati con tre elementi:
Tino Cortesi Tecniche di Analisi di Programmi 6
lub e glbDato 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 sel’ 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’ l0Se 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 7
Esempio
(x1,y1) N N (x2,y2) x1N x2 y1N
y2
N N
Y
lower bounds di Y
upper bounds di Y
lub(Y)
glb(Y)
Tino Cortesi Tecniche di Analisi di Programmi 8
Esempio
c dba
g
jih
fe
T
lub({b,c})= ?
Gli upper bounds dell’insieme {b,c} sono {h,i,T}
e questo insieme non ha un minimo elemento:
Il lub non c’è !
T
ih
Tino Cortesi Tecniche di Analisi di Programmi 9
Esempio
c dba
g
jih
fe
T
lub({a,b})= ?
Gli upper bounds dell’insieme {a,b} sono {T,h,i,f}
e questo insieme ha un f come minimo elemento:
lub({a,b})= f
ih
f
T
Tino Cortesi Tecniche di Analisi di Programmi 10
ReticoliUn 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 xy, 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 11
EsempioRivediamo tutti i possibili insiemi ordinati con tre elementi: sono reticoli?
SI NO NO NO NO
Tino Cortesi Tecniche di Analisi di Programmi 12
Esempio
a b
c d e f
g
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
Y
Tino Cortesi Tecniche di Analisi di Programmi 13
CateneDato 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)nN di elementi di L è una catena ascendente se
n m ln lm
Tino Cortesi Tecniche di Analisi di Programmi 14
Esempio: catene
c dba
g
jih
fe
T
c dba
g
jih
fe
T
Tino Cortesi Tecniche di Analisi di Programmi 15
Insiemi DirettiSia (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 16
Esempio
2 3 4 1 0 -1 -2 -3 -4
T
L= Z {T,}
n Z : n T
SF
S non è un insieme diretto:non esiste un elemento di S che appartiene all’insieme degli upper bounds di F
Tino Cortesi Tecniche di Analisi di Programmi 17
Esempio
2 3 4 1 0 -1 -2 -3 -4
T
L= Z {T,}
n Z : n T
S
F
S è un insieme diretto: per ogni F finitoesiste un elemento di S che appartiene all’insieme degli upper bounds di F
Tino Cortesi Tecniche di Analisi di Programmi 18
Insiemi diretti e catene
Sia (P,P) un insieme parzialmente ordinato. Ogni catena non vuota di P è un insieme diretto.
c dba
g
jih
fe
T
0
1
2
3
4
5
6
Tino Cortesi Tecniche di Analisi di Programmi 19
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 20
CPOUn 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 21
Reticoli completiUn 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() bottom elementT = glb(L) top element
Ogni reticolo finito è un reticolo completoOgni reticolo completo è un CPO
Tino Cortesi Tecniche di Analisi di Programmi 22
Esempio
{3}{2}{1}
{2,3}{1,3}{1,2}
{1,2,3}
L= ({1,2,3})
= lub(Y) = Yglb(Y) = Y
Tino Cortesi Tecniche di Analisi di Programmi 23
Esempio
{3}{2}{1}
{2,3}{1,3}{1,2}
{1,2,3}
L= ({1,2,3})
= lub(Y) = Yglb(Y) = Y
Y
lub(Y)
glb(Y)
Tino Cortesi Tecniche di Analisi di Programmi 24
Esempio
2 3 4 1 0 -1 -2 -3 -4
T
L= Z {T,}
n Z : n T
Tino Cortesi Tecniche di Analisi di Programmi 25
Esempio
0
1
2
3
4
5
6L= Z+
ordine totale su Z+ lub = maxglb = min
E’ un reticolo, ma non completo:Ad es. l’insieme dei pari non ha
lub
Tino Cortesi Tecniche di Analisi di Programmi 26
Esempio
0
1
2
3
4
5
6
T
L= Z+ {T}
ordine totale su Z+ {T}lub = maxglb = min
E’ un reticolo completo
Tino Cortesi Tecniche di Analisi di Programmi 27
EsempiL=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 28
Teorema: Se (L, ) è un insieme parzialmente ordinato, sono equivalenti:
1. L è un reticolo completo2. ogni sottoinsieme di L ha un least upper bound3. 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({lL | 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 29
Y
Esempio
{3}{2}{1}
{2,3}{1,3}{1,2}
{1,2,3}
Z= {lL | l’ Y : l l’}
lub(Z)
glb(Y)= lub({lL | l’ Y : l l’})
upper bounds di Z