www.matapp.unimib.it/$sim $marina/did/mdis03/
Matematica Discreta (elementi) – E-O
CdL Informatica
10 dicembre 2003
Marina Cazzola ([email protected])
Dipartimento di Matematica e Applicazioni
Università di Milano–Bicocca
Matematica Discreta (elementi) – E-O – p. 1
www.matapp.unimib.it/$sim $marina/did/mdis03/
Avvertenze
Queste fotocopie sono distribuite solo come indicazionedegli argomenti svolti a lezione e NON sostituiscono in
alcun modo il libro di testo:
A. Facchini, “Algebra e matematica discreta”,Decibel–Zanichelli
Al libro di testo si rimanda per l’effettivo svolgimento degliargomenti (e per la rettifica di eventuali errori contenuti in
queste pagine).
Matematica Discreta (elementi) – E-O – p. 2
www.matapp.unimib.it/$sim $marina/did/mdis03/
Insiemi (parzialmente) ordinati
Matematica Discreta (elementi) – E-O – p. 3
www.matapp.unimib.it/$sim $marina/did/mdis03/
Relazioni d’ordine
Dato un insieme A, una relazione ≤ su A è dettarelazione di ordine o semplicemente ordinamento su Ase ≤ è
riflessiva
antisimmetrica
transitiva
ovvero se
∀a ∈ A a≤ a
∀a, b ∈ A(
a≤ b ∧ b≤ a)
→ a = b
∀a, b, c ∈ A (a≤ b ∧ b≤ c) → (a≤ c)
Matematica Discreta (elementi) – E-O – p. 4
www.matapp.unimib.it/$sim $marina/did/mdis03/
Insiemi ordinati
Definizione – Un insieme è detto (parzialmente)ordinato se in A è definita una relazione di ordine ≤.
Definizione – Una relazione d’ordine ≤ è dettaordinamento totale se
∀a, b ∈ A (a ≤ b) ∨ (b ≤ a)
Definizione – Un insieme A è detto totalmenteordinato se su A è definita una relazione d’ordine totale.
Esempio – Z con la relazione d’ordine ≤(cfr. 19 novembre 2003) è totalmente ordinato.
Matematica Discreta (elementi) – E-O – p. 5
www.matapp.unimib.it/$sim $marina/did/mdis03/
Restrizione di una relazione
Sia A un insieme su cui è definita una relazione R, e Bun sottoinsieme di A
Definizione – La restrizione RB di R a B è ilsottoinsieme di B× B dato da
RB = R∩(
B× B)
Osserviamo che
se R è riflessiva, allora RB è riflessiva
se R è simmetrica, allora RB è simmetrica
se R è antisimmetrica, allora RB è antisimmetrica
se R è transitiva, allora RB è transitivaMatematica Discreta (elementi) – E-O – p. 6
www.matapp.unimib.it/$sim $marina/did/mdis03/
Esempi
Consideriamo A = {2, 3, 4, 6, 12} ⊆ Z con la relazione≤A (cioè la restrizione di ≤ da Z a A)
Dal momento che ≤ è un ordinamento (totale) su Z, siha che ≤A è un ordinamento (totale) su AEssendo A un insieme finito, possiamo disegnare ildiagramma di ≤
2
3
4
6
12
Matematica Discreta (elementi) – E-O – p. 7
www.matapp.unimib.it/$sim $marina/did/mdis03/
Troppe frecce!
Se sappiamo di avere a che fare con una relazione diordine possiamo accordarci per omettere dal diagrammaalcune frecce
su ogni elemento è presente un cappio, conveniamoallora di ometterli
dal momento che vale la proprietà transitiva, perogni terna di elementi a, b e c di A, ogni volta che ci
sono due frecce consecutive a b c alloradeve esserci anche la freccia che congiunge
direttamente a con c a b c conveniamo
allora di omettere quest’ultima freccia.Matematica Discreta (elementi) – E-O – p. 8
www.matapp.unimib.it/$sim $marina/did/mdis03/
Esempi
Con questa nuova convenzione, possiamo ripulire ildiagramma
2
3
4
6
12
Infatti, sapendo che la relazione è un ordinamento, lequattro condizioni
2 ≤ 3 3 ≤ 4 4 ≤ 6 6 ≤ 12
permettono di ricavare le condizioni per qualsiasi coppiadi elementi di A.
Matematica Discreta (elementi) – E-O – p. 9
www.matapp.unimib.it/$sim $marina/did/mdis03/
Esercizi
Sia A = {2, 3, 4, 6, 12}.
Mostrare che la relazione d’ordine ≤ vista è unordinamento totale su A
Si consideri in A la relazione
aRb se e solo se a | b
mostrare che R è una relazione di ordine su A
disegnare il diagramma di R
Matematica Discreta (elementi) – E-O – p. 10
www.matapp.unimib.it/$sim $marina/did/mdis03/
Esempio
Si consideri in Z la relazione a | b (cioè a e b sono inrelazione se e soltanto se a divide b).In altre parole
a | b se e soltanto se ∃k ∈ Z b = a · k
| è riflessiva: ∀a ∈ Z (a | a)
| è transitiva: ∀a, b, c ∈ Z, se a | b e b | c allora si haa | c.Infatti si si hanno h, k ∈ Z tali che b = k · a ec = h · b, allora c = h · (k · a) = (h · k) · a
ma | non è antisimmetrica: 2 | −2 e −2 | 2, ma2 6= −2
Matematica Discreta (elementi) – E-O – p. 11
www.matapp.unimib.it/$sim $marina/did/mdis03/
Esempio
La relazione | non è una relazione di ordine in Z.È però possibile aggirare il problema in due modi
sia Z = {x ∈ Z : x ≥ 0}
la relazione | ristretta a Z è antisimmetrica
sia ∼ la relazione di equivalenza in Z definitaponendo
a ∼ b se e soltanto se (a | b) ∧ (b | a)
nell’insieme quoziente Z∼ è definibile la relazione
[a]∼ |∼ [b]∼ se e soltanto se a | b
|∼ è antisimmetrica su Z∼
Matematica Discreta (elementi) – E-O – p. 12
www.matapp.unimib.it/$sim $marina/did/mdis03/
Esempio
Quindi
(Z, |) è un insieme ordinato
(Z∼, |∼) è un insieme ordinato
Le due costruzioni sono del tutto analoghe, nel senso che
si ha una corrispondenza biunivoca φ : Z → Z∼
φ conserva la relazione nel senso che per ognia, b ∈ Z si ha
a | b se e soltanto se φ(a) |∼ φ(b)
Esercizio – Relativamente a ∼, mostrare che in Z si ha
(a | b) ∧ (b | a) se e soltanto se a = ±b
Matematica Discreta (elementi) – E-O – p. 13
www.matapp.unimib.it/$sim $marina/did/mdis03/
Esempio
Consideriamo A = {2, 3, 4, 6, 12} ⊆ Z ⊆ Z con larelazione |A (cioè la restrizione di | da Z a A)
Dal momento che | è un ordinamento su Z, si ha che |Aè un ordinamento su ADi nuovo, possiamo disegnare il diagramma di |A
2
3
4
6
12
Matematica Discreta (elementi) – E-O – p. 14
www.matapp.unimib.it/$sim $marina/did/mdis03/
Una ulteriore convenzione
Possiamo omettere la freccia, pur di stabilire a priori unverso al disegno
Stabiliamo che se a ≤ b, allora nel disegno a e b sonocollegati da un segmento, ma a sta al di sotto di b.
Per (A, |) si ha allora
2 3
4 6
12
Il diagramma contienetutte le informazioni che cipermettono di ricostruirela relazione su A
Matematica Discreta (elementi) – E-O – p. 15
www.matapp.unimib.it/$sim $marina/did/mdis03/
Esempi
Nell’insieme A abbiamo quindi definito le due relazionid’ordine
|
2 3
4 6
12 ≤
2
3
4
6
12
Le due relazioni hanno proprietàalgebriche differenti: ad esempio ≤ è unordinamento totale, mentre 4 e 6 nonsono confrontabili rispetto a |
Matematica Discreta (elementi) – E-O – p. 16
www.matapp.unimib.it/$sim $marina/did/mdis03/
Esercizio
Si consideri l’insieme X = {a, b, c, d, e} e i seguentidiagrammi di relazioni d’ordine su X. Si scrivanoespressamente le relazioni come sottoinsiemi di X× X.
R1
a c
d b
e R2
e
ca b
d
Matematica Discreta (elementi) – E-O – p. 17
www.matapp.unimib.it/$sim $marina/did/mdis03/
Elementi notevoli
Sia (A,≤) un insieme ordinato. Diremo che
a ∈ A è minimo di A se
∀x ∈ A a ≤ x
a ∈ A è massimo di A se
∀x ∈ A x ≤ a
a ∈ A è un elemento minimale di A se
∀x ∈ A(
x ≤ a → x = a)
a ∈ A è un elemento massimale di A se
∀x ∈ A(
a ≤ x → x = a)
Matematica Discreta (elementi) – E-O – p. 18
www.matapp.unimib.it/$sim $marina/did/mdis03/
Esempi
In A = {1, 2, 3, 4, 5} con la relazione d’ordine Rrappresentata dal diagramma in figura
R
1 2
3 4
5non c’è minimo
5 è massimo, infatti ∀x ∈ A x ≤ 5
1 e 2 sono elementi minimali
5 è un elemento massimale
Esercizi – Si provi che se un insieme parzialmenteordinato A ha un minimo m, allora m è l’unico minimodi A (ex. 10.2, p. 92).Si provi che il minimo di A è un elemento minimale di A(p. 91).
Matematica Discreta (elementi) – E-O – p. 19
www.matapp.unimib.it/$sim $marina/did/mdis03/
Elementi notevoli
Nel seguito indichiamo con B un sottoinsieme di A.Diremo che
a ∈ A è un minorante di B se
∀x ∈ B a ≤ x
a ∈ A è un maggiorante di B se
∀x ∈ B x ≤ a
a ∈ A è un estremo inferiore di B (inf(B)) se
a è il massimo dei minoranti di B
a ∈ A è un estremo superiore di B (sup(B)) se
a è il minimo dei maggioranti di BMatematica Discreta (elementi) – E-O – p. 20
www.matapp.unimib.it/$sim $marina/did/mdis03/
Esempi
In A = {1, 2, 3, 4, 5} con la relazione d’ordine Rrappresentata dal diagramma in figura
R
1 2
3 4
5Sia B = {1, 3, 4}
B ammette 1 come minimoB non ammette massimo3 e 4 sono elementi massimalil’unico maggiorante di B è 5
l’unico minorante di B è 1
il minimo dei maggioranti di B è 5, cioèsup(B) = 5
il massimo dei minoranti di B è 1, cioèinf(B) = 1
Matematica Discreta (elementi) – E-O – p. 21
www.matapp.unimib.it/$sim $marina/did/mdis03/
Esempi
In A = {1, 2, 3, 4, 5} con la relazione d’ordine Rrappresentata dal diagramma in figura
R
1 2
3 4
5Sia B = {1, 2}
B non ammette minimoB non ammette massimo1 e 2 sono elementi siamassimali che minimali in B
B non ha minorantii maggioranti di B sono 4 e 5
il minimo dei maggioranti di B è 4, cioèsup(B) = 4
B non ammette estremo inferioreMatematica Discreta (elementi) – E-O – p. 22
www.matapp.unimib.it/$sim $marina/did/mdis03/
Esempi
In A = {1, 2, 3, 4, 5} con la relazione d’ordine Rrappresentata dal diagramma in figura
R
1 2
3 4
5Sia B = {3, 4}
B non ammette minimoB non ammette massimo3 e 4 sono elementi siamassimali che minimali in B
1 e 2 sono minoranti per B5 è l’unico maggiorante di Bil minimo dei maggioranti di B è 5
B non ammette estremo inferiore, in quantol’insieme {1, 2} non ammette massimo
Matematica Discreta (elementi) – E-O – p. 23
www.matapp.unimib.it/$sim $marina/did/mdis03/
Esercizi
Dato un insieme ordinato A, analogamente a quantovisto per minimi e elementi minimali, si provi che
se A ha un massimo M, allora M è l’unico massimodi A.
Il massimo di A è un elemento massimale di A.
Relativamente a estremo superiore ed estremo inferiore,si provi che
Se un sottoinsieme B di A ha un estremo superiorein A, allora tale estremo superiore è unico (ex. 10.3,p. 93).
Se un sottoinsieme B di A ha un estremo inferiore inA, allora tale estremo inferiore è unico.
Matematica Discreta (elementi) – E-O – p. 24
www.matapp.unimib.it/$sim $marina/did/mdis03/
Reticoli
Definizione – Un insieme parzialmente ordinato (L,≤)è detto reticolo se ogni coppia di elementi ammetteestremo superiore ed estremo inferiore.
Riscriviamo la definizione di estremo superiore diB = {x, y}
sup(B) è maggiorante di B, ovvero
x ≤ sup(B) ∧ y ≤ sup(B)
sup(B) è il minimo di tali maggioranti di B, ovvero
∀z(
(
x ≤ z ∧ y ≤ z)
→(
sup(B) ≤ z)
)
Matematica Discreta (elementi) – E-O – p. 25
www.matapp.unimib.it/$sim $marina/did/mdis03/
Notazione
Dati x, y ∈ L, utilizziamo i simboli
x ∨ y = sup({x, y})
x ∧ y = inf({x, y})
Possiamo allora scrivere che (L,≤) è un reticolo se esolo se per ogni x, y in L esistono due elementi x ∨ y ex ∧ y tali che
x ≤ (x ∨ y) e y ≤ (x ∨ y)
∀z(
(
x ≤ z e y ≤ z)
→(
(x ∨ y) ≤ z)
)
(x ∧ y) ≤ x e (x ∧ y) ≤ y
∀z(
(
z ≤ x e z ≤ y)
→(
z ≤ (x ∧ y))
)
Matematica Discreta (elementi) – E-O – p. 26
www.matapp.unimib.it/$sim $marina/did/mdis03/
Esempi
Consideriamo l’insieme A = {1, 2, 3, 4, 5} e le duerelazioni
R1
1 2
3 4
5 R2
5
4
3
2
1
(A,R1) non è un reticolo,(A,R2) è un reticolo.
Matematica Discreta (elementi) – E-O – p. 27
www.matapp.unimib.it/$sim $marina/did/mdis03/
Esempi
Consideriamo l’insieme A = {1, 2, 3, 4, 5, 6} e le duerelazioni
R3
6
5 4
3 2
1 R4
6
5 4
3 2
1
(A,R3) è un reticolo, (A,R4) non è un reticolo.Matematica Discreta (elementi) – E-O – p. 28
www.matapp.unimib.it/$sim $marina/did/mdis03/
Esempi
Sia A un insieme. In X = P(A) consideriamo larelazione di ordine ⊆.
(X,⊆) è un reticolo
infatti, dati x, y ∈ X, ovvero dati due sottoinsiemi diA, si ha
inf({x, y}) = x ∧ y = x ∩ y
sup({x, y}) = x ∨ y = x ∪ y
Esercizio – Sia A = {a, b, c} e sia X = P(A).Costruire il diagramma del reticolo (X,⊆).
Matematica Discreta (elementi) – E-O – p. 29
www.matapp.unimib.it/$sim $marina/did/mdis03/
MCD e mcm
Si consideri l’insieme ordinato (Z∼, |∼) (o se sipreferisce (Z, |)).
Definiamo
MCD (a, b) = inf({a, b}) = a ∧ b
mcm (a, b) = sup({a, b}) = a ∨ b
Cioè d è il Massimo Comun Divisore di a e b se
d | a e d | b
qualora c | a e c | b, allora c | d
L’algoritmo delle divisioni successive permette dicalcolare un tale d, e di conseguenza di mostrare che(Z∼, |∼) è un reticolo. Matematica Discreta (elementi) – E-O – p. 30
www.matapp.unimib.it/$sim $marina/did/mdis03/
MCD e mcm
Attenzione però, (Z∼, |∼) è un insieme quoziente!
Scriviamo perciò
MCD ([a]∼, [b]∼) = inf([a]∼, [b]∼) = [a]∼ ∧ [b]∼
mcm ([a]∼, [b]∼) = sup([a]∼, [b]∼) = [a]∼ ∨ [b]∼
e [d]∼ è il Massimo Comun Divisore di [a]∼ e [b]∼ se
[d]∼ |∼ [a]∼ e [d]∼ |∼ [b]∼
qualora [c]∼ |∼ [a]∼ e [c]∼ |∼ [b]∼, allora[c]∼ |∼ [d]∼
Essendo [d]∼ = {d,−d}, il Massimo Comun Divisorenon è univocamente determinato, ma è determinato ameno del segno.
Matematica Discreta (elementi) – E-O – p. 31
www.matapp.unimib.it/$sim $marina/did/mdis03/
Reticoli
Se (L,≤) è un reticolo, allora ∨ e ∧ sono operazioni in L.
In altre parole (L,∨,∧) è una struttura algebrica.
Quali sono le proprietà di ∨ e ∧?
(L,∨,∧) è una struttura “nota”?
E (L,∧,∨)?
Matematica Discreta (elementi) – E-O – p. 32
www.matapp.unimib.it/$sim $marina/did/mdis03/
Proprietà di ∨ e ∧
Sia (L,≤) un reticolo, per ogni x, y, z ∈ L si puòdimostrare che
x ∨ y = y ∨ x x ∧ y = y ∧ x
x ∨ (y ∨ z) = (x ∨ y) ∨ z x ∧ (y ∧ z) = (x ∧ y) ∧ z
x ∨ (x ∧ y) = x x ∧ (x ∨ y) = x
Osserviamo che (L,∨) e (L,∧) sono due semigruppicommutativi.
Esercizio – In generale (L,∨) e (L,∧) non sonomonoidi e/o gruppi. Negli esempi di reticoli visti, stabilirese si tratta di monoidi e/o gruppi.
Matematica Discreta (elementi) – E-O – p. 33
www.matapp.unimib.it/$sim $marina/did/mdis03/
Definizione alternativa di Reticolo
Lo studio delle proprietà di ∨ e ∧ suggerisce unadefinizione alternativa di reticolo.
Definizione – Un reticolo è una struttura algebrica(L,∨,∧) con due operazioni tali che per ogni x, y, z ∈ Lsi ha
x ∨ y = y ∨ x x ∧ y = y ∧ x
x ∨ (y ∨ z) = (x ∨ y) ∨ z x ∧ (y ∧ z) = (x ∧ y) ∧ z
x ∨ (x ∧ y) = x x ∧ (x ∨ y) = x
Osserviamo che in questa definizione di reticolo le dueoperazioni ∨ e ∧ svolgono ruoli simmetrici. Questo hauna importante conseguenza.
Matematica Discreta (elementi) – E-O – p. 34
www.matapp.unimib.it/$sim $marina/did/mdis03/
Principio di dualità per i reticoli
Proposizione – Se P è l’enunciato di un teorema diteoria dei reticoli in cui intervengono solo le operazioni ∨e ∧, e se P è l’enunciato che si ottiene da P scambiandoi simboli ∨ e ∧, allora anche P è l’enunciato di unteorema di teoria dei reticoli.
ovvero
Proposizione – Se P è una proprietà (che coinvolgesolo i simboli ∨ e ∧) vera per ogni reticolo, allora ancheP , ottenuta da P scambiando i simboli ∨ e ∧, è vera perogni reticolo.
Definizione – P è detto enunciato duale di P .Matematica Discreta (elementi) – E-O – p. 35
www.matapp.unimib.it/$sim $marina/did/mdis03/
Esempi
La seguente proposizione è vera per ogni reticolo
∀a (a ∨ a = a)
dal momento che x ∧ (x ∨ y) = x, ponendox = y = a, si ha a ∧ (a ∨ a) = a
ma allora a ∨ a = a ∨(
a ∧ (a ∨ a))
dal momento che x ∨ (x ∧ y) = x, ponendo
x = a e y = a ∨ a, si ha a ∨(
a ∧ (a ∨ a))
= a
per il principio di dualità dei reticoli è vera anche la
∀a (a ∧ a = a)Matematica Discreta (elementi) – E-O – p. 36
www.matapp.unimib.it/$sim $marina/did/mdis03/
Esempi
Attenzione però, il principio di dualità per i reticoli si puòapplicare solo a proposizioni che valgono per ognireticolo.
Ad esempio nel reticolorappresentato dal diagramma
a
b
cd
e
b ∧ (c ∨ d) = (b ∧ c) ∨ (b ∧ d) è falsa
b ∨ (c ∧ d) = (b ∨ c) ∧ (b ∨ d) è vera
Matematica Discreta (elementi) – E-O – p. 37
www.matapp.unimib.it/$sim $marina/did/mdis03/
Proprietà dei reticoli
Sia (L,∨,∧) un reticolo
∀a, b ∈ L (a ∧ b = a) ↔ (a ∨ b = b)
supponiamo che a ∧ b = a, alloraa ∨ b = (a ∧ b) ∨ b = b ∨ (a ∧ b) = b
avendo mostrato che per ogni a e b si ha(a ∧ b = a) → (a ∨ b = b) per dualità per ogni ae b si ha (a ∨ b = a) → (a ∧ b = b), ma questoè esattamente quello che dobbiamo mostrare(applicando la proprietà commutativa escambiando i ruoli di a e b).
Esercizio – Confrontare questa dimostrazione con ladimostrazione riportata da Facchini a p. 96.
Matematica Discreta (elementi) – E-O – p. 38
www.matapp.unimib.it/$sim $marina/did/mdis03/
Definizione alternativa di reticolo
Sia (L,∨,∧) un reticolo (inteso come struttura algebricacon due operazioni, . . . ).
Allora in L è definibile una relazione d’ordine, ponendo
x ≤ y se e soltanto se x ∧ y = x
per quanto visto la definizione è equivalente alla
x ≤ y se e soltanto se x ∨ y = y
Esercizio – Mostrare che ≤ è una relazione di ordine.
Mostrare inoltre che, rispetto a questa relazione d’ordine,ogni coppia di elementi ammette estremo superiore edestremo inferiore, e che sup e inf coincidonoesattamente con ∨ e ∧. Matematica Discreta (elementi) – E-O – p. 39
www.matapp.unimib.it/$sim $marina/did/mdis03/
Proprietà dei reticoli
Sia (L,∨,∧) un reticolo. Le due seguenti proposizionisono equivalenti
∀a, b, c ∈ L a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c)
∀a, b, c ∈ L a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)
Ma non valgono necessariamente in ogni reticolo, adesempio
a
b
cd
e e
ca b
db ∧ (c ∨ d) 6= (b ∧ c) ∨ (b ∧ d)
a ∧ (b ∨ c) 6= (a ∧ b) ∨ (a ∧ c)
Matematica Discreta (elementi) – E-O – p. 40
www.matapp.unimib.it/$sim $marina/did/mdis03/
Proprietà dei reticoli
Sia (L,∨,∧) un reticolo.
Definizione – Un reticolo (L,∨,∧) è detto distributivose valgono le proprietà distributive
∀a, b, c ∈ L a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c)
∀a, b, c ∈ L a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)
Si ha una completa caratterizzazione dei reticolidistributivi
Proposizione – Un reticolo è distributivo se e soltantose non ha sottoreticoli isomorfi ai due esempi visti nellucido precedente.
Matematica Discreta (elementi) – E-O – p. 41
www.matapp.unimib.it/$sim $marina/did/mdis03/
Sottoreticolo?
Data una struttura algebrica (A, ∗,⊕, . . . ), in generaleuna sottostruttura è un sottoinsieme di A che è a suavolta una struttura algebrica (rispetto alle stesseoperazioni ∗,⊕, . . . ).
Più precisamente, dato un reticolo (L,∨,∧)
Definizione – Un sottoreticolo S di L è un sottoinsiemedi L che è a sua volta un reticolo rispetto alla restrizionedi ∨ e ∧ a S.
Dato un gruppo (G, ·)
Definizione – Un sottogruppo H di G è un sottoinsiemedi G che è a sua volta un gruppo rispetto alla restrizionedi · a H. Matematica Discreta (elementi) – E-O – p. 42
www.matapp.unimib.it/$sim $marina/did/mdis03/
Esempi
Si consideri il reticolo
a
bc
d
e
fil sottoinsieme {b, c, d}non è un sottoreticolo
il sottoinsieme {c, d, e, f} è un sottoreticolo
il sottoinsieme {b, c, d, e, f} non è un sottoreticolo
il sottoinsieme {a, b, c, d, e} è un sottoreticolo
Matematica Discreta (elementi) – E-O – p. 43
www.matapp.unimib.it/$sim $marina/did/mdis03/
Isomorfo?
Quando due strutture algebriche sono “uguali”?Quando due strutture hanno le stesse
proprietà algebriche?Per rispondere occorre introdurre i concetti diomomorfismo e isomorfismo di strutture.
Date due strutture dello stesso tipo, in generale unomomorfismo è una applicazione che conserva leoperazioni. In particolare
Definizione – Dati due gruppi (G, ·) e (H, ∗), unomomorfismo di gruppi è una applicazione f : G → Htale che per ogni g1, g2 ∈ G
f (g1 · g2) = f (g1) ∗ f (g2)Matematica Discreta (elementi) – E-O – p. 44
www.matapp.unimib.it/$sim $marina/did/mdis03/
Isomorfo?
Definizione – Dati due anelli (A,+, ·) e (B,⊕,⊙), unomomorfismo di anelli è una applicazione f : A → Btale che per ogni a1, a2 ∈ A
f (a1 + a2) = f (a1)⊕ f (a2)
f (a1 · a2) = f (a1) ⊙ f (a2)
Definizione – Dati due reticoli (R,∨,∧) e (Q,g,f), unomomorfismo di reticoli è una applicazione f : R → Qtale che per ogni r1, r2 ∈ R
f (r1 ∨ r2) = f (r1) g f (r2)
f (r1 ∧ r2) = f (r1) f f (r2)Matematica Discreta (elementi) – E-O – p. 45
www.matapp.unimib.it/$sim $marina/did/mdis03/
Isomorfo?
Un isomorfismo è un omomorfismo biunivoco.
Le proprietà algebriche di una struttura sono le proprietàinvarianti per isomorfismo.
Diremo che (R,∨,∧) e (Q,g,f) sono isomorfi seesiste un isomorfismo da R a Q.
Se R ha una certa proprietà (ad esempio R è distributivo)e se R e Q sono isomorfi, allora anche Q ha quellastessa proprietà (ad esempio Q è distributivo).
Due reticoli (“disegnabili”) sono isomorfi se e solo sesono rappresentabili dallo stesso diagramma.
Matematica Discreta (elementi) – E-O – p. 46
www.matapp.unimib.it/$sim $marina/did/mdis03/
Esercizio
Stabilire se il reticolo in figura è distributivo
e
ca b d
f
non è distributivo perché{a, b, c, e, f } è un sottoreticolonon distributivo
si può anche verificare direttamenteche a ∧ (b ∨ c) 6= (a ∧ b) ∨ (a ∧ c)
Matematica Discreta (elementi) – E-O – p. 47
www.matapp.unimib.it/$sim $marina/did/mdis03/
Esempi
Stabilire se il reticolo in figura è distributivo(tema esame 25 febbraio 2002)
g
fe
d
b c
a
{d, e, f , g} è un sottoreticolo di R(distributivo)
{a, b, c, d} è un sottoreticolo di R(distributivo)
{a, d, e, f , g} è un sottoreticolo di R(distributivo)
{a, c, d, e, f , g} è un sottoreticolo di R (distributivo)
{a, b, c, e, f , g} non è un sottoreticolo di R
. . .Matematica Discreta (elementi) – E-O – p. 48
www.matapp.unimib.it/$sim $marina/did/mdis03/
Proprietà dei reticoli
Definizione – Se esiste l’elemento neutro rispetto a ∨,lo chiamiamo zero di L e lo indichiamo con il simbolo 0.Analogamente, se esiste l’elemento neutro rispetto a ∧,lo chiamiamo uno di L e lo indichiamo con il simbolo 1.
Osserviamo che, se esiste, lo zero di (L,∨,∧) è ilminimo di LInfatti per definizione lo zero è l’elemento neutro di ∨,cioè
∀x ∈ L x ∨ 0 = x
Max ∨ 0 = x se e solo se 0 ≤ x
Analogamente l’uno di (L,∨,∧) è il massimo di LMatematica Discreta (elementi) – E-O – p. 49
www.matapp.unimib.it/$sim $marina/did/mdis03/
Proprietà dei reticoli
Definizione – Un reticolo (L,∨,∧) è detto limitato seesistono 0 e 1
In altre parole, L è limitato se ammette massimo eminimo.
Sia (L,∨,∧, 0, 1) un reticolo limitato
Definizione – Dato a ∈ L, l’elemento b è dettocomplemento di a se
a ∨ b = 1
a ∧ b = 0
Matematica Discreta (elementi) – E-O – p. 50
www.matapp.unimib.it/$sim $marina/did/mdis03/
Esempi
L1
6
5 4
3 2
1 L2
5
4
3
2
1
In L1, 4 ha come complemento 3
In L2 gli unici elementi che hannocomplementi sono 1 e 5
Matematica Discreta (elementi) – E-O – p. 51
www.matapp.unimib.it/$sim $marina/did/mdis03/
Proprietà dei reticoli
Definizione – Un reticolo limitato (L,∨,∧, 0, 1) è dettocomplementato se ogni elemento ammettecomplemento.
Si ha il seguente
Teorema – Se un reticolo (L,∨,∧, 0, 1) è limitato edistributivo, allora ogni elemento ammette al più uncomplemento.
Definizione – Un reticolo di Boole è un reticololimitato, distributivo e complementato.
Matematica Discreta (elementi) – E-O – p. 52
www.matapp.unimib.it/$sim $marina/did/mdis03/
Esempi di reticoli di Boole
Sia A un insieme e sia X = P(A). Allora (X,∪,∩)è un reticolo di Boole.
L’insieme delle proposizioni con le operazioni ∨ e ∧è un reticolo di Boole.
Matematica Discreta (elementi) – E-O – p. 53