Matematica Discreta Lezione del giorno 29 settembre 2008 Elementi di Logica Elementare Proposizioni e predicati.

Matematica Discreta

Lezione del giorno 29 settembre 2008 Elementi di Logica Elementare Proposizioni e predicati.

Si definisce proposizione logica una qualunque frase di senso compiuto che sia vera o falsa.

Esempio:

P = “7>5”

é una proposizione vera (P è il nome della proposizione, fra virgolette vi è il testo o enunciato della proposizione”).

Q = “Palermo è una città della Lombardia”

é una proposizione falsa.

R = “Ciao”

non è una proposizione.

Il valore di verità o falsità di una proposizione può anche non essere conosciuto:

P=”esiste vita intelligente al di fuori della terra”

é una proposizione (anche se non sappiamo attualmente se sia vera o falsa).

Si definisce predicato logico una qualunque frase di senso compiuto che contiene delle variabili (spesso indicate con lettere come x,y,z….) e che diventa una proposizione (vera o falsa) quando si fanno assumere valori concreti alle variabili.

Esempio:

P(x,y) = “la somma dei numeri interi x,y è >40” è un predicato nelle 2 variabili x,y (P è il nome del predicato, seguito dall’elenco, facoltativo, delle variabili; fra virgolette vi è il testo o enunciato del predicato).

Se facciamo per esempio assumere alle variabili rispettivamente i valori x=19, y=28, otteniamo la proposizione vera

P(9,8) = “la somma dei numeri interi 19,28 è >40”

mentre se facciamo per esempio assumere alle variabili rispettivamente i valori x=4, y=5, otteniamo la proposizione falsa

P(4,5) = “la somma dei numeri interi 4,5 è >40”

Talvolta si restringono i valori possibili delle variabili in un predicato, indicando il campo di variabilità o universo (ossia indicando i valori permessi per le variabili).

Esempio:

Scrivendo

P(x) = “x<20” (campo di variabilità=numeri interi positivi)

si intende che nel predicato P gli unici valori possibili che si possono attribuire alla variabile x sono appunto gli interi positivi.

Una proposizione si può considerare un predicato senza variabili: in tal senso tutto ciò che diremo

sui predicati si potrà applicare alle proposizioni.

Operazioni logiche.

Introdurremo delle operazioni logiche fra i predicati: sono operazioni che, dati alcuni predicati (operandi), operano su di essi per ottenere un nuovo predicato (risultato) i cui valori di verità o falsità dipendono da quelli dei predicati operandi.

1) Congiunzione logica

Dati due predicati P, Q, si chiama congiunzione logica di P, Q il predicato che:

- ha come nome PQ (si legge P and Q oppure P e Q)

- ha come testo i testi di P e Q separati dalla congiunzione “e” (quindi ha come variabili le variabili di P e quelle di Q)

- è vero solo per i valori delle variabili che rendono veri sia P che Q, ed è falso per tutti gli altri valori delle variabili (quindi è falso per i valori delle variabili che rendono falso uno dei 2 predicati P, Q o entrambi)

Esempio:

Dati i 2 predicati P(x,y) = “x>y”

Q(y,z) = “y<z ² ”

(con campo di variabilità= numeri interi positivi) la loro congiunzione logica è il predicato [PQ](x,y,z)=”x>y e y<z ² ”.

Tale nuovo predicato è vero solo per i valori di x,y che rendono vero P e i valori di y,z che rendono vero Q.

Per esempio

[PQ](5,3,2)=”5>3 e 3<2 ² ” è una proposizione vera in quanto P(5,3)= “5>3”

Q(3,2) = “3<2 ² ”

sono entrambe proposizioni vere.

Invece

[PQ](6,4,1)=”6>4 e 4<1 ² ” è una proposizione falsa in quanto P(6,4)= “6>4”

é una proposizione vera, ma Q(4,1) = “4<1 ² ”

é una proposizione falsa.

Analogamente [PQ](1,2,4) [PQ](2,4,2)

sono proposizioni false, la prima perché P(1,2) è falsa (pur essendo Q(2,4) vera), e la seconda perché entrambe P(2,4), Q(4,2) sono false.

Se conveniamo che il simbolo 1 indica “vero”e il simbolo 0 indica “falso”, i possibili valori di verità della congiunzione PQ, in funzione di quelli di P e Q, sono i seguenti:

11=1 10=0 01=0 00=0

e si possono schematizzare in una tavola della verità come la seguente:

P Q PQ

1 1 1

1 0 0

0 1 0

0 0 0

oppure come la seguente (in cui alle righe si fanno corrispondere i valori di P, alle colonne quelli di Q, e nelle caselle all’incrocio quelli di PQ):

1 0 1

0

Analoghe tavole di verità si possono ottenere convenendo che V indichi “vero”, F indichi “falso”.

1 0

0 0

Matematica Discreta

Lezione del giorno 1 ottobre 2008 2) Disgiunzione logica

Dati due predicati P, Q, si chiama disgiunzione logica di P, Q il predicato che:

- ha come nome PvQ (si legge P or Q oppure P o Q)

- ha come testo i testi di P e Q separati dalla congiunzione “o” (quindi ha come variabili le variabili di P e quelle di Q)

- è falso solo per i valori delle variabili che rendono falsi sia P che Q, ed è vero per tutti gli altri valori delle variabili (quindi è vero per i valori delle variabili che rendono vero uno dei 2 predicati P, Q o entrambi)

Esempio:

Dati i 2 predicati (con campo di variabilità = numeri interi positivi):

P(x) = “x>10”

Q(y) = “y è pari”

la loro congiunzione logica è il predicato [PvQ](x,y)=”x >10 o y è pari”.

Tale nuovo predicato è falso solo per i valori di x che rendono falso P e i valori di y che rendono falso Q.

Per esempio

[PvQ](11,3)=”11>10 o 3 è pari” è una proposizione vera in quanto P(11)= “11>10”

è una proposizione vera, pur essendo Q(3) = “3 è pari”

una proposizione falsa.

Invece

[PvQ](9,5)=”9>10 o 5 è pari” è una proposizione falsa in quanto entrambe le proposizioni P(9), Q(5) sono false.

I possibili valori di verità della disgiunzione PvQ, in funzione di quelli di P e Q, sono i seguenti:

1v1=1 1v0=1 0v1=1 0v0=0

La tavola di verità della disgiunzione logica PvQ è la seguente:

P Q PvQ

1 1 1

1 0 1

0 1 1

0 0 0

oppure:

1 0 1

0 1 1

1 0

3) Negazione logica

Dati un predicato P si chiama negazione logica di P il predicato che:

- ha come nome P (si legge not P o non P)

- ha un testo che è opposto di quello di P da un punto di vista logico (quindi ha le stesse variabili di P)

- è vero per tutti i valori delle variabili per cui è falso P, ed è falso per tutti i valori delle variabili per cui è vero P

Per esempio dato il predicato:

P(x) = “x>6” (con campo di variabilità x=numero intero positivo) la sua negazione logica può essere

P (x)=”non è vero che x>6”

oppure, più elegantemente:

P (x)=”x≤6”.

I possibili valori di verità della negazione logica P , in funzione di quelli di P, sono i seguenti:

1 =0 0 =1

La tavola di verità della negazione logica P è la seguente:

P P

1 0

0 1

Implicazione logica

Dati due predicati P, Q, nelle stesse variabili, diremo che P implica Q (oppure: da P segue Q, o ancora: se P allora Q) quando tutti i valori delle variabili che rendono vero P rendono vero anche Q. In questo caso scriveremo il simbolo PQ

Per esempio se sono dati i seguenti predicati (con campo di variabilità x=numero intero positivo):

P(x) = “x<4”

Q(x) = “x+3<9”

allora è vero che P implica Q perché i valori della x che rendono vero P sono esattamente x=1,2,3 e si verifica facilmente che essi rendono vero anche Q.

Spesso però i valori delle variabili che rendono vero P sono in numero infinito, e in tal caso non è possibile, come nell’esempio precedente, verificare singolarmente che ciascuno di essi rende vero anche Q.

In tal caso si ricorre a una dimostrazione logico-deduttiva: si suppone di avere un valore generico delle variabili che rende vero P (ipotesi), e attraverso dei passaggi intermedi (giustificati da conoscenze acquisite in precedenza) si cerca di dimostrare che tale valore rende vero anche Q (tesi).

Per esempio se sono dati i seguenti predicati (con campo di variabilità x=numero intero positivo):

P(x) = “x>7”

Q(x) = “x+2>6”

per dimostrare che PQ si potrebbe procedere operando i seguenti passaggi:

1) supponiamo che x sia un valore che renda vero P (ipotesi) quindi che x sia un intero positivo

tale che x>7

2) applicando la proprietà delle diseguaglianze che permette di sommare ad ambo i membri lo stesso numero ottenendo una diseguaglianza ancora valida si ha x+2>9

3) osservando che 9>6 e che vale la proprietà transitiva dell’ordinamento dei numeri interi, da x+2>9 e 9>6 si ottiene x+6, quindi x rende vero anche Q (tesi)

E’ ovvio che se si vuole verificare invece che un predicato P non implica un predicato Q, allora non si deve procedere con una dimostrazione, ma bensì cercare almeno un valore delle variabili che renda vero P ma renda falso Q.

Nell’esempio precedente come visto si ha PQ, ma non è vero viceversa che QP, in quanto è possibile esibire valori di x che rendo vero Q ma falso P (per es. x=5).

La tecnica dimostrativa illustrata sopra è diretta. Vi è anche una tecnica dimostrativa per assurdo:

per dimostrare che PQ si suppone (per assurdo) che sia dato un valore delle variabili che renda vero P ma falso Q (quindi si suppone per assurdo vera l’ipotesi e falsa la tesi) e attraverso dei passaggi logici si cerca di pervenire ad una contraddizione logica (se tale contraddizione viene raggiunta, si può concludere che in effetti non esiste un valore delle variabili che renda vero P e falso Q, dunque PQ).

Per esempio se sono dati i seguenti predicati (con campo di variabilità x=numero intero positivo):

P(x,y) = “x è pari, y è dispari”

Q(x,y) = “x+y è dispari”

(dove “pari” significa multiplo di 2, e “dispari” significa non pari), per dimostrare che PQ con la tecnica della dimostrazione per assurdo si potrebbe procedere operando i seguenti passaggi:

1) supponiamo (per assurdo) che esista un valore delle variabili x,y che renda vero P ma falso Q, quindi x sia pari, y sia dispari, ma x+y non sia dispari, cioè x+y sia pari

2) applicando la definizione di numero pari, si ha x=2z, x+y=2t, dove z,t sono opportuni numeri interi positivi

3) sostituendo il valore x=2z nella seconda eguaglianza, si ha 2z+y=2t 4) sottraendo ad ambo i membri dell’eguaglianza il numero 2z si ha y=2t-2z

5) applicando la proprietà distributiva della somma rispetto al prodotto si ha y=2(t-z) e si ottiene che y è multiplo di 2, cioè y è pari (contraddizione logica, perché y è dispari).

Avendo ottenuto una contraddizione, si può concludere che in effetti PQ .

Matematica Discreta

Lezione del giorno 2 ottobre 2008 Equivalenza logica

Se sono dati due predicati P, Q, nelle stesse variabili, e se si ha sia PQ che QP, diremo allora che P se e solo se Q e scriveremo PQ.

In questo caso i valori delle variabili che rendono vero P coincidono esattamente con quelli che rendono vero Q, quindi P, Q in pratica rappresentano la stessa affermazione da un punto di vista logico: diremo allora che i predicati P e Q sono equivalenti.

Per esempio se sono dati i seguenti predicati (con campo di variabilità x=numero intero positivo):

P(x) = “x<20”

Q(x) = “x+7<27”

é facile (utilizzando metodi simili a quelli descritti in precedenza) dimostrare che PQ e che QP dunque si può concludere che PQ.

Insiemistica

Studieremo la teoria “ingenua” degli insiemi (in contrapposizione alla cosiddetta teoria

“assiomatica”), in cui il concetto di insieme si considera primitivo, ossia non si definisce, intendendo immediatamente evidente il concetto di insieme come sinonimo di raccolta, collezione di elementi.

Gli elementi di un insieme possono avere natura arbitraria, ed anche natura diversa fra loro:

potremmo per esempio costruire un insieme che ha come elementi il numero 3, la città di Palermo e il concetto astratto di bellezza.

Se A è un insieme ed x un suo elemento, diremo che x appartiene ad A e scriveremo xA. Se invece x non è elemento dell’insieme A, diremo che x non appartiene ad A e scriveremo xA.

Un insieme può essere descritto in modo esplicito, elencando tutti i suoi elementi.

Per esempio possiamo costruire il seguente insieme di nome A:

A ={3, 5, 7, 9}

contenente i 4 numeri interi elencati fra parentesi.

Un insieme si distinguerà solo per gli elementi che contiene, che si considerano sempre distinti senza ripetizioni, e non per l’ordine in cui sono elencati.

Quindi lo stesso insieme A dell’esempio precedente può essere descritto in modo esplicito anche da A ={5, 9, 7, 3}.

Nel modo esplicito per verificare se xA basta verificare se x compare nell’elenco degli elementi di A: nell’esempio precedente si ha 7A, ma 8A.

Ovviamente tale modo esplicito di descrivere un insieme è esauriente solo nel caso di insiemi che contengano un numero finito di elementi.

Un insieme può essere descritto anche in modo implicito, indicando le proprietà che caratterizzano i suoi elementi mediante un predicato.

Se P(x) è un predicato nella variabile x, possiamo costruire l’insieme di nome B:

B = { x / P(x) }

(si legge: “B è l’insieme di tutti gli x tali che P(x)”; il simbolo / può talvolta essere sostituito dal

simbolo :); con tale simbologia si intende che gli elementi dell’insieme B sono esattamente tutti i

valori della variabile x che rendono vero il predicato P(x).

Per esempio possiamo costruire il seguente insieme di nome B:

B = { x / x è un intero positivo pari }

(si legge: “B è l’insieme di tutti gli x tali che x è un intero positivo pari”).

In tale esempio il predicato che definisce l’insieme B è appunto P(x)=“x è un intero positivo pari” e gli elementi di B sono i valori di x che lo rendono vero (quindi tutti gli interi positivi pari).

Dato un insieme A, ed un elemento x, per verificare se xA:

- se A è definito in modo esplicito, basta verificare che x appaia nell’elenco degli elementi di A - se A è definito in modo implicito mediante un predicato P(x), basta verificare che x renda vero P(x)

Se il predicato che descrive in modo implicito l’insieme è falso per ogni valore della variabile, si ottiene un insieme privo di elementi, detto insieme vuoto, e indicato con .

Per esempio:

{ x / x è intero >5 e <3 } = .

Sottoinsiemi di un insieme.

Dati gli insiemi A, B, diremo che B è contenuto in A, oppure che B è sottoinsieme di A, e scriveremo BA, se ogni elemento di B è anche elemento di A.

Se B non è contenuto in A, scriveremo BA.

Se gli insiemi sono descritti in modo esplicito, per verificare se BA basta verificare che ogni elemento nell’elenco di B compaia anche nell’elenco di A.

Per esempio se A = {1,3,4,5,6,8}, B = {6, 5, 3}, C = {8, 4, 2} si ha B A (ogni elemento 6, 5, 3 dell’elenco di B appare nell’elenco di A), ma CA (l’elemento 2 dell’elenco di C non appare nell’elenco di A).

Se gli insiemi sono invece descritti in modo implicito, mediante predicati:

A = { x / P(x) } B = { x / Q(x) }

allora verificare che BA equivale a dimostrare l’implicazione Q  P (perché affermare che ogni

elemento di B è elemento di A equivale ad affermare che ogni valore di x che rende vero Q rende

vero anche P).

Matematica Discreta

Lezione del giorno 6 ottobre 2008 Eguaglianza fra insiemi

Due insiemi A, B sono uguali se contengono gli stessi elementi: questo equivale ad affermare che ogni elemento di A è anche elemento di B e che viceversa ogni elemento di B è anche elemento di A. Quindi l’eguaglianza di insiemi A=B equivale alla “doppia inclusione” AB e BA .

Se gli insiemi sono descritti in modo implicito, mediante predicati:

A = { x / P(x) } B = { x / Q(x) }

allora verificare che A=B equivale a dimostrare vera sia l’implicazione Q  P che l’implicazione inversa P  Q, quindi in questo caso l’eguaglianza di insiemi A=B corrisponde all’equivalenza dei predicati: P  Q .

Per ogni insieme A, è ovvio che A è sottoinsieme di sé stesso:

AA

Per convenzione l’insieme vuoto  si considera sottoinsieme di qualunque insieme A.

Poiché, dato un insieme A qualunque, si ha sempre A e AA, i due sottoinsiemi , A sono detti sottoinsiemi banali o impropri dell’insieme A. Per indicare che un sottoinsieme B dell’insieme A è diverso da A spesso si usa il simbolo BA (e si dice che B è contenuto propriamente in A).

Essendo arbitraria la natura degli elementi di un insieme, possiamo anche considerare insiemi i cui elementi sono a loro volta degli insiemi.

In particolare, fissato un arbitrario insieme A, possiamo costruire l’insieme delle parti di A (indicato con il simbolo P(A)), i cui elementi sono tutti i possibili sottoinsiemi di A.

Per esempio se A = {a, b, c}, l’insieme delle parti di A è l’insieme:

P(A) = { , {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, A }.

Si può notare che A contiene 3 elementi e P(A) contiene 8=2 ³ elementi: dimostreremo in seguito che ciò non è casuale.

Se A è un insieme fissato, possiamo descrivere in forma implicita un sottoinsieme B di A nel modo seguente:

B = { xA / P(x) } (dove P(x) è un predicato)

intendendo che gli elementi del sottoinsieme B sono tutti e soli gli elementi di A che rendono vero P(x).

Per esempio, se A è l’insieme dei numeri interi positivi pari, si ha:

B = { xA / x<10 } = {2,4,6,8}.

Antinomia di Russell

Nella teoria “ingenua” degli insiemi, il fatto che la natura degli elementi sia completamente arbitraria può portare a dei problemi logici, che furono messi in evidenza da Russell.

Partiamo da alcuni esempi: costruiamo l’insieme A i cui elementi sono tutti gli insiemi che contengono più di 2 elementi

A = { x / x è un insieme che contiene più di 2 elementi } Alcuni esempi di elementi di A sono gli insiemi {1,2,3}, {a,b,c,d,e}, {a,1,7,8,b,d}.

Poiché A stesso contiene più di 2 elementi si ha che A è elemento di sé stesso: AA.

Invece se costruiamo l’insieme B i cui elementi sono tutti gli insiemi che contengono esattamente 1 solo elemento

B = { x / x è un insieme che contiene esattamente 1 solo elemento }

poiché è ovvio che B stesso contiene più di 1 elemento (esempi di elementi di B sono {1},{a} etc..) si ha che B non è elemento di sé stesso: BB.

Abbiamo visto dunque che esistono insiemi che hanno sé stessi come elementi, ed insiemi che non hanno sé stessi come elementi.

Costruiamo allora l’insieme C i cui elementi sono tutti gli insiemi che non hanno sé stessi come elementi

C = { x / x è un insieme ed xx }

(un elemento di C è per esempio l’insieme B costruito sopra).

Domanda: CC oppure CC ?

Ma se CC allora dalla costruzione di C segue che CC; viceversa se CC allora dalla costruzione di C segue che CC: siamo in presenza di una contraddizione logica (antinomia di Russell), perché un’affermazione è vera e falsa nello stesso tempo.

Per risolvere questi problemi logici legati alla teoria “ingenua” degli insiemi si può ricorrere alla teoria “assiomatica” (più precisa dal punto di vista formale) oppure evitare la costruzione di insiemi che contengano tutti gli insiemi che soddisfano una proprietà fissata (quindi evitare frasi come “sia A l’insieme di tutti gli insiemi tali che …..).

Operazioni fra insiemi.

Sono procedimenti che, dati alcuni insiemi (operandi) costruiscono un nuovo insieme (risultato) i cui elementi dipendono dagli elementi degli insiemi operandi.

1) Unione di insiemi:

Dati gli insiemi A,B, si chiama insieme unione di A e B (indicato con AB) l’insieme degli elementi che appartengono ad almeno uno degli insiemi A,B.

Se A,B sono descritti in modo esplicito, AB è descritto in modo esplicito da un elenco di tutti gli elementi che compaiono nell’elenco di A o nell’elenco di B o in ambedue (questi ultimi elencati 1 sola volta).

Per esempio se A={1,2,3,4,5,6}, B={8,5,6,9} allora AB={1,2,3,4,5,6,8,9}.

Se A,B sono descritti in modo implicito:

A = { x / P(x) }, B = { x / Q(x)}

allora AB è descritto in modo implicito dal predicato disgiunzione logica PvQ.

Per esempio se A = { x / x è intero positivo dispari }, B = { x / x è intero >12 } allora:

AB = { x / x è intero positivo dispari o x è intero >12 }

(quindi AB contiene gli interi dispari 1,3,5,7,9,11 e tutti gli interi consecutivi da 13 in poi).

Proprietà evidenti dell’unione sono le seguenti:

- dato un insieme A si ha AA=A (idempotenza)

- dati 2 insiemi A,B si ha AB=BA (proprietà commutativa)

- dati 3 insiemi A,B,C si ha (AB)C= A(BC) (proprietà associativa) (per questa terza proprietà basta notare che sia (AB)C che A(BC) coincidono con l’insieme degli elementi che appartengono ad almeno uno fra gli insiemi A,B,C)

2) Intersezione di insiemi:

Dati gli insiemi A,B, si chiama insieme intersezione di A e B (indicato con AB) l’insieme degli elementi che appartengono ad ambedue gli insiemi A,B.

Se A,B non hanno elementi in comune si ha AB= e si dice che A,B sono disgiunti.

Se A,B sono descritti in modo esplicito, AB è descritto in modo esplicito da un elenco di tutti gli elementi che compaiono sia nell’elenco di A che nell’elenco di B.

Per esempio se A={1,2,3,4,5,6}, B={8,5,6,9} allora AB={5,6}.

Se A,B sono descritti in modo implicito:

A = { x / P(x) }, B = { x / Q(x)}

allora AB è descritto in modo implicito dal predicato congiunzione logica PQ.

Per esempio se A = { x / x è intero positivo dispari }, B = { x / x è intero >12 } allora:

AB = { x / x è intero positivo dispari e x è intero >12 } (quindi AB contiene tutti gli interi dispari da 13 in poi).

Proprietà evidenti dell’intersezione sono le seguenti:

- dato un insieme A si ha AA=A (idempotenza)

- dati 2 insiemi A,B si ha AB=BA (proprietà commutativa)

- dati 3 insiemi A,B,C si ha (AB)C=A(BC) (proprietà associativa) (per questa terza proprietà basta notare che sia (AB)C che A(BC) coincidono con l’insieme degli elementi che appartengono ad tutti e 3 gli insiemi A,B,C)

3) Differenza di insiemi:

Dati gli insiemi A,B, si chiama insieme differenza A meno B (indicato con A-B) l’insieme degli elementi che appartengono ad A ma non appartengono a B.

Se A,B non hanno elementi in comune si ha ovviamente A-B=A, B-A=B.

Se A,B sono descritti in modo esplicito, A-B è descritto in modo esplicito da un elenco di tutti gli elementi che compaiono nell’elenco di A ma non nell’elenco di B.

Per esempio se A={1,2,3,4,5,6}, B={8,5,6,9} allora A-B={1,2,3,4} mentre B-A={8,9}.

Se A,B sono descritti in modo implicito:

A = { x / P(x) }, B = { x / Q(x)}

allora A-B è descritto in modo implicito dal predicato P ^Q congiunzione logica di P e della negazione di Q.

Per esempio se A = { x / x è intero positivo dispari }, B = { x / x è intero >12 } allora:

A-B = { x / x è intero positivo dispari ed x è intero ≤12 } = {1,3,5,7,9,11}

mentre:

B-A = { x / x è intero >12 ed x è intero positivo pari}

(quindi B-A contiene tutti gli interi pari da 14 in poi).

Dall’esempio precedente si deduce che in generale A-BB-A (dunque l’operazione differenza non soddisfa la proprietà commutativa.

4) Complementare di un sottoinsieme in un inseme:

Dati gli insiemi A,B e nel caso particolare in cui l’insieme B sia sottoinsieme dell’insieme A, la differenza A-B è detta complementare di B in A e indicata con

B: dunque il complementare di B in A ha come elementi tutti gli elementi di A che non appartengono a B.

Le proprietà principali del complementare sono espresse dalle leggi di DeMorgan:

se B,C sono sottoinsiemi dell’insieme A (notare che anche BC, BC sono sottoinsiemi di A e si possono considerare i 4 complementari ^c B, ^c C, ^c (BC), ^c (BC)) si ha

^c (BC)= ^c B ^c C ^c (BC)= ^c B ^c C

Le dimostrazione di ognuna di queste 2 proprietà comporta la dimostrazione di una doppia inclusione. Per esempio per dimostrare la prima proprietà, si devono dimostrare le 2 inclusioni:

^c (BC) ^c B ^c C ^c B ^c C ^c (BC)

Dimostriamo la prima delle 2 inclusioni (la dimostrazione della seconda é analoga): se x è un elemento generico di ^c (BC), allora, per definizione di complementare, si ha xA ma xBC, e per definizione di unione si ha xB e xC, dunque xA e xB e simultaneamente xA e xC, ossia x ^c B e simultaneamente x ^c C, e si può concludere che x ^c B ^c C.

Per concludere la trattazione delle operazioni fra insiemi, notiamo che valgono le seguenti proprietà distributive di unione e intersezione:

dati gli insiemi A,B,C si ha A(BC)=(AB)(AC) e A(BC)=(AB)(AC).

Esse si dimostrano facilmente con le doppie inclusioni.

Diagrammi di Eulero-Venn.

Sono rappresentazioni grafiche di un insieme, in cui gli elementi si rappresentano come punti del piano all’interno di una curva chiusa (spesso una circonferenza).

Esempio di diagramma di Eulero-Venn che rappresenta l’insieme A={1,2,3,4,5}:

Si possono rappresentare con tali diagrammi anche i risultati delle operazioni fra insiemi: unione, intersezione e differenza.

Per esempio per rappresentare l’intersezione AB:

A B

(l’insieme A è rappresentato con linee orizzontali, l’insieme B con righe verticali: l’insieme intersezione AB sarà rappresentato dalla quadrettatura).

Le proprietà già enunciate per le operazione fra insiemi si possono verificare graficamente sui diagrammi di Eulero-Venn..

1 2 3

4 5

Matematica Discreta

Lezione del giorno 8 ottobre 2008 Prodotto cartesiano

Se a,b sono 2 elementi (di natura arbitraria, nello stesso insieme o in insiemi diversi) anche possibilmente coincidenti fra loro, la coppia ordinata (a,b) con primo elemento a, secondo elemento b è una struttura insiemistica in cui si tiene conto sia degli elementi a,b che dell’ordine in cui sono elencati.

Dunque la coppia ordinata (a,b) si distingue dall’insieme {a,b} perché (se ab) si ha (a,b)(b,a) (mentre invece come insiemi si ha {a,b}={b,a}).

Dati 2 insiemi A,B si chiama prodotto cartesiano AxB l’insieme che contiene tutte le possibili coppie ordinate (a,b) dove il primo elemento aA, ed il secondo elemento bB.

Esempio: se A={3,a,5}, {a,5,2} allora

AxB={(3,a),(3,5),(3,2),(a,a),(a,5),(a,2),(5,a),(5,5),(5,2)}.

Relazioni fra insiemi

Dati gli insieme A,B, si chiama relazione dall’insieme A all’insieme B un qualunque sottoinsieme R del prodotto cartesiano AxB (quindi R è un insieme di coppie (a,b) con il primo elemento in A e il secondo in B). Se una coppia (a,b) (con aA, bB) appartiene ad R, diremo che l’elemento aA è associato nella relazione R all’elemento bB e scriveremo il simbolo aRb (se invece la coppia (a,b) non appartiene ad R si scrive il simbolo aRb con una sbarra che taglia la R).

Esempio: se A={1,2,3,6}, B={2,3,5} e se la relazione da A a B è il seguente sottoinsieme di AxB:

R = {(1,2), (1,3), (2,3), (6,2)}

Allora 1R2, 1R3, 2R3, 6R2 (ma l’elemento 1A non è per esempio associato all’elemento 5B).

Come si vede dall’esempio, in una relazione R da A a B un elemento di A può essere associato a più di un elemento di B, oppure non essere associato a nessun elemento di B.

Spesso una relazione R da A a B viene descritta da un predicato P(x,y) in 2 variabili (in cui la variabile x assume valori in A, la variabile y assume valori in B): il predicato fornisce la “regola”

con cui gli elementi di A sono associati agli elementi di B, nel senso che, dati un elemento aA, e un elemento bB, si ha aRb (quindi l’elemento aA è associato nella relazione R all’elemento bB) solo quando P(a,b) è vero (dove ricordiamo che P(a,b) è la proposizione ottenuta sostituendo x con a, y con b).

Esempio: se A={1,2,3,6}, B={2,3,5} e se la relazione R da A a B è descritta dal predicato P(x,y)=”x<y” (in pratica un elemento aA è associato nella relazione R ad un elemento bB quando a<b), allora il sottoinsieme R del prodotto cartesiano AxB che descrive la relazione è:

R={(1,2),(1,3),(1,5),(2,3),(2,5),(3,5)}.

Se A,B sono insiemi con un numero finito di elementi, una relazione R da A a B si può rappresentare graficamente rappresentando A,B con i diagrammi di Eulero-Venn, e unendo con una freccia un elemento aA con un elemento bB solo quando aRb.

Esempio: nell’esempio precedente si ottiene la seguente rappresentazione grafica

R

A B

Si può anche usare la rappresentazione matriciale: se A contiene n elementi e se B contiene m elementi, si costruisce una “tabella” (matrice) con n righe ed m colonne, in cui si fanno corrispondere ad ogni riga un elemento di a, ad ogni colonna un elemento di B, e si pone in ogni casella un valore 1 oppure 0 a secondo se l’elemento della riga della casella è o no associato nella relazione R all’elemento della colonna della casella.

Esempio: nell’esempio precedente si ottiene la seguente rappresentazione matriciale (in cui la matrice ha 4 righe e 4 colonne, con le righe che ordinatamente corrispondono agli elementi 1,2,3,6, le colonne agli elementi 2,3,5):

1 1 1 0 1 1 0 0 1 0 0 0

Funzioni

Dati gli insiemi A,B, una funzione da A a B è una relazione da A a B tale che ogni elemento di A è associato ad uno e un solo elemento di B.

L’insieme A è detto dominio della funzione, l’insieme B codominio.

Esempio: se A= {1,2,-2,3}, B={1,3,4,9}, e se la relazione da A a B è descritta dal predicato P(x,y)=”x ² =y” (quindi in pratica un elemento di A è associato ad un elemento di B se il quadrato del primo è uguale al secondo) allora si ottiene una funzione da A a B in quanto il sottoinsieme R del prodotto cartesiano AxB è R={(1,1),(2,4),(-2,4),(3,9)} e si nota che ogni elemento di A è associato ad uno e un solo elemento di B.

Spesso una funzione da A a B è indicata col simbolo f: A  B. Dato un elemento a del dominio A, l’unico elemento b del codominio B che è associato all’elemento a è detto corrispondente o immagine di a, ed è indicato con il simbolo f(a).

Nel caso di funzioni fra insiemi numerici, talvolta una funzione f: A  B è definita scrivendo un’espressione del tipo f(x)=….. dove i puntini contengono una formula algebrica nella variabile x, intendendo con ciò che, dato un elemento aA, il corrispondente b=f(a)B si ottiene sostituendo nella formula la variabile con il valore a, e calcolando il risultato. Naturalmente non tutte le formule producono funzioni da A a B.

Esempio: se A è l’insieme degli interi positivi, negativi o nulli e B quello degli interi positivi, la formula f(x)=x ² +1 definisce una funzione da A a B (perché ad ogni intero a, positivo, negativo o

1 2 3 6

2

3

5

nullo, è associato un unico intero positivo f(a)=a ² +1). Invece se A è l’insieme degli interi positivi e B quello dei razionali positivi, f(x)=1/(x-2) non definisce una funzione da A a B (perché l’intero positivo 2 non ha corrispondente f(2) in B).

Se la relazione è rappresentata graficamente (con le frecce), essa è una funzione quando da ogni elemento del dominio A parte una e una sola freccia verso il codominio B.

Se la relazione è rappresentata con una matrice, essa è una funzione quando ogni riga contiene un solo valore=1 (e tutti gli altri =0).

Funzioni iniettive

Dati gli insiemi A,B una funzione f: A  B è detta iniettiva quando elementi diversi del dominio A hanno sempre corrispondenti diversi nel codominio B.

Quindi f non sarà iniettiva quando esistono almeno 2 elementi diversi del dominio A che hanno lo stesso corrispondente nel codominio B.

Se f è rappresentata graficamente, la f è iniettiva quando le frecce che partono dagli elementi del dominio A arrivano su elementi tutti diversi nel codominio B (cioè non devono esistere 2 frecce che hanno la “punta” sullo stesso elemento di B).

Esempio:

Esempio di rappresentazione grafica di una funzione iniettiva

f

A B

Esempio di rappresentazione grafica di una Funzione non iniettiva

f

A B

Se f è rappresentata con una matrice, la f è iniettiva quando ogni colonna non contiene più di un valore =1 (quindi in ogni colonna non vi sono valori =1 oppure vi è esattamente un solo valore=1).

In modo formale, per verificare se una funzione è iniettiva si deve dimostrare la seguente implicazione:

x,yA, xy  f(x)f(y) 1

2 6

2 3 5 6 7

1 2 6

2

5

7

La dimostrazione si può effettuare “per assurdo”: si suppone vera l’ipotesi x,yA, xy, e falsa la tesi (quindi si suppone per assurdo f(x)=f(y)) e si cerca di pervenire ad una contraddizione logica.

Esempio: se A=B={interi >0}, e se f: A  B è la funzione definita da f(x)=3x+4, allora f è

iniettiva. Infatti se per assurdo supponiamo x,yA, xy, f(x)=f(y), si ha 3x+4=3y+4, da cui,

sottraendo 4 e dividendo per 3, si ottiene x=y (contraddizione).

Matematica Discreta

Lezione del giorno 9 ottobre 2008 Cardinalità di un insieme

Se A è un insieme finito, ossia che contiene un numero finito di elementi, si chiama cardinalità di A (e si indica con il simbolo A) il numero degli elementi distinti di A.

Per esempio se A={1,a,2,3,b} si ha A=5. Ovviamente =0.

Per il momento, se A è un insieme infinito (ossia non finito), ci limiteremo a dire che la sua cardinalità è infinita (in seguito approfondiremo l’argomento).

Teorema. Se A,B sono insiemi finiti, se A=n, B=m, e se f: A  B è una funzione iniettiva, allora nm.

Dimostrazione:

Elenchiamo esplicitamente gli n elementi distinti di A:

A={a 1 , a 2 , a 3 , …….., a n }

(dove a 1 indica l’elemento al primo posto nell’elenco, a 2 quello al secondo posto,….., a n quello al posto n, ultimo nell’elenco).

Poiché per ipotesi f è iniettiva, i corrispondenti:

f(a 1 ), f(a 2 ), f(a 3 ),……, f(a n )

sono elementi tutti diversi nel codominio B, quindi tali corrispondenti sono esattamente in numero di n. L’insieme B contiene dunque almeno n elementi, e allora la cardinalità di B non è inferiore ad n, cioè nm (tesi).

Una conseguenza immediata del teorema precedente è la seguente: se A,B sono insiemi finiti e se

A>B allora non è possibile costruire una funzione iniettiva f: A  B.

Funzioni surgettive

Dati gli insiemi A,B una funzione f: A  B è detta surgettiva quando ogni elemento y del codominio B é corrispondente di almeno un elemento x del dominio A.

Quindi f non sarà surgettiva quando esiste qualche elemento del codominio B che non è corrispondente di nessun elemento del dominio A.

Se f è rappresentata graficamente, la f è surgettiva quando ogni elemento di B è coperto da almeno una punta delle frecce che partono dagli elementi del dominio A.

Esempio:

Esempio di rappresentazione grafica di una funzione surgettiva

f

A B 1

2 3 6

2

5

7

Esempio di rappresentazione grafica di una funzione non surgettiva (l’elemento 5 di B f non è corrispondente di nessun elemento di A) A B

Se f è rappresentata con una matrice, la f è surgettiva quando ogni colonna contiene almeno un valore =1 (quindi non vi sono colonne con tutte le caselle contenenti valori =0).

Per verificare formalmente se una funzione f: A  B é surgettiva, si prende un generico elemento yB e si cerca almeno un elemento xA tale che si abbia f(x)=y: se un tale xA esiste sempre (comunque sia preso yB) allora f é surgettiva; se per alcuni valori di yB tale xA non esiste, allora la f non è surgetttiva.

Spesso, nelle funzioni matematiche, la f(x)=y diventa un’equazione di cui si devono cercare le soluzioni x nel dominio A: se almeno una di tali soluzioni esiste sempre in A (comunque sia preso yB) allora f é surgettiva.

Esempio: se A é l’insieme dei numeri interi >8, e se B é l’insieme dei numeri interi >0, la funzione f: A  B definita da f(x)=x-8 é surgettiva. Infatti, preso un generico intero yB, la ricerca di un valore intero xA tale che si abbia f(x)=y porta all’equazione x-8=y, che ha la soluzione x=y+8 (soluzione il cui valore é in A, per ogni yB, perché essendo y un intero positivo, certamente x=y+8 è un intero >8).

Invece, se A,B sono come sopra, la funzione f: A  B definita da f(x)=x-5 non é surgettiva. Infatti, preso un generico intero yB, la ricerca di un valore xA tale che si abbia f(x)=y porta all’equazione x-5=y, che ha la soluzione x=y+5 (soluzione il cui valore però non sempre é elemento di A: per esempio per y=2B si ha x=2+5=7A).

Teorema. Se A,B sono insiemi finiti, se A=n, B=m, e se f: A  B è una funzione surgettiva, allora nm.

Dimostrazione:

Elenchiamo esplicitamente gli m elementi distinti di B:

B={b 1 , b 2 , b 3 , …….., b m }

Poiché per ipotesi f è surgettiva, troviamo almeno un elemento c 1 A tale che f(c 1 )=b 1 ; per lo stesso motivo troviamo almeno un elemento c 2 A tale che f(c 2 )=b 2 e così procediamo fino a trovare almeno un elemento c m A tale che f(c m )=b m .

Gli elementi trovati c 1 , c 2 , …. ,c m sono tutti diversi fra loro (se 2 fra essi coincidessero, la f non sarebbe più una funzione) quindi il loro numero è esattamente m.

L’insieme A contiene dunque almeno questi m elementi, cioé la cardinalità di A è non inferiore ad m, ossia nm (tesi).

Una conseguenza immediata del teorema precedente è la seguente: se A,B sono insiemi finiti e se

A<B allora non è possibile costruire una funzione surgettiva f: A  B.

1 2 3 6

2

5

7

Matematica Discreta

Lezione del giorno 13 ottobre 2008 Funzioni biunivoche

Dati gli insiemi A,B una funzione f: A  B è detta biunivoca (o bigettiva) quando è sia iniettiva che surgettiva (quindi quando elementi diversi del dominio A hanno sempre corrispondenti diversi nel codominio B, e ogni elemento del codominio B é corrispondente di almeno un elemento del dominio A).

Teorema. Se A,B sono insiemi finiti, se A=n, B=m e se f: A  B è una funzione biunivoca, allora n=m.

Dimostrazione:

Essendo f iniettiva, per un teorema già dimostrato si ha nm; essendo f surgettiva, per un altro teorema già dimostrato si ha nm. Si conclude allora che n=m.

Una conseguenza del teorema precedente è la seguente: se A,B sono insiemi finiti di cardinalità differente, non esiste nessuna funzione biunivoca f: A  B.

Teorema. Siano A,B insiemi di cardinalità finita, e supponiamo anche che essi abbiano uguale cardinalitàA= n=B. Allora, data una funzione f: A  B, si ha:

f è iniettiva  f è surgettiva.

Dimostrazione:

Dimostriamo la prima implicazione , in cui l’ipotesi è che f sia iniettiva e la tesi è che f sia surgettiva.

Elenchiamo esplicitamente gli n elementi distinti di A:

A={a 1 , a 2 , a 3 , …….., a n }

Poiché per ipotesi f è iniettiva, i corrispondenti:

f(a 1 ), f(a 2 ), f(a 3 ),……, f(a n )

sono elementi tutti diversi nel codominio B, quindi tali corrispondenti sono esattamente in numero di n. Ma l’insieme B contiene esattamente n elementi, e dunque tali corrispondenti esauriscono tutti gli n elementi di B. Questo vuol dire che ogni elemento di B è corrispondente di qualche elemento di A, cioè f è surgettiva (tesi).

Dimostriamo la seconda implicazione , in cui l’ipotesi è che f sia surgettiva e la tesi è che f sia iniettiva.

Ragioniamo per assurdo: supponiamo vera l’ipotesi e falsa la tesi, cioé supponiamo f surgettiva ma f non iniettiva.

Elenchiamo esplicitamente gli n elementi distinti di A:

A={a 1 , a 2 , a 3 , …….., a n }

Poiché per assurdo f non è iniettiva, i corrispondenti:

f(a 1 ), f(a 2 ), f(a 3 ),……, f(a n )

non sono tutti distinti, quindi sono in numero minore di n. Ma l’insieme B contiene esattamente n

elementi, dunque tali corrispondenti non esauriscono tutti gli n elementi di B. Questo vuol dire che

esiste qualche elemento di B che non è corrispondente di nessun elemento di A, cioè f non é

surgettiva (contraddizione).

Funzione inversa di una funzione biunivoca.

Sia data una funzione biunivoca f: A  B. Comunque preso un elemento bB, essendo f surgettiva esiste almeno un elemento aA tale che si abbia f(a)=b. Ma essendo f iniettiva è unico tale elemento aA che abbia la proprietà f(a)=b.

Se allora associamo all’elemento bB questo unico elemento aA che soddisfa la proprietà f(a)=b, otteniamo una nuova funzione da B ad A, detta funzione inversa di f .

Tale funzione inversa è indicata con il simbolo f ^-1 : B  A.

Se la funzione f è rappresentata graficamente, la f ^-1 è rappresentata graficamente semplicemente invertendo il verso delle frecce.

Esempio:

funzione biunivoca f

A f B

funzione inversa f ^-1

B f ^-1 A

Formalmente, per costruire la funzione inversa di una funzione biunivoca, si deve seguire il procedimento usato per dimostrarne la surgettività; in tale procedimento, dato un elemento generico del codominio, si cerca un elemento del dominio la cui immagine è l’elemento dato: tale elemento del dominio è per costruzione proprio l’immagine dell’elemento di partenza mediante la funzione inversa.

Esempio: se A è l’insieme dei numeri razionali positivi, negativi o nulli e se f: A  A è la funzione definita da f(x)=(x+7)/9, è facile verificare che f è iniettiva. Dimostriamo che f è surgettiva: preso un generico elemento yA, cerchiamo l’esistenza di un elemento xA tale che f(x)=(x+7)/9=y; si ottiene la soluzione x=9y-7A. Ciò dimostra che f è surgettiva (quindi biunivoca), ma permette anche di costruire la funzione inversa f ^–1 : A  A, definita appunto da f ^–1 (y)=9y-7.

Teorema. Sia f: A  B una funzione biunivoca. Allora la funzione inversa f ^–1 : B  A è anch’essa biunivoca.

Dimostrazione:

Dimostriamo che f ^–1 è iniettiva: se per assurdo esistessero b,cB, bc tali che f ^–1 (b)= f ^–1 (c), denotato con a tale elemento f ^–1 (b)=f ^–1 (c), si avrebbe, per definizione di funzione inversa f(a)=b, f(a)=c, e l’elemento aA avrebbe 2 immagini diverse mediante f, contraddicendo l’ipotesi che f è una funzione. Graficamente si avrebbe:

a b c

2 5 7

2 5 7

a

b

c

f  b a=f ^–1 (b)=f ^–1 (c) 

f  c

Dimostriamo che f ^–1 è surgettiva: dato un elemento generico yA, dobbiamo trovare un elemento xB tale che si abbia f ^–1 (x)=y: ma a tale scopo basta scegliere tale x coincidente con l’immagine f(y) dell’elemento y mediante f. Graficamente:

y f x  

y f ^-1 x  

Funzione identica

Dato un insieme A, si definisce la cosiddetta funzione identica di A: essa è la funzione che ha dominio e codominio coincidenti entrambi con A, ed associa ogni elemento di A con sé stesso.

Tale funzione si indica con il simbolo:

i A : A  A

ed è quindi definita ponendo i A (x)=x per ogni xA. Ovviamente la funzione identica è biunivoca.

Composizione di funzioni

Siano A,B,C, 3 insiemi e siano f: A  B, g: B  C delle funzioni (notare che il codominio di f coincide con il dominio di g). Se prendiamo un elemento generico xA, la f associa a tale elemento x un unico elemento y=f(x)B; a sua volta la g associa a tale elemento y un unico elemento z=g(y)C. In tal modo, associando ad xA l’unico elemento zC si ottiene una nuova funzione con dominio A e codominio C, detta composizione di f e g (o funzione composta di f e g), e indicata con il simbolo gf: A  C. In pratica l’azione di gf è ottenuta applicando f e poi g:

(gf)(x)=z=g(y)=g(f(x))

(notare che la funzione f, che agisce per prima, è scritta per seconda nel simbolo gf).

Esempi:

1) Siano A={1,2,3,4}, B={a,b,c}, C={5,6,8} e siano f: A  B, g: B  C le funzioni descritte graficamente da:

f g

Allora la composizione gf: A  C è descritta graficamente da:

1 2 3 4

a b c

5 6 8

1

2

3

4

gf

2) Se A è l’insieme dei numeri interi positivi, B l’insieme dei numeri razionali positivi, C l’insieme dei numeri reali positivi, date le 2 funzioni f: A  B, g: B  C definite da f(x)=x/3, g(x)= x ²  1 , la composizione gf: A  C è definita da:

(gf)(x)=g(f(x))=g(x/3)= ^{(x/3 ) 2}  ¹ = ^{(x 2  9 ) / 9}

Teorema. La composizione di 2 funzioni iniettive è una funzione iniettiva. La composizione di 2 funzioni surgettive è una funzione surgettiva. La composizione di 2 funzioni biunivoche è una funzione biunivoca.

Dimostrazione:

Siano f: A  B, g: B  C due funzioni.

Supponiamo dapprima che f, g siano iniettive e dimostriamo che gf è iniettiva: se a,bA, ab, si ha f(a)f(b) (per l’iniettività di f), e allora g(f(a))g(f(b)) ((per l’iniettività di g) dunque si conclude che (gf)(a) (gf)(b), ossia gf è iniettiva.

Supponiamo ora che f, g siano surgettive e dimostriamo che gf è surgettiva: dato cC, cerchiamo una elemento aA tale che (gf)(a)=c; ma, per la surgettività di g, esiste bB tale che g(b)=c;

inoltre, per la surgettività di f, esiste aA tale che f(a)=b, da cui in totale (gf)(a)=c.

La terza affermazione segue ovviamente dalle prime due.

Calcoliamo la composizione di funzioni in alcuni casi particolari.

Siano A,B insiemi, sia f: A  B una funzione e consideriamo la funzione identica di B:

i B : B  B

Possiamo allora considerare la composizione i B f : A  B.

Per ogni elemento xA si ha (i B f)(x)= i B (f(x))=f(x), e si conclude che le funzioni i B f ed f sono uguali: i B f = f

Analogamente siano A,B insiemi, sia f: A  B una funzione e consideriamo la funzione identica di A:

i A : A  A

Possiamo allora considerare la composizione fi A : A  B.

Per ogni elemento xA si ha (fi A )(x)= f(i A (x))=f(x), e si conclude che le funzioni fi A ed f sono uguali: fi A = f

Se A,B sono insiemi e se f: A  B una funzione biunivoca, possiamo considerare la funzione inversa f ^-1 : B  A, e le due composizioni:

f ^-1 f : A  A ff ^-1 : B  B

Per ogni elemento xA si ha (f ^-1 f)(x)= f ^-1 (f(x))=x, e si conclude che la funzione f ^-1 f coincide con la funzione identica di A:

f ^-1 f = i A

Con ragionamento analogo di ha che la funzione ff ^-1 coincide con la funzione identica di B:

5

6

8

ff ^-1 = i B .

Matematica Discreta

Lezione del giorno 15 ottobre 2008

Useremo i seguenti simboli per indicare gli insiemi numerici più comuni: N è l’insieme dei numeri interi >0, detti numeri naturali; Z è l’insieme dei numeri interi relativi (cioè positivi, negativi e lo zero); Q è l’insieme dei numeri razionali relativi; R è l’insieme dei numeri reali relativi.

Un asterisco sul simbolo indicherà che dall’insieme è escluso lo 0 (per es. Q* è l’insieme dei numeri razionali relativi non nulli); un segno + sul simbolo indicherà che dell’insieme sono considerati solo i positivi (per es. Q

è l’insieme dei numeri razionali positivi)

Cardinalità degli insiemi infiniti: insiemi equipotenti

Per un insieme finito A (cioè che contiene un numero finito di elementi), abbiamo definito la cardinalità A di A coincidente appunto con il numero di elementi di A.

Se volessimo definire il concetto di cardinalità anche per un insieme infinito A, una soluzione (poco soddisfacente dal punto di vista matematico) potrebbe essere quella di dire semplicemente che la cardinalità di un insieme infinito è uguale a infinito: ciò porterebbe a non distinguere fra i vari “tipi” di cardinalità infinita.

Cantor propose invece di costruire una teoria per gli insiemi infiniti che fosse coerente con i risultati validi nel caso degli insiemi finiti. Ricordiamo un teorema già dimostrato: se A,B sono insiemi finiti e se esiste una funzione biunivoca f: A  B, allora A e B hanno la stessa cardinalità.

L’esistenza o la non esistenza di una funzione biunivoca f: A  B, con A,B insiemi infiniti, potrebbe allora essere presa come misura dell’eguaglianza o differenza della cardinalità.

Se A,B sono insiemi infiniti, diremo che A è equipotente a B (o anche che A,B hanno la stessa cardinalità) se esiste una funzione biunivoca f: A  B (scriveremo in tal caso AB).

Notiamo che:

- ogni insieme A è equipotente a sé stesso, in quanto la funzione identica i A : A  A è biunivoca - se A,B sono insiemi e se A è equipotente a B allora anche B è equipotente a A, in quanto se esiste una funzione biunivoca f: A  B, sappiamo che anche la funzione inversa f ^-1 : A  B è biunivoca

- se A,B,C sono insiemi e se A è equipotente a B e B è equipotente a C, allora A è equipotente a C, in quanto se esistono due funzioni biunivoche f: A  B, g: B  C, sappiamo che anche la loro composizione gf : A  C è biunivoca

Il modello più semplice di insieme infinito è l’insieme N dei numeri naturali: diremo che un insieme infinito A ha la cardinalità del numerabile se A è equipotente ad N, cioè se esiste una funzione biunivoca f: N  A.

Cerchiamo esempi di insiemi numerici infiniti che abbiano la cardinalità del numerabile.

L’insieme Z dei numeri interi relativi ha la cardinalità del numerabile.

Esiste infatti una funzione biunivoca f: N  Z, che si può descrivere graficamente (anche se in modo incompleto) nel modo seguente:

1 2 3 4 5 6 . . .

0

1

-1

2

-2

3

-3

.

.

.

f

N Z

e che formalmente è definita ponendo f(x)=x/2 se x pari, ed f(x)=(1-x)/2 se x è dispari.

Dimostriamo che f è biunivoca.

Iniettività di f: per assurdo siano x,yN, con xy, e tali che f(x)=f(y). Distinguiamo i 3 casi possibili e in ognuno troviamo una contraddizione:

- x,y entrambi pari: si ha f(x)=x/2=f(y)=y/2, da cui x=y (contraddizione)

- x,y entrambi dispari: si ha f(x)=(1-x)/2=f(y)=(1-y)/2, da cui x=y (contraddizione)

- x,y uno pari (per es. x) ed uno dispari (per es. y): si ha f(x)=x/2=f(y)=(1-y)/2, da cui x=1-y (contraddizione perché x>0, 1-y≤0).

Surgettività di f: per ogni yZ cerchiamo un xN tale che f(x)=y; se y>0, l’equazione f(x)=x/2=y ha la soluzione x=2yN; se invece y≤0, l’equazione f(x)=(1-x)/2=y ha la soluzione x=1-2yN (perché 2y≤0, dunque x=1-2y>0).

L’insieme Q

dei numeri razionali positivi ha la cardinalità del numerabile.

Si può infatti, come vedremo, costruire una funzione biunivoca f: N  Q

.

Disponiamo tutti i numeri razionali positivi, sotto forma di frazioni, in una tabella con infinite righe e colonne, con la regola che nella casella all’incrocio fra la riga numero n e la colonna numero m poniamo la frazione con numeratore n e denominatore m; costruendo per semplicità per esempio solo le prime 5 righe e 5 colonne si ha:

1/1 1/2 1/3 1/4 1/5 2/1 2/2 2/3 2/4 2/5 3/1 3/2 3/3 3/4 3/5 4/1 4/2 4/3 4/4 4/5 5/1 5/2 5/3 5/4 5/5

(Notiamo che nelle infinite caselle della tabella troviamo tutti i numeri razionali positivi, nessuno escluso, anche se alcune caselle contengono lo stesso valore)

Poi percorriamo in successione le caselle con il seguente procedimento a “zig-zag”:

Definiamo la funzione f: N  Q

associando al numero naturale 1 il contenuto della prima casella

del percorso (quindi f(1)=1/1) , al 2 quello della seconda casella (quindi f(2)=1/2), al 3 quello della

terza casella (quindi f(3)=2/1) e così via, con la regola che se tocchiamo una casella il cui contenuto

è già stato incontrato in precedenza, la saltiamo (quindi f(4)=3/1, ma f(5)=1/3 e non f(5)=2/2,

perché 2/2=1/1=f(1)). Tale regola ci garantisce che f è iniettiva (perché numeri naturali diversi

saranno associati a razionali diversi); inoltre il fatto che la tabella contiene tutti i razionali positivi garantisce che f è surgettiva (ogni razionale positivo si trova in qualche casella della tabella, dunque è il corrispondente di qualche numero naturale).

L’insieme Q dei numeri razionali relativi ha la cardinalità del numerabile.

Si dimostra con procedimenti simili.

Non è facile, invece, trovare un insieme numerico infinito che non abbia la cardinalità del numerabile. Fu lo stesso Cantor a dimostrare che:

L’insieme R

dei numeri reali positivi non ha la cardinalità del numerabile.

Per assurdo supponiamo che esista una funzione biunivoca f: N  R ⁺ .

Rappresentiamo ogni reale positivo in forma decimale, con una parte intera e delle cifre (scelte fra 0 e 9) dopo la virgola.

Per ogni numero naturale nN usiamo la seguente notazione per rappresentare l’immagine f(n)R

: f(n) = a n , b n1 b n2 b n3 b n4 . . .

(dove a n indica la parte intera, e b nj indica la cifra dopo la virgola che occupa il posto j).

Seguendo tale notazione si ha:

f(1) = a 1 , b 11 b 12 b 13 b 14 . . . f(2) = a 2 , b 21 b 22 b 23 b 24 . . . f(3) = a 3 , b 31 b 32 b 33 b 34 . . . f(4) = a 4 , b 41 b 42 b 43 b 44 . . . . . . .

. . . . . . . .

Per la surgettività di f, l’elenco dei numeri dopo i segni di eguaglianza dovrebbe esaurire tutti i numeri reali positivi.

Costruiamo allora (con il cosiddetto “procedimento diagonale di Cantor”) un numero reale x con parte intera a piacere e con le cifre dopo la virgola scelte con la seguente regola: la cifra al posto 1 è diversa dalla cifra b 11 (cifra di posto 1 di f(1)); la cifra al posto 2 è diversa dalla cifra b 22 (cifra di posto 2 di f(2)); etc…, quindi in generale la cifra di posto j è diversa dalla cifra b jj (cifra di posto j di f(j)).

Tale numero x dovrebbe essere uguale all’immagine f(n) di qualche numero naturale n: ma ciò è una contraddizione, perché f(n) ha almeno una cifra dopo la virgola diversa dalla cifra dello stesso posto del numero x (per costruzione esattamente la cifra b nn di posto n).

Definiremo cardinalità del continuo la cardinalità dell’insieme R dei numeri reali (e quindi di tutti gli insiemi equipotenti ad R).

Matematica Discreta

Lezione del giorno 17 novembre 2008

Principio delle scelte multiple.

Supponiamo di volere contare il numero di elementi di un insieme finito X e di sapere che ogni elemento di X dipende dai valori di 2 variabili x,y, di modo che contare il numero di elementi di X equivalga a contare le possibili coppie di valori x,y: potremmo allora, per ogni fissato valore di x, calcolare il numero dei corrispondenti valori di y e poi sommare.

Esempio: supponiamo che X sia l’insieme dei numeri naturali di 2 cifre (in base 10) con cifre scelte fra i valori 1,2,3,4,5,6 e tali che la cifra delle decine sia minore di quella delle unità. Per contare il numero di elementi di X, possiamo notare che ogni elemento dipende dai valori di 2 variabili: la cifra x delle decine e la cifra y delle unità.

Fissato il valore x=1 otteniamo in corrispondenza 5 valori di y (2,3,4,5,6), analogamente fissato il valore x=2 otteniamo in corrispondenza 4 valori di y, fissato il valore x=3 otteniamo in corrispondenza 3 valori di y, fissato il valore x=4 otteniamo in corrispondenza 2 valori di y, fissato il valore x=5 otteniamo in corrispondenza 1 valore di y, fissato il valore x=6 otteniamo in corrispondenza 0 valori di y. In totale il numero di coppie di valori x,y (e quindi il numero di elementi di X) è la somma 5+4+3+2+1+0=15.

Sempre nell’ambito del problema di contare il numero di elementi di un insieme finito X in cui ogni elemento dipende dai valori di 2 variabili x,y, facciamo un ulteriore ipotesi (che non è verificata nell’esempio precedente): supponiamo che la variabile x assuma un numero n di valori diversi e che, fissato un valore di x, il numero dei corrispondenti valori di y sia costantemente uguale ad m (indipendentemente dal valore fissato per x).

In tale caso il numero delle coppie di valori di x,y (e quindi il numero di elementi di X) si otterrà sommando m+m+….+m (con n addendi) quindi sarà uguale al prodotto nm (principio delle scelte multiple per 2 variabili).

Esempio: supponiamo che X sia l’insieme dei numeri naturali di 2 cifre (in base 10) con cifre scelte fra i valori 1,2,3,4,5,6 e tali che la cifra delle decine sia diversa da quella delle unità. Come nell’esempio precedente, possiamo notare che ogni elemento dipende dai valori di 2 variabili: la cifra x delle decine e la cifra y delle unità.

La variabile x può assumere 6 valori distinti 1,2,3,4,5,6. Fissato un valore di x, il numero dei valori corrispondenti di y è costantemente uguale a 5 (sono tutti i valori 1,2,3,4,5,6 tranne quello scelto per x).

Siamo nelle ipotesi del principio delle scelte multiple e possiamo concludere che il numero di elementi di X è il prodotto 65=30

Con ragionamenti simili ai precedenti si ottiene il principio delle scelte multiple per più variabili:

supponiamo che ogni elemento dell’insieme finito X dipenda dai valori di n variabili x 1 ,x 2 ,….,x k ; supponiamo inoltre che:

- la variabile x 1 assuma un numero n 1 di valori diversi

- fissato un valore di x 1 , il numero dei corrispondenti valori di x 2 sia costantemente uguale ad n 2

(indipendentemente dal valore fissato per x 1 )

- fissato un valore di x 1 e un valore di x 2 , il numero dei corrispondenti valori di x 3 sia costantemente uguale ad n 3 (indipendentemente dai valori fissati per x 1 e di x 2 )

……etc

- fissato un valore per ognuna delle variabili di x 1 ,x 2 ,…,x k-1 , il numero dei corrispondenti valori di x k

sia costantemente uguale ad n k (indipendentemente dai valori fissati per x 1 ,x 2 ,…,x k-1 ) allora il numero degli elementi di X è uguale al prodotto n 1 n 2 ……n k .

Numero delle funzioni fra insiemi finiti

Siano A,B due insiemi finiti rispettivamente con A=n, B=m, e contiamo il numero di tutte le possibili funzioni f: A  B.

Se {a 1 , a 2 , ….., a n } sono gli elementi di A, ognuna di tali funzioni dipende dalle n variabili seguenti:

x 1 =valore del corrispondente in B dell’elemento a 1 ; x 2 =valore del corrispondente in B dell’elemento a 2 ;

…..

x n =valore del corrispondente in B dell’elemento a n .

La variabile x 1 ha m valori possibili (gli m elementi di B); fissato un valore di x 1 , la variabile x 2 ha m valori possibili (di nuovo gli m elementi di B); fissato un valore di x 1 e un valore di x 2 , la variabile x 3 ha m valori possibili (di nuovo gli m elementi di B); etc ..…. ; infine fissato un valore di x 1 , uno di x 2 ,…, uno di x n-1 , la variabile x n ha m valori possibili (sempre gli m elementi di B). Per il principio delle scelte multiple, il numero delle possibili funzioni f: A  B è il prodotto mm…..m (con n fattori), quindi è la potenza m ⁿ .

La formula che dà il numero di tutte le funzioni f: A  B è allora B ^A .

Esempio: Se A={a,b}, B={1,2,3}, il numero delle possibili funzioni f: A  B è 3 ² =9, mentre il numero delle possibili funzioni f: B  A è 2 ³ =8 .

Numero delle funzioni iniettive fra insiemi finiti

Siano A,B due insiemi finiti rispettivamente con A=n, B=m, e contiamo il numero di tutte le possibili funzioni iniettive f: A  B.

Sappiamo già che nel caso n>m non esiste nessuna di tali funzioni iniettive.

Quindi supponiamo nm.

Se {a 1 , a 2 , ….., a n } sono gli elementi di A, ognuna di tali funzioni iniettive dipende dalle n variabili seguenti:

x 1 =valore del corrispondente in B dell’elemento a 1 ; x 2 =valore del corrispondente in B dell’elemento a 2 ;

…..

x n =valore del corrispondente (in B) dell’elemento a n .

La variabile x 1 ha m valori possibili (gli m elementi di B); fissato un valore di x 1 , la variabile x 2 ha m-1 valori possibili (gli m elementi di B escluso quello scelto come corrispondente di a 1 ); fissato un valore di x 1 e uno di x 2 , la variabile x 3 ha m-2 valori possibili (gli m elementi di B meno quelli scelti come corrispondenti di a 1 ,a 2 ); etc...…. ; fissato un valore di x 1 , uno di x 2 ,…, uno di x n-1 , la variabile x n ha m-(n-1)=m-n+1 valori possibili (gli m elementi di B meno quelli scelti come corrispondenti di a 1 ,a 2 ,….,a n-1 ).

Per il principio delle scelte multiple, il numero delle possibili funzioni iniettive f: A  B è il prodotto m(m-1)(m-2)…..(m-n+1), quindi è il prodotto in ordine decrescente dei numeri naturali da m ad m-n+1 (supponendo sempre nm) .

Esempio: Se A={a,b,c,d}, B={1,2,3,4,5,6}, A=4, B=6 il numero delle possibili funzioni iniettive f: A  B è 6543=360.

Numero delle funzioni surgettive fra insiemi finiti

Il problema di contare il numero delle funzioni surgettive fra insiemi finiti sarà affrontato in seguito, nell’ambito della teoria dei numeri di Stirling.

Numero delle funzioni biunivoche fra insiemi finiti

Siano A,B due insiemi finiti rispettivamente con A=n, B=m, e contiamo il numero di tutte le possibili funzioni biunivoche f: A  B.

Sappiamo già che nel caso nm non esiste nessuna di tali funzioni.

Quindi supponiamo n=m.

Per un teorema già dimostrato, sappiamo che, sotto l’ipotesiA=B, una funzione iniettiva è sempre anche surgettiva, quindi biunivoca: basta allora contare le funzioni iniettive da A a B.

Applicando la formula precedente (con n=m) si ottiene che il numero delle possibili funzioni biunivoche f: A  B è il prodotto n(n-1)(n-2)…..1, ossia il prodotto di tutti i numeri naturali consecutivi da 1 ad n, detto fattoriale di n e indicato con il simbolo n! .

Esempio: Se A={a,b,c,d,e}, B={1,2,3,4,5}, il numero delle possibili funzioni biunivoche f: A  B è 5!=12345=120.

Matematica Discreta

Lezione del giorno 19 novembre 2008

Permutazioni