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