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