marina/did/mdis03/concat4up.pdf · 6 ottobre 2003 Mar ina Cazz ola (mar [email protected] ......

www.matapp.unimib.it/marina/did/mdis03/

1

Matematica Discreta (elementi) – E-O

CdL Informatica

6 ottobre 2003

Marina Cazzola ([email protected])

Dipartimento di Matematica e ApplicazioniUniversità di Milano–Bicocca

Matematica Discreta (elementi) – E-O – p. 1


2

Avvertenze

Queste fotocopie sono distribuite solo comeindicazione degli 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 svolgimentodegli argomenti (e per la rettifica di eventuali errori

contenuti in queste pagine).



3

Questioni organizzative

Docente: Marina CazzolaUfficio U7-336 (edificio U7, terzo piano)

Orario lezionilunedì, dalle 13.30 alle 15.30, aula U3-05mercoledì, dalle 9.30 alle 12.30, aula U3-05

(si inizia rispettivamente alle 13.30 e alle 9.30)Ricevimento studenti:lunedì dalle 15.30 alle 17.30Libro di testo: A. Facchini, “Algebra e matematicadiscreta”, Decibel–Zanichelli (potranno essereindicati altri testi per particolari argomenti)



4

Sito web del corso

Il sito ufficiale del corso di laurea èwww.disco.unimib.it

(per informazioni dalla “segreteria”: date e risultatidegli esami, variazioni dell’orario, programma‘ufficiale’ . . . )

Come negli anni passati sarà al più presto attivoanche un sito web, contenente informazioni relative aicontenuti del corso. Sarà accessibile dall’indirizzo

www.matapp.unimib.it/marina/did/(al momento sono attive le pagine relative ai corsitenuti negli anni accademici passati: potete già trovareuna buona raccolta di testi dei temi d’esame).


1


5

Programma del corso

Cenni di logica formale e di teoria degli insiemi.

Strutture algebriche.Numeri naturali e numeri interi: questioni didivisibilità. In particolare massimo comundivisore: calcolo e applicazioni.

Insiemi e relazioni: relazioni di equivalenza (classidi resto modulo n) e relazioni d’ordine (reticoli).

Cenni di teoria dei grafi.

Cenni di combinatoria.



6

Esami

L’esame è costituito da una parte scritta e da unaparte orale.Durante l’anno sono previsti 7 appelli d’esame edue compitini.



7

Uno sguardo al passato



8

Qualche numero

Nell’AA 2002/03 le matricole del gruppo E-Oerano circa 200Durante l’anno si sono svolti due compitini, ilprimo a metà novembre e il secondo a finegennaio.Al primo compitino sono stati consegnati 146compiti, sono stati ammessi al secondo compitinoin 111 (di cui 27 insufficienti).Al secondo compitino sono stati consegnati 97compiti e, confrontando i risultati dei duecompitini, sono stati ammessi all’orale in 56.All’orale sono stati promossi in 45.


2


9

AA 2002/03

Gli esami dell’AA 2002/03 in sintesi

appello compiticonsegnati

ammessiall’orale

promossiall’orale

febbraio 61 37 18aprile 22 12 1giugno 31 18 16luglio 33 19 18

settembre 41 12 4

NOTA: all’appello di aprile sono ammessi solo glistudenti del secondo anno o successivi, si devonoancora svolgere gli appelli di ottobre e gennaio.



10

Riassumendo

Numero di matricole: 200Promossi in seguito ai compitini: 45

Promossi negli appelli da febbraio a settembre: 57Promossi in totale: 102Percentuale: 51%

Questa percentuale attorno al 50% è purtroppo ormaiun dato “consolidato” (3 anni).

A mio parere questo è un problema: soluzioni????



11

Elementi di logica formale



12

Proposizioni e valori di verità

Definizione – Si dice proposizione (o enunciato)un’affermazione che assume uno e un solo valore diverità: V (vero) oppure F (falso).

Esempi di proposizioni:

Roma è in FranciaRoma non è in Francia2 ≥ 7− 126 = 3 · 2Parigi è in America

A volte si usano le lettere inglesi T (true) e F (false)per indicare i valori di verità.


3


13

Operatore di negazione

Le due proposizioni

Roma è in FranciaRoma non è in Francia

si ottengono l’una dall’altra aggiungendo o togliendo laparola non.

La parola non ha la proprietà di invertire il valore diverità della prima proposizione.

Si tratta di un procedimento generalizzabile ad unaqualsiasi proposizione.

Questo procedimento è detto operatore dinegazione e è indicato con il simbolo ¬.



14


Definizione – Si dice operatore di negazionel’operatore, indicato con il simbolo “¬”, che, antepostoalla proposizione “p”, ne inverte i valori di verità: se “p”è vera, allora “¬p” è falsa; analogamente se “p” èfalsa, allora “¬p” è vera.

Se ad esempio p = “Roma è in Francia”, allora¬p = “Roma non è in Francia”.

Analogamente se q = “6 = 3 · 2”, allora¬q = “6 6= 3 · 2”.

E ancora se r = “2 ≥ 7− 12”, allora ¬r = “2 < 7− 12”.



15

Tavole di verità

Chiameremo tavola di verità della proposizione Puna tabella che consenta di ricavare il valore di veritàdi P sulla base dei valori di verità assunti dalleproposizioni eventualmente presenti in P.

Possiamo sintetizzare le caratteristiche dell’operatoredi negazione nella seguente tavola di verità: laproposizione P = ¬p ha valore di verità dipendentedal valore di verità di p

p ¬pV FF V



16

Tavole di verità

È possibile costruire tavole di verità anche perproposizioni più complicate.

Ad esempio, data una proposizione p, consideriamo laproposizione ¬(¬p). Che valore di verità ha?

p ¬p ¬(¬p)

V F VF V F

Dalla tavole ricaviamo che p e ¬(¬p) hanno lo stessovalore di verità, indipendentemente dal valore diverità di p.


4


17

Proposizioni composte e connettivi

Consideriamo ora alcune proposizioni composte,ovvero costituiti da più proposizioni componenti,collegate da opportuni termini, detti connettivi.

Il valore di verità di una proposizione compostadipende dai valori di verità delle proposizioni che lacompongono e dai connettivi impiegati.

I connettivi logici che prenderemo in considerazionesono la congiunzione e la disgiunzione.

congiunzione: “p ∧ q”; “p e q”; “p et q”.

disgiunzione: “p ∨ q”, “p o q”; “p vel q”.



18

Congiunzione

Definizione – La proposizione composta “p ∧ q” (chescriviamo anche come “p e q” oppure come “p et q”) èvera se e soltanto se sono vere entrambe leproposizioni componenti “p” e “q”.

Possiamo sintetizzare questa definizione in una tavoladi verità

p q p ∧ qV V VF V FV F FF F F



19

Esempi

Consideriamo la proposizione

3 + 4 = 7 e 2 + 6 = 8

che possiamo anche scrivere

(3 + 4 = 7) ∧ (2 + 6 = 8)

è una proposizione vera see soltanto se sono vereentrambe le proposizioni“3 + 4 = 7” e “2 + 6 = 8”.




20

Esempi

Consideriamo la proposizione

4 + 3 = 7 e 5 > 2 e 2 + 6 = 8

In linea di principio non è ovvio quale dei dueconnettivi “e” vada applicato per primo.

Per questo è meglio utilizzare delle parentesi escrivere la proposizione in uno dei due modi seguenti:

(

(4 + 3 = 7) ∧ (5 > 2))

∧ (2 + 6 = 8)

(4 + 3 = 7) ∧(

(5 > 2) ∧ (2 + 6 = 8))


5


21

Esempi

Quale delle due scritture

(p ∧ q) ∧ r p ∧ (q ∧ r)

è quella corretta?

Consideriamo entrambe le proposizioni ecostruiamone la tavola di verità

p q r (p ∧ q) ∧ r p ∧ (q ∧ r)VF



22

Esempi

Da quante righe è composta la tavola?

p q r (p ∧ q) ∧ r p ∧ (q ∧ r)V V VF V VV F VF F VV V FF V FV F FF F F



23

Esempi

Analizziamo anche le proposizioni intermedie “p ∧ q” e“q ∧ r”

p q r p ∧ q q ∧ r (p ∧ q) ∧ r p ∧ (q ∧ r)V V V V V V VF V V F V F FV F V F F F FF F V F F F FV V F V F F FF V F F F F FV F F F F F FF F F F F F F



24

Credits

Testi di riferimento per questa parte:

il già citato “A. Facchini, Algebra e matematicadiscreta, Decibel–Zanichelli” (capitolo 5);

“K. H. Rosen, Discrete Mathematics and ItsApplications, McGraw-Hill” (capitoli 1 e 3);

“G. T. Bagni, Matematica, Processi formativi escienze dell’educazione, Guerini studio (capitolo1, §1.1-§1.5).


6


1


CdL Informatica

8 ottobre 2003





2

Avvertenze








3

Elementi di logica formale



4


Definizione – Si dice operatore di negazionel’operatore, indicato con il simbolo “¬”, che, antepostoalla proposizione “p”, ne inverte i valori di verità: se “p”è vera, allora “¬p” è falsa; analogamente se “p” èfalsa, allora “¬p” è vera.

p ¬pV FF V


7


5

Congiunzione

Definizione – La proposizione composta “p ∧ q” (chescriviamo anche come “p e q” oppure come “p et q”) èvera se e soltanto se sono vere entrambe leproposizioni componenti “p” e “q”.




6

Esempi

Abbiamo visto vari esempi, in particolare

i valori di verità di p e di ¬(¬p) coincidono,qualunque sia il valore di verità di p

i valori di verità di (p ∧ q) ∧ r e di p ∧ (q ∧ r)coincidono, qualunque siano i valori di verità di p,q e r



7

Esempi

Consideriamo le due proposizioni

¬(p ∧ q) (¬p) ∧ q

qual è la scrittura “giusta”?

Analizziamo le tavole di verità

p q ¬(p ∧ q) (¬p) ∧ q



8

Esempi

Occorre ancora una volta considerare alcuneproposizioni intermedie

p q p ∧ q ¬p ¬(p ∧ q) (¬p) ∧ qV V V F F FF V F V V VV F F F V FF F F V V F

Osserviamo quindi che ¬(p ∧ q) e (¬p) ∧ q sono dueproposizioni diverse.


8


9

Differenze dal linguaggio comune

La congiunzione “e” è utilizzata anche nel linguaggiocomune.Si considerino ad esempio le due proposizioni

“Gianni investì un pedone e accelerò”

“Gianni accelerò e investì un pedone”Nel linguaggio comune le due proposizioni sonodifferenti: si attribuisce infatti alla congiunzione e unaconnotazione temporale.



10


Secondo la nostra definizione, a differenza dellinguaggio comune, il connettivo “e” non ha alcunavalenza temporale.

Osserviamo infatti la tavola di verità

p q p ∧ q q ∧ pV V V VF V F FV F F FF F F F

Esercizio: confrontare con l’utilizzo di �� inprogrammazione. Matematica Discreta (elementi) – E-O – p. 10


11

Operatori e connettivi

Fino a qui abbiamo introdotto

l’operatore “¬”

il connettivo “∧”Effettivamente ¬ e ∧ hanno un diversocomportamento:

¬ prende come “input” una proposizione e“produce” una nuova proposizione;

∧ prende come “input” due proposizioni e“produce” una nuova proposizione.



12

Operazioni n-arie

Possiamo evidenziare il diverso comportamento con idue schemi

¬

∧

Impareremo ad usare il termine operazione:

¬ è una operazione unaria∧ è una operazione binaria


9


13

Disgiunzione

Definizione – La proposizione composta “p ∨ q” (chescriviamo anche come “p o q” oppure come “p vel q”,oppure come “p or q”) è vera se e soltanto se è veraalmeno una delle proposizioni componenti “p” e “q”.

In altre parole la proposizione composta “p ∨ q” è falsase e soltanto se sono false entrambe le proposizionicomponenti p e q.



14

Disgiunzione


p q p ∨ qV V VF V VV F VF F F



15

Esempi

Ad esempio la proposizione

4 + 5 = 9 o 7 + 3 = 8

che possiamo anche scrivere

(4 + 5 = 9) ∨ (7 + 3 = 8)

è una proposizione vera see soltanto se è veraalmeno una delle dueproposizioni “4 + 5 = 9” e“7 + 3 = 8”.

p q p ∨ qV V VF V VV F VF F F



16


Nel linguaggio comune alla congiunzione “o” è spessodato un significato diverso

o il motorino, o i soldi per le vacanze!in altre parole con il significato

“o questo, o quello, ma non entrambe le cose”

Questo significato corrisponde ad un altro connettivo:“xor”.


10


17

“o” esclusivo

Si indica con p⊕ q la proposizione che è vera quandouna sola tra le proposizioni p e q è vera, ma nonentrambe.

A ⊕ corrisponde la tavola di verità

p q p⊕ qV V FF V VV F VF F F



18

Implicazione materiale

Molti enunciati di risultati matematici utilizzano lacostruzione

se . . . allora . . .

Questa stessa costruzione è utilizzata nel linguaggiocomune con un nesso di causalità.L’espressione

se A allora Bintuitivamente ci fa pensare che il verificarsi di B è resoimmediatamente possibile dal previo verificarsi di A.

In questa fase vogliamo analizzare la costruzionesemantica, senza entrare nell’analisi dei significati.



19


Definizione – La proposizione composta “p → q”(che leggiamo “se p allora q”) è falsa se e soltanto sela proposizione p è vera e (contemporaneamente) laproposizione q è falsa.


p q p → qV V VF V VV F FF F V



20


La proposizione p → q si legge in molti modi

“p implica q”

“se p allora q”

“p solo se q”

“p è sufficiente per q”

“q se p”

“q ogniqualvolta p”

“q è necessaria per p”


11


21

Esempi

(Parigi è in Francia) → (4 + 4 = 8)

(Parigi è in Belgio) → (4 + 4 = 8)

(Parigi è in Germania) → (4 + 4 = 6)

(Parigi è in Francia) → (4 + 4 = 6)



22

Inversa e contronominale

Accanto all’implicazione “p → q” possiamoconsiderarne altre due correlate

“q → p”, detta inversa di “p → q”

“(¬q) → (¬p)”, detta contronominale di “p → q”



23

Precedenze

Quando si scrivono proposizioni complesse,utilizzando le varie costruzioni introdotte fin qui, sicerca di ridurre il più possibile la scrittura (omettendo isimboli “inutili”).Occorre allora stabilire a priori alcune precedenze,esattamente come si fa per le operazioni tra i numeri

2 · 3 + 5

corrisponde ad una (e una sola) delle due scritture

2 · (3 + 5) (2 · 3) + 5



24

Precedenze

Esattamente come si è stabilito che · ha laprecedenza su +, si stabilisce che le “operazioni”logiche siano eseguite in quest’ordine

l’operatore di negazione ¬i connettivi ∧ e ∨l’implicazione materiale →

(per tutti i casi dubbi è necessario scrivereesplicitamente le parentesi).

La contronominale (¬q) → (¬p) si può quindi scriveresemplicemente ¬q → ¬p.


12


25

Doppia implicazione

Definizione – La proposizione composta “p ↔ q” èvera se e soltanto se le proposizioni componenti p e qhanno lo stesso valore di verità.


p q p ↔ qV V VF V FV F FF F V



26

Doppia implicazione

La proposizione p ↔ q si legge in vari modi

“p se e solo se q”

“p è necessaria e sufficiente per q”

“se p allora q, e viceversa”

“p è equivalente a q”



27

Esercizi

Scrivere le tavole di verità delle seguenti proposizioni

(p ∨ q) ∧ ¬r

p ∨ (q ∧ ¬r)

¬(p ∧ q)

p ∨ ¬q

(p → q) ↔(

(¬q) → (¬p))

(p → q) → (q → p)

(p → q) ∨ (¬p → q)



28

Equivalenza di proposizioni

Il ragionamento matematico consiste nell’operare suproposizioni, sostituendo proposizioni date conproposizioni con lo stesso valore di verità.

Per costruire una dimostrazione matematica sonoperciò necessarie tecniche che ci permettano, datauna proposizione composta (e complicata) dicostruirne una più semplice con lo stesso valore diverità.

Definizione – Una proposizione composta P cheassume valore di verità V qualunque siano i valori diverità delle proposizioni componenti (p, q, r, . . . ) èdetta tautologia.


13


29

Equivalenza di proposizioni

Definizione – Le proposizioni p e q sono equivalentise p ↔ q è una tautologia. Scriveremo in tal casop ⇐⇒ q.

Esempi(p ∧ q) ⇐⇒ (q ∧ p)

¬(¬p) ⇐⇒ p

p ∧ (q ∧ r) ⇐⇒ (p ∧ q) ∧ r



30

Equivalenze logiche fondamentali

Ci sono alcune equivalenze che risultano più utili dialtre:[In quanto segue usiamo la convenzione di indicarecon la lettera V una qualsiasi proposizione vera e conF una qualsiasi proposizione falsa]

(p ∨ ¬p) ⇐⇒ V

(p ∧ ¬p) ⇐⇒ F

(p → q) ⇐⇒ (¬q → ¬p)

(p → q) ⇐⇒ (¬p ∨ q)

p ∧ V ⇐⇒ p e p ∨ F ⇐⇒ p [cancellazione]



31


p ∨ V ⇐⇒ V e p ∧ F ⇐⇒ F [dominanza]

p ∨ p ⇐⇒ p e p ∧ p ⇐⇒ p [idempotenza]

¬(¬p) ⇐⇒ p [doppia negazione]p ∨ q ⇐⇒ q ∨ p e p ∧ q ⇐⇒ q ∧ p

[commutatività]

(p ∨ q) ∨ r ⇐⇒ p ∨ (q ∨ r) e(p ∧ q) ∧ r ⇐⇒ p ∧ (q ∧ r) [associatività]

p ∨ (q ∧ r) ⇐⇒ (p ∨ q) ∧ (p ∨ r) ep ∧ (q ∨ r) ⇐⇒ (p ∧ q) ∨ (p ∧ r) [distributività]



32


¬(p ∧ q) ⇐⇒ ¬p ∨ ¬q e¬(p ∨ q) ⇐⇒ ¬p ∧ ¬q [De Morgan]

[p ∨ (p ∧ q)] ⇐⇒ p e [p ∧ (p ∨ q)] ⇐⇒ p[assorbimento]

Tutte queste equivalenze possono essere verificatecostruendo le rispettive tavole di verità.


14


33

Catene di equivalenze

Tramite le equivalenze logiche fondamentali possiamoprocedere alla dimostrazione di equivalenza diproposizioni senza doverne costruire ogni volta latavola di verità.

Esercizio – Mostrare tramite una catena diequivalenze logiche che la proposizione¬(p ∨ (¬p ∧ q)) è equivalente alla proposizione¬p ∧ ¬q.

¬(p ∨ (¬p ∧ q)) ⇐⇒ ¬p ∧ ¬(¬p ∧ q)[De Morgan]

¬p ∧ ¬(¬p ∧ q) ⇐⇒ ¬p ∧(

¬(¬p) ∨ ¬q)

[De Morgan]Matematica Discreta (elementi) – E-O – p. 33


34


¬p ∧(

¬(¬p) ∨ ¬q)

⇐⇒ ¬p ∧ (p ∨ ¬q)

[doppia negazione]

¬p ∧ (p ∨ ¬q) ⇐⇒ (¬p ∧ p) ∨ (¬p ∧ ¬q)[distributività]

(¬p ∧ p) ∨ (¬p ∧ ¬q) ⇐⇒ F ∨ (¬p ∧ ¬q)

F ∨ (¬p ∧ ¬q) ⇐⇒ (¬p ∧ ¬q) ∨ F[commutatività]

(¬p ∧ ¬q) ∨ F ⇐⇒ ¬p ∧ ¬q [cancellazione]

Abbiamo così scritto una successione di proposizioniequivalenti che possiamo schematizzare nel modoseguente: Matematica Discreta (elementi) – E-O – p. 34


35


¬(p ∨ (¬p ∧ q)) ⇐⇒ ¬p ∧ ¬(¬p ∧ q) De Morgan⇐⇒ ¬p ∧ [¬(¬p) ∨ ¬q] De Morgan⇐⇒ ¬p ∧ (p ∨ ¬q) doppia neg.⇐⇒ (¬p ∧ p) ∨ (¬p ∧ ¬q) distributività⇐⇒ F ∨ (¬p ∧ ¬q) ¬p ∧ p ⇐⇒

F

⇐⇒ (¬p ∧ ¬q) ∨ F commutatività⇐⇒ ¬p ∧ ¬q cancellazione



36

Credits


il già citato “A. Facchini, Algebra e matematicadiscreta, Decibel–Zanichelli” (capitolo 5);



15


1


CdL Informatica

13 ottobre 2003





2

Avvertenze








3

Cenni di logica formalee di teoria degli insiemi



4

x

Consideriamo l’espressione

x ≥ 5

Si tratta di una proposizione?Siamo in grado di attribure un valore di verità?

La difficoltà sta nell’interpretazione del simbolo x.

Solo quando diamo un “significato” ad x, siamo ingrado di attribuire un valore di verità all’espressionex ≥ 5.


16


5

Predicati

“x ≥ 5” è un predicato, cioè una espressione P(x) incui compare una variabile x, espressione che diventauna proposizione nel momento in cui diamo un“significato” ad x.

Scriviamo allora

P(x) = “x ≥ 5”

Il modo più ovvio (ma non l’unico!) per dare un“significato” ad x è assegnargli un valore numerico.

Ad esempio P(4) = “4 ≥ 5” è una proposizione.



6

Predicati

Possiamo anche scrivere predicati in cui compaionopiù indeterminate

Ad esempio l’espressione

R(x, y) = “x + y < 12”

diventa una proposizione nel momento in cui aentrambe le indeterminate x e y sostituiamo deinumeri.

Ad esempio R(5, y) = “5 + y < 12” è un predicato.R(5, 2) = “5 + 2 < 12” è una proposizione.



7

Insiemi numerici

Quando parliamo di numeri, dobbiamo tenerepresente che ci sono però diversi “tipi” di numero.

numeri naturali: N = {0, 1, 2, 3, 4, 5, . . .}

numeri interi: Z = {0,±1,±2,±3,±4, . . .}

numeri razionali: Q =

{

pq

∣

∣

∣

∣

(p, q ∈ Z) ∧ (q 6= 0)

}

numeri reali: R (i numeri che “corrispondono aipunti di una retta”)

numeri complessi: C (per questi si rimanda alcorso di “complementi”)



8

Insiemi

Un insieme (che in genere viene “definito” con suoisinonimi quali classe, collezione, raggruppamento) èin realtà un concetto primitivo.

Operativamente, un insieme è un oggetto matematicoche ha degli elementi.

Se l’insieme A ha come elementi gli oggetti a, b, c,allora scriviamo

A = {a, b, c}

E scriviamo anche

a ∈ A A 3 a


17


9

Insiemi

In altre parole, se

A = {a, b, c}

“a ∈ A” è una proposizione con valore di veritàvero“¬(a ∈ A)” è una proposizione con valore di veritàfalso, che scriviamo come “a 6∈ A”“d ∈ A” è una proposizione con valore di veritàfalso“d 6∈ A” è una proposizione con valore di veritàvero



10

Interi e naturali

Se torniamo indietro, osserviamo che per gli insieminumerici abbiamo utilizzato notazioni leggermentediverse

numeri naturali: N = {0, 1, 2, 3, 4, 5, . . .}

numeri interi: Z = {0,±1,±2,±3,±4, . . .}

Essendo insiemi che contengono infiniti elementi nonè possibile elencare tutti gli elementi.Pertanto si utilizzano i puntini “. . . ” ad indicare chel’elenco è incompleto (“e così via . . . ”).

NOTA –vale la pena di osservare che per alcuni autori 0 6∈ N.



11

Insiemi e predicati

Un altro modo di descrivere gli elementi di un insiemeè l’utilizzo di un predicato.

Dato un predicato P(x), con la scrittura

X = {x | P(x)} = {x : P(x)}

intendiamo che gli elementi dell’insieme X sono tutti esoli gli oggetti x che sostituiti alla variabile danno unaproposizione con valore di verità vero.

Si ha cioèa ∈ X ⇐⇒ P(a)

(infatti a ∈ X è vera, se e solo se P(a) è vera).Matematica Discreta (elementi) – E-O – p. 11


12

Numeri razionali

Per definire i numeri razionali abbiamo utilizzato ilpredicato

P(p, q) = “(p, q ∈ Z) ∧ (q 6= 0)”

Quando scriviamo

numeri razionali: Q =

{

pq

∣

∣

∣

∣

(p, q ∈ Z) ∧ (q 6= 0)

}

intendiamo che gli elementi dell’insieme Q sono tutte

e sole le frazionipq

per le quali, inserendo i valori di p

e q nel predicato, si ottiene che P(p, q) ha valore diverità vero.


18


13

Un’ulteriore precisazione

Quali sono gli elementi dell’insieme

K ={

x | x2 = 1}

?

Possiamo pensare a almeno due risposte diverse

K = {1}

K = {1,−1}

Questo significa che la scrittura utilizzata era un po’ambigua, a meno di non essersi accordati su unparticolare contesto.In quale insieme numerico pensiamo di “pescare” glielementi di K?



14

Un’ulteriore precisazione

K ={

x | x2 = 1}

?

Abbiamo due modi per eliminare l’ambiguità.Possiamo accordarci a priori su quale sia ilcontesto, ovvero definire l’insieme universo:

se l’universo è N, allora K = {1};se l’universo è Z, allora K = {1,−1}.

Possiamo ogni volta esplicitare il contesto nellascrittura, e utilizzare le diverse notazioni

K ={

x ∈ N | x2 = 1}

= {1};

K ={

x ∈ Z | x2 = 1}

= {1,−1}.Matematica Discreta (elementi) – E-O – p. 14


15

Quantificatori

Dato un predicato P(x), è possibile ottenere unaproposizione quantificando la variabile.Questo può essere fatto in due modi

Definizione – Il quantificatore universale di P(x) èuna proposizione che è vera se e solo seogniqualvolta sostituiamo alla variabile x un valorenell’universo otteniamo una proposizione vera.

Il quantificatore universale di P(x) si scrive

∀x P(x)

(“per ogni x, P(x)”).



16

Esempi

Il quantificatore∀x (x ≥ 0)

è una proposizione vera o falsa?

Anche in questo caso, per stabilire la verità o falsitàdella proposizione è indispensabile aver definitol’universo.

Nell’universo N dei numeri naturali laproposizione “∀x (x ≥ 0)” è vera.

Nell’universo Z dei numeri interi la proposizione“∀x (x ≥ 0)” è falsa.


19


17

Esempi

Ancora una volta si può esplicitare l’universo escrivere rispettivamente

“∀x ∈ N (x ≥ 0)”

“∀x ∈ Z (x ≥ 0)”

(La prima è una proposizione vera, la seconda è unaproposizione falsa.)



18

Esempi

Nell’insieme dei numeri reali, consideriamo ilquantificatore

∀x (x < 2)

Si tratta di una proposizione falsa.

Per affermare che il quantificatore “∀x P(x)” è falso èsufficiente trovare un elemento x dell’universo tale chesostituendo il valore di x nel predicato si ottiene unaproposizione falsa. Tale x è detto controesempio.

In questo caso è immediato verificare che 3 è unelemento dell’universo per cui è falsa la proposizione

“3 < 2”Matematica Discreta (elementi) – E-O – p. 18


19

Esempi

Nell’insieme dei numeri reali consideriamo ilquantificatore

∀x (x + 1 > x)

Si tratta di una proposizione vera.

Per mostrare che un quantificatore universale è veroin generale occorre una vera e propria dimostrazione,basata sulle nostre conoscenze matematiche.Per quel che riguarda

6x + 1 > 6x [ovvero 1 > 0]

sappiamo che nell’insieme dei numeri reali valgono leleggi di cancellazione.



20

Ancora sull’universo

Consideriamo la proposizione“ogni studente di questo corso

segue il corso di programmazione”

La proposizione è un quantificatore universale,possiamo metterlo in evidenza utilizzando il predicato

P(x) = “x segue il corso di programmazione”

e scrivere quindi∀x P(x)

Questo però “funziona” perchè stiamo implicitamentepensando che l’universo è costituito dall’insieme deglistudenti di questo corso.


20


21

Ancora sull’universo

E se consideriamo come universo l’insieme costituitoda tutti gli studenti del corso di laurea in informatica?

Abbiamo bisogno di utilizzare due predicati

P(x) = “x segue il corso di programmazione”

Q(x) = “x è studente di questo corso”

La proposizione“ogni studente di questo corso

segue il corso di programmazione”

si scrive allora

∀x (Q(x) → P(x))Matematica Discreta (elementi) – E-O – p. 21


22

Universi finiti

Se l’universo è un insieme finito, ad esempio

X = {1, 2, 3, 4}

allora, dato un predicato P(x), la proposizione

∀x P(x)

è equivalente alla proposizione

P(1) ∧ P(2) ∧ P(3) ∧ P(4)



23

Quantificatore esistenziale

Abbiamo un secondo modo di quantificare la variabiledi un predicato.

Definizione – Il quantificatore esistenziale di P(x)è una proposizione che è vera se e solo se possiamotrovare nell’universo un valore che sostituito allavariabile x ci permette di ottenere una proposizionevera.

Il quantificatore esistenziale di P(x) si scrive

∃x P(x)

(“esiste x, P(x)”).



24

Esempi

Nell’universo dei numeri reali il quantificatore

∃x (x > 3)

è una proposizione vera o falsa?

Detto P(x) il predicato “x > 3”, si verificaimmediatamente che la proposizione P(5) è vera(infatti è vero che 5 > 3).Ne consegue che ∃x P(x) è una proposizione vera.

In generale per mostrare che il quantificatore“∃x P(x)” è vero, è sufficiente fornire un esempio.


21


25

Esempi

Nell’insieme dei numeri reali consideriamo ilquantificatore

∃x (x = x + 1)

Si tratta di una proposizione falsa.

Per mostrare che un quantificatore esistenziale è falsoin generale occorre una vera e propria dimostrazione,basata sulle nostre conoscenze matematiche.Per quel che riguarda

6x = 6x + 1 [ovvero 0 = 1]

sappiamo che nell’insieme dei numeri reali valgono leleggi di cancellazione.



26

Esempi

Anche per il quantificatore esistenziale il valore diverità dipende dall’universo che si sta considerando:

“∃x ∈ N (x + 3 = 0)” è una proposizione falsa;

“∃x ∈ Z (x + 3 = 0)” è una proposizione vera.

Esercizio – Per quali insiemi X i seguentiquantificatori sono veri? E per quali falsi?

“∃x ∈ X (x · 4 = 1)”

“∃x ∈ X (x · 2 = 0)”

“∃x ∈ X (x2 = 1)”

“∃x ∈ X (x2 = 2)”Matematica Discreta (elementi) – E-O – p. 26


27

Universi finiti

Se l’universo è un insieme finito, ad esempio

X = {a, b, c, d}

allora, dato un predicato P(x), la proposizione

∃x P(x)

è equivalente alla proposizione

P(a) ∨ P(b) ∨ P(c) ∨ P(d)



28

Quantificatori

Il quantificatore ∀x P(x)

è una proposizione vera se la proposizioneP(x) è vera assegnando ad x ogni valoredell’universo;è una proposizione falsa se nell’universo èpossibile trovare un controesempio.

Il quantificatore ∃x P(x)

è una proposizione vera se nell’universo èpossibile trovare un esempio;è una proposizione falsa se P(x) è falsaassegnando ad x ogni valore dell’universo.


22


29

Quantificatori

Analizzando il variare dei valori di verità nella paginaprecedente si può concludere che

“¬(

∀x P(x))

” è equivalente a “∃x(

¬P(x))

”

“¬(

∃x P(x))

” è equivalente a “∀x(

¬P(x))

”



30

Insiemi

Definizione – Dati due insiemi A e B, si dice che B èun sottoinsieme di A se ogni elemento di B è ancheun elemento di A.

Si scrive allora B ⊆ A, ovvero A ⊇ B(che si legge “B è contenuto in A”, ovvero“A contiene B”).

La definizione di sottoinsieme corrisponde allaseguente proposizione

∀x(

x ∈ B → x ∈ A)



31

Eguaglianza di insiemi

Definizione – Dati due insiemi A e B diremo che A eB sono uguali se è vero che

(A ⊆ B) ∧ (B ⊆ A)

Scriveremo allora A = B.

In caso contrario scriveremo A 6= B.



32


La definizione di eguaglianza di insiemi corrispondealla seguente proposizione

∀x(

(

x ∈ B → x ∈ A)

∧(

x ∈ A → x ∈ B)

)

che è equivalente alla proposizione

∀x(

x ∈ B ↔ x ∈ A)

In altre parole gli insiemi A e B sono uguali se esoltanto se hanno gli stessi elementi.


23


1


CdL Informatica

15 ottobre 2003





2

Avvertenze

Queste fotocopie sono distribuite solo come indicazionedegli argomenti svolti a lezione e NON sostituiscono in

alcun modo il libro di testo:


Al libro di testo si rimanda per l’effettivo svolgimento degliargomenti (e per la rettifica di eventuali errori contenuti in

queste pagine).



3

Cenni di logica formalee di teoria degli insiemi



4

Insiemi

Definizione – Dati due insiemi A e B, si dice che B è unsottoinsieme di A se ogni elemento di B è anche unelemento di A.

Si scrive allora B ⊆ A, ovvero A ⊇ B(che si legge “B è contenuto in A”, ovvero“A contiene B”).

La definizione di sottoinsieme corrisponde alla seguenteproposizione

∀x(

x ∈ B → x ∈ A)


24


5


Definizione – Dati due insiemi A e B diremo che A e Bsono uguali se è vero che

(A ⊆ B) ∧ (B ⊆ A)

Scriveremo allora A = B.

In caso contrario scriveremo A 6= B.



6


La definizione di eguaglianza di insiemi corrisponde allaseguente proposizione

∀x(

(

x ∈ B → x ∈ A)

∧(

x ∈ A → x ∈ B)

)

che è equivalente alla proposizione

∀x(

x ∈ B ↔ x ∈ A)

In altre parole gli insiemi A e B sono uguali se e soltantose hanno gli stessi elementi.



7

Insieme vuoto

L’insieme vuoto, denotato con ∅, è l’insieme che rendefalsa la proposizione

x ∈ ∅

qualunque sia x.

Questo in particolare significa che, qualunque sial’insieme A si ha ∅ ⊆ A.È infatti sufficiente osservare che è sempre vera laproposizione

∀x(

x ∈ ∅ → x ∈ A)



8

Insieme universo

Per “simmetria” vorremmo trovare un analogodell’insieme vuoto che dia “vero”, cioè un insieme X percui, qualunque sia x, sia sempre vera la proposizione

x ∈ X

Questo non è possibile.(Si veda ad esempio P. R. Halmos, Naive Set Theory,Springer, o la traduzione in italiano di questo testo.)

È però possibile fissare un contesto, in modo daoperare in un insieme che contenga tutti gli elementi.Ad esempio se vogliamo mostrare una proprietà deinumeri reali, ci accordiamo a priori per operarenell’insieme R.


25


9

Insieme universo

A volte è utile fissare un contesto, ovvero accordarsi suun insieme U che contenga tutti gli elementi che stiamoprendendo in considerazione. Fissato questo contesto, laproposizione

x ∈ U

è sempre vera, qualunque sia x.

Questo in particolare significa che, qualunque sial’insieme A si ha A ⊆ U .È infatti sufficiente osservare che è sempre vera laproposizione

∀x(

x ∈ A → x ∈ U)



10

Esempi

{x | (x ∈ Z) ∧ (2 < x < 5)} ={x ∈ Z | 2 < x < 5} = {3, 4}

{x ∈ N | (x è un numero primo) ∧ (3 ≤ x ≤ 15)} ={3, 5, 7, 11, 13}

{x | ∃y ∈ Z (x = 2 · y)}, cioè l’insieme dei numeri(interi) pari{

x ∈ Q | x2 − 4 = 0}

= {2,−2}

(Facchini p. 4)



11

Esempi

Osserviamo che in un insieme non si consideral’ordine (e le eventuali ripetizioni) nell’elenco deglielementi. I seguenti insiemi coincidono{a, b} = {b, a} = {a, a, b} = {a, a, a, b, a, b, b}.

I due simboli x e {x} indicano cose diverse (e nonvanno confusi!)

Analogamente i simboli ∅, {∅}, {∅, {∅}}, . . .Ha perfettamente senso scrivere ∅ ∈ {∅}!



12

Operazioni tra insiemi

Dati due insiemi A e B, possiamo considerare

l’unione di A e B, cioè l’insieme

A ∪ B = {x | (x ∈ A) ∨ (x ∈ B)}

l’intersezione di A e B, cioè l’insieme

A ∩ B = {x | (x ∈ A) ∧ (x ∈ B)}

la differenza di A e B (o il complementare di B inA, o il complemento di B in A, che si legge anchesemplicemente A meno B), cioè l’insieme

A \ B = {x | (x ∈ A) ∧ (x 6∈ B)}


26


13

Operazioni tra insiemi

la differenza simmetrica di A e B, cioè l’insieme

A4 B = {x | (x ∈ A)⊕ (x ∈ B)}

il complemento di A, cioè l’insieme

A = {x | x 6∈ A}



14

Esempi

Dato un insieme, ad esempio

A = {1, 2, 3, 4, 5}

è possibile rappresentarlo tramite un diagramma diquesto tipo

12

345

(Diagramma di Eulero-Venn.)



15

Questioni organizzative

Lunedì 20 ottobre cominciano le esercitazioni(Dott. P. Galbiati). Si inizia alle ore 13.30.

Il ricevimento studenti di lunedì 20 ottobre 2003 èposticipato a martedì 21 ottobre dalle 14.30 alle16.30.



16

Credits


“A. Facchini, Algebra e matematica discreta,Decibel–Zanichelli” (capitolo 5);


P. R. Halmos, Naive Set Theory, Springer (anche initaliano).


27


17

Sito web del corso

Il sito ufficiale del corso di laurea èwww.disco.unimib.it

(per informazioni dalla “segreteria”: date e risultati degliesami, variazioni dell’orario, programma ‘ufficiale’ . . . )

Come negli anni passati sarà al più presto attivo ancheun sito web, contenente informazioni relative aicontenuti del corso. L’indirizzo è

www.matapp.unimib.it/marina/did/mdis03/(sono anche attive le pagine relative ai corsi tenuti neglianni accademici passati: potete già trovare una buonaraccolta di testi dei temi d’esame).



18

Esempi

Anche le operazioni tra insiemi possono essererappresentate tramite diagramma.Siano A = {1, 2, 3, 4, 5} e B = {0, 2, 4, 8}I due insiemi possono allora essere rappresentati daldiagramma

A B

12

345

0

8



19

Diagrammi di Eulero-Venn

In generale un insieme è rappresentato da una curvachiusa (in generale un ovale)

Gli elementi dell’insieme sono semplicemente elencati orappresentati da “pallini”.Una colorazione uniforme in generale sta ad indicare latotalità degli elementi dell’insieme.



20

Unione

l’unione di A e B è l’insieme

A ∪ B = {x | (x ∈ A) ∨ (x ∈ B)}

AB

L’insieme A ∪ B corrisponde all’area colorata in giallo.


28


21

Intersezione

l’intersezione di A e B è l’insieme

A ∩ B = {x | (x ∈ A) ∧ (x ∈ B)}

AB

L’insieme A ∩ B corrisponde all’area colorata in verde.



22

Differenza

Nel diagramma appena visto

AB

individuiamo anche

A \ B = {x | (x ∈ A) ∧ (x 6∈ B)}

B \ A = {x | (x ∈ B) ∧ (x 6∈ A)}



23

Differenza simmetrica

Per quel che riguarda la differenza simmetrica

la differenza simmetrica di A e B è l’insieme

A4 B = {x | (x ∈ A)⊕ (x ∈ B)}

AB

L’insieme A4 B corrisponde all’area colorata in giallo.



24

Complemento

Per individuare il complemento di Ail complemento di A è l’insieme

A = {x | x 6∈ A}

occorre accordarsi (anche nel diagramma) su cosa siintenda come universo

A

U

A L’insieme Acorrispondeall’area coloratain giallo.


29


25

Insiemi e logica proposizionale

I concetti di insieme e di proposizione sono strettamentecollegati tra loro.

Ad esempio per definire le operazioni tra gli insiemi(unione, intersezione, . . . ) abbiamo utilizzato leoperazioni tra proposizioni.

Prima di proseguire ricordiamo un paio di definizioni.



26

Tautologie e contraddizioni

Definizione – Una proposizione composta P cheassume valore di verità V qualunque siano i valori diverità delle proposizioni componenti (p, q, r, . . . ) è dettatautologia.

Definizione – Una proposizione composta P cheassume valore di verità F qualunque siano i valori diverità delle proposizioni componenti (p, q, r, . . . ) è dettacontraddizione.

Definizione – Le preposizioni p e q sono equivalenti see soltanto se la proposizione p ↔ q è una tautologia.



27

Identità insiemistiche

Le equivalenze logiche fondamentali introdotte le scorselezioni permettono di ricavare identità insiemistichefondamentali.Ad esempio:

(p ∧ ¬p) ⇐⇒ F

Permette di mostrare che, dato un qualunque insieme A,si ha A ∩ A = ∅.Infatti la proposizione x ∈ (A ∩ A) è equivalente allaproposizione (x ∈ A) ∧ (x ∈ A).A sua volta (x ∈ A) ∧ (x ∈ A) è equivalente a(x ∈ A) ∧ (x 6∈ A) ovvero a (x ∈ A) ∧ ¬(x ∈ A).Infine (x ∈ A) ∧ ¬(x ∈ A) è una contraddizione.



28

Identità insiemistiche

Riassumendo in un’unico schema

x ∈ (A ∩ A) ⇐⇒ (x ∈ A) ∧ (x ∈ A)

⇐⇒ (x ∈ A) ∧ (x 6∈ A)

⇐⇒ (x ∈ A) ∧ ¬(x ∈ A)

⇐⇒ F

qualunque sia x.

Questo significaA ∩ A = ∅


30


29

De Morgan

Anche per gli insiemi valgono le analoghe delle leggi diDe Morgan. Ad esempio la

¬(p ∧ q) ⇐⇒ ¬p ∨ ¬qsi traduce in

A ∩ B = A ∪ B

Infatti x ∈ A ∩ B è equivalente a x 6∈ (A ∩ B).A sua volta x 6∈ (A ∩ B) è equivalente a ¬

(

x ∈ (A ∩ B))

.A sua volta ¬

(

x ∈ (A ∩ B))

è equivalente a¬

(

(x ∈ A) ∧ (x ∈ B))

.A questo punto possiamo applicare De Morgan eottenere la proposizione ¬(x ∈ A) ∨ ¬(x ∈ B).



30

De Morgan

Concludiamo riassumendo in uno schema

x ∈ A ∩ B ⇐⇒ x 6∈ (A ∩ B)

⇐⇒ ¬(

x ∈ (A ∩ B))

⇐⇒ ¬(

(x ∈ A) ∧ (x ∈ B))

⇐⇒ ¬(x ∈ A) ∨ ¬(x ∈ B)

⇐⇒ (x 6∈ A) ∨ (x 6∈ B)

⇐⇒ (x ∈ A) ∨ (x ∈ B)

⇐⇒ x ∈(

A ∪ B)

qualunque sia x.

Queste equivalenze ci permettono di concludere cheA ∩ B = A ∪ B.



31

Doppia inclusione

L’eguaglianza di due insiemi si può anche dimostrareapplicando alla lettera la definizione:

per definizione dati due insiemi A e B, si ha che A = Bse e solo se (A ⊆ B) ∧ (B ⊆ A).

Mostrare che A ∩ B = A ∪ B è quindi equivalente amostrare le due inclusioni

A ∩ B ⊆ A ∪ B

A ∪ B ⊆ A ∩ B



32

Doppia inclusione

Mostriamo che A ∩ B ⊆ A ∪ B

Se x ∈ A ∩ B, per definizione x 6∈ (A ∩ B).

Questo può accadere solo se almeno uno tra A e B noncontiene x.

Cioè se (x 6∈ A) ∨ (x 6∈ B), ovvero (x ∈ A) ∨ (x ∈ B).

Il che significa x ∈ (A ∪ B)

Abbiamo cioè dimostrato(

x ∈ A ∩ B)

→(

x ∈ (A ∪ B))

che è l’inclusione voluta.


31


33

Doppia inclusione

Viceversa mostriamo che A ∪ B ⊆ A ∩ B

Se x ∈ A ∪ B, per definizione (x ∈ A) ∨ (x ∈ B), ovvero(x 6∈ A) ∨ (x 6∈ B).

Questo può accadere solo se almeno uno tra A e B noncontiene x.

Ovvero se x 6∈ (A ∩ B).

Il che significa x ∈ (A ∪ B)

Abbiamo cioè dimostrato(

x ∈ (A ∪ B))

→(

x ∈ A ∩ B)

che è l’inclusione voluta.Matematica Discreta (elementi) – E-O – p. 33


34

De Morgan

La legge di De Morgan appena dimostrata può ancheessere schematizzata con un diagramma di Eulero Venn

A ∩ B = A ∪ B

U

AB



35

Esercizi

Mostrare le seguenti identità insiemistiche

A ∪ B = A ∩ BA ∪ A = AA ∩ B = B ∩ A

(A) = A

A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)

A ∪ (A ∩ B) = A

(A ∪ B) ∪ C = A ∪ (B ∪ C)

A4 B = (A ∪ B) \ (B ∩ A) = (A \ B) ∪ (B \ A).



36

Tecniche di dimostrazione

Le tautologie fin qui viste ci servono anche per introdurrealcune tecniche di dimostrazione.

Fare una dimostrazione in generale significa mostrareche una data proposizione è vera.

Ci sono proposizioni a cui è immediato attribuire unvalore di verità

“5 > 1”

Ce ne sono però di più complicate“ogni numero naturale è esprimibilecome somma di due numeri primi”

(vera o falsa???).


32


37


Una dimostrazione consiste nel sostituire proposizionicon proposizioni equivalenti.

Non sempre è possibile trovare una proposizioneequivalente a quella che vogliamo dimostrare, in questocaso si possono applicare ragionamenti particolari, dettiregole di deduzione o regole di inferenza.

Osserviamo che in generale un teorema matematico èuna proposizione del tipo

p → q

In tal caso la proposizione “p” è detta ipotesi, mentre laproposizione “q” è detta tesi.



38

Regole di inferenza

Osserviamo che la proposizione

p → (p ∨ q)

è una tautologia.Il fatto che questa sia una tautologia

se p è una proposizione vera,

ci permette di dedurre che

p ∨ q è una proposizione vera.

Schematizziamo questa regola con questo simbolo:

p∴ p ∨ q



39

Regole di infrenza

Analogamente la tautologia

(p ∧ q) → p

ci permette di ricavare la regola di inferenza

p ∧ q∴ p

Cioè se sappiamo che la proposizione p ∧ q è vera,possiamo dedurre che la proposizione p è vera.



40

Modus ponens

La tautologia(p ∧ (p → q)) → q


pp → q

∴ q

Sapendo che la proposizione “p” è vera, e che laproposizione “p → q” è vera, possiamo dedurre che laproposizone “q” è vera.


33


41

Esercizio

Mostriamo che (p ∧ (p → q)) → q è una tautologia.Infatti

(

(

p ∧ (p → q))

→ q)

⇐⇒(

¬(

p ∧ (p → q))

∨ q)

⇐⇒(

(

¬p ∨ ¬(p → q))

∨ q)

⇐⇒(

(

¬p ∨ ¬(¬p ∨ q))

∨ q)

⇐⇒(

(

¬p ∨ (p ∧ ¬q))

∨ q)

⇐⇒(

(

(¬p ∨ p) ∧ (¬p ∨ ¬q))

∨ q)



42

Esercizio

⇐⇒(

(

(¬p ∨ p) ∧ (¬p ∨ ¬q))

∨ q)

⇐⇒(

(

V ∧ (¬p ∨ ¬q))

∨ q)

⇐⇒(

(

¬p ∨ ¬q)

∨ q)

⇐⇒(

¬p ∨(

¬q ∨ q)

)

⇐⇒(

¬p ∨ V)

⇐⇒ V

In conclusione(

(

p ∧ (p → q))

→ q)

⇐⇒ V .Matematica Discreta (elementi) – E-O – p. 42


43

modus tolens

La tautologia

(¬q ∧ (p → q)) → ¬p


¬qp → q

∴ ¬p

Sapendo che la proposizione “q” è falsa, e che laproposizione “p → q” è vera, possiamo dedurre che laproposizone “p” è falsa.



44

Sillogismo ipotetico

La tautologia(

(p → q) ∧ (q → r))

→ (p → r)


p → qq → r

∴ p → r

Sapendo che la proposizione “p → q” è vera, e che laproposizione “q → r” è vera, possiamo dedurre che laproposizone “p → r” è vera.


34


45

Esercizio

Mostriamo che(

(p → q) ∧ (q → r))

→ (p → r) è unatautologia. Infatti

(

(p → q) ∧ (q → r))

→ (p → r)⇐⇒ ¬

(

(p → q) ∧ (q → r))

∨ (p → r)

⇐⇒(

¬(p → q) ∨ ¬(q → r))

∨ (p → r)

⇐⇒ ¬(p → q) ∨ ¬(q → r) ∨ (p → r)

⇐⇒ ¬(¬p ∨ q) ∨ ¬(¬q ∨ r) ∨ (¬p ∨ r)

⇐⇒ (p ∧ ¬q) ∨ (q ∧ ¬r) ∨ (¬p ∨ r)

⇐⇒(

(p ∧ ¬q) ∨ ¬p)

∨(

(q ∧ ¬r) ∨ r)



46

Esercizio

⇐⇒(

(p ∧ ¬q) ∨ ¬p)

∨(

(q ∧ ¬r) ∨ r)

⇐⇒(

(p ∨ ¬p) ∧ (¬q ∨ ¬p))

∨(

(q ∨ r) ∧ (¬r ∨ r))

⇐⇒(

V ∧ (¬q ∨ ¬p))

∨(

(q ∨ r) ∧ V)

⇐⇒ (¬q ∨ ¬p) ∨ (q ∨ r)

⇐⇒ (¬q ∨ q) ∨ (¬p ∨ r)

⇐⇒ V ∨ (¬p ∨ r)

⇐⇒ (¬p ∨ r)

⇐⇒ (p → r)



47

Sillogismo disgiuntivo

La tautologia(

(p ∨ q) ∧ ¬p)

→ q


p ∨ q¬p

∴ q

Sapendo che la proposizione “p ∨ q” è vera, e che laproposizione “p” è falsa, possiamo dedurre che laproposizone “q” è vera.



48

Falsi amici

Attenzione però: la proposizione

((p → q) ∧ q) → p

non è una tautologia.

È quindi un grosso errore pensare di applicare la regoladi inferenza

p → qq

∴ p

(errore nell’affermare la tesi).


35


49

Falsi amici

Attenzione però: la proposizione

((p → q) ∧ ¬p) → ¬q

non è una tautologia.

È quindi un grosso errore pensare di applicare la regoladi inferenza

p → q¬p

∴ ¬q

(errore nel negare l’ipotesi).



50

Dimostrazione indiretta

Le due proposizionip → q

e¬q → ¬p

sono equivalenti.

Una dimostrazione indiretta consiste nel dimostrare laproposizione contronominale.



51

Dimostrazione per assurdo

Volendo dimostrare che una proposizione p è vera, latecnica di dimostrazione per assurdo ci fornisce unmetodo per mostrare che ¬p non può che essere falsa.

Ci serviamo a questo scopo di una proposizione F falsa.E mostriamo che la proposizione

¬p → F

è vera.

Confrontando la tavola di verità che definisce “→”, l’unicovalore di verità per “¬p” che renda vera questaimplicazione è F.Come proposizione falsa è utile considerare unaproposizione del tipo “q ∧ ¬q”.



52

Esercizi

Mostrare, sia tramite tavola di verità che tramiteequivalenze di proposizioni, che le seguenti sonotautologie

(p ∧ q) → p

p → (p ∨ q)

¬p → (p → q)

(p ∧ q) → (p → q)

¬(p → q) → p

¬(p → q) → ¬q

[¬p ∧ (p ∨ q)] → qMatematica Discreta (elementi) – E-O – p. 52

36


1


CdL Informatica

22 ottobre 2003





2

Avvertenze





queste pagine).



3

Principio d’induzione



4


Nella scorsa lezione elencato una serie di regole dideduzione, che ci permettono di costruire unadimostrazione.

Rimandiamo gli esempi dell’utilizzo di queste tecnichealle dimostrazioni che incontreremo nello svolgimento diquesto corso.

Se l’universo prefissato è l’insieme dei numeri interiallora abbiamo una ulteriore tecnica di dimostrazione.


37


5

Principio di induzione

Sia P(n) un predicato che ha come universo l’insiemedei numeri interi Z. Allora vale la seguente regola dideduzione

∃n0 ∈ Z (P(n0))

∀n > n0 (P(n− 1) → P(n))

∴ ∀n ≥ n0 (P(n))

Se è possibile determinare un intero n0 tale cheP(n0) sia vera

e se per ogni fissato n > n0 è possibile dimostrareche l’implicazione P(n− 1) → P(n) è vera

allora è possibile dedurre che per qualunque assegnaton ≥ n0 la proposizione P(n) è vera. Matematica Discreta (elementi) – E-O – p. 5


6

Esempi

Esercizio (compitino 22 novembre 2002)

Dimostrare, utilizzando il principio di induzione, cheper ogni intero n ≥ 1 si ha

1 + 3 + 5 + . . . + (2n− 1) = n2

Soluzione:Per utilizzare il principio di induzione dobbiamocome prima cosa verificare che l’eguaglianza

1 + 3 + 5 + . . . + (2n− 1) = n2

è vera quando ad n sostituiamo il valore 1 (questovalore è dato dall’enunciato dell’esercizio).



7

Esempi

1 + 3 + 5 + . . . + (2n− 1) = n2 ??

Per n = 1 l’eguaglianza da dimostrare diventa

2 · 1− 1 = 12

che è vera.

A questo punto assumiamo vera l’eguaglianza pern− 1, ovvero assumiamo valida l’eguaglianza che siottiene sostituendo n− 1 ad n

1 + 3 + 5 + . . . +(

2(n− 1)− 1)

= (n− 1)2

(questa è quella che si chiama ipotesi induttiva)



8

Esempi

Assumendo valida l’ipotesi induttiva

1 + 3 + 5 + . . . +(

2(n− 1)− 1)

= (n− 1)2

valutiamo l’eguaglianza per il valore n. Si ha

1 + 3 + 5 + . . . + (2n− 1) =

=[

1 + 3 + 5 + . . . +(

2(n− 1)− 1)

]

+ (2n− 1) =

= (n− 1)2 + (2n− 1) =

= n2 − 2n + 1 + 2n− 1= n2

per l’ipotesi induttivaMatematica Discreta (elementi) – E-O – p. 8

38


9

Notazioni compatte

Per scrivere somme “ripetute” è possibile utilizzare unanotazione compatta.Nella scrittura di

1 + 3 + 5 + . . . + (2n− 1)

può essere utilizzando il simbolo di sommatorian

∑i=1

(2 i − 1)

Si può anche scrivere

n

∑j=1

(2 j− 1)n

∑k=1

(2 k− 1)n−1

∑k=0

(2 k + 1)



10

Notazioni compatte

Analoghi simboli esistono per le operazioni di prodotto,unione e intersezione

5

∏i=1

i2 = 12 · 22 · 32 · 42 · 52

4⋃

i=1

Ai = A1 ∪ A2 ∪ A3 ∪ A4

6⋂

i=1

Bi = B1 ∩ B2 ∩ B3 ∩ B4 ∩ B5 ∩ B6



11

Ancora insiemi

Definizione – Dati due insiemi A e B, il prodottocartesiano di A per B, che indichiamo con A× B, èl’insieme che ha come oggetti le coppie (ordinate) dielementi (a, b), tali che a ∈ A e b ∈ B.

Esempio – Consideriamo gli A = {1, 2, 4} eB = {3, 6, 9} allora A× B può essere ricavatocostruendo una tabella

3 6 91 (1, 3) (1, 6) (1, 9)

2 (2, 3) (2, 6) (2, 9)

4 (4, 3) (4, 6) (4, 9)



12

Corrispondenze

Il concetto di prodotto cartesiano ci permette diformalizzare il concetto di corrispondenza

Definizione – Dati due insiemi A e B, unacorrispondenza ρ di A in B è un qualsiasi sottoinsiemedi A× B.

Come abbiamo visto nelle scorse lezioni ci sono varimodi per indicare un insieme. Ad esempio sianoA = {1, 2, 4} e B = {3, 6, 9}. Possiamo definire

ρ1 = {(1, 3), (2, 6), (2, 9)}

ρ2 = {(x, y) | y = 2 x}

ρ3 = {(x, y) | la parola ‘x’ è composta da ‘y’ lettere}Matematica Discreta (elementi) – E-O – p. 12

39


13

Corrispondenze

Osserviamo anche che stando alla defizione data duecorrispondenze coincidono se coincidono come insiemi.

Per quel che riguarda gli esempi visti, ricordando che si èposto A = {1, 2, 4} e B = {3, 6, 9}

ρ2 = {(x, y) | y = 2 x} = ∅

ρ3 = {(x, y) | la parola ‘x’ è composta da ‘y’ lettere}= {(1, 3), (2, 3)}

Definizione – Data una corrispondenza ρ di A in B, sela coppia (a, b) ∈ ρ, allora diremo che a corrisponde a bnella corrispondenza ρ. Diremo anche che a è incorrispondenza con b. Scriveremo anche aρb.



14

Diagrammi

Anche le corrispondenze possono essere rappresentatecon diagrammi e frecce.Data una corrispondenza di A in B si disegnano idiagrammi di Eulero-Venn di A e B e si congiungonopunti corrispondenti con delle frecce

A B

��

��

�

��

��



15

Esempi

Rivedendo gli esempi con A = {1, 2, 4} e B = {3, 6, 9}

ρ1 = {(1, 3), (2, 6), (2, 9)}

A B

ρ1

1

2

4

3

6

9

Esercizio – Costruire i diagrammi analoghi di ρ2 e ρ3.Matematica Discreta (elementi) – E-O – p. 15


16

Applicazioni

Definizione – Una applicazione φ di A in B è unacorrispondenza di A in B tale che per ogni elementoa ∈ A esiste uno e un solo elemento b ∈ B tale che(a, b) ∈ φ.

Per indicare che φ è una applicazione scriveremo

φ : A → B

e se (a, b) ∈ φ, scriveremo anche

φ : a 7→ b

Diremo anche che b è immagine di a.


40


17

Esempi

Le ρ1, ρ2 e ρ3 viste non sono applicazioni.Nella ρ1 l’elemento 2 ha due immagini el’elemento 4 non ne ha nessuna.Nella ρ2 nessun elemento di A ha immagine.Nella ρ3 l’elemento 4 non ha immagine.

φ1 = {(x, 2x) | x ∈ Z} è una applicazione di Z

in Z.φ1 è l’applicazione che ad ogni intero x associal’intero 2x, scriviamo anche φ1 : x 7→ 2x.Nel caso di applicazioni si usa anche lanotazione φ1(x) = 2x



18

Nota

Secondo la nostra definizione gli insiemi A e B sonoparte integrante dell’applicazione.Le due applicazioni

f : Z → Z definita ponendo x 7→ 2x

h : R → R definita ponendo x 7→ 2xsono due applicazioni differenti.



19

Applicazioni

Data una applicazione φ : A → B

l’insieme A si dice dominio di φ;

l’insieme B si dice codominio di φ;

se b = φ(a), allora b è detta immagine di atramite φ;

se b = φ(a), allora a è detta retroimmagine, ocontroimmagine di b;

se A′ ⊆ A, allora φ(A′) = {φ(x) | x ∈ A′} è dettaimmagine di A′ tramite φ;

φ(A) è detta immagine dell’applicazione φ;



20

Applicazioni

se B′ ⊆ B, allora l’immagine inversa di B′ èl’insieme φ−1(B′) = {x ∈ A | φ(x) ∈ B′};

se b ∈ B, allora φ−1({b}) si scrive semplicementeφ−1(b) e consiste dell’insieme delle retroimmaginidell’elemento b

φ−1(b) = {x ∈ A | φ(x) = b}


41


21

Esempi

Consideriamo φ : Z → Z definita ponendo x 7→ 2x.

Z è sia dominio che codominio per φ;

se A′ = {1, 2, 5} allora φ(A′) = {2, 4, 10};

φ(A) è costituita dall’insieme di tutti i numeri interipari;

se B′ = {2, 3, 4}, allora φ−1(B′) = {1, 2};

φ−1(4) = {2}, mentre φ−1(7) = ∅.



22

Esempi

A Bφ

1

2

3

3

6

9

φ(A) = {3, 6};

φ−1(3) = {1}; φ−1(6) = {2, 3}; φ−1(9) = ∅;

φ−1({3, 6}) = A;

φ−1({6, 9}) = {2, 3}.



23

Applicazioni

Sia φ : A → B una applicazione. Allora

φ si dice iniettiva se è vero che

∀a1, a2 ∈ A(

(

φ(a1) = φ(a2))

→ (a1 = a2))

φ si dice suriettiva se

∀b ∈ B(

∃a ∈ A (φ(a) = b))

φ si dice biiettiva (o biunivoca) se è sia iniettivache suriettiva. φ è detta anche biiezione ocorrispondenza biunivoca.

Se φ : A → B è una biiezione si dice anche che A e Bsono in corrispondenza biunivoca.



24

Quantificatori multipli

Osserviamo che nelle definizioni di applicazione iniettivae suriettiva compaiono dei predicati con due variabili chesono quantificati due volte.

Più precisamente, per quel che riguarda la definizione diapplicazione iniettiva si utilizza il predicato

P(a1, a2) = “(

φ(a1) = φ(a2))

→ (a1 = a2)”

E la definizione corrisponde alla proposizione

∀a1(

∀a2 P(a1, a2))

che è equivalente alla

∀a2(

∀a1 P(a1, a2))


42


25


Dal momento che le due proposizioni sono equivalenti

∀a1(

∀a2 P(a1, a2))

⇐⇒ ∀a2(

∀a1 P(a1, a2))

abbiamo utilizzato la scrittura abbreviata

∀a1, a2 P(a1, a2)

Discorso analogo vale per il quantificatore esistenziale.Le due proposizioni sono equivalenti

∃a1(

∃a2 P(a1, a2))

⇐⇒ ∃a2(

∃a1 P(a1, a2))

e possono essere abbreviate nella scrittura

∃a1, a2 P(a1, a2)



26


Diverso discorso se si “mischiano” i quantificatori.Le due proposizioni seguenti non sono equivalenti

∃a1(

∀a2 P(a1, a2))

⇐⇒ ∀a2(

∃a1 P(a1, a2))

Intuitivamente, nella proposizione di sinistral’elemento a1 è “fissato una volta per tutte”; nellaproposizione di destra invece l’elemento a1 può“variare” al variare di a2.

Pertanto la seguente è una definizione sbagliata disuriettività

∃a ∈ A(

∀b ∈ B (φ(a) = b))



27


Osserviamo che abbiamo quattro possibilità

∃a ∈ A(

∀b ∈ B (φ(a) = b))

∀b ∈ B(

∃a ∈ A (φ(a) = b))

∀a ∈ A(

∃b ∈ B (φ(a) = b))

∃b ∈ B(

∀a ∈ A (φ(a) = b))

e solo una di queste corrisponde alla definizione giusta!



28


∃a ∈ A(

∀b ∈ B (φ(a) = b))

A B

φ

�

�

�

��

��

�

che non è una applicazione!


43


29


∀b ∈ B(

∃a ∈ A (φ(a) = b))

A B

φ

��

��

�

��

��

�

che è la definizione corretta di suriettività.



30


∀a ∈ A(

∃b ∈ B (φ(a) = b))

A B

φ

��

!

"

#$

%&

'

che non è una applicazione!



31


∃b ∈ B(

∀a ∈ A (φ(a) = b))

A B

φ

()

*+

,

-.

/0

1Matematica Discreta (elementi) – E-O – p. 31


32

Applicazioni iniettive

Osserviamo che la definizione di applicazione iniettiva

∀a1, a2 ∈ A(

(

φ(a1) = φ(a2))

→ (a1 = a2))

è equivalente alla sua contronominale

∀a1, a2 ∈ A(

(a1 6= a2) →(

φ(a1) 6= φ(a2))

)

Possiamo allora dire che φ è iniettiva se e solo seelementi distinti di A hanno immagini distinte in B.

Possiamo anche dire che ogni elemento b di B ha al piùuna controimmagine.


44


33

Applicazioni biunivoche

Osserviamo che φ : A → B è una applicazione biunivocase

ogni elemento a ∈ A ha una e una sola immagineφ(a) = b in B

[questa non è altro che la definizione diapplicazione]

ogni elemento b ∈ B ha una controimmagine[essendo φ suriettiva]

ogni elemento b ∈ B ha al più una controimmagine[essendo φ iniettiva]

Ogni elemento b ∈ B ha una e una sola controimmagine.Matematica Discreta (elementi) – E-O – p. 33


34

Applicazioni biunivoche

Se φ : A → B è una applicazione biunivoca, ognielemento b ∈ B ha una e una sola controimmagine.

Questo ci permette di costruire una nuova applicazione,diciamo ψ : B → A che ad ogni elemento di b associaquell’unico elemento a tale che b = φ(a)

In altre parole

a = ψ(b) ⇐⇒ b = φ(a)

È immediato verificare che anche ψ è unacorrispondenza biunivoca.



35

Credits


“A. Facchini, Algebra e matematica discreta,Decibel–Zanichelli” (p. 31 “Principio di induzione” e§2 “Corrispondenze e applicazioni”);



36

Sito web del corso

Copia di questi lucidi è disponibile sul sito web del corso,all’indirizzo

www.matapp.unimib.it/marina/did/mdis03/(sono anche attive le pagine relative ai corsi tenuti neglianni accademici passati: potete già trovare una buonaraccolta di testi dei temi d’esame).


45


1


CdL Informatica

29 ottobre 2003





2

Avvertenze





queste pagine).



3

Applicazioni



4

Corrispondenze e applicazioni

Definizione – Dati due insiemi A e B, unacorrispondenza ρ di A in B è un qualsiasi sottoinsiemedi A× B.

Definizione – Una applicazione φ di A in B è unacorrispondenza di A in B tale che per ogni elementoa ∈ A esiste uno e un solo elemento b ∈ B tale che(a, b) ∈ φ.

Per indicare che φ è una applicazione scriveremo

φ : A → B

Se (a, b) ∈ φ, scriveremo anche φ : a 7→ b, oppureb = φ(a), e diremo che b è immagine di a.


46


5

Applicazioni

Sia φ : A → B una applicazione. Allora

φ si dice iniettiva se è vero che

∀a1, a2 ∈ A(

(

φ(a1) = φ(a2))

→ (a1 = a2))

φ si dice suriettiva se

∀b ∈ B(

∃a ∈ A (φ(a) = b))

φ si dice biiettiva (o biunivoca) se è sia iniettivache suriettiva. φ è detta anche biiezione ocorrispondenza biunivoca.

Se φ : A → B è una biiezione si dice anche che A e Bsono in corrispondenza biunivoca.



6

Restrizione di una applicazione

Se φ : A → B è una applicazione, e se A′ ⊆ A è unsottoinsieme di A, allora è possibile definire unaapplicazione φA′ : A′ → B, detta restrizione di φ ad A′

ponendo, per ogni a ∈ A′

φA′ : a 7→ φ(a)

Esercizi – Mostrare che

se φ : A → B è iniettiva, allora qualunque siaA′ ⊆ A si ha che φA′ è iniettiva;

se φ : A → B è suriettiva, non è detto che φA′ siaancora suriettiva.



7

Composizione di applicazioni

Siano A, B e C insiemi e siano φ : A → B e ψ : B → Cdue applicazioni.

Definizione – L’applicazione composta (oapplicazione prodotto) di φ per ψ è l’applicazione

ψ ◦ φ : A → C

definita ponendo per ogni a ∈ A

ψ ◦ φ : a 7→ ψ(φ(a))



8

Esempi

Sia φ1 : Z → N definita ponendo φ1 : z 7→ z2

e sia φ2 : N → N definita ponendo φ2 : n 7→ 2n

Allora

φ2 ◦ φ1 : Z → N è l’applicazione definita ponendoφ2 ◦ φ1 : z 7→ 2z2;

infatti (φ2 ◦ φ1)(z) = φ2(φ1(z)) = φ2(z2) = 2z2

non è invece definita φ1 ◦ φ2

infatti la composizione ψ ◦ φ è definita solo seφ : A → B e ψ : B → C.


47


9


Proposizione – Siano φ : A → B e ψ : B → Capplicazioni. Allora

se φ e ψ sono entrambe iniettive, allora anche ψ ◦ φ

è iniettiva;

se φ e ψ sono entrambe suriettive, allora ancheψ ◦ φ è suriettiva;

se φ e ψ sono entrambe biunivoche, allora ancheψ ◦ φ è biunivoca.

Dimostrazione – Siano φ e ψ iniettive. Siano a1 6= a2,dobbiamo mostrare che (ψ ◦ φ)(a1) 6= (ψ ◦ φ)(a2).



10


Essendo φ iniettiva, si ha che φ(a1) 6= φ(a2).Dal fatto che φ(a1) 6= φ(a2), essendo ψ iniettiva, segueche ψ(φ(a1)) 6= ψ(φ(a2)).

Questo è esattamente quello che volevamo dimostrarecome si legge nella seguente catena di relazioni

(ψ ◦ φ)(a1) = ψ(φ(a1)) 6= ψ(φ(a2)) = (ψ ◦ φ)(a2)

[Si lascia il resto della dimostrazione come esercizio.]



11


Osserviamo che non vale il viceversa della proposizioneappena dimostrata. In generale non è vero che se lacomposizione di due applicazioni è iniettiva, alloraentrambe le applicazioni sono iniettive:

A B Cφ ψ

��

��

��

��

�

��

Analogamente se la composizione è suriettiva non èdetto che entrambe le applicazioni siano suriettive.



12


La proposizione appena dimostrata ci dice che, dateφ : A → B e ψ : B → C applicazioni, allora

se φ e ψ sono entrambe iniettive, allora anche ψ ◦ φ

è iniettiva;

se φ e ψ sono entrambe suriettive, allora ancheψ ◦ φ è suriettiva;

Vale un parziale “viceversa”:


se ψ ◦ φ è iniettiva, allora φ è iniettiva;

se ψ ◦ φ è suriettiva, allora ψ è suriettiva.Matematica Discreta (elementi) – E-O – p. 12

48


13


Dimostrazione – Mostriamo che se φ non è iniettiva,allora ψ ◦ φ non è iniettiva.

Se φ non è iniettiva, possiamo trovare a1, a2 ∈ A tali chea1 6= a2, ma φ(a1) = φ(a2).

Ma allora ψ(φ(a1)) = ψ(φ(a2)).

Questo significa esattamente che(ψ ◦ φ)(a1) = (ψ ◦ φ)(a2), ovvero che ψ ◦ φ non èiniettiva.

[Si lascia il resto della dimostrazione come esercizio.]Matematica Discreta (elementi) – E-O – p. 13


14


La proposizione appena vista


se ψ ◦ φ è iniettiva, allora φ è iniettiva;

se ψ ◦ φ è suriettiva, allora ψ è suriettiva.

ha una immediata conseguenza:

Corollario – Siano φ : A → B e ψ : B → C applicazionie sia ψ ◦ φ biunivoca, allora

φ è iniettiva;

ψ è suriettiva.Matematica Discreta (elementi) – E-O – p. 14


15


Si ha la seguente

Proposizione – Sia A un insieme con m elementi e Bun insieme con n elementi. Supponiamo che m > n,allora non esistono applicazioni f : A → B iniettive.

Procediamo con una dimostrazione indiretta. Mostriamocioè che

se esiste una f : A → B iniettiva, allora m ≤ n.

Prima di proseguire introduciamo una nuova notazione:se A è un insieme con m elementi, allora scriviamo

|A| = m.

Diciamo anche che l’ordine (o la cardinalità) di A è m.Matematica Discreta (elementi) – E-O – p. 15


16


Possiamo servirci del seguente predicato

P(n) =se |B| = n e ∃ f : A → Biniettiva, allora |A| ≤ n

La proposizione che vogliamo dimostrare è equivalenteal quantificatore

∀n P(n)

Osserviamo che l’universo che stiamo prendendo inconsiderazione è l’insieme dei numeri naturali.

Possiamo perciò procedere per induzione su n.


49


17

Osservazione

Nella pagina precedente abbiamo utilizzato per la


una scrittura vicina al linguaggio “comune”.

È comunque importante mettere in evidenza che lastruttura della proposizione che stiamo considerando è

P(n) =(

(|B| = n) ∧ (∃ f : A → B in. ))

→ (|A| ≤ n)



18



∃n0 ∈ Z (P(n0))

∀n > n0 (P(n− 1) → P(n))

∴ ∀n ≥ n0 (P(n))



allora è possibile dedurre che per qualunque assegnaton ≥ n0 la proposizione P(n) è vera. Matematica Discreta (elementi) – E-O – p. 18


19

∃n0 ∈ Z (P(n0))

n0 = 0? Occorre considerare la proposizione P(0)

P(0) =se |B| = 0 e ∃ f : A → Biniettiva, allora |A| ≤ 0

e capire se

ha senso

è vera

Dire |B| = 0 è come dire che B non ha elementi, ovveroB = ∅.

Dal momento che f : A → B è una applicazione(iniettiva), significa che per ogni elemento a ∈ A esisteun elemento b ∈ B tale che b = f (a). Matematica Discreta (elementi) – E-O – p. 19


20

n0 = 0

Riscriviamo l’affermazione precedente

(a ∈ A) → (∃b ∈ B)

Dal momento che ∃b ∈ B è falsa, essendo B = ∅, l’unicomodo per cui l’implicazione sia vera è che

a ∈ A

sia falsa comunque si scelga a.

Cioè A = ∅.

In altre parole, se A è un insieme non vuoto, allora nonpossono esserci applicazioni f : A → ∅.


50


21

n0 = 0

Tornando alla

P(0) =se |B| = 0 e ∃ f : A → Biniettiva, allora |A| ≤ 0

P(0) ha senso, in quanto al simbolo |B| = 0 diamo ilsignificato B = ∅

P(0) è vera, in quanto abbiamo mostrato che si hanecessariamente A = ∅, ovvero |A| = 0 ed è veroche 0 ≤ 0.

Esercizio – Considerare il caso n0 = 1, ovvero stabilirese P(1) è vera.



22

∀n > n0 (P(n − 1) → P(n))

Assumiamo vera P(n− 1) ovvero

P(n− 1) =se |B| = n− 1 e ∃ f : A → Biniettiva, allora |A| ≤ n − 1

dobbiamo mostrare che è vera anche P(n), ovvero


Consideriamo perciò un insieme A, un insieme B con nelementi, e una applicazione f : A → B iniettiva.

Se fosse A = ∅, allora |A| = 0 ≤ n e la tesi sarebbeverificata. Matematica Discreta (elementi) – E-O – p. 22


23

∀n > n0 (P(n − 1) → P(n))

Possiamo perciò supporre ∃a ∈ A.

Sia b = f (a), e consideriamo

A∗ = A \ {a}

B∗ = B \ {b}

f ∗ l’applicazione da A∗ a B∗ che coincide con f sututti gli elementi di A∗

Essendo f iniettiva osserviamo che

f ∗ è ben definita in quanto non si ha mai chef (a∗) = b; in altre parole f (A∗) ⊆ B∗

f ∗ è iniettiva.Matematica Discreta (elementi) – E-O – p. 23


24

∀n > n0 (P(n − 1) → P(n))

Dal momento che |B∗| = n − 1, possiamo applicarel’ipotesi induttiva a A∗, B∗ e f ∗

P(n− 1) =se |B| = n− 1 e ∃ f : A → Biniettiva, allora |A| ≤ n − 1

Otteniamo allora|A∗| ≤ n− 1

Dal momento che

A = A∗ ∪ {a}

otteniamo che

|A| = |A∗|+ 1 ≤ (n− 1) + 1 = nMatematica Discreta (elementi) – E-O – p. 24

51


25

Esercizio

Abbiamo visto come il principio di induzione può essereutilizzato per dimostrare la proposizione

Proposizione – Sia A un insieme con m elementi e Bun insieme con n elementi.

Se esiste una applicazione f : A → B iniettiva,allora m ≤ n.

Se esite una applicazione f : A → B suriettiva,allora m ≥ n.

Esercizio – Utilizzare il principio di induzione perdimostrare la seconda parte della proposizione(suggerimento, utilizzare l’induzione su |A|).



26

Corrispondenze biunivoche

Di nuovo sia A un insieme con m elementi e B uninsieme con n elementi. Sia f : A → B una applicazionebiunivoca. (Ricordiamo che in questo caso diciamoanche che f è una corrispondenza biunivoca.)Per quanto visto possiamo immediatamente concludereche m = n.

Questo fatto ha una immediata conseguenza. Se A è uninsieme di m elementi e B è un suo sottoinsieme proprio,allora non può esistere una corrispondenza biunivocaf : A → B.

Questa proprietà distingue gli insiemi di cui possiamocontare gli elementi dagli insiemi di cui non possiamocontare gli elementi.



27

Corrispondenze biunivoche

Sia B l’insieme dei numeri pari e consideriamol’applicazione φ : Z → B definita ponendo

φ : z 7→ 2z

Osserviamo che

B 6= Z;

φ è iniettiva, in quanto se z1 6= z2 allora 2z1 6= 2z2;

φ è suriettiva, in quanto se b è un qualsiasi numeropari, allora b può essere scritto come b = 2a eproprio questa a è una controimmagine per b.

Quindi φ è una corrispondenza biunivoca.



28

Insiemi infiniti

Definizione – Due insiemi A e B si dicono equipotentise esiste una biiezione di A in B. Si dice anche che A eB hanno la stessa cardinalità.

Nel lucido precedente abbiamo visto l’esempio di unaapplicazione biunivoca φ : Z → B, dove B è l’insieme deinumeri pari.

Abbiamo quindi mostrato che Z è equipotente ad un suosottoinsieme proprio (B 6= Z).

Questa osservazione ci permette la seguente definizione:

Definizione – Un insieme è infinito se è equipotente adun suo sottoinsieme proprio.


52


29

Confronto di cardinalità

Ha senso/è possibile rispondere alla domanda“Sono di più i numeri interi o i numeri pari?”

In realtà abbiamo mostrato che l’insieme Z dei numeriinteri e l’insieme B dei numeri pari hanno la stessacardinalità.L’unico modo che abbiamo per confrontare insiemi infinitiè l’utilizzo di applicazioni:

Definizione – Siano A e B due insiemi.

se esiste una applicazione iniettiva da A a B diremoche A ha cardinalità minore o uguale a quella di B;

se esiste una applicazione suriettiva da A a Bdiremo che A ha cardinalità maggiore o uguale aquella di B. Matematica Discreta (elementi) – E-O – p. 29


30

Insiemi numerabili

Definizione – Un insieme è detto numerabile se èequipotente all’insieme N.

Esempi –N è numerabile

l’applicazione id : N → N definita ponendoid : n 7→ n è biunivoca

Z è numerabilel’applicazione φ : Z → N definita ponendo

φ(z) =

{

2z se z ≥ 0−2z− 1 se z < 0

è biunivoca. Matematica Discreta (elementi) – E-O – p. 30


31

Insiemi numerabili

Per completezza citiamo (senza per ora dimostrare) ilfatto che

ogni sottoinsieme infinito di N è numerabile;

il prodotto cartesiano N×N è numerabile;

il prodotto cartesiano Z×Z è numerabile;

Q è numerabile;

R non è numerabile;

C non è numerabile.

Siamo in grado di costruire un esempio di insieme infinitonon numerabile.



32

Insieme delle parti

Definizione – Dato un insieme A, l’insieme delle partidi A, che indichiamo con P(A), è l’insieme che ha comeelementi i sottoinsiemi di AEsempio – Consideriamo l’insieme A = {a, b, c}

{a}, {b}, {c}

{a, b}, {b, c}, {a, c}

{a, b, c}∅

Quindi P(A) ={∅, {a} , {b} , {c} , {a, b} , {b, c} , {a, c} , {a, b, c}}


53


33

Insieme delle parti

Proposizione – Sia A un insieme con n elementi. Alloral’insieme delle parti P(A) di A ha 2n elementi.

Dimostrazione – Consideriamo il predicato

P(n) = se |A| = n, allora |P(A)| = 2n

e procediamo per induzione su n.

∃n0 ∈ Z (P(n0)) – Consideriamo

P(0) = se |A| = 0, allora |P(A)| = 20

che è vera dal momento che P(∅) = {∅}.Matematica Discreta (elementi) – E-O – p. 33


34

P(n − 1) → P(n)

Assumiamo vera P(n− 1) ovvero

P(n− 1) = se |A| = n− 1, allora |P(A)| = 2n−1

Sia A un insieme con n elementi, cerchiamo di valutarequanti elementi ha P(A).Per semplicità scriviamo

A = {x1, x2, . . . , xn}

Fissiamo x1 ∈ A e cominciamo con il contare isottoinsiemi di A che non contengono x1.Osserviamo che X è un sottoinsieme di A che noncontiene x1 se e soltanto se X è un sottoinsieme di{x2, . . . , xn}.



35

P(n − 1) → P(n)

Osserviamo che per l’ipotesi induttiva, i sottoinsiemi di{x2, . . . , xn} sono 2n−1.Quindi i sottoinsiemi di A che non contengono x1 sono2n−1.

Contiamo ora i sottoinsiemi di A che contengono x1.

Ogni sottoinsieme di A che contiene x1 si ottiene da unsottoinsieme di A che non contiene x1 semplicementeaggiungendo x1.

Esempio – Se A = {a, b, c}, fissato a

∅, {b}, {c}, {b, c} non contengono a;

{a}, {a, b}, {a, c}, {a, b, c} contengono a.Matematica Discreta (elementi) – E-O – p. 35


36

P(n − 1) → P(n)

In altre parole si ha una corrispondenza biunivoca tra isottoinsiemi di A che non contengono x1 e i sottoinsiemidi A che contengono x1.

I sottoinsiemi di A che contengono x1 sono pertanto2n−1.

Il numero totale di sottoinsiemi di A è quindi dato da

2n−1 + 2n−1 = 2 · (2n−1) = 2n

che è quanto volevamo dimostrare.

(Facchini: definizione di P(A) p. 6, cardinalità di P(A)p. 73.)


54


37

Esercizio

Abbiamo fin qui enunciato il principio di induzione come

∃n0 ∈ Z (P(n0))

∀n > n0 (P(n− 1) → P(n))

∴ ∀n ≥ n0 (P(n))

È immediato osservare che tale regola di deduzione èequivalente alla seguente

∃n0 ∈ Z (P(n0))

∀n ≥ n0 (P(n) → P(n + 1))

∴ ∀n ≥ n0 (P(n))



38

Insiemi non numerabili

Siamo ora in grado di costruire un esempio di insiemenon numerabile.

Ci serve ricordare la tecnica di dimostrazione perassurdo.



39

Dimostrazione per assurdo

Volendo dimostrare che una proposizione p è vera, latecnica di dimostrazione per assurdo ci fornisce unmetodo per mostrare che ¬p non può che essere falsa.

Ci serviamo a questo scopo di una proposizione F falsa.E mostriamo che la proposizione

¬p → F

è vera.

Confrontando la tavola di verità che definisce “→”, l’unicovalore di verità per “¬p” che renda vera questaimplicazione è F.Come proposizione falsa è utile considerare unaproposizione del tipo “q ∧ ¬q”.



40


Proposizione – Sia A un insieme, allora A e P(A) nonsono equipotenti.

Dimostrazione – Procediamo per assurdo. Sia p laproposizione “A e P(A) non sono equipotenti” eassumiamo come ipotesi ¬p, ovvero “A e P(A) sonoequipotenti”.In altre parole esiste una biiezione φ : A → P(A).Possiamo allora costruire il sottoinsieme di A

X = {x ∈ A | x 6∈ φ(x)}

Essendo φ una biiezione, si ha che φ−1(X) è costituitoda un solo elemento, diciamo aX.


55


41


In altre parole aX è l’unico elemento di A tale cheφ(aX) = X.

Consideriamo la proposizione q = “aX ∈ X”

Per come è definito X

X = {x ∈ A | x 6∈ φ(x)}

per un qualsiasi elemento a ∈ A

a ∈ X ⇐⇒ a 6∈ φ(a)

in particolare questo vale per aX

aX ∈ X ⇐⇒ aX 6∈ φ(aX) = X

cioè q ∧ ¬q.Matematica Discreta (elementi) – E-O – p. 41


42


La contraddizione deriva dall’aver assunto vera laproposizione p

“A e P(A) sono equipotenti”e quindi la nostra tesi ¬p è vera

“A e P(A) non sono equipotenti”

Corollario – N e P(N) non sono equipotenti.

In altre parole P(N) è un insieme non numerabile.

Esercizio – Che cosa possiamo dire di P(P(N))?


56


1


CdL Informatica

5 novembre 2003





2

Avvertenze





queste pagine).



3

Contare



4

Contare applicazioni

Sia A un insieme con m elementi e B un insieme con nelementi:

quante sono le applicazioni di A in B?

A Ba1a2a3a4

...am

b1

b2

b3

...bn

Ad ognuno deicolori corrispondeuna applicazionedifferente.


57


5


Per definire l’applicazione f dobbiamo definire f (ai) perogni elemento ai di A.

Abbiamo n modi di definire f (ai) e ognuno di questi modiorigina una applicazione diversa.

Dobbiamo compiere m scelte, una per ogni ai.

Questo significa che il numero totale di possibilità è

n · n · . . . · n︸︷︷︸

m volte

cioènm



6

Scelte

Il conteggio che abbiamo fatto non è differente dalseguente problema

Un ristorante offre 5 primi e 4 secondi.Quanti sono i possibili menù?

La risposta è un “prodotto cartesiano”

PRIMIA B C D E

1

SECONDI234

Le possibilitàsono 4 · 5.Ogni sceltacorrisponde a unamoltiplicazione.



7


Proposizione – Siano A e B insiemi non vuoti.Supponiamo che A abbia m elementi e B abbia nelementi. Allora è possibile definire nm applicazioni di Ain B.

L’insieme di tutte le applicazioni di A in B è denotato conil simbolo BA.

[Questa è la proposizione 9.6 a p. 73: attenzione peròche l’ipotesi che A e B siano nonvuoti è necessaria!

Esercizio – Leggere attentamente la dimostrazione eosservare dove entrano in gioco le ipotesi A 6= ∅ eB 6= ∅.]



8

Contare applicazioni iniettive


quante sono le applicazioni iniettive di A in B?

Se m > n sappiamo che non ci sono applicazioniiniettive.

Se m ≤ n proviamo a costruire f assegnando leimmagini degli elementi di A.

Consideriamo il primo elemento, diciamo a1, di A,osserviamo che abbiamo n possibilità per f (a1).

Quando passiamo al secondo elemento, diciamo a2, diA, ci accorgiamo che perché f sia iniettiva abbiamo solon− 1 possibilità per f (a2).


58


9

Contare applicazioni iniettive

Per mantenere l’iniettività ad ogni passo le sceltediminuiscono di uno.

Questo significa che il numero totale di possibilità è

n · (n− 1) · (n− 2) . . .︸︷︷︸

m volte

cioèn · (n− 1) · (n− 2) · . . . ·

(n− (m− 1)

)

ovvero

n · (n− 1) · (n− 2) · . . . · (n−m + 1)

[Proposizione 9.8, p. 74]Matematica Discreta (elementi) – E-O – p. 9


10

Contare applicazioni biunivoche

Sia A un insieme con m elementi e B un insieme con nelementi e sia f : A → B una applicazione. Osserviamoche

f è iniettiva se e soltanto se | f (A)| = |A|;

f è suriettiva se e soltanto se | f (A)| = |B|.

Queste osservazioni hanno come immediataconseguenza il fatto che, se |A| = |B| allora

f è iniettiva se e soltanto se f è suriettiva



11



quante sono le applicazioni biunivoche di A in B?

Se A e B sono in corrispondenza biunivoca, alloram = n.

Se m = n allora ogni applicazione iniettiva è anchesuriettiva, e viceversa ogni applicazione suriettiva èanche iniettiva.

Ogni applicazione iniettiva è biunivoca, quindi il numerodelle applicazioni biunivoche corrisponde al numero delleapplicazioni iniettive cioè

n · (n− 1) · (n− 2) · . . . · (n−m + 1)Matematica Discreta (elementi) – E-O – p. 11


12


Se m = n, la

n · (n− 1) · (n− 2) · . . . · (n−m + 1)

si scriven · (n− 1) · (n− 2) · . . . · 1

Possiamo dare la seguente

Definizione – Il fattoriale di un numero naturale èdefinito ricorsivamente nel modo seguente

n! =

{1 se n = 0n · (n− 1)! se n > 0


59


13


Siano A e B insiemi con n elementi. Allora il numerodelle applicazioni biunivoche di A in B è pari a

n! = n · (n− 1) · (n− 2) · . . . · 1

In particolare il numero delle applicazioni biunivoche di Ain se stesso è

n!

Definizione – Se A è un insieme finito, una applicazionebiunivoca f : A → A è detta permutazione di A.



14

Contare sottoinsiemi

Sia A un insieme con n elementi:quanti sono i sottoinsiemi di A di ordine m?

Esempio – Sia A = {1, 2, 3, 4, 5}, quanti sono isottoinsiemi di ordine 2 di A?

Anche in questo caso si tratta di contare delle scelte.Infatti se X ⊆ A ha ordine 2, allora si può scrivere

X = {·, ·}

5 scelte 4 scelteAttenzione però che ogni sottoinsieme di due elementiammette una doppia scrittura

{1, 2} = {2, 1} Matematica Discreta (elementi) – E-O – p. 14


15


Sia A un insieme con n elementi:quanti sono i sottoinsiemi di A di ordine m?

Si può scrivereX = {·, ·, . . .}

n scelte n− 1 scelte

Il numero totale di scritture è quindi pari a

n · (n− 1) · (n− 2) . . .︸︷︷︸

m volte

cioèn · (n− 1) · (n− 2) · . . . · (n−m + 1)



16


Abbiamo contato il numero di possibili scritture, a questopunto dobbiamo capire

quante scritture diverse ammette un sottoinsieme diordine m?

È sufficiente osservare che ogni scrittura diversa di Xcorrisponde ad una permutazione degli elementi di X.

Esempio – Il sottoinsieme X = {1, 2} ammette le 2possibili scritture {1, 2} = {2, 1}

Il sottoinsieme X = {2, 4, 5} ammette le 3! possibiliscritture

{2, 4, 5} = {2, 5, 4} = {4, 2, 5} = {4, 5, 2} = {5, 2, 4} = {5, 4, 2}


60


17


Tornando all’esempio A = {1, 2, 3, 4, 5}

il numero dei sottoinsiemi di ordine 2 è5 · 4

2possiamo elencarli: {1, 2}, {1, 3}, {1, 4}, {1, 5},{2, 3}, {2, 4}, {2, 5}, {3, 4}, {3, 5}, {4, 5}

il numero dei sottoinsiemi di ordine 3 è5 · 4 · 3

3 · 2possiamo elencarli: {3, 4, 5}, {2, 4, 5}, {2, 3, 5},{2, 3, 4}, {1, 4, 5}, {1, 3, 5}, {1, 3, 4}, {1, 2, 5},{1, 2, 4}, {1, 2, 3}

Esercizio – Osservare che i sottoinsiemi di ordine 2sono tanti quanti i sottoinsiemi di ordine 3.



18


Riassumendo

Se A è un insieme di n elementi il numero dipossibili scritture di collezioni di m elementi è pari a

n · (n− 1) · (n− 2) · . . . · (n−m + 1)

ogni sottoinsieme di m elementi ammette m!scritture

possiamo concludere che il numero di sottoinsiemi diordine m in un insieme di n elementi è pari a

n · (n− 1) · (n− 2) · . . . · (n−m + 1)

m!



19

Coefficiente binomiale

Definizione – Il coefficiente binomiale(

nm

)

(che leggiamo “n su m”) è il numero di sottoinsiemi diordine m in un insieme di n elementi.

Per quanto visto(

nm

)

=n · (n− 1) · (n− 2) · . . . · (n−m + 1)

m!



20


Osserviamo che

il coefficiente binomiale (“numero di sottoinsiemi diordine m in un insieme di ordine n”) è definito solose 0 ≤ m ≤ n;

si han · (n− 1) · (n− 2) · . . . · (n−m + 1)

m!=

=

[n · (n− 1) · (n− 2) · . . . · (n−m + 1)

]· (n−m)!

(m!) · (n−m)!

=n!

m! · (n−m)!Matematica Discreta (elementi) – E-O – p. 20

61


21


Possiamo quindi scrivere(

nm

)

=n!

m! (n−m)!

Si dice anche che il coefficiente binomiale conta lecombinazioni di n oggetti presi m a m [p. 76–79].



22

Proprietà del coefficiente binomiale

(n0

)

= 1

“quanti sono i sottoinsiemi di ordine 0 in uninsieme di n elementi?”(

n0

)

=n!

0!(n− 0)!(

nn

)

= 1

“quanti sono i sottoinsiemi di ordine n in uninsieme di n elementi?”(

nn

)

=n!

n!(n− n)!Matematica Discreta (elementi) – E-O – p. 22


23

Proprietà del coefficiente binomiale

(nm

)

=

(n

n−m

)

“in un insieme A di n elementi si ha unacorrispondenza biunivoca

φ : X 7→ A \ X

tra i sottoinsiemi di m elementi e i sottoinsiemi din−m elementi”(

nn−m

)

=n!

(n−m)! · (n− (n−m))!=

n!(n−m)!(m!)Matematica Discreta (elementi) – E-O – p. 23


24

Triangolo di Tartaglia

Proposizione – Qualunque sia l’intero n, per ogni interom con 1 ≤ m ≤ n− 1 si ha

(nm

)

=

(n− 1m− 1

)

+

(n− 1

m

)

Dimostrazione –(

n− 1m− 1

)

+

(n− 1

m

)

=

=(n− 1)!

(m− 1)! · ((n− 1)− (m− 1))!+

(n− 1)!m! · ((n− 1)−m)!

=(n− 1)!

(m− 1)! · (n−m)!+

(n− 1)!m! · (n− 1−m)!


62


25


=(n− 1)!

(m− 1)! · (n−m)!+

(n− 1)!m! · (n− 1−m)!

=(n− 1)! ·m

(m− 1)! · (n−m)! ·m+

(n− 1)! · (n−m)

m! · (n− 1−m)! · (n−m)

=(n− 1)! ·m

m! · (n−m)!+

(n− 1)! · (n−m)

m! · (n−m)!

=

[(n− 1)! ·m

]+[(n− 1)! · (n−m)

]

m! · (n−m)!

=(n− 1)! ·

[m + (n−m)

]

m! · (n−m)!=

(n− 1)! · nm! · (n−m)!

=

(nm

)



26


La(

nm

)

=

(n− 1m− 1

)

+

(n− 1

m

)

(con 1 ≤ m ≤ n− 1) ci

permette di calcolare tutti i coefficienti binomialiricorsivamente

calcoliamo tutti i coefficienti binomiali per n = 0(0

0)

= 1


0)

= 1,(1

1)

= 1


0)

= 1,(2

2)

= 1, mentre(2

1)

=(1

0)

+(1

1)

= 2, siricava a partire da quelli già calcolati.



27


Possiamo schematizzare con il seguente triangolo:(

00

)

(10

) (11

)

(20

) (21

) (22

)

(30

) (31

) (32

) (33

)

(40

) (41

) (42

) (43

) (44

)



28


Passando ai numeri:

11 1

1 2 11 3 3 1

1 4 6 4 11 5 10 10 5 1

1 6 15 20 15 6 11 7 21 35 35 21 7 1

e così via . . .


63


29

Formula del binomio

Proposizione – Siano x, y ∈ R, con x, y 6= 0. Allora perogni intero n ≥ 1 si ha

(x + y)n =n

∑k=0

(nk

)

xn−kyk

Dimostrazione – Procediamo per induzione su nutilizzando il predicato

P(n) = (x + y)n =n

∑k=0

(nk

)

xn−kyk



30

∃n0 P(n0)

In questo caso n0 = 1 è dato dall’enunciato dellaproposizione. Scriviamo allora P(1)

P(1) = (x + y)1 =1

∑k=0

(1k

)

x1−kyk

Espandiamo la sommatoria

1

∑k=0

(1k

)

x1−kyk =

=

(10

)

x1−0y0 +

(11

)

x1−1y1 = x + y



31

P(n − 1) → P(n)

Assumiamo vera P(n− 1), cioè

P(n− 1) = (x + y)n−1 =n−1

∑k=0

(n− 1

k

)

x(n−1)−kyk

e andiamo a valutare (x + y)n. Si ha

(x + y)n = (x + y) · (x + y)n−1

= (x + y) ·

(n−1

∑k=0

(n− 1

k

)

x(n−1)−kyk

)

= x ·

(

. . .

)

+ y ·

(

. . .

)



32

P(n − 1) → P(n)

=n−1

∑k=0

(n− 1

k

)

x(n−1)−kyk x +n−1

∑k=0

(n− 1

k

)

x(n−1)−kyk y

=n−1

∑k=0

(n− 1

k

)

xn−kyk +n−1

∑k=0

(n− 1

k

)

x(n−1)−kyk+1

j = k + 1

=n−1

∑k=0

(n− 1

k

)

xn−kyk +n

∑j=1

(n− 1j− 1

)

xn−jyj

k = j

=n−1

∑k=0

(n− 1

k

)

xn−kyk +n

∑k=1

(n− 1k − 1

)

xn−kyk


64


33

P(n − 1) → P(n)

=n−1

∑k=0

(n− 1

k

)

xn−kyk +n

∑k=1

(n− 1k − 1

)

xn−kyk

=

(n− 1

0

)

xn−0y0 +n−1

∑k=1

(n− 1

k

)

xn−kyk

+n−1

∑k=1

(n− 1k− 1

)

xn−kyk +

(n− 1n− 1

)

xn−nyn

=

(n− 1

0

)

xn−0y0 +n−1

∑k=1

[(n− 1

k

)

+

(n− 1k− 1

)]

xn−kyk

+

(n− 1n− 1

)

xn−nyn



34

P(n − 1) → P(n)

Osservando che(

n− 10

)

=

(n0

)

e(

n− 1n− 1

)

=

(nn

)

(n− 1

k

)

+

(n− 1k − 1

)

=

(nk

)

possiamo concludere

(x + y)n =

(n0

)

xn−0y0 +n−1

∑k=1

(nk

)

xn−kyk +

(nn

)

xn−nyn

che è esattamente quanto volevamo dimostrare.



35

Esercizi

Utilizzando la formula del binomio, mostrare chen

∑k=0

(nk

)

= 2n

Dall’identità precedente concludere che se A è uninsieme con n elementi, allora P(A) ha 2n elementi.

Esercizi 9.18 e 9.19 del Facchini (gioco del Lotto edel Superenalotto).



36

Contare corrispondenze

Sia A un insieme di m elementi e B un insieme di nelementi:

quante sono le corrispondenze di A in B?

Ricordiamo che una corrispondenza di A in B è perdefinizione un qualsiasi sottoinsieme di A× B.

Si tratta allora di contare i sottoinsiemi del prodottocartesiano A× B, ovvero di contare gli elementi diP(A× B).Si ha

|P(A× B)| = 2|A×B| = 2m·n = (2m)n


65


37

Questioni di divisibilità in Z



38

Quoziente e resto

Proposizione – Siano a, b ∈ Z con b 6= 0, alloraesistono e sono univocamente determinati due interi q er tali che

a = b · q + r 0 ≤ r < |b|

Osservazioni –Con il simbolo |b| si indica il modulo di b, ovverol’applicazione | | : Z → Z definita ponendo

|z| ={

z se z ≥ 0−z se z < 0

Gli interi q e r sono detti rispettivamente quozientee resto della divisione di a per b.



39

Quoziente e resto

Dati ad esempio a = 7 e b = 3, quoziente e restodella divisione di a per b sono gli interi 2 e 1rispettivamente, infatti

7 = 3 · 2 + 1 0 ≤ 1 < |3|

Se invece a = −7 e b = 3 si ha cheil quoziente è −3il resto è 2

infatti

−7 = (−3) · 3 + 2 0 ≤ 2 < |3|



40

Divisibilità in Z

Dati a, b ∈ Z con b 6= 0 possiamo dire che b divide a se ilresto della divisione di a per b è zero. In realtà l’ipotesib 6= 0 può essere superata dando invece la seguente:

Definizione – Diremo che b divide a se e soltanto seesiste q ∈ Z tale che

a = b · q

Se b divide a, scriviamo b | a.

0 ∈ Z non divide alcun intero a 6= 0, infatti lacondizione a = 0 · q è soddisfatta se e solo se a = 0.

0 è divisibile per un qualunque b ∈ Z, infatti si puòsempre porre q = 0 e scrivere 0 = b · 0.


66


41

Relazioni

Introduciamo la seguente definizione

Definizione – Dato un insieme A, una corrispondenzadi A in A è detta relazione su A.

Ripassando la definizione di corrispondenza,possiamo dire che una relazione su A è un qualsiasisottoinsieme di A× AQuella appena introdotta è la relazione di “divide”,data da R = {(a, b) | b divide a} ⊆ A× A

Esercizio – Se A è un insieme con n elementi, quantesono le possibili relazioni su A?



42

Divisibilità, somma e prodotto

Se a | b e a | c, allora a | (b + c), infattia | b se e soltanto se esiste q1 tale che b = a · q1

a | c se e soltanto se esiste q2 tale che c = a · q2

ma allora b + c = a · (q1 + q2)

Se a | b e c è un qualunque intero, allora a | (b · c),infatti

a | b se e soltanto se esiste q tale che b = a · qma allora b · c = (a · q) · c = a · (qc)

Se a | b e b | a, allora a = ±b, infattiesistono q1 e q2 tali che b = a · q1 e a = b · q2

ma allora ab = (a · q1) · (b · q2) da cui q1 · q2 = 1Matematica Discreta (elementi) – E-O – p. 42


43

Numeri primi

Definizione – Un intero p 6= ±1 è detto primo se i suoidivisori sono solo ±1, ±p.

Osserviamo che secondo questa definizione 1 e −1 nonsono numeri primi.Osserviamo anche che 0 non è un numero primo inquanto ogni intero n divide 0.

Si ha il seguente

Teorema fondamentale dell’aritmetica – Ogni numerointero a 6= 0, 1,−1 è prodotto di numeri primi (nonnecessariamente distinti).Tale fattorizzazione è essenzialmente unica.Esempio – 6 = 2 · 3 = 3 · 2 = (−2) · (−3)= (−3) · (−2) Matematica Discreta (elementi) – E-O – p. 43


44

Numeri primi

Si ha il seguente

Teorema – Esistono infiniti numeri primi.

Dimostrazione – Supponiamo per assurdo che i numeriprimi siano in numero finito.Possiamo quindi elencarli: p1, p2, · · · , pn.

Consideriamo il numero a = (p1 · p2 · . . . · pn) + 1.Per il teorema fondamentale dell’aritmetica a è unprodotto di primi.In altre parole esiste un primo q (q 6= ±1) tale che q | a.Dal momento che la lista dei numeri primi èp1, p2, · · · , pn, il primo q deve essere uno di questi.Ma allora q | (p1 · p2 · . . . · pn)


67


45

Numeri primi

Dalle

q | a = (p1 · p2 · . . . · pn) + 1

q | (p1 · p2 · . . . · pn)

possiamo concludereq | 1

ma questa è una contraddizione in quanto q 6= ±1.


68


1


CdL Informatica

12 novembre 2003





2

Avvertenze





queste pagine).



3

Esercizi



4

Esercizi

Ricordando il risultato visto la scorsa lezione


a = b · q + r 0 ≤ r < |b|

Sia n un numero naturale, n ≥ 1. Si consideri lacorrispondenza fn : N → N che ad ogni numeronaturale x associa il resto della divisione di x per n.

fn è una applicazione?fn è iniettiva?fn è suriettiva?


69


5

Esercizi

Sia n un numero naturale, n ≥ 1. Si consideri lacorrispondenza gn : Z → Z che ad ogni numeronaturale x associa il resto della divisione di x per n.

gn è una applicazione?gn è iniettiva?gn è suriettiva?

Sia n un numero naturale come sopra, siaX = {0, 1, 2, . . . , n − 1} e si consideri lacorrispondenza hn : Z → X definita da

hn = {(a, b) | b è il resto della divisione di a per n}

hn è una applicazione? È iniettiva? È suriettiva?Matematica Discreta (elementi) – E-O – p. 5


6

Esercizi

Si consideri la corrispondenza h : N×N → N chead ogni coppia (a, b) in N×N associa il resto delladivisione di a per b.

h è una applicazione? È iniettiva? È suriettiva?

Si consideri la corrispondenza k : Z×Z → Z chead ogni coppia (a, b) in Z×Z associa il resto delladivisione di a per b.

k è una applicazione? È iniettiva? È suriettiva?

Si consideri la corrispondenza l : Z×Z → Z chead ogni coppia (a, b) in Z×Z associa il quozientedella divisione di a per b.

l è una applicazione? È iniettiva? È suriettiva?Matematica Discreta (elementi) – E-O – p. 6


7

Esercizi

Definizione – Dati a, b ∈ Z, diremo che b divide a, escriviamo b | a, se esiste un q ∈ Z tale che a = b · q.

EserciziConsideriamo la corrispondenza g : Z → N definitada

g = {(a, b) : a | b} ⊆ Z×N

g è una applicazione? È iniettiva? È suriettiva?

Consideriamo la corrispondenza h : Z → N definitada

h = {(a, b) : a | b ∧ b | a} ⊆ Z×N

h è una applicazione? È iniettiva? È suriettiva?Matematica Discreta (elementi) – E-O – p. 7


8

Massimo Comun Divisore

Dati due numeri naturali a e b, il massimo comundivisore di a e b è il più grande numero naturale chedivide sia a che b.

EserciziQual è il massimo comun divisore tra 10 e 12?

E tra 104 729 e 27 407?

Sia consideri la corrispondenza f : N×N → N

che ad ogni coppia (a, b) in N×N associa ilmassimo comun divisore tra a e b.

f è una applicazione?f è iniettiva?f è suriettiva?


70


9

Massimo Comun Divisore

Se vogliamo estendere la definizione di massimo comundivisore ai numeri interi, abbiamo bisogno di “tradurre” ilconcetto di più grande numero naturale.

Qual è il massimo comun divisore tra −10 e −12?

Come vedremo, la traduzione si può fare sostituendo “piùgrande” con “è divisibile da”. Diremo che d è il massimocomun divisore di a e b se e solo se

d | a e d | b

se d′ è un altro divisore comune di a e b, allora d′ | d



10

Esercizi

Sia consideri la corrispondenza f : Z×Z → Z chead ogni coppia (a, b) in Z×Z associa il massimocomun divisore tra a e b.

f è una applicazione? È iniettiva? È suriettiva?

Sia consideri la corrispondenza g : Z×Z → N chead ogni coppia (a, b) in Z×Z associa il massimocomun divisore positivo tra a e b.

g è una applicazione? È iniettiva? È suriettiva?



11

Esercizi

Sia A un insieme

Fissato B ⊆ A, si consideri la corrispondenzafB : P(A) → P(A) che ad ogni sottoinsieme X di Aassocia X ∩ B. fB è una applicazione? È iniettiva?È suriettiva?

Si consideri la corrispondenza g : P(A) → P(A)che ad ogni sottoinsieme X di A associa A \ X. g èuna applicazione? È iniettiva? È suriettiva?

Si consideri la corrispondenza h : P(A) → Adefinita da h = {(X, a) | a ∈ X}. h è unaapplicazione? È iniettiva? È suriettiva?


71


1


CdL Informatica

17 novembre 2003





2

Avvertenze





queste pagine).



3

Correzione compitino



4

Domande con risposta a scelta multipla

Siano p, q, r tre proposizioni. Allora:a) p ∨ (q ∧ r) ↔ (p ∨ q) ∧ (p ∨ r) è una tautologia;b) p ∨ (q ∧ r) ↔ (p ∨ q) ∧ (p ∨ r) è una

contraddizione;c) p ∨ (q ∧ r) ↔ (p ∨ q) ∧ (p ∨ r) non è una

contraddizione né una tautologia.

Si tratta della proprietà distributiva di ∨ rispetto a ∧.

Per mostrare che la proposizione data è una tautologia èsufficiente scriverne la tavola di verità


72


5

Proprietà distributiva di ∨ rispetto a ∧

p q r q ∧ r p ∨ (q ∧ r) p ∨ q p ∨ r (p ∨ q) ∧ (p ∨ r)V V V V V V V VF V V V V V V VV F V F V V V VF F V F F F V FV V F F V V V VF V F F F V F FV F F F V V V VF F F F F F F F

L’eguaglianza delle colonne in rosso implica l’equivalenzadelle due proposizioni.



6

Proposizioni e predicati

Si consideri la seguente funzione proposizionale (opredicato):

x + y = 5.

Allora:a) in Z, “x + y = 5” ha valore di verità “vero”;b) la proposizione “∀x ∈ Z ∃y ∈ Z : x + y = 5” ha

valore di verità “vero”;c) la proposizione “∃y ∈ Z ∀x ∈ Z : x + y = 5” ha

valore di verità “vero”.

Quanto alla risposta “a)”, notiamo che se non diamo unsignificato a x e y non siamo in grado di attribuire alcunvalore di verità all’espressione “x + y = 5”.



7


Relativamente alla risposta “c)”

la proposizione “∃y ∈ Z ∀x ∈ Z : x + y = 5” havalore di verità “vero”

notiamo che è richiesto di trovare un valore in Z daassegnare ad y tale che una volta fissato questo valore(y = . . . ) la proposizione

∀x ∈ Z : x + y = 5

è vera.D’altra parte se alla y è stato assegnato un valore in Z,la relazione x + y = 5 è valida per un solo valore di xcioè x = 5− y.



8


Relativamente alla risposta “b)”

la proposizione “∀x ∈ Z ∃y ∈ Z : x + y = 5” havalore di verità “vero”;

una volta assegnato x in Z è sempre possibile trovare uny in Z (un y che può dipendere da x) tale che x + y = 5.

È infatti sufficiente porre y = 5− x.

La proposizione è quindi vera.


73


9

Corrispondenze

Siano A e B due insiemi, di cardinalitàrispettivamente 3 e 2. Allora:a) ci sono esattamente 26 corrispondenze (o

relazioni) da A a B e il numero dicorrispondenze da B a A è uguale al numero dicorrispondenze da A a B;

b) ci sono esattamente 26 corrispondenze da A aB e il numero di corrispondenze da B a A èdiverso dal numero di corrispondenze da A a B;

c) ci sono esattamente 62 corrispondenze da Aa B.



10

Corrispondenze

Infatti dato un insieme A di n elementi e un insieme B dim elementi, una corrispondenza di A in B (o “da A a B”)è un qualsiasi sottoinsieme di A× B.

I sottoinsiemi di A× B sono gli elementi dell’insiemeP(A× B) delle parti di A× B.Dal momento che |A× B| = n ·m, si ha che|P(A× B)| = 2n·m = 22·3 = 26.

Osserviamo che |B× A| = m · n = n ·m, quindi anche ilnumero di corrispondenze di B in A è 2n·m.

NOTA – Ricordiamo che A× B 6= B× A.



11

Applicazioni

Dire quale delle seguenti affermazioni è vera:a) ogni applicazione iniettiva dall’insieme degli

interi Z in se stesso è suriettiva;b) per ogni intero positivo n, una applicazione

iniettiva dall’insieme degli interi compresi tra −ne n in se stesso è suriettiva;

c) esistono interi positivi n per cui sia possibilecostruire una applicazione iniettiva dall’insiemedegli interi compresi tra −n e n in se stesso chenon sia suriettiva.

Nella domanda “a)” è richiesto di considerare leapplicazioni di Z in se stesso, mentre nelle domande “b)”e “c)” è invece richiesto di considerare l’insiemeXn = {−n, . . . , 0, . . . , n}.



12

Applicazioni

Relativamente alla risposta “a)”

ogni applicazione iniettiva dall’insieme degli interi Z

in se stesso è suriettiva;

sappiamo che è falsa.

Infatti Z è un insieme infinito e questo significa che èpossibile costruire una corrispondenza biunivoca φ di Z

in un suo sottoinsieme proprio B.

Ma questo equivale a dire che abbiamo una applicazioneφ1 : Z → Z che è iniettiva ma non è suriettiva.

Possiamo infatti definire φ1 : Z → Z ponendoφ1(z) = φ(z) per ogni z ∈ Z.Infatti φ1(Z) = B 6= Z, e quindi φ1 non è suriettiva.


74


13

Applicazioni

Relativamente alle risposte “b)” e “c)”

per ogni intero positivo n, una applicazione iniettivadall’insieme degli interi compresi tra −n e n in sestesso è suriettiva;

esistono interi positivi n per cui sia possibilecostruire una applicazione iniettiva dall’insieme degliinteri compresi tra −n e n in se stesso che non siasuriettiva.

dal momento che Xn = {−n, . . . , 0, . . . , n} è invece uninsieme finito, sappiamo che ogni applicazione iniettiva diXn in se stesso è necessariamente suriettiva.



14

Applicazioni

Dati tre insiemi A, B, C, sia f una applicazione da Aa B, e g una applicazione da B a C. Allora:a) se f e g sono iniettive, g ◦ f è iniettiva;b) se f è iniettiva, g ◦ f è iniettiva;c) se f è iniettiva, g ◦ f è suriettiva.

Dati tre insiemi A, B, C, sia f una applicazione da Aa B, e g una applicazione da B a C. Allora:a) se f e g sono suriettive, g ◦ f è suriettiva;b) se g è suriettiva, g ◦ f è iniettiva;c) se g è suriettiva, g ◦ f è suriettiva.



15

Applicazioni

Abbiamo infatti visto la seguente

Proposizione – Dati tre insiemi A, B, C, sia f unaapplicazione da A a B, e g una applicazione da B a C.

Se f e g sono iniettive, allora g ◦ f è iniettiva.

Se f e g sono suriettive, allora g ◦ f è suriettiva.

[Facchini, p. 21]



16

Applicazioni

se f è iniettiva, allora g ◦ f è iniettiva?

A B C

f g

��

��

��

��

�

��

Osserviamo che g ◦ f non è iniettiva (vedi frecce blu).

L’esempio mostra anche che la falsità di

se f è iniettiva, allora g ◦ f è suriettivaMatematica Discreta (elementi) – E-O – p. 16

75


17

Applicazioni

se g è suriettiva, allora g ◦ f è suriettiva?

A B C

f g

�

��

��

��

�

��

��

Osserviamo che g ◦ f non è suriettiva (ad esempio nonha alcuna retroimmagine in A).

Le frecce blu mostrano anche la falsità di

se g è suriettiva, allora g ◦ f è suriettivaMatematica Discreta (elementi) – E-O – p. 17


18

Insieme delle parti

Si consideri un insieme A di n elementi e sia P(A)l’insieme delle parti di A.a) Si dica se esiste un’applicazione suriettiva di A

in P(A).b) Si dica se la corrispondenza (o relazione)

g = {(a, X) : a ∈ X} ⊆ A×P(A)

è o meno una applicazione.c) Si dica se la corrispondenza (o relazione)

h = {(a, {a}) : a ∈ A} ⊆ A×P(A)

è o meno una applicazione.



19

Insieme delle parti

Relativamente alla domanda “a)”

Si dica se esiste un’applicazione suriettiva di A inP(A).

è sufficiente osservare che se A ha n elementi, alloraP(A) ha 2n elementi.Occorre anche osservare che, qualunque sia n ≥ 0, si ha

n < 2n

Sappiamo allora che se A è un insieme di n elementi e Bè un insieme con m elementi con m > n, allora non cisono applicazioni suriettive di A in B.

Esercizio – Mostrare che per ogni n ≥ 0 si ha n < 2n.Matematica Discreta (elementi) – E-O – p. 19


20

Errori comuni

Si dica se esiste un’applicazione suriettiva di A inP(A).

Un errore comune è stato quello di considerare(implicitamente o esplicitamente) una particolareapplicazione di A in P(A), ma il testo (come si vede)non propone alcuna applicazione!

Osserviamo poi che non è ∅ ∈ P(A) a dare particolariproblemi (“∅ non ha una retroimmagine”)Ad esempio sia A = {x1, x2}, allora

x1 7→ ∅ x2 7→ {x1}

è una applicazione di A in P(A) in cui ∅ ha unaretroimmagine. Matematica Discreta (elementi) – E-O – p. 20

76


21

Errori comuni

Qualcuno ha scritto qualcosa tipo

Essendo |A| < |P(A)|, questo non èconcorde con la definizione di suriettività

Questo è un errore, perché la definizione di suriettivitànon ha nulla a che vedere con |A|.

Esercizio – L’affermazione “non esistono applicazionisuriettive di A in P(A)” è vera anche per insiemi infiniti.

Suggerimento: rivedere l’esempio di insieme nonnumerabile dato a lezione il 29 ottobre e la dimostrazionefatta in quel caso.



22

Insieme delle parti

Relativamente alla domanda “b)”

Si dica se la corrispondenza (o relazione)

g = {(a, X) : a ∈ X} ⊆ A×P(A)


si osserva che g è una corrispondenza di A in P(A),essendo g per definizione un sottoinsieme di A×P(A).

Per dire se g è una applicazione occorre verificare cheper ogni a ∈ A esiste una e una sola coppia (a, ?) ∈ gcon a come prima componente.

Occorre a questo punto distinguere due casi.



23

Insieme delle parti

Se l’insieme A contiene un solo elemento, diciamo a1,allora

A = {a1}

P(A) = {∅, {a1}}

Osserviamo quindi che g

g = {(a, X) : a ∈ X} ⊆ A×P(A)

si riduce all’unica coppia

(a1, {a1})

Quindi, se A ha un solo elemento, g è una applicazione

g : a1 7→ {a1}Matematica Discreta (elementi) – E-O – p. 23


24

Insieme delle parti

Se l’insieme A contiene almeno due elementi, diciamo a1e a2, allora

A = {a1, a2, . . .}P(A) = {∅, {a1} , {a2} , {a1, a2} , . . .}

Osserviamo quindi che g

g = {(a, X) : a ∈ X} ⊆ A×P(A)

contiene per lo meno gli elementi

(a1, {a1}), (a1, {a1, a2}), . . .

Quindi g non è una applicazione se A ha almeno dueelementi.


77


25

Insieme delle parti

Relativamente alla domanda “c)”

Si dica se la corrispondenza (o relazione)

h = {(a, {a}) : a ∈ A} ⊆ A×P(A)


osserviamo che, fissato un qualunque elemento a ∈ A,l’unica coppia in h che ha questo a come primacomponente è

(a, {a})

quindi h è l’applicazione

h : a 7→ {a}



26

Induzione

Mostrare per induzione che, per ogni x ∈ R diversoda 0 e da 1, si ha

n

∑i=0

xi =1− xn+1

1− x

Prima di cominciare occorre precisare

cosa sono x e n?

induzione su cosa?

qual è il predicato a cui applico l’induzione?

Durante la dimostrazione è importante descrivere ilpasso induttivo, precisando con chiarezza cosa è ipotesie cosa è tesi. Matematica Discreta (elementi) – E-O – p. 26


27

Induzione

n

∑i=0

xi =1− xn+1

1− x

per ipotesi x è un numero reale diverso da 0 e da 1.Questo significa che:

ha senso scrivere x0, più precisamente si hax0 = 1ha senso dividere per 1− xnon ha alcun senso fare “induzione su x”

n è un numero naturale, per cui ha senso definire lasomma ∑

ni=0 xi

tale scrittura ha senso per ogni n ≥ 0Matematica Discreta (elementi) – E-O – p. 27


28

Induzione

una volta fissato il numero reale x, il predicato P(n)cui applichiamo l’induzione è

n

∑i=0

xi =1− xn+1

1− x

la variabile rispetto alla quale argomentiamo perinduzione è il numero naturale nvogliamo mostrare che il predicato è vero per ognin ≥ 0


78


29

∃n0 P(n0)

per quanto detto possiamo assumere n0 = 0. Si ha0

∑i=0

xi = x0 = 1

1− x0+1

1− x=

1− x1− x

= 1

quindi P(n0), cioè

0

∑i=0

xi =1− x0+1

1− x

è vera.



30

P(n − 1) → P(n)

Assumiamo come ipotesi P(n− 1), cioè assumiamovera l’eguaglianza

n−1

∑i=0

xi =1− x(n−1)+1

1− x=

1− xn

1− x

(che d’ora in poi chiameremo ipotesi induttiva)

dobbiamo mostrare chen

∑i=0

xi =1− xn+1

1− x



31

P(n − 1) → P(n)

Andiamo a valutaren

∑i=0

xi

Si han

∑i=0

xi =n−1

∑i=0

xi + xn per l’ipotesi induttiva=

=1− xn

1− x+ xn =

1− xn + (1− x)xn

1− x=

=1− xn + xn − xn+1

1− x=

1− xn+1

1− xche è quanto volevamo dimostrare.


79


1


CdL Informatica

19 novembre 2003





2

Avvertenze





queste pagine).



3

Relazioni su un insieme

Dato un insieme A, ricordiamo che una relazione su A (o“in A”) è una corrispondenza di A in A, in altre parole

Definizione – Una relazione R su A è un qualsiasisottoinsieme di A× A.

Esempio – Dato l’insieme A = {1, 2, 3, 4, 5, 6}, leseguenti sono relazioni su A:

R1 ={(1, 1), (2, 2), (3, 3), (4, 4), (4, 5), (5, 4), (5, 5)};

R2 = {(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)};

R3 ={(1, 6), (2, 1), (3, 4), (4, 4), (5, 1), (5, 2), (6, 3)}.



4


Dato un insieme A e una relazione R su A, se per dueelementi a, b ∈ A la coppia (a, b) ∈ R allora diremo chea è in relazione con b e scriveremo aRb.

Tornando all’esempio

R1 = {(1, 1), (2, 2), (3, 3), (4, 4), (4, 5), (5, 4), (5, 5)}

possiamo dire che

1 è in relazione con 11R11

1 non è in relazione con 21 6R1 2


80


5


Relativamente al terzo esempio

R3 = {(1, 6), (2, 1), (3, 4), (4, 4), (5, 1), (5, 2), (6, 3)}

osserviamo che

(2, 1) ∈ R3ovvero 2 è in relazione con 1

ma (1, 2) 6∈ R3cioè 1 non è in relazione con 2.



6

Esempi di relazioni

Sia A = N. Consideriamo

δ = {(x, y) | (x, y ∈ N) ∧ (y = 2x)}

Si ha

(2, 4) ∈ δ, ovvero 2 δ 4

(1, 7) 6∈ δ, ovvero 1 6 δ 7

in generale la coppia (x, y) ∈ δ se e solo se laseconda componente y è il doppio della primacomponente x

Quest’ultima osservazione ci permette di definire δ inmaniera alternativa ponendo

x δ y se e solo se y = 2xMatematica Discreta (elementi) – E-O – p. 6


7

Relazioni e predicati

Le relazioni, essendo insiemi, possono essere definitetramite predicati

Dato un predicato P(x, y) di due variabili (che abbiasenso in A), è possibile definire una relazione in A

R = {(x, y) | P(x, y)} ⊆ A× A

Assegnati due elementi di A, diciamo x e y, possiamodire che

x è in relazione con y se e solo se P(x, y) è verae scrivere semplicemente

x R y se e solo se P(x, y)

“dimenticandoci” di scrivere esplicitamente ilsottoinsieme R.



8

Esempi di relazioni

Si consideri l’insieme N e la relazione definitaponendo

x ≤ y se e solo se ∃t ∈ N (x + t = y)

allora2 ≤ 3 t = 17 ≤ 7 t = 08 ≤6≤ 2 6 ∃ t

Sia X un qualunque insieme, allora in P(X)possiamo definire la relazione

A ⊆ B se e solo se A è un sottoinsieme di B

[notazione che abbiamo già utilizzato].Matematica Discreta (elementi) – E-O – p. 8

81


9

Esempi di relazione

Nell’insieme della popolazione di una città èpossibile considerare le seguenti relazioni

x µ y se e solo se x è marito di yx φ y se e solo se x è fratello di yx σ y se e solo se x è sorella di y. . .. . .



10

Diagramma di una relazione

Se l’insieme A è un insieme finito, è possibilerappresentare graficamente una relazione nel modoseguente

disegniamo il diagramma di Eulero-Venndell’insieme Aper ogni coppia di elementi x e y di A, disegniamouna freccia da x a y se e soltanto se x è in relazionecon y

nel caso in cui x sia in relazione con se stesso,disegniamo una freccia che parte e torna su x(tale freccia è detta cappio)



11

Esempi di relazioni

Dati A = {1, 2, 3, 4, 5, 6} eR1 = {(1, 1), (2, 2), (3, 3), (4, 4), (4, 5), (5, 4), (5, 5)}

1 2 3 4 5 6



12

Esempi di relazioni

Dati invece A = {1, 2, 3, 4, 5, 6} eR2 = {(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)}

1 2 3 4 5 6


82


13

Esempi di relazioni

Infine dati A = {1, 2, 3, 4, 5, 6} eR3 = {(1, 6), (2, 1), (3, 4), (4, 4), (5, 1), (5, 2), (6, 3)}

1 2 3 4 5 6



14

Proprietà delle relazioni

Dato un insieme A e una relazione R su A, diremo che

R è riflessiva se

∀a ∈ A aR a

R è simmetrica se

∀a, b ∈ A aR b → bR a

R è antisimmetrica se

∀a, b ∈ A (aR b ∧ bR a) → (a = b)

R è transitiva se

∀a, b, c ∈ A (aR b ∧ bR c) → (aR c)



15

Esempi

Dato A = {1, 2, 3, 4, 5, 6}

R1 = {(1, 1), (2, 2), (3, 3), (4, 4), (4, 5), (5, 4), (5, 5)}

R1 non è riflessiva, in quanto 6 ∈ A, ma(6, 6) 6∈ R1R1 è simmetricaR1 non è antisimmetrica, in quanto 4R1 5 e5R1 4, con 4 6= 5R1 è transitiva

Si noti che

queste proprietà sono proprietà della relazione, nonhanno senso affermazioni del tipo

R1 è riflessiva per a = 1Matematica Discreta (elementi) – E-O – p. 15


16

R1 è simmetrica?

Avendo a che fare con un quantificatore ∀, per mostrareche R1 è simmetrica dobbiamo fare una verifica per ogniscelta possibile di a e b in A

1R1 1 → 1R1 1 V → V1R1 2 → 2R1 1 F → F1R1 3 → 3R1 1 F → F. . .

4R1 5 → 5R1 4 V → V. . .

Esercizio – Quante verifiche dobbiamo fare se A è uninsieme con n elementi?In modo del tutto analogo (quante verifiche?) si mostrache R1 è transitiva. Matematica Discreta (elementi) – E-O – p. 16

83


17

Esempi

Dato A = {1, 2, 3, 4, 5, 6}

R2 = {(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)}

R2 è riflessivaR2 è simmetricaR2 è antisimmetricaR2 è transitiva

Si noti che “antisimmetrica” non significa “nonsimmetrica”.

Infatti la negazione di

∀a, b ∈ A aR b → bR a

è∃a ∃b ¬(aR b → bR a)



18

Antisimmetrica e non simmetrica

La R2 è un esempio di relazione che è sia simmetricache antisimmetrica

Questo è invece il diagramma di una relazione che non èné simmetrica né antisimmetrica

1 2 3 4 5

(e non è neppure riflessiva, né transitiva).Matematica Discreta (elementi) – E-O – p. 18


19

Esempi di relazioni

Dato A = {1, 2, 3, 4, 5, 6}

R3 = {(1, 6), (2, 1), (3, 4), (4, 4), (5, 1), (5, 2), (6, 3)}

R3 non è riflessiva, in quanto ad esempio(1, 1) 6∈ R3R3 non è simmetrica, in quanto ad esempio(1, 6) ∈ R3 ma (6, 1) 6∈ R3R3 è antisimmetricaR3 non è transitiva, in quanto ad esempio(2, 1) ∈ R3 e (1, 6) ∈ R3, ma (2, 6) 6∈ R3



20

Proprietà delle relazioni e frecce

Quando A è un insieme finito, ovvero quando è possibiledisegnare il diagramma della relazione, le proprietà dellerelazioni su A si possono tradurre nel linguaggio delle“frecce”.

Più precisamente

R è riflessiva, se su ogni elemento di A è disegnatoun cappio

R è simmetrica, se ogni coppia di elementi a e b di

A è collegata da una doppia freccia a b (o da

nessuna freccia!)

R è antisimmetrica, se non compare mai la doppiafreccia Matematica Discreta (elementi) – E-O – p. 20

84


21

Proprietà delle relazioni e frecce

R è transitiva, se per ogni terna di elementi a, b e cdi A, ogni volta che ci sono due frecce consecutive

a b c allora deve esserci anche la frecciache congiunge direttamente a con ca b c

Osserviamo che nella definizione non è richiesto a 6= c,le due frecce consecutive potrebbero essere

a = c b e quindi perché la relazione sia transitiva è

necessario che su a = c sia disegnato un cappio.



22

E senza disegno?

Consideriamo in N la relazione

x ≤ y se e solo se ∃t ∈ N (x + t = y)

≤ è riflessiva, in quanto 0 ∈ N e, qualunque siax ∈ N si ha x + 0 = x, ovvero x ≤ x≤ non è simmetrica, in quanto 2 ≤ 3, ma 3 6≤ 2≤ è antisimmetrica, in quanto se ∃t1 tale chex + t1 = y e ∃t2 tale che y + t2 = x, allorapossiamo scrivere

y = x + t1 = (y + t2) + t1

da cuit1 + t2 = 0

ovvero t1 = t2 = 0, ovvero x = y. Matematica Discreta (elementi) – E-O – p. 22


23

≤

≤ è transitiva, in quanto se ∃t1 tale che x + t1 = y e∃t2 tale che y + t2 = z, allora

z = y + t2 = (x + t1) + t2 = x + (t1 + t2)

ovvero x ≤ z.



24

Equivalenze e ordinamenti

Dato un insieme A e una relazione ρ su A

Definizione – ρ è una relazione di equivalenza se è

riflessiva

simmetrica

transitiva

Definizione – ρ è una relazione di ordine se è

riflessiva

antisimmetrica

transitiva


85


25

Equivalenze

Dato un qualsiasi insieme A la più ovvia relazione diequivalenza definibile su A è l’eguaglianza

a ρ b se e solo se a = b

ρ è una relazione di equivalenza in quanto

ρ è riflessiva, qualunque sia a ∈ A si ha a = a

ρ è simmetrica, se a = b (cioè se a e b sono lostesso elemento), allora b = aρ è transitiva, se a = b e b = c, allora tutti e tre glielementi sono uguali, in particolare a = c

In realtà le relazioni di equivalenza sono proprio unageneralizzazione della relazione di eguaglianza “=”.



26

Congruenza modulo n

Fissiamo ora un intero n > 1. Nell’insieme Z possiamodefinire la seguente relazione

a ≡ b (mod n) se e solo se n | a− b

in altre parolea ≡ b (mod n) se e solo se ∃k ∈ Z (a− b = k · n)

o ancoraa ≡ b (mod n) se e solo se ∃k ∈ Z (a = b + kn)

Definizione – La relazione a ≡ b (mod n) è dettacongruenza modulo n. Se a è in relazione con b,diciamo che a è congruo a b modulo n



27

Congruenza modulo n

Proposizione – Qualunque sia l’intero n fissato, lacongruenza modulo n è una relazione di equivalenzain Z.

Dimostrazione –la congruenza modulo n è riflessiva, infattiqualunque sia z ∈ Z si ha che z = z + 0 n, ovveroz ≡ z (mod n)

la congruenza modulo n è simmetrica, infatti sez ≡ w (mod n), allora ∃k ∈ Z tale che z = w + k n.Ma questo significa che w = z + (−k) n,cioè w ≡ z (mod n)



28

Congruenza modulo n

la congruenza modulo n è transitiva. Infattisupponiamo che

x ≡ y (mod n), cioè ∃k1 tale che x = y + k1ny ≡ z (mod n), cioè ∃k2 tale che y = z + k2n

possiamo dedurre che

x = y + k1n = (z + k2n) + k1n = z + (k2n + k1n)

da cuix = z + (k2 + k1)n

ovverox ≡ z (mod n)


86


29

Equivalenze e partizioni

Definizione – Sia A un insieme non vuoto. Unapartizione F di A è una famiglia F di sottoinsiemi di Atali che

∀X ∈ F si ha X 6= ∅

A =⋃

X∈F X

∀X, Y ∈ F si ha che X 6= Y → X ∩ Y = ∅

Osserviamo che se F è una partizione su A, allora ognielemento di A appartiene ad uno ed un solo X di F ,infatti dato a0 ∈ A

essendo A =⋃

X∈F X, si ha ∃X in F con a0 ∈ X

se a0 ∈ X ∩ Y, allora X = YMatematica Discreta (elementi) – E-O – p. 29


30

Classi di equivalenza

Dato un insieme A in cui è definita una relazione diequivalenza ρ

Definizione – Se a ∈ A è un elemento di A, allora laclasse di equivalenza di a modulo ρ è l’insieme

[a]ρ = {x | x ∈ A ∧ x ρ a}

Se dal contesto è chiaro di quale relazione si staparlando, possiamo indicare la classe di equivalenza di asemplicemente con [a].

Nota – Una classe di equivalenza è un sottoinsiemedi A.



31

Insieme quoziente

Dato un insieme A in cui è definita una relazione diequivalenza ρ

Definizione – L’insieme quoziente di A modulo ρ èl’insieme i cui oggetti sono le classi di equivalenza di ρ.

Denotando l’insieme quoziente con il simbolo

A/ρ

si ha alloraA/ρ =

{

[a]ρ | a ∈ A}



32

Esempi

Sia A un insieme, si consideri su A la relazione dieguaglianza a ρ b se e solo se a = b

qualunque sia a ∈ A si ha

[a]ρ = {a}

A/ρ = {{a} | a ∈ A}a 7→ {a} è una corrispondenza biunivoca di A inA/ρ, in altre parole “A e A/ρ si assomiglianomolto”


87


1


CdL Informatica

26 novembre 2003





2

Avvertenze





queste pagine).



3

Relazioni di equivalenza



4

Relazioni di equivalenza

Dato un insieme A, una relazione ∼ su A è dettarelazione di equivalenza o semplicemente equivalenzasu A se ∼ è

riflessiva

simmetrica

transitiva

ovvero se

∀a ∈ A a∼ a∀a, b ∈ A a∼ b → b∼ a∀a, b, c ∈ A (a∼ b ∧ b∼ c) → (a∼ c)


88


5

Classi di equivalenza

Dato un insieme A in cui è definita una relazione diequivalenza ∼

Definizione – Se a ∈ A è un elemento di A, allora laclasse di equivalenza di a modulo ∼ è l’insieme

[a]∼ = {x | (x ∈ A) ∧ (x∼ a)}

Se dal contesto è chiaro di quale relazione si staparlando, possiamo indicare la classe di equivalenza di asemplicemente con [a].

Nota – Una classe di equivalenza è un sottoinsiemedi A.



6

Esempi di relazioni di equivalenza

I seguenti sono esempi di relazioni di equivalenza

In Z, la congruenza modulo n:

a ≡ b (mod n) se e solo se n | (a− b)

In Z la relazione definita ponendo

a ∼ b se e solo se (a | b) ∧ (b | a)

In N×N la relazione definita ponendo

(a1, a2) ∼ (b1, b2) se e solo se a1 + b2 = a2 + b1

In Z× (Z \ {0}), la relazione definita ponendo

(a1, a2) ∼ (b1, b2) se e solo se a1 · b2 = a2 · b1

Esercizio – Mostrare che si tratta di equivalenze.Matematica Discreta (elementi) – E-O – p. 6


7

Partizioni

Definizione – Sia A un insieme non vuoto. Unapartizione F di A è una famiglia F di sottoinsiemi di Atali che

∀X ∈ F si ha X 6= ∅

A =⋃

X∈F X

∀X, Y ∈ F si ha che X 6= Y → X ∩ Y = ∅



8


Proposizione – Dato un insieme A e una relazione diequivalenza ∼ su A, le classi di equivalenza di ∼costituiscono una partizione di A.

Si ha infatti

∀a ∈ A si ha [a]∼ 6= ∅

questa è esattamente la traduzione dellaproprietà riflessiva di ∼: dal momento che a∼ asi ha a ∈ [a]∼

A =⋃

a∈A[a]∼per quanto visto sopra {a} ⊆ [a]∼, e quindiA =

⋃

a∈A {a} ⊆⋃

a∈A[a]∼Matematica Discreta (elementi) – E-O – p. 8

89


9


osserviamo che [a]∼ = [b]∼ se e solo se a∼ bInfatti a ∈ [a]∼, cioè, per l’eguaglianza delleclassi, a ∈ [b]∼, e questo implica a∼ bViceversa, se a∼ b, allora x∼ a, per latransitività, implica x∼ b, ovvero x ∈ [b]∼.Abbiamo cioè mostrato che ogni elemento di[a]∼ è necessariamente un elemento di [b]∼,ovvero [a]∼ ⊆ [b]∼.Ricordando che ∼ è simmetrica e quindi sea∼ b allora b∼ a, è possibile scambiare i ruoli dia e b e mostrare che [b]∼ ⊆ [a]∼, ovvero che idue insiemi coincidono.



10


∀a, b ∈ A, si ha che [a]∼ ∩ [b]∼ 6= ∅ se e solo se[a]∼ = [b]∼

Supponiamo che [a]∼ ∩ [b]∼ 6= ∅, ovvero cheesista un x ∈ [a]∼ ∩ [b]∼. Questo significa chex∼ a e x∼ b, e, per le proprietà simmetrica etransitiva, a∼ b.Per quanto visto al punto precedente [a]∼ = [b]∼

Viceversa, se [a]∼ = [b]∼ allora chiaramente[a]∼ ∩ [b]∼ = [a]∼ = [b]∼Dal momento che a ∈ [a]∼, si ha [a]∼ ∩ [b]∼ 6= ∅



11


Proposizione – Sia A un insieme

Se ∼ è una relazione di equivalenza su A, alloral’insieme quoziente A/∼ è una partizione di A

Se F è una partizione di A, allora è possibiledefinire una relazione di equivalenza in A ponendo

a σ b se e solo se ∃X ∈ F (a ∈ X ∧ b ∈ X)

In questo caso l’insieme quoziente A/σ coincidecon F

(Esercizio)



12

Classi di resto modulo n

Definizione – Fissato un intero n > 1, si consideri in Zla relazione ≡n di congruenza modulo n. Le classi diresto modulo n sono le classi di equivalenza di ≡n.

Abbiamo mostrato che la relazione di congruenzamodulo n è una relazione di equivalenza, ha quindisenso parlare di classi di equivalenza

Dato un a ∈ Z la classe di resto di a modulo n è ilsottoinsieme di Z

[a]n = {x ∈ Z : x ≡ a (mod n)}

L’insieme quoziente Z/≡n è detto insieme delleclassi di resto modulo n ed è denotato con il simboloZn.


90


13


Come sono fatte le classi di resto modulo n?Quante sono?

Quali elementi contengono?Per rispondere a queste domande possiamo ancheservirci di una nuova relazione

Fissato un n > 1, consideriamo in Z la seguenterelazione

xRn y se e solo sex e y divisi per ndanno lo stessoresto

Si ha che Rn è una relazione su Z equivalente allacongruenza modulo n.



14

Relazioni equivalenti

Dato un insieme A e due relazioni R1 e R2 su A, diremoche R1 è equivalente a R2 se R1 e R2 coincidonocome sottoinsiemi di A× A.In particolare, R1 è equivalente a R2 se e solo se

∀x, y ∈ A(

(x, y) ∈ R1 ↔ (x, y) ∈ R2)

in altre parole, se e solo se

∀x, y ∈ A(

xR1 y ↔ xR2 y)

Se R1 è definita tramite il predicato P1(x, y) e R2 èdefinita tramite il predicato P2(x, y), allora le due relazionisono equivalenti se e soltanto se

∀x, y ∈ A(

P1(x, y) ↔ P2(x, y))



15

Congruenza modulo n

Mostriamo allora che

∀x, y ∈ Z

(

x ≡ y (mod n) ↔x e y divisi per ndanno lo stessoresto

)

supponiamo che x e y divisi per n diano lo stessoresto r0, e mostriamo che n | (x− y). Questosignifica che possiamo scrivere

∃q1 ∈ Z tale che x = n q1 + r0

∃q2 ∈ Z tale che y = n q2 + r0ma allora

x− y = (n q1 + r0)− (n q2 + r0)

= n(q1 − q2) + (r0 − r0) = n(q1 − q2)



16

Congruenza modulo n

Viceversa, supponiamo che n | (x− y) e mostriamoche x e y divisi per n danno lo stesso resto.Possiamo scrivere

∃q1, r1 ∈ Z tale che x = n q1 + r1 [0 ≤ r1 < n]∃q2, r2 ∈ Z tale che y = n q2 + r2 [0 ≤ r2 < n]

occorre mostrare che r1 = r2Scriviamo

x− y = (n q1 + r1)− (n q2 + r2)

= n(q1 − q2) + (r1 − r2)

Dal momento che n | (x− y) si ha

n |(

n(q1 − q2) + (r1 − r2))


91


17

Congruenza modulo n

Dal momento che

n |(

n(q1 − q2) + (r1 − r2))

ne conseguen | (r1 − r2)

A questo punto occorre ricordare le condizioni sui resti

0 ≤ r1 < n 0 ≤ r2 < n

per dedurre cher1 − r2 = 0

ovvero cher1 = r2



18

Risultati compitino

ancora un po’ di pazienza . . .

i risultati saranno esposti (per tutti e tre i corsi) sulsito della segreteria

www.disco.unimib.it

(cui dovete fare riferimento per ogni informazionedalla “segreteria”: date e risultati degli esami, . . . )

Statistiche sulla scelta multipla

Totale studenti: 144 Compiti corretti: 144Voto massimo: 10 Voto minimo:-2Voto medio: 6.5

A: 57 (39.0%) B: 42 (28.8%) C: 30 (20.5%) D: 15 (10.3%)



19

Risultati compitino

Statistiche sul compito finale

Totale studenti: 144 Compiti corretti: 144Voto massimo: 30 Voto minimo:1Voto medio: 16

A: 19 (13.2%) B: 39 (27.1%) C: 39 (27.1%) D: 47 (32.6%)



20


Avendo dimostrato che

∀x, y ∈ Z

(

x ≡ y (mod n) ↔x e y divisi per ndanno lo stessoresto

)

possiamo dedurre che, qualunque sia a ∈ Z

[a]n ={

x ∈ Z : x e a divisi per n dannolo stesso resto

}

Resta allora da rispondere alla seguente domandaper un assegnato n, quanti e quali sono i possibili resti

della divisione per n?


92


21

Resti della divisione per n


a = b · q + r 0 ≤ r < |b|

ci permette di affermare che l’insieme dei possibili restidella divisione per n è contenuto nell’insieme

{r ∈ Z : 0 ≤ r < n}

Viceversa è immediato verificare che un qualunque interox che soddisfa le condizioni 0 ≤ x < n è un possibileresto. Per un tale x si ha infatti

x = 0 · n + x 0 ≤ x < nMatematica Discreta (elementi) – E-O – p. 21


22


Dato un a ∈ Z la classe di resto di a modulo n è ilsottoinsieme di Z

[a]n ={

x ∈ Z : x e a divisi per n dannolo stesso resto

}

L’insieme quoziente Zn ha come oggetti le classi diresto modulo n, cioè

Zn = {[a]n : a ∈ Z}

Per quanto visto si può scrivere

Zn = {[a]n : (a ∈ Z) ∧ (0 ≤ a < n)}

o anche

Zn = {[0]n, [1]n, [2]n, . . . , [n− 1]n}Matematica Discreta (elementi) – E-O – p. 22


23

Esempi

Sia n = 4, allora

Z4 = {[0]4, [1]4, [2]4, [3]4}

Z4 = {[218]4, [−15]4, [412]4, [7]4}

Infatti

[218]4 = [2]4 se e solo se 218 ≡ 2 (mod 4)

[−15]4 = [1]4 se e solo se −15 ≡ 1 (mod 4)

[412]4 = [0]4 se e solo se 412 ≡ 0 (mod 4)

[7]4 = [3]4 se e solo se 7 ≡ 3 (mod 4)

Gli interi 0, 1, 2 e 3 costituiscono un sistema completodi rappresentanti per gli elementi di Z4.

Come pure gli interi 218, −15, 412 e 7.Matematica Discreta (elementi) – E-O – p. 23


24

Strutture algebriche


93


25

Leggi di composizione

Definizione – Dato un insieme A, una legge dicomposizione binaria su A (ovvero una operazionebinaria in A) è una applicazione ·

· : A× A → A

Se a e b sono due elementi di A, allora · associa allacoppia (a, b) uno e un solo elemento di A, chechiamiamo prodotto di a e b

(a, b) 7→ a · b

o secondo uno schema già visto

·b

aa · b



26

Esempi

∧ è una operazione nell’insieme delle proposizioni

analogamente ∨ è una operazione nell’insieme delleproposizioni

∪ è una operazione tra gli insiemi, analogamente ∩

+ è una operazione tra i numeri (naturali, interi,reali, . . . )

− non è una operazione tra i numeri naturali, ma èuna operazione nell’insieme dei numeri interi(relativi)

il prodotto è una operazione tra i numeri (naturali,interi, reali, . . . )

la divisione non è una operazione tra i numeri interiMatematica Discreta (elementi) – E-O – p. 26


27


Definizione – Una struttura algebrica è un insiemedotato di una o più operazioni.

L’algebra è lo studio delle proprietà delle strutturealgebriche.

Esempi –

(N, +), (Z, +), (Q, +), (R, +)

(N, ·), (Z, ·), (Q, ·), (R, ·)

(N, +, ·), (Z, +, ·), (Q, +, ·), (R, +, ·)



28

Esempi

Dato un qualsiasi n > 1, l’insieme Zn può essere dotatodi una operazione + di somma e di una operazione · diprodotto.

Ad esempio in Z5 = {[0]5, [1]5, [2]5, [3]5, [4]5}, possiamodefinire

[1]5 + [3]5 = [4]5

analogamente[2]5 + [4]5 = [1]5

(“2 + 4 = 1”)


94


29

Esempi

Osserviamo che la scrittura

[2]5 + [4]5 = [1]5

avrebbe potuto essere invece

[517]5 + [424]5 = [941]5

Utilizzando due scritture diverse, abbiamo ottenuto duerisultati apparentemente diversi. Questo significherebbeche + non rispetta la definizione di applicazione.

Questi due risultati sono in contraddizione??



30

Somma in Zn

Proposizione – Qualunque sia n > 1, la somma in Zndefinita ponendo

[a]n + [b]n = [a + b]n

è ben definita.

In altre parole se cambiamo i rappresentanti delle classi,il risultato della somma non cambia:

se [a1]n = [a2]n

e se [b1]n = [b2]n

allora[a1 + b1]n = [a2 + b2]n



31

Somma in Zn

Dimostrazione – Si ha che

[a1]n = [a2]n se e solo se a1 ≡ a2 (mod n)

ovvero se e solo se

∃k ∈ Z (a1 = a2 + k n)

Analogamente

[b1]n = [b2]n se e solo se ∃h ∈ Z (b1 = b2 + h n)

Ne consegue che

a1 + b1 = (a2 + k n) + (b2 + h n) = (a2 + b2) + (k + h) n

ovvero[a1 + b1]n = [a2 + b2]n



32

Somma in Zn

L’insieme Zn dotato dell’operazione di somma

[a]n + [b]n = [a + b]n

è una struttura algebrica che denotiamo con (Zn, +).

In maniera analoga si mostra che in Zn è definibile unprodotto

[a]n · [b]n = [a · b]n

ed è così definibile la struttura algebrica (Zn, ·). . . come pure la struttura algebrica (Zn, +, ·).

Esercizio – In maniera analoga a quanto fatto per lasomma, mostrare che il prodotto in Zn è ben definito.


95


33

Proprietà delle strutture algebriche

Dato un insieme A dotato di una operazione· : A× A → A

l’operazione · è associativa se

∀a, b, c ∈ A a · (b · c) = (a · b) · c

· è commutativa se

∀a, b ∈ A a · b = b · a

· ammette unità in A se

∃u ∈ A ∀a ∈ A a · u = u · a = a

se si ha u, diremo che a ∈ A è invertibile in A se

∃b ∈ A a · b = b · a = uMatematica Discreta (elementi) – E-O – p. 33


34

Proprietà delle strutture algebriche

Osserviamo che

u è detta unità, o identità di ·

u è spesso indicata con il simbolo 1 (se · è un“prodotto”), o con il simbolo 0 (se · è una “somma”)

dato un elemento a invertibile, l’elemento b tale chea · b = b · a = u è detto inverso di a.

L’algebra studia quelle proprietà delle strutture algebricheche possono essere dedotte dalle proprietà descritte.Ad esempio il seguente è un risultato “algebrico”

data una operazione associativa ·,allora l’unità di · (se esiste) è unica

ol’unità di · è invertibile rispetto a ·



35

Semigruppi

Definizione – La struttura algebrica (A, ·) dotata di unaoperazione · è detta semigruppo se · è associativa.

Esempi -le usuali somma e prodotto di “numeri” sonoassociative

(N, +), (N, ·), (Z, +), (Z, ·) sono semigruppi(Zn, +), (Zn, ·) sono semigruppi

unione e intersezione di insiemi sono associativese X è un qualsiasi insieme, allora (P(X),∪) e(P(X),∩) sono semigruppi

(N,−), (Z,−) ?



36

Semigruppi

(N,−), (Z,−) ?− non è una operazione in N

− è una operazione in Z, ma non è associativa

È sufficiente osservare che

(5− 3)− 4 6= 5− (3− 4)

Un semigruppo (A, ·) è detto commutativo (o abeliano)se · è commutativa.

Tutti gli esempi di semigruppo visti fin qui sonocommutativi.

Vedremo ora un esempio non commutativo.Matematica Discreta (elementi) – E-O – p. 36

96


37

Applicazioni

Sia A un insieme e sia AA l’insieme di tutte leapplicazioni di A in A. La composizione di applicazioni ◦è una operazione in AA.

Si può dimostrare che ◦ è associativa

(AA, ◦) è un semigruppo non abeliano

Ad esempioA A A

ρ σ

a1a2a3a4

a1a2a3a4

a1a2a3a4



38


A A A

σ ρ

a1a2a3a4

a1a2a3a4

a1a2a3a4

A Aσ ◦ ρa1

a2a3a4

a1a2a3a4

A Aρ ◦ σa1

a2a3a4

a1a2a3a4



39

Monoidi

Un semigruppo dotato di unità è detto monoide

In altre parole

Definizione – La struttura algebrica (A, ·) dotata di unaoperazione · è detta monoide se

· è una operazione in A· è associativa

∃u ∈ A ∀a ∈ A a · u = u · a = a

Esempi –

(N, +) è un monoide con unità il numero 0analogamente lo sono (Z, +), (Q, +), (R, +)

(Zn, +) è un monoide con unità [0]nMatematica Discreta (elementi) – E-O – p. 39


40

Esempi

(N, ·) è un monoide con unità il numero 1analogamente lo sono (Z, ·), (Q, ·), (R, ·)

(Zn, ·) è un monoide con unità [1]n

(P(X),∪) è un monoide con unità ∅

(P(X),∩) è un monoide con unità X

(AA, ◦) è un monoidesi tratta di determinare una applicazioneid : A → A tale che per ogni σ ∈ AA si abbia

id ◦ σ = σ ◦ id = σ


97


41

Applicazione identica

A A A

σ id

a1a2a3a4

a1a2a3a4

a1a2a3a4

L’applicazione identica

id : A → A

definita ponendo per ogni a ∈ A

id : a 7→ a

funge da unità per il monomio (AA, ◦)Matematica Discreta (elementi) – E-O – p. 41


42

Monoide delle parole

Sia A un insieme. Una parola nell’alfabeto A è unaqualunque sequenza a1a2 . . . an di n elementi di A.La parola vuota è l’unica parola di lunghezza zero

Nell’insieme delle parole è definibile una operazione. Sew1 = a1a2 · · · an e w2 = b1b2 . . . bm allora si pone

w1 ◦ w2 = a1a2 . . . anb1b2 . . . bm

L’insieme delle parole nell’alfabeto A rispettoall’operazione ◦ ha struttura di monoide. La parola vuotafunge da unità per ◦.Tale monoide è detto monoide delle parolenell’alfabeto A o monoide libero su A.



43

Gruppi

Un monoide in cui ogni elemento è invertibile è dettogruppo

In altre parole

Definizione – La struttura algebrica (A, ·) dotata di unaoperazione · è detta gruppo se


∃u ∈ A ∀a ∈ A a · u = u · a = a∀a ∈ A ∃b ∈ A a · b = b · a = u



44

Esercizi

Determinare gli elementi invertibili negli esempi dimonoidi visti

Stabilire quali di quei monoidi sono anche gruppi


98


1


CdL Informatica

3 dicembre 2003





2

Avvertenze





queste pagine).



3




4

Gruppi

Un monoide in cui ogni elemento è invertibile è dettogruppo

In altre parole

Definizione – La struttura algebrica (A, ·) dotata di unaoperazione · è detta gruppo se


∃u ∈ A ∀a ∈ A a · u = u · a = a∀a ∈ A ∃b ∈ A a · b = b · a = u


99


5

Esempi

(N, +) non è un gruppol’unico elemento invertibile in N è 0

(Z, +) è un gruppoper ogni a ∈ Z esiste l’elemento −a per cui si ha

a + (−a) = 0

nel caso di operazione di “somma”, come inquesto caso, si preferisce il termine opposto altermine inverso

(Z, ·) non è un gruppogli unici elementi invertibili in (Z, ·) sono 1 e −1per gli elementi di Z in genere il termineinvertibile sottointende rispetto al prodotto



6

Esempi

(Zn, +) è un gruppoper ogni [a]n ∈ Zn esiste l’elemento [−a]n percui si ha

[a]n + [−a]n = [0]n

anche in questo caso si preferisce il termineopposto al termine inverso

(Zn, ·) ?

(AA, ◦) ?

Quali sono gli elementi invertibili di (Zn, ·) e di (AA, ◦)?



7

Elementi invertibili di (AA, ◦)

Per definizione σ ∈ AA è invertibile se e solo se esisteτ ∈ AA tale che

σ ◦ τ = τ ◦ σ = idOsserviamo che id : a 7→ a è una applicazione biunivoca,e quindi

τ ◦ σ = id implica che σ è iniettiva

σ ◦ τ = id implica che σ è suriettiva

Possiamo concludere checondizione necessaria affinchè σ sia invertibile

è che σ sia biunivoca



8

Elementi invertibili di (AA, ◦)

Viceversa

abbiamo visto (22 ottobre 2003) che se σ è unaapplicazione biunivoca di A in A allora esiste unaapplicazione biunivoca τ di A in A tale che per ognia, b ∈ A si ha

a = σ(b) ⇐⇒ b = τ(a)

È immediato verificare che τ ◦ σ = σ ◦ τ = id

In altre parole

Proposizione – Una applicazione di A in A è invertibilerispetto a ◦ se e solo se è biunivoca.


100


9

Esercizi

Per un n fissato, determinare gli elementi invertibilidi Zn

si tratta di individuare quelle classi [a]n per lequali è possibile determinare una classe [b]n taleche

[a]n · [b]n = [1]n

anche per Zn il termine “invertibile” in generesottointende rispetto al prodotto (perl’operazione di somma si preferisce il termine“opposto”)



10

Elementi invertibili di Zn

L’elemento [a]n ∈ Zn è invertibile in (Zn, ·) se e solo seè possibile determinare una classe [b]n tale che

[a]n · [b]n = [1]n

cioè se e solo se[a · b]n = [1]n

cioè se e solo se

ab ≡ 1 (mod n)

Prima di proseguire analizziamo il problema più ingenerale: dati a e c ∈ Z è possibile determinare b ∈ Ztale che

ab ≡ c (mod n) ?Matematica Discreta (elementi) – E-O – p. 10


11

Congruenze lineari

Dati a, b ∈ Z l’equazione

a x ≡ b (mod n)

(nell’incognita x ∈ Z) è detta congruenza lineare.

È possibile determinare un tale x ∈ Z se e solo seesiste k ∈ Z tale che

a x = b + k novvero

a x − k n = b



12


Dobbiamo a questo punto ricordare alcune cose viste aesercitazione

dati due interi a e b (non entrambi nulli) tramitel’algoritmo euclideo delle divisioni successive èpossibile determinare un massimo comun divisore ddi a e b

il massimo comun divisore di a e b cosìdeterminato è sempre positivo

l’algoritmo delle divisioni successive permette anchedi determinare due interi x e y tali che

a x + b y = d

(identità di Bezout)Matematica Discreta (elementi) – E-O – p. 12

101


13

Equazioni diofantee

dati a, b, c ∈ Z l’equazione

a x + b y = c

ha soluzioni in Z se e solo se

MCD (a, b) | c

una soluzione particolare x0, y0 è determinabiletramite l’identità di Bezoutuna volta determinata una soluzione particolare,tutte e sole le soluzioni sono gli interi della forma

x = x0 +b

MCD (a, b)k y = y0 −

aMCD (a, b)

k

dove k è un qualsiasi numero intero.Matematica Discreta (elementi) – E-O – p. 13


14

Congruenze lineari

Dati a, b ∈ Z la congruenza lineare

a · x ≡ b (mod n)

(nell’incognita x ∈ Z)è equivalente all’equazione diofantea

a x − k n = b(nelle incognite x e k ∈ Z)

Ha quindi soluzioni se e solo se

MCD (a, n) | b

L’identità di Bezout ci permette di determinareesplicitamente una soluzione particolare (x0, k0), dallaquale ricavare tutte le possibili soluzioni.



15


Applicando la definizione, un elemento [a]n è invertibile in(Zn, ·) se e solo se esiste una classe [x]n tale che

[a]n · [x]n = [1]n

questo significa[a · x]n = [1]n

ovveroa · x ≡ 1 (mod n)

congruenza che è risolubile se e solo se

MCD (a, n) | 1

quindi [a]n è invertibile in (Zn, ·) se e solo seMCD (a, n) = 1.



16


Esercizio – L’elemento [2583]4712 è invertibile in Z4712?

Osserviamo che in questo caso il termine“invertibile” sottointende “rispetto al prodotto”

[2583]4712 è invertibile in Z4712 se e solo seMCD (2 583, 4 712) | 1Utilizziamo l’algoritmo delle divisioni successive perdeterminare MCD (2 583, 4 712)

2 583 = 0 · 4 712 + 2 5834 712 = 1 · 2 583 + 2 1292 583 = 1 · 2 129 + 4542 129 = 4 · 454 + 313454 = 1 · 313 + 141313 = 2 · 141 + 31

141 = 4 · 31 + 1731 = 1 · 17 + 1417 = 1 · 14 + 314 = 4 · 3 + 23 = 1 · 2 + 12 = 2 · 1 + 0


102


17


2 583 = 0 · 4 712 + 2 5834 712 = 1 · 2 583 + 2 1292 583 = 1 · 2 129 + 4542 129 = 4 · 454 + 313454 = 1 · 313 + 141313 = 2 · 141 + 31141 = 4 · 31 + 1731 = 1 · 17 + 1417 = 1 · 14 + 314 = 4 · 3 + 2 2 = 14− 4 · 33 = 1 · 2 + 1 1 = 3− 1 · 2 = 3− 1 · (14− 4 · 3)



18


1 = 3− 1 · (14− 4 · 3) = 5 · 3− 1 · 14= 5 · (17− 1 · 14)− 1 · 14 = 5 · 17− 6 · 14= 5 · 17− 6 · (31− 1 · 17) = −6 · 31 + 11 · 17= −6 · 31 + 11 · (141− 4 · 31) = 11 · 141− 50 · 31= 11 · 141− 50 · (313− 2 · 141) = 111 · 141− 50 · 313= . . .= 1 671 · 2 583− 916 · 4 712

Possiamo rileggere l’ultima eguaglianza “modulo” 4 712

[1]4 712 = [1 671]4 712 · [2 583]4 712 + [0]4 712



19


Abbiamo quindi ottenuto che

[2 583]4 712 è invertibile in (Z4 712, ·)l’inverso di [2 583]4 712 è [1 671]4 712

Quando il modulo è più piccolo si possono fare i conti piùvelocemente:

Quali sono gli elementi invertibili di (Z5, ·)?[1]5, [2]5, [3]5, [4]5

Quali sono gli elementi invertibili di (Z6, ·)?[1]6, [5]6

Esercizio – Negli esempi determinare esplicitamente gliinversi degli elementi invertibili.



20

Esercizi

In N×N si consideri la relazione di equivalenzadefinita ponendo

(a1, a2) ∼ (b1, b2) se e solo se a1 + b2 = a2 + b1

Si consideri quindi l’insieme quoziente (N×N)∼.in (N×N)∼ la somma

[(a1, a2)] + [(b1, b2)] = [(a1 + b1, a2 + b2)]

è ben definita(

(N×N)∼, +)

è un gruppo


103


21

Esercizi

In Z× (Z \ {0}) si consideri la relazione diequivalenza definita ponendo

(a1, a2) ∼ (b1, b2) se e solo se a1 · b2 = a2 · b1

Si consideri quindi l’insieme quoziente(Z× (Z \ {0}))∼.

in (Z× (Z \ {0}))∼ il prodotto

[(a1, a2)] + [(b1, b2)] = [(a1 · b2 + b1 · a2, a2 · b2)]

è ben definito(

(Z× (Z \ {0}))∼, +)

è un gruppo?

Suggerimento – scrivere la coppia (a1, a2) come“frazione” a1/a2



22

Anelli

Un anello è una struttura algebrica con due operazioni(A, +, ·), tale che

(A, +) è un gruppo abeliano

(A, ·) è un semigruppo

le operazioni + e · “si comportano bene l’unarispetto all’altra”, nel senso che per ogni a, b, c ∈ Asi ha

a · (b + c) = (a · b) + (a · c)(a + b) · c = (a · c) + (b · c)

(proprietà distributive di + rispetto a ·)L’operazione + è chiamata somma di A mentrel’operazione · è chiamata prodotto di A



23

Nomenclatura

Ricordiamo che dire che (A, +) è un gruppo abelianosignifica chiedere che

+ è una operazione in A, ovvero per ogni coppia dielementi a, b di A è univocamente determinataa + b ∈ A∀a, b, c ∈ A (a + b) + c = a + (b + c)∃u ∈ A ∀a ∈ A a + u = u + a = a

in questo caso u è chiamata zero di A ed èspesso indicata con il simbolo 0A o 0

∀a ∈ A∃b ∈ A a + b = b + a = 0tale elemento b (che dipende da a) è dettoopposto di a ed è indicato con il simbolo −a

∀a, b ∈ A a + b = b + aMatematica Discreta (elementi) – E-O – p. 23


24

Nomenclatura

Dire che (A, ·) sia un semigruppo significa chiedere che

· è una operazione in A, ovvero per ogni coppia dielementi a, b di A è univocamente determinatoa · b ∈ A∀a, b, c ∈ A (a · b) · c = a · (b · c)

OSSERVAZIONE – Alcuni testi nella definizione dianello chiedono che (A, ·) abbia la struttura di monoidecioè è richiesto che

∃u ∈ A ∀a ∈ A a · u = u · a = aNoi diremo che A è un anello con unità o anello conidentità.In questo caso tale u è chiamata uno di A ed è indicatacon il simbolo 1A o 1 Matematica Discreta (elementi) – E-O – p. 24

104


25

Esercizio

Il libro di testo, nella definizione, chiede che se un anelloA ammetta unità 1 si abbia che 1 6= 0.

Omettendo questa clausola, ovvero si accettando che 1possa coincidere con 0, dare un esempio di anello in cui0 = 1.



26

Esercizio

Sia X un insieme. Nell’insieme delle parti P(X)sono definite le due operazioni ∪ e ∩.

(P(X),∪,∩) è un anello? È dotato di unità?

(P(X),∩,∪) è un anello? È dotato di unità?



27

Anelli con unità

Sia (A, +, ·) un anello con unità

utilizziamo espressamente la notazione (A, +, ·, 1) aindicare che 1 è tale unità

ha senso analizzare l’invertibilità degli elementi di Aanche rispetto al prodotto

osserviamo che tutti gli elementi sono invertibilirispetto alla somma, quindi la domanda “qualielementi di A sono invertibili rispetto alla somma”non ha alcun senso.

Definizione – In un anello con unità (A, +, ·) diremoche a ∈ A è invertibile

∃b ∈ A a · b = b · a = 1Matematica Discreta (elementi) – E-O – p. 27


28

Esempi

(Z, +, ·) è un anello commutativo con unità ilnumero 1

“anello commutativo” significa che · ècommutativa (+ è sempre commutativa)gli unici elementi invertibili dell’anello Z sono 1 e−1

(Q, +, ·) è un anello commutativo con unità 1tutti gli elementi a

b 6= 0 sono invertibili: ab ·

ba = 1

(R, +, ·) è un anello commutativo con unità 1ogni elemento non nullo è invertibile

ad esempio√

2 è invertibile con inverso1√2

=√

22 Matematica Discreta (elementi) – E-O – p. 28

105


29

Campi

Si può dimostrare che in un anello (A, +, ·) l’elemento 0non è invertibile.Questo dipende dal fatto che si può dimostrare che∀b ∈ A 0 · b = 0, da cui

∀b ∈ A 0 · b = 0 6= 1

Relativamente alla ricerca di elementi invertibili,osserviamo quindi che Q e R hanno il massimo dielementi invertibili possibile.Questa osservazione detta la seguente definizione

Definizione – Un campo è un anello commutativo conunità in cui ogni elemento non nullo è invertibile.



30

Esempi

Sono campi:

(Q, +, ·)(R, +, ·)(C, +, ·)(Zn, +, ·)?

[a]n è invertibile in (Zn, +, ·) se e soltanto seMCD (a, n) = 1in Z5 tutti gli elementi, eccetto [0]5, sonoinvertibiliin Z6 gli unici elementi invertibili sono [1]6 e [5]6

(Zn, +, ·) è un campo se e soltanto se n è unnumero primo



31

Campi

Prima di passare alla dimostrazione, ci convieneosservare che in un anello ci sono elementi che hannoun comportamento peculiare

in Z6 le classi [4]6 e [3]6 sono elementi non nulli, mail loro prodotto è nullo

[4]6 · [3]6 = [12]6 = [0]6

questo ha come conseguenza il fatto che nonvalgono leggi di cancellazione: da

[4]6 · [3]6 = [2]6 · [3]6

non segue[4]6 = [2]6



32

Divisori dello zero

Definizione – In un anello (A, +, ·) un elemento a ∈ Aè detto divisore dello zero se a 6= 0 e se esiste unelemento b ∈ A, b 6= 0 tale che

a · b = 0 ∨ b · a = 0

Osserviamo che se a è un elemento invertibile di(A, +, ·) allora a non è un divisore dello zero di A.

Dimostrazione – Se a è invertibile, allora esiste a0 taleche a · a0 = a0 · a = 1.Ma allora qualunque sia b ∈ A si ha

a · b = 0 implica a0 · (a · b) = a0 · 0 = 0

da cui 0 = a0 · (a · b) = (a0 · a) · b = 1 · b = b.Matematica Discreta (elementi) – E-O – p. 32

106


33

Campi

Proposizione – (Zn, +, ·) è un campo se e soltanto sen è un numero primo

Dimostrazione – Se n non è un numero primo, alloran = a · b con a e b diversi da ±1 e da ±n.Ma allora

[a]n · [b]n = [n]n = [0]n

Quindi [a]n e [b]n, essendo divisori dello zero, non sonoinvertibili, e Zn non è un campo.

Viceversa, se n è un numero primo, allora qualunque siaa ∈ Z si ha che

MCD (a, n) =

{

1 se n6 | an se n | a



34

Campi

In altre parole

MCD (a, n) =

{

1 se [a]n 6= [0]nn se [a]n = [0]n

Cioè [a]n è invertibile se e solo se [a]n 6= [0]n.

Esercizio – Per ogni n, si indichi con Z∗n l’insieme degli

elementi invertibili di Zn. Mostrare che (Z∗n, ·) è un

gruppo.Suggerimento: dal momento che la proprietà associativavale in (Zn, ·), allora deve valere anche in un qualsiasisottoinsieme di Zn, etc. Quali sono i punti delladefinizione che vanno effettivamente verificati?



35

Funzione φ di Eulero

Definizione – L’applicazione che ad ogni intero nassocia il numero di elementi invertibili di Zn è dettafunzione φ di Eulero

Se con Z∗n denotiamo l’insieme degli elementi invertibili

di Zn, alloraφ : n 7→ |Z∗

n|Abbiamo visto che, se p è un numero primo, allora ognielemento non nullo di Zp è invertibile, ovveroZ∗

p = Zp \{

[0]p}

e quindiφ(p) = p− 1



36

Funzione φ di Eulero

Proposizione –

Se MCD (m, n) = 1, allora φ(m · n) = φ(m) · φ(n)

Se p è un numero primo e k un qualsiasi interomaggiore o uguale a 1, allora φ(pk) = pk − pk−1

Osserviamo che

È proprio lo studio astratto della struttura algebricadei gruppi (Z∗

n, ·) che ci permette di mostrarequeste proprietà

Grazie a queste proprietà siamo in grado dicalcolare il valore di φ(n), qualunque sia n, pur diessere in grado di scomporre n in fattori primi.


107


37

Scomposizione in fattori primi

Dal punto di vista computazionale la scomposizione infattori primi è un problema “difficile”.

Esercizio – Scomporre in fattori primi il numero1 427 393 202 994 830 938 302 827 392 024 938 200 307 907 657

La funzione di Eulero ha una importante proprietà

Teorema di Eulero-Fermat – Se MCD (a, n) = 1, allora

aφ(n) ≡ 1 (mod n)



38

Teorema di Eulero-Fermat

Un buon riferimento sul Teorema di Eulero-Fermat esulle possibili applicazioni in crittografia è “L. Childs,Algebra un’introduzione concreta, ETS Editrice”

Childs lo chiama “Teorema di Eulero”, p. 102Le principali applicazioni sono i test di primalità,Childs p. 235

Se p è un numero primo, il Teorema di EF si puòenunciare nella forma (Piccolo Teorema di Fermat)

se p6 | a allora ap−1 ≡ 1 (mod p)

che equivale a dire che qualunque sia a ∈ Z

ap ≡ a (mod p)

(questa è la forma del PTF riportata da Facchini,p. 392) Matematica Discreta (elementi) – E-O – p. 38


39

Test di primalità

Dal punto di vista computazionale i due seguentiproblemi sono differenti

Scomporre in fattori primi il numero

1 427 393 202 994 830 938 302 827 392 024 938 200 307 907 657

Stabilire se è primo il numero

1 427 393 202 994 830 938 302 827 392 024 938 200 307 907 657

Un test di primalità per n è una condizione necessariaperché n sia un numero primo

Ad esempio, condizione necessaria perché n sia primo èche per ogni 0 < a < n si abbia an−1 ≡ 1 (mod n)



40

Test di primalità

La “fallibilità” di un test di primalità sta nel fatto che sitratta di condizioni necessarie, ma non sufficienti.

Sono necessari studi probabilistici per dare una stimadell’affidabilità del test (di quanto la condizionenecessaria è distante dall’essere anche sufficiente).

I sistemi di crittografia moderni si basano sul fatto che lascomposizione in numeri primi sia un problema difficiledal punto di vista computazionale.


108


41

Insiemi (parzialmente) ordinati



42

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)


109


1


CdL Informatica

10 dicembre 2003





2

Avvertenze





queste pagine).



3

Insiemi (parzialmente) ordinati



4

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)


110


5

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.



6

Restrizione di una relazione

Sia A un insieme su cui è definita una relazione R, e Bun sottoinsieme di ADefinizione – 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


7

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



8

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

111


9

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.



10

Esercizi

Sia A = {2, 3, 4, 6, 12}.

Mostrare che la relazione d’ordine ≤ vista è unordinamento totale su ASi consideri in A la relazione

aRb se e solo se a | b

mostrare che R è una relazione di ordine su Adisegnare il diagramma di R



11

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



12

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∼


112


13

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 = ±bMatematica Discreta (elementi) – E-O – p. 13


14

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



15

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

12Il diagramma contienetutte le informazioni che cipermettono di ricostruirela relazione su A



16

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 |


113


17

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



18

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)



19

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



20

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 Ba ∈ A è un estremo superiore di B (sup(B)) se

a è il minimo dei maggioranti di BMatematica Discreta (elementi) – E-O – p. 20

114


21

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 è 5l’unico minorante di B è 1il minimo dei maggioranti di B è 5, cioèsup(B) = 5il massimo dei minoranti di B è 1, cioèinf(B) = 1



22

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 BB non ha minorantii maggioranti di B sono 4 e 5il minimo dei maggioranti di B è 4, cioèsup(B) = 4B non ammette estremo inferiore



23

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 B1 e 2 sono minoranti per B5 è l’unico maggiorante di Bil minimo dei maggioranti di B è 5B non ammette estremo inferiore, in quantol’insieme {1, 2} non ammette massimo



24

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.


115


25

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)

)



26

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

)



27

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.



28

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

116


29

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 ∩ ysup({x, y}) = x ∨ y = x ∪ y

Esercizio – Sia A = {a, b, c} e sia X = P(A). Costruireil diagramma del reticolo (X,⊆).



30

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 | dL’algoritmo delle divisioni successive permette dicalcolare un tale d, e di conseguenza di mostrare che(Z∼, |∼) è un reticolo.



31

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.



32

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


117


33

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 sono monoidie/o gruppi. Negli esempi di reticoli visti, stabilire se sitratta di monoidi e/o gruppi.



34

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.



35

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


36

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

118


37

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



38

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



39

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


40


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)


119


41


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.



42

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.



43

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



44

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

120


45

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


46

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.



47

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)



48

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


121


49


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


50


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 = 1a ∧ b = 0



51

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



52


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.


122


53

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.


123


1


CdL Informatica

17 dicembre 2003





2

Avvertenze





queste pagine).



3

Grafi



4

Notazione

Dato un insieme A, la notazione P(A) indica l’insiemedelle parti di A, cioè l’insieme i cui elementi sono tutti esoli i sottoinsiemi di A.

Utilizziamo la notazione Pn(A) per indicare l’insieme icui elementi sono tutti e soli i sottoinsiemi di ordine ndi A.

In particolare con P2(A) indichiamo l’insieme i cuielementi sono tutte e sole le coppie {a, b} con a, b ∈ A.

Osserviamo che, essendo sottoinsiemi di A, le coppie{a, b} e {b, a} coincidono. Si parla perciò di coppie nonordinate.


124


5

Grafi

Definizione – Un grafo semplice G consiste di

un insieme finito non vuoto V(G) di elementi chechiameremo vertici di Gdi un sottoinsieme L(G) di P2(V(G)) di elementiche chiameremo lati di G.

Quindi un lato di G è una coppia (non ordinata) {a, b} divertici distinti di G.

Esempio – Possiamo definire il grafo G definendo

V(G) = {a, b, c, d, e}

L(G) = {{a, b} , {a, c} , {b, c} , {b, d} , {d, e}}Matematica Discreta (elementi) – E-O – p. 5


6

Diagramma di un grafo

Un grafo può essere rappresentato da un diagramma

si disegna il diagramma di Eulero-Venn dell’insiemedei vertici di Gsi disegna una linea a congiungere il vertice x con ilvertice y se e soltanto se la coppia {x, y} è un latodi G

Un grafo può essere rappresentato da più di undiagramma

a

b

c

de

a

b

c

d

e



7

Il problema dei ponti di Königsberg

Königsberg era attraversata dal fiume Pregel. Parte dellacittà era situata sulle due sponde del fiume e parte sudue isole. Le zone della città erano collegate da setteponti in questo modo

È possibile fare una passeggiatapartendo da un punto della città eritornandovi dopo aver percorsoesattamente una volta ogni ponte?



8


La pianta di Königsberg con i suoi ponti

è schematizzabile da qualcosa che assomiglia molto adun grafo


125


9


Il diagrammaa

b

c

d

corrisponde al diagramma di un grafo?

V(G) =??? Poniamo V(G) = {a, b, c, d}

L(G) =??? Dovremmo porre L(G) ={{a, b} , {a, b} , {b, c} , {b, c} , {a, d} , {b, d} , {c, d}}



10

Multigrafi

Occorre un modo per distinguere le due occorrenze di{a, b} (e di {b, c})

a

b

c

d

l1 l2

l3 l4

l5l6l7

Scriviamo

V(G) = {a, b, c, d}

L(G) = {l1, l2, l3, l4, l5, l6, l7}

È lecito?Matematica Discreta (elementi) – E-O – p. 10


11

Multigrafi

Definizione – Un multigrafo G = (V, L, φ) consiste di

Un insieme finito V di elementi detti vertici di GUn insieme finito L di elementi detti lati di GUn’applicazione φ : L → P2(V)

Nell’esempio dei ponti di Königsberg, si ha

V(G) = {a, b, c, d}

L(G) = {l1, l2, l3, l4, l5, l6, l7}

φ è l’applicazione definita ponendo: l1 7→ {a, b},l2 7→ {a, b}, l3 7→ {b, c}, l4 7→ {b, c},l5 7→ {a, d}, l6 7→ {b, d}, l7 7→ {c, d}



12

Multigrafi

Un grafo semplice può essere pensato come unmultigrafo a

b

c

d

e

V(G) = {a, b, c, d, e}

L(G) = {{a, b} , {a, c} , {b, c} , {b, d} , {d, e}}

φ : L(G) → P2(V(G)) è definita ponendoφ : {a, b} 7→ {a, b} φ : {a, c} 7→ {a, c}φ : {b, c} 7→ {b, c} φ : {b, d} 7→ {b, d}φ : {d, e} 7→ {d, e}

Nel seguito perciò spesso con la parola “grafo”intenderemo un “multigrafo”. Matematica Discreta (elementi) – E-O – p. 12

126


13

(Multi)Grafi

Dato un (multi)grafo G = (V(G), L(G), φ).Se l ∈ L(G) è un lato e φ(l) = {v, w}, allora diremo chel è un lato da v a w, ovvero diremo che l unisce v a w.Diremo anche che v e w sono gli estremi di l.Due vertici v e w di G si dicono adiacenti se esiste unlato da v a w.Analogamente due lati l e m si dicono adiacenti sehanno un estremo in comune. a

b

c

d

l1 l2

l3 l4

l5l6l7

l6 è un lato da b a d (o da d a b)

i vertici a e b sono adiacenti

i lati l1 e l5 sono adiacenti

d e c sono gli estremi di l7 Matematica Discreta (elementi) – E-O – p. 13


14

Grado di un vertice

Dato un (multi)grafo G = (V(G), L(G), φ).

Definizione – Dato a ∈ V(G), diremo grado di a ilnumero dei lati in L(G) che hanno a come estremo.

Indicheremo con d(a) il grado del vertice a.a

b

c

d

l1 l2

l3 l4

l5l6l7

d(a) = 3

d(b) = 5

d(c) = 3

d(d) = 3

Definizione – Un vertice a ∈ V(G) è detto isolato sed(a) = 0. Matematica Discreta (elementi) – E-O – p. 14


15

Isomorfismo di (multi)grafi

Definizione – Due (multi)grafi G1 e G2 sono isomorfi seesiste una applicazione biunivoca

f : V(G1) → V(G2)

tale che per ogni coppia di vertici a, b ∈ V(G1) il numerodi lati in L(G1) che unisce a a b è uguale al numero di latiin L(G2) che unisce f (a) a f (b).

Esercizio – Confrontare questa definizione con ledefinizioni del libro di testo di “isomorfismo di grafi”(p. 109) e “isomorfismo di multigrafi” (p. 113). Sonoequivalenti?(Suggerimento: per quel che riguarda i multigrafi, si vedaex. 12.1, parte (b), p. 113)



16

Esempi

Si considerino i due seguenti (multi)grafia b c

d e f

G1

l

m

n

p

q

rG2

Ove i due diagrammi stanno ad indicare che

V(G1) = {a, b, c, d, e, f } e L(G1) ={{a, d} , {a, e} , {a, f } , {b, d} , {b, e} , {b, f } , {c, d} , {c, e} , {c, f }}

V(G2) = {l, m, n, p, q, r} e L(G2) ={{l, p} , {l, q} , {l, r} , {m, p} , {m, q} , {m, r} , {n, p} , {n, q} , {n, r}}

L’applicazione f : V(G1) → V(G2) definita ponendoa 7→ l b 7→ m c 7→ n d 7→ p e 7→ q f 7→ rè un isomorfismo di (multi)grafi. Matematica Discreta (elementi) – E-O – p. 16

127


17

Esercizi

Stabilire se le seguenti coppie di (multi)grafi sonocostituite o meno da (multi)grafi isomorfi

a b c

d e f

g

3 1 7

4 2 6

5

1 2

3 4

5 6

7 8L M

P K

J N

O Q



18

Esercizi


a

b

cd

eA

B

CD

E

lm

no

pL

M

NO

P



19

Esercizi


l

m

n

o

L

M

N

O

a

b

c

d

A

B

C

D



20

Numero dei lati di un (multi)grafo

Dato un (multi)grafo G = (V(G), L(G), φ), si ha laseguente

Proposizione – Il numero dei lati di G è dato da

|L(G)| =12 ∑

v∈V(G)

d(v)

Dimostrazione – È sufficiente contare il numero dei“mezzi lati”, numero che indichiamo con M

ogni lato ha due “mezzi lati”, quindi M = 2 |L(G)|

ogni vertice v appartiene esattamente a d(v) “mezzilati”, quindi M = ∑v∈V(G) d(v)


128


21

Esempio

Osserviamo il grafo

a

b

c

d

l1" l2"

l3" l4"

l5"

l6"

l7"Possiamo pensare di tagliarei lati del grafoevidenziando così i “mezzi lati”.Ritroviamo in questo modo l’idea che sta alla base delladimostrazione appena conclusa.

Esercizio – Secondo la nostra definizione di grafo,l’insieme V(G) è finito (mentre non è così per il libro ditesto). Confrontare la proposizione appena dimostratacon quella riportata nel libro di testo (Lemma 12.3,p. 109).



22

Grafi

Definizione – Un grafo è detto regolare di grado d setutti i suoi vertici hanno grado d.

Esercizio – Quanti lati ha un grafo regolare di grado dcon n vertici?

Definizione – Un grafo (semplice) è detto completo setutti i suoi vertici sono a due a due adiacenti.

Osserviamo che per ogni n ≥ 1 esiste uno e un solografo semplice completo.



23

Cammini

Dato un (multi)grafo G = (V(G), L(G), φ)

Definizione – Un cammino in G è una successione dilati distinti l1, l2, . . . , lk di L(G) tale che si abbia unasuccessione di vertici (non necessariamente distinti)v0, v1, . . . , vk in V(G) con (per ogni i, 1 ≤ i ≤ k)

φ(li) = {vi−1, vi}

a

b

c

d

l1 l2

l3 l4

l5l6l7l1, l2, l4, l7 è un cammino in G

la successione dei vertici è b, a, b, c, dl5, l6, l7 non è un cammino in G

Diciamo anche che l1, l2, . . . , lk è un cammino da v0 a vk.Matematica Discreta (elementi) – E-O – p. 23


24

Cammini

Dato un cammino l1, l2, . . . , lk, l’intero k è detta lalunghezza del cammino.

Un cammino può anche essere vuoto. Diremo allora cheil cammino ha lunghezza 0 (zero), ovvero che è ilcammino nullo.

Dato un qualsiasi vertice v ∈ V(G) diremo che ilcammino nullo “va da v a v”.

Un circuito è un cammino (diverso dal cammino nullo)da un qualunque vertice v a quello stesso vertice v.


129


25

Connessione


Definizione – Il grafo G è connesso se per ogni coppiadi vertici v, w ∈ V(G) esiste un cammino da v a w.

In V(G) possiamo definire una relazione di equivalenza

v ∼ w se e solo se esite un camminoda v a w

Esercizio – Mostrare che ∼ è una relazione diequivalenza.

Definizione – Le classi di equivalenza di ∼ sono dettecomponenti connesse di G.



26

Esempio

Consideriamo il seguente grafoa b c

d e fa ∼ a, a ∼ e, a ∼ f , e ∼ f , . . .

[a]∼ = [e]∼ = [ f ]∼ = {a, e, f }

d ∼ d, d ∼ b, d ∼ c, . . .[d]∼ = [b]∼ = [c]∼ = {d, b, c}

Il grafo non è connesso.

Ogni grafo è l’unione delle sue componenti connesse (nelsenso che l’insieme dei vertici V(G) è l’unioneinsiemistica delle componenti connesse di G).



27

Cammini Euleriani


Definizione – Un cammino l1, l2, . . . , lk in G è detto uncammino euleriano se L(G) = {l1, l2, . . . , lk}

In altre parole un cammino euleriano è un cammino chepassa una e una sola volta per ogni lato di G.

Si parla di circuito euleriano se il cammino euleriano èun circuito.

La soluzione del problema dei pontidi Königsberg equivale adeterminare un circuito eulerianonel grafo che rappresentai ponti della città

a

b

c

d

l1 l2

l3 l4

l5l6l7



28

Teorema di Eulero

Si ha la seguente risposta (Eulero, 1736)

Teorema – Sia G un multigrafo privo di vertici isolati.Allora G ha un circuito euleriano se e solo se è connessoe tutti i suoi vertici hanno grado pari.

Dal momento che il grafo dei ponti diKönigsberg ha vertici di grado dispari,non è possibile fare una passeggiatache, dopo aver percorso tutti i pontidella città una e una sola volta,ci riporti al punto di partenza.

a

b

c

d

l1 l2

l3 l4

l5l6l7


130


29

Esami

Questioni burocratiche

Al più presto (febbraio 2004??) sarà obbligatorioiscriversi agli esami via SIFA per poter sostenerel’esame

In particolare sarà indispensabile iscriversiall’esame giusto!

Il 20 di gennaio 2004, ore 9.30, si terrannoil secondo compitino (solo per chi ha passato ilprimo)un “pre-appello”, cioè un esame completo direcuperoAttenzione non iscriversi all’esame da “12crediti”



30



∃n0 ∈ Z (P(n0))

∀n > n0 (P(n− 1) → P(n))

∴ ∀n ≥ n0 (P(n))



allora è possibile dedurre che per qualunque assegnaton ≥ n0 la proposizione P(n) è vera.



31

Principio di induzione (seconda forma)

Sia P(n) un predicato che ha come universo l’insiemedei numeri interi Z. Allora

∃n0 ∈ Z (P(n0))

∀n > n0

(

∀m(n0 ≤ m < n) P(m))

→ P(n))

∴ ∀n ≥ n0 (P(n))


e se, per ogni fissato n > n0, supponendo che P(m)sia vera per ogni n0 ≤ m < n è possibile dimostrareche P(n) è vera

allora è possibile dedurre che per qualunque assegnaton ≥ n0 la proposizione P(n) è vera.



32

Induzione

In altre parole, mettendo a confronto le due formedell’induzione

Sia per la prima che per la seconda forma si verificaun caso base, cioè si verifica che P(n0) sia vera perun intero n0 opportuno

L’ipotesi induttiva è, se n > n0,che P(n− 1) sia vera (I forma)che P(m) sia vera per ogni m con n0 ≤ m < n(II forma)

Assumendo vera l’ipotesi induttiva, si dimostra cheP(n) è vera


131


33

Induzione

Si può dimostrare che le due forme dell’induzione sonoequivalenti

Teorema – La prima forma dell’induzione è valida se esolo se la seconda forma dell’induzione è valida.

(Si veda ad esempio Childs, Algebra, un’introduzioneconcreta, ETS ed., p. 11.)

Può essere sorprendente osservare che un’altra versionedell’induzione è la seguente

Principio del buon ordinamento – Sia n0 un interoqualunque. Un qualunque insieme di interi contenuto in{z | z ≥ n0} ammette minimo.

(Childs, p. 14)Matematica Discreta (elementi) – E-O – p. 33


34

Teorema di Eulero

Siamo a questo punto in grado di dare cenni delladimostrazione del teorema di Eulero.


Assumiamo perciò che G sia un grafo privo di verticiisolati.Questo significa che il grafo ha almeno due vertici e cheogni vertice è estremo almeno di un lato.

Per mostrare la prima parte del teorema supponiamo cheesista un circuito euleriano l1, l2, . . . , lk.Questo equivale a supporre che esista una successionedi vertici v0, v1, v2, . . . , vk (non necessariamente distinti)tale che li congiunga vi−1 a vi. Matematica Discreta (elementi) – E-O – p. 34


35

Teorema di Eulero

Partendo dal vertice v0 percorriamo il circuito (tenendoconto di come i lati percorsi contribuiscano al calcolo delgrado dei vertici)

seguendo il lato l1 andiamo da v0 a v1il grado di v0 è 1, il grado di v1 è 1

seguendo l2 andiamo da v1 a v2potrebbe succedere che v2 = v0, in tal caso ilgrado di v0 è 2, il grado di v1 è 2se invece v2 è un vertice “nuovo”, il grado di v0 è1, il grado di v1 è 2 e il grado di v2 è 1

Continuando così ci accorgiamo che i vertici “iniziali” e“finali” (come v0 e v2) se sono distinti hanno gradodispari, mentre i vertici “di passaggio” (come v1) hannogrado pari. Matematica Discreta (elementi) – E-O – p. 35


36

Esempio

Il grafo in figura ammette il circuito eulerianol1, l2, l5, l7, l3, l4, l6

a

b

c

d

l1 l2

l3 l4

l6

l5

l7

partiamo dal vertice a eseguendo l1 arriviamo a b

d(a) = 1, d(b) = 1

seguendo l2 andiamo da b a ad(a) = 2, d(b) = 2

seguendo l5 andiamo da a a dd(a) = 3, d(b) = 2, d(d) = 1

. . .d(a) = 3, d(b) = 2, d(d) = 2, d(c) = 1d(a) = 3, d(b) = 3, d(d) = 2, d(c) = 2


132


37

Esempio

Prima di percorre l’ultimo lato del circuito, il conto deigradi dei vertici è

d(a) = 3, d(b) = 4, d(d) = 2, d(c) = 3

Percorrendo infine l6 otteniamo che i gradi dei verticisono

d(a) = 4, d(b) = 4, d(d) = 2, d(c) = 4

Cioè tutti i vertici del grafo hanno grado pari.



38

Teorema di Eulero

Tornando alla dimostrazione del teorema, per concluderela prima parte della dimostrazione resta da mostrare cheil grafo è connesso.

Occorre cioè mostrare che data una qualunque coppia divertici, questi sono uniti da un cammino.

Abbiamo osservato che, essendo G privo di vertici isolati,ogni vertice di G appartiene ad almeno un lato.Questo significa che ogni vertice di G è nella “lista”v0, v1, . . . , vk.

Due qualsiasi vertici vm e vn della lista v0, v1, . . . , vk sonoconnessi dal cammino formato da lm, lm+1, . . . , ln−1, ln(questo se m ≤ n, altrimenti . . . ).



39

Teorema di Eulero

Mostriamo ora il viceversa.

Sia G connesso e tutti i suoi vertici abbiano grado pari.

Procediamo per induzione sul numero dei lati di G emostriamo come costruire un circuito euleriano

In altre parole consideriamo il predicatose G è connesso con n lati e tutti i suoi vertici

hanno grado pari, alloraG ammette un circuito euleriano

e procediamo per induzione su n.



40

Teorema di Eulero

Partiamo da un qualunque vertice del grafo, chechiamiamo v0.Il fatto che tutti i vertici hanno grado pari, significa chepercorrendo i lati del grafo, senza ripetizioni, prima o poiritroverò v0.Infatti ogni volta che si “entra” in uno dei vertici (diversi dav0), essendo il grado del vertice pari, avrò un lato in“uscita” dal vertice.

Esempio –· · v0

· · · ·

1

3 7

4 5 6

2 8


133


41

Teorema di Eulero

A questo punto cancelliamo dal grafo tutti i lati giàpercorsi e applichiamo l’induzione a quello che resta

Esempio –· · v0

· · · ·

ATTENZIONE: non possiamo applicare l’induzione aquello che resta, perché nelle ipotesi abbiamo che ilgrafo deve essere connesso.Possiamo però applicare l’ipotesi induttiva ad ognicomponente connessa del grafo dei “resti”.



42

Teorema di Eulero

Dal momento che ogni componenete connessa di quelche resta ha un numero di lati strettamente minore di n,per ipotesi induttiva in ogni componente connessapossiamo trovare un circuito euleriano.

Ma allora è possibile costruire un circuito euleriano sututto G mettendo assieme il primo circuito da v0 a v0 conquello ottenuto in ogni componente connessa.

Esempio –· · v0

· · · ·

a 1

3 c 7

b

4 5 6d

2 8



43

Base dell’induzione

Manca la verifica ∃n0 ∈ Z (P(n0))

Qual è il minimo numero di lati per cui l’enunciato delteorema ha senso?

Per tale numero di lati, il teorema è vero?

Il caso da considerare è un grafo del tipo

· ·

per il quale il teorema è vero.



44

Esempio

Ricordiamo ancora una volta l’enunciato del teorema diEulero


È possibile che un grafo non connessoammetta un circuito euleriano?

a b

c d e

V(G) = {a, b, c, d, e}


134


45

Corollario

Il teorema di Eulero ha il seguente corollario

Corollario – Sia G un (multi)grafo privo di vertici isolati.Allora G ha un cammino euleriano se e solo se èconnesso e ha zero o due vertici di grado dispari.

Osserviamo perciò che il grafo dei ponti di Königsbergnon ammette neppure un cammino euleriano.



46

Cammini Hamiltoniani

Si può considerare anche una sorta di problema dualedel problema dei cammini euleriani.

Un cammino hamiltoniano in un grafo G è un camminoche passa una e una sola volta per ogni vertice di G

Il problema si rivela però più complesso: non abbiamo unanalogo del teorema di Eulero.(In genere abbiamo teoremi che danno condizionisufficienti per l’esistenza di un cammino hamiltoniano.)

Esercizio – In tutti gli esempi di grafi visti provare acostruire cammini euleriani e cammini hamiltoniani.



47

Reticoli e anelli



48

Reticoli e anelli

Riprendiamo l’esercizio

(P(X),∪,∩) è un anello? È dotato di unità?

(P(X),∩,∪) è un anello? È dotato di unità?

Per dotare P(X) della struttura di anello dobbiamodefinire le operazioni in altro modo

il ruolo dell’operazione di “somma” è giocato dalladifferenza simmetrica

A4 B = {x | (x ∈ A)⊕ (x ∈ B)}

il ruolo dell’operazione di “prodotto” è giocatodall’intersezione

(P(X),4,∩) è un anello con unità.Matematica Discreta (elementi) – E-O – p. 48

135


49

Reticoli e anelli

La costruzione appena vista vale in un qualsiasi reticolodi Boole.Sia (L,∧,∨) un reticolo di Boole, se indichiamo con a′ ilcomplemento di a, allora possiamo definire dueoperazioni in L

a + b = (a ∧ b′) ∨ (a′ ∧ b)

a · b = a ∧ bAllora (L, +, ·) è un anello con unità.



50

Anelli



51

Anelli

Concludiamo con un ultimo esempio di anelloSia A l’insieme costituito da tabelle di questo tipo (dovea, b, c, d sono numeri interi)

[

a bc d

]

In A possiamo definire una “somma” e un “prodotto” inquesta maniera

[

a1 b1c1 d1

]

+

[

a2 b2c2 d2

]

=

[

a1 + a2 b1 + b2c1 + c2 d1 + d2

]

[

a1 b1c1 d1

]

·

[

a2 b2c2 d2

]

=

[

a1 · a2 + b1 · c2 a1 · b2 + b1 · d2c1 · a2 + d1 · c2 c1 · b2 + d1 · d2

]



52

Anelli

Esercizio – Verificare che (A, +, ·) è un anello con unitàla “tabella”

[

1 00 1

]

Il prodotto non è commutativo, come si vedemoltiplicando, ad esempio le due “tabelle”

[

1 00 0

] [

0 75 0

]

Per determinarne gli elementi invertibili (rispetto alprodotto) seguite “Matematica Discreta (complementi)”


136

marina/did/mdis03/concat4up.pdf · 6 ottobre 2003 Mar ina Cazz ola (mar [email protected] ......

Documents

Transcript of marina/did/mdis03/concat4up.pdf · 6 ottobre 2003 Mar ina Cazz ola (mar [email protected] ......