sim $marina/did/mdis03/marina/did/mdis03/4up-2003-12-10.pdf · sim $marina/did/mdis03/ Matematica...

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


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).



Insiemi (parzialmente) ordinati



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)


mailto:[email protected]


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.



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


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



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


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.



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



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



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∼



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



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



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



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 |



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



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)



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).



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


Esempi


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



Esempi


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


Esempi


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



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.



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)

)



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))

)



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.



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


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,⊆).



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


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.



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,∧,∨)?



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.



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.



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


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


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



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.



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



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)




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.



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


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



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


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


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.



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)



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



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



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



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




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.



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.


Date post:	05-Aug-2020
Category:	Documents
Upload:	others
View:	4 times
Download:	0 times

sim $marina/did/mdis03/marina/did/mdis03/4up-2003-12-10.pdf · sim $marina/did/mdis03/ Matematica...

Documents