Post on 02-May-2015
G. Amodeo,C. Gaibisso Programmazione di Programmazione di
CalcolatoriCalcolatori
Lezione IIICenni di Teoria Ingenua
degli Insiemi
Programmazione di Calcolatori: Cenni di Teoria Ingenua degli Insiemi 1
G. Amodeo,C. Gaibisso
Gli insiemiGli insiemi
Programmazione di Calcolatori: Cenni di Teoria Ingenua degli Insiemi 2
una collezione di oggetti distinti dettielementi
• Insieme:
Lunedì
Martedì
Mercoledì
Mercoledì
Giovedì
Venerdì
Sabato
Domenica
• Esempio:
i giorni della
settimana
G. Amodeo,C. Gaibisso
Gli insiemiGli insiemi
Programmazione di Calcolatori: Cenni di Teoria Ingenua degli Insiemi 3
• Esempio:i numeri interi positivi minori o uguali a 10
2
4
1
5
36
8
7
9
10
G. Amodeo,C. Gaibisso
NotazioneNotazione
Programmazione di Calcolatori: Cenni di Teoria Ingenua degli Insiemi 4
2
4
1
3 5
A A 5
A 9
• Appartenenza:
se a è un elemento di A, scriveremo
A ase a non è un elemento di A, scriveremo
A a• Esempio:
G. Amodeo,C. Gaibisso
Definizione di un insiemeDefinizione di un insieme
Programmazione di Calcolatori: Cenni di Teoria Ingenua degli Insiemi 5
• Modalità di definizione di un insieme:intensionale
estensionale
descrizione della caratteristica posseduta da tutti e soli gli elementi dell’insieme
• Definizione intensionale:
I giorni della settimanasettimana} della giorno un è x | x {
I numeri interi positivi minori o uguali a 1010} x 1 and x | x {
• Esempio:
G. Amodeo,C. Gaibisso
Definizione di un insiemeDefinizione di un insieme
Programmazione di Calcolatori: Cenni di Teoria Ingenua degli Insiemi 6
elenco di tutti e soli gli elementi dell’insieme
• Definizione estensionale:
i numeri interi positivi minori o uguali a 10
10} 9, 8, 7, 6, 5, 4, 3, 2, 1, {
• Esempio:
domenica} sabato, venerdì,giovedì,
mercoledì, martedì, lunedì, {
i giorni della settimana
G. Amodeo,C. Gaibisso
Intensionale vs EstensionaleIntensionale vs Estensionale
Programmazione di Calcolatori: Cenni di Teoria Ingenua degli Insiemi 7
• Esempio:
....} 12, 10, 8, 6, 4, 2, {
• Esempio:
} i i, * 2 x | x { intensionale
?estensionale
26 63
1.039.806126
1.009.311
979.418
9
…
…
…
979.418
estensionale
intensionale{ x | x = i3+4i2-2i+6, iN, 1 i 100}
G. Amodeo,C. Gaibisso Intensionale vs Intensionale vs
EstensionaleEstensionale
Programmazione di Calcolatori: Cenni di Teoria Ingenua degli Insiemi 8
àCardinalit
della RisenteSemplicitàleEstensiona
ileIndividuab
nteDifficilme
àCardinalit della
Risente NonleIntensiona
SvantaggiVantaggi
G. Amodeo,C. Gaibisso
SottinsiemeSottinsieme
Programmazione di Calcolatori: Cenni di Teoria Ingenua degli Insiemi 9
• Sottinsieme:A è un sottoinsieme di B se e solo se ogni elemento di A è anche elemento di B
B a A a BA
Festivi
Feriali
GdSFerialiLunedì
Martedì
Mercoledì
Mercoledì
Giovedì
Venerdì
Sabato
Domenica
Giorni della Settimana (GdS)
FestiviFeriali
GdSFestivi
• Esempio:
G. Amodeo,C. Gaibisso
Prodotto cartesianoProdotto cartesiano
Programmazione di Calcolatori: Cenni di Teoria Ingenua degli Insiemi 10
• 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
B b e A a | b)(a, B A
G. Amodeo,C. Gaibisso
Prodotto cartesianoProdotto cartesiano
Programmazione di Calcolatori: Cenni di Teoria Ingenua degli Insiemi 11
2
1
3
Numeri Decimali
II
IV
I
III
Numeri Romani
(1, I)
(1, II)
(1, III)
(1, IV)
(2, I)
(2, II)
(2, III)(2, IV)
(3, I)
(3, II)(3, III)
(3, IV)
Numeri Decimali x Numeri Romani•Esempio:
G. Amodeo,C. Gaibisso
Prodotto cartesianoProdotto cartesiano
Programmazione di Calcolatori: Cenni di Teoria Ingenua degli Insiemi 12
IV) (3,IV3III) (3,III3II) (3,II3I) (3,I3IV) (2,IV2III)(2,III2II)(2,II2I) (2,I2
IV) (1,IV1III) (1,III1II) (1,II1I) (1,I1Romane x DecimaliRomaneDecimali
• Esempio:
G. Amodeo,C. Gaibisso
Relazioni binarieRelazioni binarie
Programmazione di Calcolatori: Cenni di Teoria Ingenua degli Insiemi 13
B A R
è un sottoinsieme del prodotto
cartesiano di A per B
• Relazione binaria R tra A e B:
G. Amodeo,C. Gaibisso
Relazioni binarieRelazioni binarie
Programmazione di Calcolatori: Cenni di Teoria Ingenua degli Insiemi 14
2
1
3
Numeri Decimali
II
IV
I
III
Numeri Romani(1, I)
(1, II)
(1, III)(1, IV)
(2, I)(2, II)
(2, III)
(2, IV)
(3, I)
(3, II)
(3, III)
(3, IV)
Numeri Decimali x Numeri Romani
Maggiori Uguali di
• Esempio:
G. Amodeo,C. Gaibisso
Relazioni binarieRelazioni binarie
Programmazione di Calcolatori: Cenni di Teoria Ingenua degli Insiemi 15
IV) (3,IV3III) (3,III3II) (3,II3I) (3,I3IV) (2,IV2III)(2,III2II)(2,II2I) (2,I2
IV) (1,IV1III) (1,III1II) (1,II1I) (1,I1
di Uguali MinoriRomaneDecimali
• Esempio:
G. Amodeo,C. Gaibisso
FunzioniFunzioni
Programmazione di Calcolatori: Cenni di Teoria Ingenua degli Insiemi 16
•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. aA (a,b)fe
se (a,b) e (a, b’) f b=b’
G. Amodeo,C. Gaibisso
FunzioniFunzioni
Programmazione di Calcolatori: Cenni di Teoria Ingenua degli Insiemi 17
(1, I)
(1, II)
(1, III)(1, IV)
(2, I)
(2, II)
(2, III)
(2, IV)
(3, I)(3, II)
(3, III)
(3, IV)
Numeri Decimali x Numeri Romani
Conversione
• Esempio:
2
1
3
Numeri Decimali
II
IV
I
III
Numeri Romani
G. Amodeo,C. Gaibisso
FunzioniFunzioni
Programmazione di Calcolatori: Cenni di Teoria Ingenua degli Insiemi 18
• Esempio:
IV) (3,IV3III) (3,III3II) (3,II3I) (3,I3IV) (2,IV2III)(2,III2II)(2,II2I) (2,I2
IV) (1,IV1III) (1,III1II) (1,II1I) (1,I1
eConversionRomaneDecimali
G. Amodeo,C. Gaibisso
FunzioniFunzioni
Programmazione di Calcolatori: Cenni di Teoria Ingenua degli Insiemi 19
• E’ una funzione?
(1, I)
(1, II)
(1, III)(1, IV)
(2, I)
(2, II)
(2, III)
(2, IV)
(3, I)
(3, II)
(3, III)
(3, IV)
Numeri Decimali x Numeri Romani
Conversione
NO
G. Amodeo,C. Gaibisso
FunzioniFunzioni
Programmazione di Calcolatori: Cenni di Teoria Ingenua degli Insiemi 20
• E’ una funzione?
IV) (3,IV3III) (3,III3II) (3,II3I) (3,I3IV) (2,IV2III)(2,III2II)(2,II2I) (2,I2
IV) (1,IV1III) (1,III1II) (1,II1I) (1,I1
eConversionRomaneDecimali
NO
G. Amodeo,C. Gaibisso Nome, dominio, codominio, Nome, dominio, codominio,
immagineimmagine
Programmazione di Calcolatori: Cenni di Teoria Ingenua degli Insiemi 21
•Notazione:
B A: fDominio
Codominio
• Immagine di f:
y}(x) A, x |B {y f Im(f)
Nome
G. Amodeo,C. Gaibisso Nome, dominio, codominio, Nome, dominio, codominio,
immagineimmagine
Programmazione di Calcolatori: Cenni di Teoria Ingenua degli Insiemi 22
(1, I)
(1, II)
(1, III)(1, IV)
(2, I)
(2, II)
(2, III)
(2, IV)
(3, I)(3, II)
(3, III)
(3, IV)
Numeri Decimali x Numeri Romani
Conversione
• Esempio:
2
1
3
Numeri Decimali
II
I
IV
III
Numeri Romani
Codominio
Immagine
Dominio
Nome
G. Amodeo,C. Gaibisso
Definizione di una funzioneDefinizione di una funzione
Programmazione di Calcolatori: Cenni di Teoria Ingenua degli Insiemi 23
1. Signature o arietà:
• nome
• dominio
• codominio
2. Legge che associa ad ogni
elemento del dominio un
elemento del codominio
G. Amodeo,C. Gaibisso
Definizione di una funzioneDefinizione di una funzione
Programmazione di Calcolatori: Cenni di Teoria Ingenua degli Insiemi 24
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
• Esempio: funzione che associa ad ogni numero naturale il suo quadrato
G. Amodeo,C. Gaibisso
Funzioni iniettiveFunzioni iniettive
Programmazione di Calcolatori: Cenni di Teoria Ingenua degli Insiemi 25
• Funzione iniettiva:
f : AB è iniettiva se e solo se associa valori diversi ad argomenti diversi
f : A B e iniettiva se a, a’A, se f(a)=f(a’), allora a = a’
o più formalmente
G. Amodeo,C. Gaibisso
Funzioni iniettive?Funzioni iniettive?
Programmazione di Calcolatori: Cenni di Teoria Ingenua degli Insiemi 26
SISI
NO
G. Amodeo,C. Gaibisso
Funzioni iniettive?Funzioni iniettive?
Programmazione di Calcolatori: Cenni di Teoria Ingenua degli Insiemi 27
• La funzione identità f(x)=x
• La funzione f : N→N definita da
f(x)=2x+1
• La funzione g : N→N definita da
g(x)=x2
• La funzione g : Z→N definita da
g(x)=|x|
SI
SI
NO
NO
G. Amodeo,C. Gaibisso
Funzioni suriettiveFunzioni suriettive
Programmazione di Calcolatori: Cenni di Teoria Ingenua degli Insiemi 28
• Funzione suriettiva:
f : AB è surgettiva se e solo se Im(f) = B
f : A B è suriettiva se e solo se bB, aA, t.c. f(a)=b
o analogamente
G. Amodeo,C. Gaibisso
Funzioni suriettive?Funzioni suriettive?
Programmazione di Calcolatori: Cenni di Teoria Ingenua degli Insiemi 29
SINO
SI
G. Amodeo,C. Gaibisso
Funzioni suriettive?Funzioni suriettive?
Programmazione di Calcolatori: Cenni di Teoria Ingenua degli Insiemi 30
• La funzione identità
• La funzione f : N→N definita da
f(x)=2x+1
• La funzione g : N→N definita da
g(x)=x2
• La funzione g : Z→N definita da
g(x)=|x|
SI
NO
NO
SI
G. Amodeo,C. Gaibisso
Funzioni biiettiveFunzioni biiettive
Programmazione di Calcolatori: Cenni di Teoria Ingenua degli Insiemi 31
• Funzione biiettiva:
f : A B è biettiva se e solo seè iniettiva e suriettiva
SI
NO
NO
G. Amodeo,C. Gaibisso
Equipotenza tra insiemiEquipotenza tra insiemi
Programmazione di Calcolatori: Cenni di Teoria Ingenua degli Insiemi 32
• A è equipotente a B (AB)
se e solo se f : A →B biettiva
• Esempio:
N {x | x = i 3, i N}
Npari Ndispari