Analisi e Verifica di Programmi

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:
antisimmetrica:
" l1, l2, l3  L : l1 l2  l2 l3  l1 l3
" l1, l2  L : l1 l2  l2 l1  l1= l2
Un poset (L, ) è insieme parzialmente ordinato, ovvero è un
insieme L sul quale è definito un ordine parziale .
Tino Cortesi
Tecniche di Analisi di Programmi
2
Diagramma di Hasse
Un diagramma di Hasse di un poset (L, ) è un grafo con
vertici: gli elementi di L
archi: le coppie (a,b) tali che ab e non esiste c  L tale che
a<c<b
gli archi sono disegnati dal basso all’alto
gli archi non si incrociano mai
Tino Cortesi
Tecniche di Analisi di Programmi
3
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, ) è poset, ovvero un un insieme parzialmente
ordinato (finito)
Tino Cortesi
Tecniche di Analisi di Programmi
4
Esempio
6
5
L= N
 ={(0,1), (1,2), (2,3), (3,4), (4,5),…}T
4
3
2
(L, ) è un insieme totalmente ordinato (infinito)
1
0
Tino Cortesi
Tecniche di Analisi di Programmi
5
Esempio
9
8
7
6
5
4
3
2
Tino Cortesi
L= N
 ={(n,m): $ k tale che m=n*k}
(L, ) è un insieme parzialmente ordinato (infinito)
Tecniche di Analisi di Programmi
6
Esempio
A partire dallo stesso insieme E={1,2,3,4,6,12}
possono essere definiti diversi ordini parziali:
12
12
6
4
3
2
12
6
6
4
3
2
1
1
Ordine usuale
Tino Cortesi
4
2
3
1
Ordine indotto
dalla divisibilità
Tecniche di Analisi di Programmi
Numeri dispari
minori dei pari
7
Esempio
Tutti i possibili insiemi parzialmente ordinati con tre
elementi:
Tino Cortesi
Tecniche di Analisi di Programmi
8
Composizione di ordini parziali
Prodotto cartesiano
Dati due ordini parziali (P, p ) ed (T, t ), il prodotto
cartesiano (P  T, P  T) ha come elementi le coppie in
{(p,t)) | p
 P, t  T}
L’ordine parziale: (x1,y1) P  T (x2,y2)  x1P x2  y1T y2
Tino Cortesi
Tecniche di Analisi di Programmi
9
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
10
Composizione di ordini parziali
Unione disgiunta
Dati due ordini parziali (P, p ) ed (T, t ), l’unione disgiunta
(P e T, P e T) ha come elementi {x | x
L’ordine parziale: x P e T y  x,y
P
 P oppure x  T}
e x P y
oppure
x,y  t e x t y
Tino Cortesi
Tecniche di Analisi di Programmi
11
Esempio
P
Tino Cortesi
T
(P e T, P e T)
Tecniche di Analisi di Programmi
12
Composizione di ordini parziali
Somma lineare
Dati due ordini parziali (P, p ) ed (T, t ), la somma lineare
(P t T, P t T) ha come elementi {x | x  P oppure x
 T}
L’ordine parziale: x P t T y  x,y  P e x P y
Oppure
x,y  t e x t y
Oppure
xP e yt .
Tino Cortesi
Tecniche di Analisi di Programmi
13
Esempio
P
Tino Cortesi
T
PtT
Tecniche di Analisi di Programmi
14
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
15
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
16
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
17
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
18
Down-sets e Up-sets
Dato un insieme parzialmente ordinato P,
Un sottoinsieme D di P è un down-set se
per ogni x  D, e per ogni y  P, se y  x allora y  D.
Un sottoinsieme D di P è un up-set se
per ogni x  D, e per ogni y  P, se x  y allora y  D.
Tino Cortesi
b
c
a
d
{a,b,d} è un down-set
{b,c,d} è un up-set
{a,b} è un up-set ma non un down-set
Tecniche di Analisi di Programmi
19
Down-sets e up-sets
In particolare, se Q è un qualsiasi sottoinsieme di P, definiamo
iQ = {y  P | (esiste x  Q) y  x } è un down-set
hQ = {y  P | (esiste x  Q) x  y } up-set
Se x è un qualsiasi elemento di P, definiamo
ix = {y  P | y  x }
hx = {y  P | x  y }
In questo caso si chiamano down-sets e up-sets principali
Tino Cortesi
Tecniche di Analisi di Programmi
20
Down-sets e Up-sets
i{b,d} = {a,b,d}
h{c,d} = {b,c,d}
b
a
Tino Cortesi
c
d
ib = {a,b,d}
ic = {c,d}
hd = {b,c,d}
ha = {a,b}
hb = {b}
Tecniche di Analisi di Programmi
21
Esempio
Consideriamo l’insieme dei numeri razionali positivi Q.
L’insieme S={q  Q | q2  2 } è un insieme chiuso verso il basso
(down-set) che non è principale.
Infatti non esiste nessun numero razionale q tale che S= iq.
Tino Cortesi
Tecniche di Analisi di Programmi
22
L’ordine parziale
dei down-sets di P
Dato un insieme parzialmente ordinato P, la famiglia O(P) di tutti
i down-sets di P è un insieme parzialmente ordinato.
{a,b,c,d}
{a,b,d}
b
c
a
d
{a, c,d}
{a,d}
{a}
{c,d}
{d}

Tino Cortesi
Tecniche di Analisi di Programmi
23
Lemma
Sia P un ordine parziale e x,y due suoi elementi. Sono
equivalenti:
xy
ix  iy
" Q  O(P). y  Q _ x  Q
Esercizio: dimostrarlo!
Tino Cortesi
Tecniche di Analisi di Programmi
24
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
25
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
26
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
27
Esempi
S2
S1
L’insieme S1 è diretto
Tino Cortesi
L’insieme S2 non è diretto
Tecniche di Analisi di Programmi
28
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
29
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
30
Insiemi diretti e catene
T
Sia (P,P) un insieme
parzialmente ordinato. Ogni
catena non vuota di P è un
insieme diretto.
Esercizio: dimostrarlo!
h
e
a
i
f
6
j
5
4
g
b
c
3
2
d
1
0
^
Tino Cortesi
Tecniche di Analisi di Programmi
31
Insiemi diretti
In (N),) l’insieme S=U{X  N | X è finito} è diretto?
Dim: Sia F  S, F finito. Devo dimostrare che esiste un upper
bound di F che appartiene a S.
Prendo come upper bound di F l’unione degli insiemi in F.
L’unione finita di insiemi finiti è finita (la cardinalità è al più la
somma delle cardinalità degli insiemi), e quindi appartiene a S.
In (N),) l’insieme S=U{X  N | N-X è finito} è diretto?
Tino Cortesi
Tecniche di Analisi di Programmi
32
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
33
Esempio
Rivediamo tutti i possibili insiemi ordinati con tre elementi: sono
reticoli?
SI
Tino Cortesi
NO
NO
Tecniche di Analisi di Programmi
NO
NO
34
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
35
Il reticolo dei down-sets
Se P è un insieme ordinato e A e B sono due down-sets di P,
allora:
A  B è un down-set
A  B è un down-set
L’insieme O(P) dei down-sets di P è un reticolo:
lub(A,B)= A  B e glb(A,B)= A  B.
Il bottom del reticolo O(P) è l’insieme vuoto
Il top del reticolo O(P) è l’insieme P
Tino Cortesi
Tecniche di Analisi di Programmi
36
Il reticolo O(P)
Esempio
{a,b,c,d}
{a,b,d}
b
c
a
d
{a, c,d}
{a,d}
{a}
{c,d}
{d}

Tino Cortesi
Tecniche di Analisi di Programmi
37
Esercizi
Costruire il reticolo O(P) quando P è il seguente ordine parziale:
b
c
a
d
e
Costruire il reticolo O(P) quando P è il seguente ordine parziale:
Tino Cortesi
Tecniche di Analisi di Programmi
38
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
39
Esempio
E’ un CPO
(c’è il bottom e ogni sottoinsieme diretto ha lub),
ma non è un reticolo
Tino Cortesi
Tecniche di Analisi di Programmi
40
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:
^ = glb(L)
T = lub(L)
bottom element
top element
Ogni reticolo finito è un reticolo completo
Ogni reticolo completo è un CPO
Tino Cortesi
Tecniche di Analisi di Programmi
41
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
42
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
43
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
44
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
45
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
46
Esempio
T’
T
7’
L= Z+  {T}  Z’+-{0}  {T}
6
 ordine totale su Z+  {T}
6’
5
 ordine totale su Z’+  {T’}
5’
4
4’
Bottom element: 0
3
2
E’ un CPO ma non è un reticolo
1
3’
2’
1’
0
Tino Cortesi
Tecniche di Analisi di Programmi
47
Esempi
Consideriamo 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
Consideriamo 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
48
Teorema: Se (L, ) è un reticolo, 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
49
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

50
Esempio
Si consideri l’insieme dei numeri interi non negativi, ordinati per
divisione:
n d m se $ h tale che m=n*h
Ricordiamo che k è il massimo comun divisore di due interi se:
k divide sia n che m (e quindi k d n e k d m)
Se j divide sia m che n, allora j divide k, cioè j d k per tutti i
lower-bounds j di {m,n}.
Allora il massimo comun divisore di m ed n è proprio il greatest
lower bound di m ed n (e dualmente, il minimo comune multiplo
è il least upper bound). Si può dimostrare che è un reticolo.
Tino Cortesi
Tecniche di Analisi di Programmi
51