Fondamenti dell'informatica

A A B B

La caratterizzazione fornito dal teorema può essere resa ancora più forte utilizzando

la definizione di relazione inversa:

Fondamenti di informatica

Data R : A ↔ B, una relazione S : B ↔ A è l’inversa di R se Id = R;S e Id = S;R.

A B

R : A ↔ B è invertibile se esiste almeno una relazione inversa.

Questo comporta che per tutti gli insiemi A, B e per tutte le relazioni R: A ↔ B vale

che: R è una biiezione se e solo se R è invertibile.

Quindi per dimostrare che una relazione R è biiettiva basta fornire una S e mostrare che

Id = R;S e Id = S;R

A B

Attenzione: -1 op

È possibile scrivere R al posto di R quando R è una biiezione, per

op

enfatizzare che R è l’inversa di R.

Insiemi in biiezione

Due insiemi A e B sono in biiezione (o in corrispondenza uno a uno) se esiste una

biiezione i : A → B. In questo caso scriviamo A B.

≅

Esempio:

2 = {0,1} bool = {t, f} 2 bool

≅

P(A) Fun(A,2)

≅

Fun(A X B,C) Fun(A, Fun(B, C))

≅

(A X B) X C A X (B X C)

≅

1 = {0} A X 1 A

≅

AXB BXA

≅

Dimostrazione 1 = {0} A X 1 A

≅

i : {(a,0)|a A and 0 1} → A

∊ ∊

Pensiamo a due funzioni:

● i((a,0)) = a

● j(a) = (a,0) (l’inverso della precedente)

C’è quindi da dimostrare che : i;j = Id e che j;i = Id

A x 1 A

Prendiamo un elemento di A, come per esempio a, applichiamo j e ci da (a,0);

se applichiamo la i otteniamo l’elemento di partenza, ovvero a.

Per avere un ulteriore controllo prendo un elemento di AX1, come (a,0), applico

i e ottengo solo a, poi applico j e torno alla coppia di partenza.

Dimostrazione (A X B) X C A X (B X C)

≅

Definiamo le due relazioni (funzioni):

● i : (A X B) X C → A X (B X C)

○ ((a,b), c) (a, (b,c))

↦

● j : A X (B X C) → (A X B) X C

○ (a, (b,c)) ((a,b), c)

↦

Fondamenti di informatica

Ovviamente:

● ((a,b), c) (A X B) X C

∊

● (a, (b,c)) A X (B X C)

∊

Dobbiamo dimostrare (1) id = i;J e (2) id = j;i

(A X B) X C A X (B X C)

1. i;j ((a,b),c) = j(i((a,b),c)) = j(a,(b,c)) = ((a,b),c)

2. j;i (a,(b,c) = … identico

Dimostrazione P(A) Fun(A,2)

≅

Definiamo due funzioni i : P(A) → Fun(A,2) e j : Fun(A,2) → P(A) e mostriamo

che id = i;j e id = J;I

P(A) Fun(A,2)

1. La funzione i deve mappare ogni sottoinsieme B A su una funzione

⊆

da A a 2 = 0,1

Definiamo i(B) = : A → 2 (la funzione caratteristica di B) come

B

a 1 se a B, 0 se a B

↦ ∈ ∉

Quindi se A = {x, y, z}, B = {x, y} allora : A → 2 = x 1, y 1, z 0

↦ ↦ ↦

B

2. La funzione j Fun(A, 2) → P(A) deve mappare ogni funzione da A a 2

∶

= {0,1} su un sottoinsieme B A.

⊆

Definiamo j(f) = Sub(f) A come Sub(f) = { a A | f(a) = 1}

⊆ ∈

Quindi se A = {x, y, z}, f : A → 2 = x 1 y 0 z 1;

↦ ↦ ↦

perciò Sub() = {x, z}

Mostriamo che (1) id = i;j e (2) id = j;i

P(A) Fun(A,2)

1. Per ogni B P(A) vale i;j(B) = id (B) = B, cioè Sub( ) = B

∊ P(A) B

a Sub( ) (a) = 1 (def d sub) a B (def di )

∊ ⇔ ⇔ ∊

B B B

2. Per ogni f : A → 2 vale j;i(f) = id (f) = f, cioè = f

Fun(A,2) Sub(f)

(a) = 1 se a Sub(f) oppure 0 se a Sub(F)

∊ ∉

Sub(f)

= 1 se f(a) = 1 oppure 0 se f(a) = 0

= f(a)

Attenzione:

Fun(A,B) è l’insieme di tutte le funzioni da A a B

Proprietà di ≅

Per tutti gli insiemi A,B,C vale che:

● Riflessiva → A A → Id è un testimone di questa biezione

≅ A -1

● Simmetrica → A B B A → i e i sono testimoni di questa biezione

≅ ⇒ ≅

● Transitiva → A B B C A C → i, j e i;j sono i testimoni di questa biezione

≅ ∧ ≅ ⇒ ≅

Fondamenti di informatica

Funzione caratteristica di un insieme

Per ogni insieme B A, definiamo la sua funzione caratteristica : A → Bool come:

⊆ B

(a) = {t se a B, f se a B}

∊ ∉

B Attenzione:

L’insieme bool è stato preso solo per rendere più chiara la definizione; sulla

destra ci può essere qualsiasi numero.

Equivalentemente, possiamo definire questa funzione come una relazione, cioè un

sottoinsieme di A X Bool.

= {(a, t) A X Bool | a B} U {(a, f) A X Bool | a B}

∊ ∊ ∊ ∉

B Esempio:

A = {x, y, z}, B = {x, y} allora : A → 2 = x 1, y 1, z 0

↦ ↦ ↦

B

Sottoinsieme di una funzione

Mappare ogni funzione da A a 2 = {0,1} su un sottoinsieme B A significa definire

⊆

Sub(f) A come Sub(f) = {a A | f(a) = 1} A

⊆ ∊ ⊆

Esempio:

A = {x, y, z}, f : A → 2 = x 1 y 0 z 1;

↦ ↦ ↦

perciò Sub(f) = {x, z}

Relazioni con SQL

Esempio:

Queries come operazioni su relazioni

Tabelle di dati Relazioni

➔

Fondamenti di informatica

Studenti = {Lucia, Mario, Franca, Luisa, Gino, Marco, Marco, Gaia, Carlo}

Corsi = {PA, LAB, FDI, ANA}

Professori = {Paperino, Pippo, Pluto, Paperone}

Segue Studenti X Corsi

⊆

Insegna Professori X Corsi

⊆

Esempio:

Queries come composizione di relazioni

Fondamenti di informatica

Quali professori ha ciascun studente?

op

Segue;Insegna = {(s,p) | s Studenti, p Professori (∃ c corsi . (s,c)

∊ ∊ ∧ ∊ ∊

op

Segue (c,p) Insegna ).

∧ ∊

Quali studenti ha ciascun professore?

op

Insegna; Segue Professore X Studenti

⊆

Triple, quadruple, n-uple

Anche se (A X B) X C ≠ A X (B X C), abbiamo (A X B) X C A X (B X C) (associatività a

≅

meno di biiezione); perciò possiamo ignorare le parentesi e definire l'insieme di triple:

A X B X C = {(a,b,c) | a A, b B, c C}

∊ ∊ ∊

Analogamente l’insieme delle quadruple:

A X B X C X D = {(a,b,c,d) |a A, b B, c C, d D}

∊ ∊ ∊ ∊

e così via per ogni n N

∊

Attenzione:

Per n=0 c’è solo la tupla vuota.

N-upla - Sequenze di lunghezza fissata

Sia A un insieme e n N. Una sequenza su A di lunghezza n è una n-upla (a ,a ,…,a )

∊ 0 1 n-1

dove a A per ogni indice i (0,1,…n-1); e quindi definiamo:

∊ ∊

i

n

A = { (a , a , … , a ) (∀ {0,1, … , n − 1} . a A) }

∣ ∈ ∈

0 1 n−1 i

Fondamenti di informatica

Esempio:

A = {a,b}

0

A = {()}

1

A = {(a),(b)}

2

A = {(a,a), (a,b), (b,a), (b,b)}

n

Vettori in R sono sequenze di R di lunghezza n.

n

Un elemento di A può essere visto come un array.

Attenzione:

0 1 2 3 n

A 1, A A, A A X A, A A X (A X A), A A X (A X (...))

≅ ≅ ≅ ≅ ≅

A* - Sequenze di lunghezza arbitraria i

Consideriamo la famiglia di insiemi su N {A | i N}; definiamo:

∊

i 0 1 2 3

A* = U A =A U A U A U A U …

i∊N

Quindi A* contiene come elementi sequenze di lunghezza arbitraria ma finita di

elementi dell’insieme A.

Esempio:

AN è l’insieme dei caratteri alfanumerici

AN* è l’insieme di tutte le stringhe composte da caratteri alfanumerici: si, 123,

anna, pippo, Pluto, Pluto3 AN∗

∈

1 = {0}

1* N

≅

Induzione matematica

Insiemi infiniti e definizioni per induzione

Perché è necessaria l’induzione? Per definire precisamente e correttamente gli insiemi

infiniti. Pensiamo per esempio ad N = {0,1,2,3,…} ovvero l’insieme dei naturali; i “…” sono

rivolti ad un lettore umano, infatti questa definizione non ci soddisfa a pieno. Cosa

rappresentano i punti sospensivi? In questo caso i numeri > 3. L’ordine degli elementi conta,

perciò l’insieme dei naturali potrebbe essere anche scritto N = {2,0,1,…} e già questo non è

più chiaro ad un umano; inoltre, con una definizione del genere, come possiamo indicare

che la radice di 10 non appartiene ma la radice di 9 si? Come facciamo a sapere che uno

non volesse definire un qualcosa diverso da N che può essere 0,1,2,3,4,5? è totalmente

ambigua.

Fondamenti di informatica

Per risolvere tutti i problemi utilizziamo l'induzione, tramite il quale possiamo definire in

modo formalmente ineccepibile insiemi infiniti, fornendo elementi base e regole per

costruirne altri.

Tre usi complementari dell’induzione

L’induzione può presentare 3 usi complementari:

● Definizione induttiva di insiemi

● Definizione induttiva di funzioni che presentano come insieme di partenza un

insieme definito induttivamente

● Dimostrazione di proprietà per induzione.

Per capire andiamo a vedere la definizione induttiva dei numeri naturali, i numeri triangolari

e la dimostrazione della formula di gauss.

Definizione induttiva di un insieme A

La definizione induttiva di un insieme A si basa su 3 clausole:

1. Clausola base, ovvero fornisce certi elementi che appartengono ad A

2. Clausola induttiva, ovvero fornisce come usare degli elementi di A per costruirne

altri

3. Clausola terminale, ovvero dimostra che l'insieme A non contiene altro

Esempio:

N = {0,1,2,3}

Definizione induttiva:

N è il più piccolo insieme di numeri che soddisfa (questa è la clausola

terminale):

1. Clausola base: 0 N

∈

2. Clausola induttiva: se n N allora n+1 N

∈ ∈

In questa definizione viene utilizzato lo 0, il + e 1, quindi si assume che si

conosca la somma di numeri e almeno i primi 2 numeri, come per esempio

conoscere i numeri Reali.

Fondamenti di informatica

Come si usa una definizione induttiva?

radice di 9 N?

∈

1. Sicuramente sappiamo che radice di 9 = 3, perché conosciamo le

operazioni ecc. 3 N?

∈

1. 3 = 0 ? No, non è nei naturali per il caso base, quindi deve esserci per

la clausola induttiva; 3= n+1 = 2 + 1 se e solo se 2 N

∈

2. 2 = 0? No, quindi 2 = n+1 = 1 +1 a N se e solo se 1 N

∈ ∈

3. …

4. Alla fine si conclude che appartiene

2,7 N?

∈

1. 2,7 = 0? no, non è nei naturali quindi 2,7 N se e solo se 1,7 N

∈ ∈

2. 1,7 = 0? No, 1,7 N se e solo se 0,7 N

∈ ∈

3. 0,7 = 0? No …

4. Alla fine si conclude che non appartiene

+

L’insieme N dei numeri naturali positivi:

+

● Clausola base: 1 N

∈ + +

● Clausola induttiva: