C. Gaibisso Programmazione di Programmazione di calcolatoricalcolatori
Lezione IIICenni di teoria ingenua
degli insiemi
Programmazione di calcolatori: Cenni di teoria ingenua degli insiemi 1
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ì
Giovedì
Venerdì
Sabato
Domenica
• Esempio:
i giorni della
settimana
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
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:
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:
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
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}
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
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ì
Giovedì
Venerdì
Sabato
Domenica
Giorni della Settimana (GdS)
FestiviFeriali
GdSFestivi
• Esempio:
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 appartiene ad A
e il cui secondo elemento
appartiene a B
B b e A a | b)(a, B A
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:
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:
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:
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:
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:
C. Gaibisso
FunzioniFunzioni
Programmazione di calcolatori: Cenni di teoria ingenua degli insiemi 16
•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. aA (a,b)fe
se (a,b) e (a, b’) f b=b’
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
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
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
Funzione ?
NO
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
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
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
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
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
C. Gaibisso
Funzioni iniettiveFunzioni iniettive
Programmazione di calcolatori: Cenni di teoria ingenua degli insiemi 25
• Funzione iniettiva:
f : AB è iniettiva se associa a valori diversi del dominio valori diversi del codominio
f : A B è iniettiva se a e a’A t.c. a ≠ a’ f(a) ≠ f(a’)
o più formalmente
C. Gaibisso
Funzioni iniettive?Funzioni iniettive?
Programmazione di calcolatori: Cenni di teoria ingenua degli insiemi 26
SISI
NO
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 : Z→N definita da
g(x)=x2
• La funzione g : Z→N definita da
g(x)=|x|
SI
SI
NO
NO
C. Gaibisso
Funzioni suriettiveFunzioni suriettive
Programmazione di calcolatori: Cenni di teoria ingenua degli insiemi 28
• Funzione suriettiva:
f : AB è suriettiva se e solo se Im(f) = B
f : A B è suriettiva bB, aA, t.c. f(a)=b
o analogamente
C. Gaibisso
Funzioni suriettive?Funzioni suriettive?
Programmazione di calcolatori: Cenni di teoria ingenua degli insiemi 29
SINO
SI
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
C. Gaibisso
Funzioni biunivocheFunzioni biunivoche
Programmazione di calcolatori: Cenni di teoria ingenua degli insiemi 31
• Funzione biunivoca:
f : A B è biunivoca se e solo seè iniettiva e suriettiva
SI
NO
NO
C. Gaibisso
Funzioni invertibiliFunzioni invertibili
Programmazione di calcolatori: Cenni di teoria ingenua degli insiemi 32
• Funzione inversa:
se f : A B è biunivoca allora esistef-1: B A, t.c. se b=f(a) allora f-
1(b)=a, bB
f-1
C. Gaibisso
Equipotenza tra insiemiEquipotenza tra insiemi
Programmazione di calcolatori: Cenni di teoria ingenua degli insiemi 33
• A è equipotente a B (AB)
se e solo se f : A →B biunivoca
• Esempio:
N {x | x = i 3, i N}
Npari Ndispari