G. Amodeo,
C. Gaibisso
Programmazione di Calcolatori
Lezione III
Cenni di Teoria Ingenua degli
Insiemi
Programmazione di Calcolatori: Cenni di Teoria Ingenua degli Insiemi
1
G. Amodeo,
C. Gaibisso
Gli insiemi
• Insieme:
una collezione di oggetti distinti detti
elementi
• Esempio:
Mercoledì
Lunedì
i giorni
della
settimana
Domenica
Mercoledì
Martedì
Giovedì
Sabato
Venerdì
Programmazione di Calcolatori: Cenni di Teoria Ingenua degli Insiemi
2
G. Amodeo,
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
G. Amodeo,
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
G. Amodeo,
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
G. Amodeo,
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
G. Amodeo,
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
intensionale
…
1.009.311
9
63
…
{ x | x = i3+4i2-2i+6, iN, 1  i 100}
Programmazione di Calcolatori: Cenni di Teoria Ingenua degli Insiemi
7
G. Amodeo,
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
G. Amodeo,
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
Mercoledì
Lunedì
Giovedì
Martedì
Mercoledì
Domenica
Festivi  GdS
Sabato
Feriali  GdS
Festivi
Feriali  Festivi
Venerdì
Programmazione di Calcolatori: Cenni di Teoria Ingenua degli Insiemi
9
G. Amodeo,
C. Gaibisso
Prodotto cartesiano
• Prodotto Cartesiano:
il prodotto cartesiano di A e B è
l’insieme di tutte le coppie il cui
primo elemento è un elemento di A e
il cui secondo elemento è un
elemento di B
A  B  (a, b)|a  A e b  B
Programmazione di Calcolatori: Cenni di Teoria Ingenua degli Insiemi
10
G. Amodeo,
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
G. Amodeo,
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
G. Amodeo,
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
G. Amodeo,
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
G. Amodeo,
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
G. Amodeo,
C. Gaibisso
Funzioni
• Funzione:
una funzione f definita su A e a valori in
B è una relazione binaria che associa ad
ogni elemento a di A uno e un solo
elemento b 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
G. Amodeo,
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
G. Amodeo,
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
G. Amodeo,
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)
Conversione
NO
(3, II)
(3, III)
(1, I)
(2, II)
Programmazione di Calcolatori: Cenni di Teoria Ingenua degli Insiemi
19
G. Amodeo,
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
G. Amodeo,
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
G. Amodeo,
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
G. Amodeo,
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
G. Amodeo,
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
G. Amodeo,
C. Gaibisso
Funzioni iniettive
• Funzione iniettiva:
f : AB è iniettiva se e solo se associa valori
diversi ad argomenti diversi
o più formalmente
f : A B e iniettiva se  a, a’A, se f(a)=f(a’),
allora a = a’
Programmazione di Calcolatori: Cenni di Teoria Ingenua degli Insiemi
25
G. Amodeo,
C. Gaibisso
Funzioni iniettive?
SI
SI
NO
Programmazione di Calcolatori: Cenni di Teoria Ingenua degli Insiemi
26
G. Amodeo,
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 : N→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
G. Amodeo,
C. Gaibisso
Funzioni suriettive
• Funzione suriettiva:
f : AB è surgettiva se e solo se Im(f) = B
o analogamente
f : A B è suriettiva se e solo se  bB,  aA,
t.c. f(a)=b
Programmazione di Calcolatori: Cenni di Teoria Ingenua degli Insiemi
28
G. Amodeo,
C. Gaibisso
Funzioni suriettive?
NO
SI
SI
Programmazione di Calcolatori: Cenni di Teoria Ingenua degli Insiemi
29
G. Amodeo,
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
G. Amodeo,
C. Gaibisso
Funzioni biiettive
• Funzione biiettiva:
SI
f : A B è biettiva se e solo se
è iniettiva e suriettiva
NO
NO
Programmazione di Calcolatori: Cenni di Teoria Ingenua degli Insiemi
31
G. Amodeo,
C. Gaibisso
Equipotenza tra insiemi
• A è equipotente a B (AB)
se e solo se  f : A →B biettiva
• Esempio:
N  {x | x = i  3, i  N}
Npari  Ndispari
Programmazione di Calcolatori: Cenni di Teoria Ingenua degli Insiemi
32