C. Gaibisso Programmazione di calcolatori Lezione III Cenni di teoria ingenua degli insiemi...

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


una collezione di oggetti distinti dettielementi

• Insieme:

Lunedì

Martedì

Mercoledì

Giovedì

Venerdì

Sabato

Domenica

• Esempio:

i giorni della

settimana

C. Gaibisso

Gli insiemiGli insiemi


• Esempio:i numeri interi positivi minori o uguali a 10

2

4

1

5

36

8

7

9

10

C. Gaibisso

NotazioneNotazione


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


• 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


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


• 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


àCardinalit

della RisenteSemplicitàleEstensiona

ileIndividuab

nteDifficilme

àCardinalit della

Risente NonleIntensiona

SvantaggiVantaggi

C. Gaibisso

SottinsiemeSottinsieme


• 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


• 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



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



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


B A R

è un sottoinsieme del prodotto

cartesiano di A per B

• Relazione binaria R tra A e B:

C. Gaibisso



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




IV) (1,IV1III) (1,III1II) (1,II1I) (1,I1

di Uguali MinoriRomaneDecimali

• Esempio:

C. Gaibisso

FunzioniFunzioni


•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


(1, I)

(1, II)

(1, III)(1, IV)

(2, I)

(2, II)

(2, III)

(2, IV)

(3, I)(3, II)

(3, III)

(3, IV)


Conversione

• Esempio:

2

1

3

Numeri Decimali

II

IV

I

III

Numeri Romani

C. Gaibisso

FunzioniFunzioni


• Esempio:



eConversionRomaneDecimali

C. Gaibisso

FunzioniFunzioni


• 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)


Funzione ?

NO

C. Gaibisso

FunzioniFunzioni


• E’ una funzione?



eConversionRomaneDecimali

NO

C. Gaibisso Nome, dominio, codominio, Nome, dominio, codominio, immagineimmagine


•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


(1, I)

(1, II)

(1, III)(1, IV)

(2, I)

(2, II)

(2, III)

(2, IV)

(3, I)(3, II)

(3, III)

(3, IV)


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


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


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


• 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?


SISI

NO

C. Gaibisso

Funzioni iniettive?Funzioni iniettive?


• 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


g(x)=|x|

SI

SI

NO

NO

C. Gaibisso

Funzioni suriettiveFunzioni suriettive


• 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?


SINO

SI

C. Gaibisso

Funzioni suriettive?Funzioni suriettive?


• La funzione identità

• La funzione f : N→N definita da

f(x)=2x+1

• La funzione g : N→N definita da

g(x)=x2


g(x)=|x|

SI

NO

NO

SI

C. Gaibisso

Funzioni biunivocheFunzioni biunivoche


• Funzione biunivoca:

f : A B è biunivoca se e solo seè iniettiva e suriettiva

SI

NO

NO

C. Gaibisso

Funzioni invertibiliFunzioni invertibili


• 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


• A è equipotente a B (AB)

se e solo se f : A →B biunivoca

• Esempio:

N {x | x = i 3, i N}

Npari Ndispari

C. Gaibisso Programmazione di calcolatori Lezione III Cenni di teoria ingenua degli insiemi...

Documents

Transcript of C. Gaibisso Programmazione di calcolatori Lezione III Cenni di teoria ingenua degli insiemi...