C. Gaibisso
Programmazione di calcolatori
Lezione III
Cenni di teoria ingenua degli
insiemi
Programmazione di calcolatori: Cenni di teoria ingenua degli insiemi
1
C. Gaibisso
Gli insiemi
• Insieme:
una collezione di oggetti distinti detti
elementi
• Esempio:
Mercoledì
Domenica
Lunedì
i giorni
della
settimana
Martedì
Giovedì
Sabato
Venerdì
Programmazione di calcolatori: Cenni di teoria ingenua degli insiemi
2
C. Gaibisso
Gli insiemi
• Esempio:
i numeri interi positivi minori o uguali
a 10
10
1
5
2
4
3
7
9
8
6
Programmazione di calcolatori: Cenni di teoria ingenua degli insiemi
3
C. Gaibisso
Notazione
• Appartenenza:
se a è un elemento di A, scriveremo
a A
se a non è un elemento di A, scriveremo
a A
• Esempio:
5 A
A
1
2
3
5
4
9 A
Programmazione di calcolatori: Cenni di teoria ingenua degli insiemi
4
C. Gaibisso
Definizione di un insieme
• Modalità di definizione di un insieme:
• intensionale
• estensionale
• Definizione intensionale:
descrizione della caratteristica posseduta da
tutti e soli gli elementi dell’insieme
• Esempio:
I giorni della settimana
{ x|x è un giorno della settimana}
I numeri interi positivi minori o uguali a 10
{ x | x   and 1  x  10}
Programmazione di calcolatori: Cenni di teoria ingenua degli insiemi
5
C. Gaibisso
Definizione di un insieme
• Definizione estensionale:
elenco di tutti e soli gli elementi dell’insieme
• Esempio:
i giorni della settimana
{ lunedì, martedì, mercoledì,
giovedì, venerdì, sabato, domenica}
i numeri interi positivi minori o uguali a 10
{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Programmazione di calcolatori: Cenni di teoria ingenua degli insiemi
6
C. Gaibisso
Intensionale vs Estensionale
• Esempio:
• intensionale
{ x| x  2 * i, i   }
• estensionale
?
{ 2, 4, 6, 8, 10, 12, ....}
• Esempio:
• estensionale
979.418
1.039.806
26
…
126
979.418
…
1.009.311
9
63
…
• intensionale
{ x | x = i3+4i2-2i+6, iN, 1  i 100}
Programmazione di calcolatori: Cenni di teoria ingenua degli insiemi
7
C. Gaibisso
Intensionale vs Estensionale
Vantaggi
Svantaggi
Non Risente
Difficilmente
Intensionale
della Cardinalità Individuabile
Estensionale
Semplicità
Risente della
Cardinalità
Programmazione di calcolatori: Cenni di teoria ingenua degli insiemi
8
C. Gaibisso
Sottinsieme
• Sottinsieme:
A è un sottoinsieme di B se e solo se ogni
elemento di A è anche elemento di B
A  B   a  A  a B
• Esempio:
Giorni della Settimana (GdS)
Feriali
Domenica
Festivi  GdS
Sabato
Feriali  GdS
Lunedì
Giovedì
Martedì
Mercoledì
Festivi
Feriali  Festivi
Venerdì
Programmazione di calcolatori: Cenni di teoria ingenua degli insiemi
9
C. Gaibisso
Prodotto cartesiano
• Prodotto Cartesiano:
il prodotto cartesiano di A e B è
l’insieme di tutte le coppie il cui primo
elemento appartiene ad A e il cui
secondo elemento appartiene a B
A  B  (a, b)|a  A e b  B
Programmazione di calcolatori: Cenni di teoria ingenua degli insiemi
10
C. Gaibisso
Prodotto cartesiano
• Esempio:
Numeri Decimali x Numeri Romani
(1, I)
(2, I)
Numeri Decimali 1
2
(1, II)
3
(3, I)
(2, II)
(1, IV)
(1, III)
(3, II)
(2, IV)
I
Numeri Romani
(2, III)
IV
II
(3, III)
(3, IV)
III
Programmazione di calcolatori: Cenni di teoria ingenua degli insiemi
11
C. Gaibisso
Prodotto cartesiano
• Esempio:
Decimali Romane Decimali x Romane
(1, I)
I
1
(1, II)
II
1
(1, III)
III
1
(1, IV)
IV
1
(2, I)
I
2
(2, II)
II
2
(2, III)
III
2
(2, IV)
IV
2
(3, I)
I
3
(3, II)
II
3
(3, III)
III
3
(3, IV)
IV
3
Programmazione di calcolatori: Cenni di teoria ingenua degli insiemi
12
C. Gaibisso
Relazioni binarie
• Relazione binaria R tra A e B:
è un sottoinsieme del prodotto
cartesiano di A per B
R  AB
Programmazione di calcolatori: Cenni di teoria ingenua degli insiemi
13
C. Gaibisso
Relazioni binarie
• Esempio:
Numeri Decimali x Numeri Romani
Numeri Decimali
1
(1, IV)
(3, IV)
2
3
(1, III)
(2, III)
(2, IV)
(1, II)
Maggiori Uguali di
Numeri Romani
II
I
(2, II)
IV
III
(3, III)
(1, I)
(2, I)
(3, I)
(3, II)
Programmazione di calcolatori: Cenni di teoria ingenua degli insiemi
14
C. Gaibisso
Relazioni binarie
• Esempio:
Decimali Romane Minori Uguali di
1
I
(1, I)
1
II
(1, II)
1
III
(1, III)
1
IV
(1, IV)
2
I
(2, I)
2
II
(2, II)
2
III
(2, III)
2
IV
(2, IV)
3
I
(3, I)
3
II
(3, II)
3
III
(3, III)
3
IV
(3, IV)
Programmazione di calcolatori: Cenni di teoria ingenua degli insiemi
15
C. Gaibisso
Funzioni
• Funzione:
una funzione f da A in B è una relazione
binaria che associa ad ogni elemento di A
uno e un solo elemento di B
f  AxB t.c. aA  (a,b)f
e
se (a,b) e (a, b’) f  b=b’
Programmazione di calcolatori: Cenni di teoria ingenua degli insiemi
16
C. Gaibisso
Funzioni
• Esempio:
Numeri Decimali x Numeri Romani
Numeri Decimali
(1, IV)
1
(3, IV)
2
II
(2, III)
(2, IV)
3
Numeri Romani
(1, III)
(2, I)
(1, II)
(3, II)
(3, I)
Conversione
I
IV
III
(3, III)
(1, I)
(2, II)
Programmazione di calcolatori: Cenni di teoria ingenua degli insiemi
17
C. Gaibisso
Funzioni
• Esempio:
Decimali Romane Conversione
1
I
(1, I)
1
II
(1, II)
1
III
(1, III)
1
IV
(1, IV)
2
I
(2, I)
2
II
(2, II)
2
III
(2, III)
2
IV
(2, IV)
3
I
(3, I)
3
II
(3, II)
3
III
(3, III)
3
IV
(3, IV)
Programmazione di calcolatori: Cenni di teoria ingenua degli insiemi
18
C. Gaibisso
Funzioni
• E’ una funzione?
Numeri Decimali x Numeri Romani
(1, IV)
(1, III)
(2, III)
(3, IV)
(1, II)
(2, IV)
(2, I)
(3, I)
Funzione ?
NO
(3, II)
(3, III)
(1, I)
(2, II)
Programmazione di calcolatori: Cenni di teoria ingenua degli insiemi
19
C. Gaibisso
Funzioni
• E’ una funzione?
NO
Decimali Romane Conversione
1
I
(1, I)
1
II
(1, II)
1
III
(1, III)
1
IV
(1, IV)
2
I
(2, I)
2
II
(2, II)
2
III
(2, III)
2
IV
(2, IV)
3
I
(3, I)
3
II
(3, II)
3
III
(3, III)
3
IV
(3, IV)
Programmazione di calcolatori: Cenni di teoria ingenua degli insiemi
20
C. Gaibisso
Nome, dominio, codominio, immagine
• Notazione:
Nome
f :A B
Codominio
Dominio
• Immagine di f:
Im(f)  {y  B |  x  A, f (x)  y}
Programmazione di calcolatori: Cenni di teoria ingenua degli insiemi
21
C. Gaibisso
Nome, dominio, codominio, immagine
• Esempio:
Dominio
Numeri Decimali x Numeri Romani
Numeri Decimali
2
1
(1, IV)
(3, IV)
3
(1, III)
(2, III)
(2, IV)
(2, I)
Codominio
Numeri Romani
II
IV
(3, II)
(3, I)
Nome Conversione
I
III
(1, II)
(3, III)
Immagine
(1, I)
(2, II)
Programmazione di calcolatori: Cenni di teoria ingenua degli insiemi
22
C. Gaibisso
Definizione di una funzione
1. Signature o arietà:
•
nome
•
dominio
•
codominio
2. Legge che associa ad ogni elemento del
dominio un elemento del codominio
Programmazione di calcolatori: Cenni di teoria ingenua degli insiemi
23
C. Gaibisso
Definizione di una funzione
• Esempio: funzione che associa ad ogni
numero naturale il suo quadrato
1. Signature o arietà:
•
Nome:
quadrato
•
Dominio:
N
•
Codominio:
N
2. Legge che associa ad ogni elemento del dominio un
elemento del codominio:
quadrato(x) = x*x
Programmazione di calcolatori: Cenni di teoria ingenua degli insiemi
24
C. Gaibisso
Funzioni iniettive
• Funzione iniettiva:
f : AB è iniettiva se associa a valori diversi
del dominio valori diversi del codominio
o più formalmente
f : A B è iniettiva se  a e a’A t.c. a ≠ a’ 
f(a) ≠ f(a’)
Programmazione di calcolatori: Cenni di teoria ingenua degli insiemi
25
C. Gaibisso
Funzioni iniettive?
SI
SI
NO
Programmazione di calcolatori: Cenni di teoria ingenua degli insiemi
26
C. Gaibisso
Funzioni iniettive?
• La funzione identità f(x)=x
SI
• La funzione f : N→N definita da f(x)=2x+1
SI
• La funzione g : Z→N definita da g(x)=x2
NO
• La funzione g : Z→N definita da g(x)=|x|
NO
Programmazione di calcolatori: Cenni di teoria ingenua degli insiemi
27
C. Gaibisso
Funzioni suriettive
• Funzione suriettiva:
f : AB è suriettiva se e solo se Im(f) = B
o analogamente
f : A B è suriettiva  bB,  aA, t.c. f(a)=b
Programmazione di calcolatori: Cenni di teoria ingenua degli insiemi
28
C. Gaibisso
Funzioni suriettive?
NO
SI
SI
Programmazione di calcolatori: Cenni di teoria ingenua degli insiemi
29
C. Gaibisso
Funzioni suriettive?
• La funzione identità
SI
• La funzione f : N→N definita da f(x)=2x+1
NO
• La funzione g : N→N definita da g(x)=x2
NO
• La funzione g : Z→N definita da g(x)=|x|
SI
Programmazione di calcolatori: Cenni di teoria ingenua degli insiemi
30
C. Gaibisso
Funzioni biunivoche
• Funzione biunivoca:
SI
f : A B è biunivoca se e solo se
è iniettiva e suriettiva
NO
NO
Programmazione di calcolatori: Cenni di teoria ingenua degli insiemi
31
C. Gaibisso
Funzioni invertibili
• Funzione inversa:
se f : A B è biunivoca allora esiste
f-1: B A, t.c. se b=f(a) allora f-1(b)=a,  bB
f-1
Programmazione di calcolatori: Cenni di teoria ingenua degli insiemi
32
C. Gaibisso
Equipotenza tra insiemi
• A è equipotente a B (AB)
se e solo se  f : A →B biunivoca
• Esempio:
N  {x | x = i  3, i  N}
Npari  Ndispari
Programmazione di calcolatori: Cenni di teoria ingenua degli insiemi
33