Esame Fondamenti di informatica

FONDAMENTI DI INFORMATICA

RIASSUNTO

Università di Pisa – Dipartimento di Informatica

- STUDENTE: Valerio Capizzi

- PROFESSORE: Andrea Corradini

capizzi.valerio@outlook.com FDI 22/23 Prof. Andrea Corradini

Insiemi

Un insieme è una collezione di oggetti, chiamati elementi, essi possono essere di qualsiasi tipo.

∅.

L’Insieme Vuoto non contiene nessun elemento e viene rappresentato con il simbolo

Simboli di Appartenenza:

• ∈ (appartenenza): indica se un elemento appartiene a un insieme

• ∉ (non appartenenza): indica se un elemento non appartiene ad un insieme.

Simboli di inclusione:

• ⊆

Sottoinsieme proprio: ogni elemento di A appartiene anche a B.

• ⊆

⊂ ≠ )

Inclusione stretta: ( e indica che A è contenuto in B e sono diversi.

• ∩ = ∅

Insiemi disgiunti: cioè non hanno elementi in comune.

Insiemi matematici Proprietà di uguaglianza e inclusione

Definizione insieme

Enumerazione (estensionale): si elencano tutti gli elementi contenuti nell’insieme.

▪ ∅ = {} → insieme vuoto

▪ A = {1,2,3,4,5} → insieme A dei numeri da 1 a 5

Sé gli insiemi sono grandi o infiniti si utilizzano i “… “ (Es. {1, 2, 3, …,60}; {1,2,…})

Per proprietà (intensionale): si definisce una proprietà che tutti gli elementi devono rispettare.

(insieme X contiene tutti e soli gli elementi di A che soddisfano P(x))

{ |

= ()} Quando A è ovvio dal contesto

Esempio:

P ∈

N = {n∣n N e n eˋ divisibile per 2} = {0, 2, 4, 6, 8, ...} naturali pari)

capizzi.valerio@outlook.com FDI 22/23 Prof. Andrea Corradini

Paradosso di Russel:

Possono esiste insiemi che contengono se stessi, di conseguenza può essere definito l’insieme avente come

elementi tutti gli insiemi contenenti se stessi, e viceversa, tutti gli insiemi non contenenti se stessi.

Ma ciò implica che l’insieme di tutti gli insiemi non contenente se stessi deve essere contenuto in se stesso.

Diagrammi di Eulero-Venn

- Universo: - Insiemi:

- Inclusione: - Disgiunzione:

Operazioni su Insiemi

Unione: Intersezione:

Differenza: Complemento:

Dimostrazioni

Permettono di verificare la validità di un’uguaglianza, ne esistono principalmente 3 tipi:

- Grafica: con i diagrammi di Eulero-Venn, permettono di dimostrare una formula visivamente;

- Sostituzione: l’uguaglianza viene dimostrata attraverso formule già dimostrate;

- Discorsiva: facilitano la dimostrazione, elaborando un ragionamento che conclude la dimostrazione.

capizzi.valerio@outlook.com FDI 22/23 Prof. Andrea Corradini

Insiemi di Insiemi

Utili nel caso si voglia investigare, tutte le possibili combinazioni di elementi presenti in un insieme.

Sono degli insiemi nei quali gli elementi sono a loro volta atri insiemi { { 2,4,6,8}, { 1,3,5,7,9} }.

Insieme delle parti

E’ un insieme che ha come elementi tutti e soli i sottoinsiemi di A.

{ }

() = ∣ ⊆

2

Gli elementi presenti in un sottoinsieme sono

Esempio: 3

{0}, {1}, {2}, {0,1}, {0,2}, {1,2}, {0,1,2}}

({0,

1, 2}) = , 2 = 8

{ ∅ Famiglie di insiemi

,

Dato un insieme nel quale per ogni suo elemento è definito un certo insieme indicizzato .

.

L’insieme (famiglia) ha come elementi tutti gli insiemi contenuti nell’insieme

{ } { }

= ∈ = ∈

∣

Le operazioni di unione e intersezione per le famiglie di insiemi:

• = ∈ .

→ insieme degli elementi di per un qualche indice

⋃ ⋃ ∈

• = ∈ .

→ insieme degli elementi di Ai per tutti gli indici

⋂ ⋂ ∈ Partizioni

È una famiglia di sottoinsiemi, NON VUOTI, appartenenti all’insieme A e diversi tra loro:

• ∅

Ogni insieme è diverso da (insiemi non vuoti);

• ∪ ∈ = (copertura di A);

• ≠ ∩ = ∅

Presi due indici qualsiasi e con (elementi diversi)

Prodotto cartesiano

(, ) ∈ ∈ )

È un insieme formato da tutte le coppie ordinate degli insiemi e ( e

{(,

× = )| ∈ , ∈ } Es. A={(a,1)(a,2)(b,1)(b,2)}

Numeri naturali come insiemi

∈ , { ∈ ∣ < } = {0, 1, 2, . . . , − 1}

Per ogni elemento l’insieme è definito come

∉ – 1. ∣ ∣ =

Quindi perché l’insieme arriva solamente al valore Però

Esempio:

∅

0 = = {} (insieme vuoto), 1 = {0} = {∅} = {{}}, 2 = {0,1} = {∅,{∅}} = {{},{{}}}, 3 = ….

capizzi.valerio@outlook.com FDI 22/23 Prof. Andrea Corradini

Relazioni

↔ )

Una relazione tra e (: è un sottoinsieme del prodotto cartesiano tra i due insiemi.

{(, |

× = ) , } = ⊆ × = ×

(, ) = ( × ).

L’insieme di tutte le relazioni tra e è dato da (, )

Le relazioni su insieme è quando l’insieme di partenza e di arrivo coincidono, cioè

Rappresentazioni

= {, } = {, , }

Relazione proprietà Relazione completa

{(, (,

), )} ⊆ × × ∈ ↔

Relazione identità Relazioni su insieme

= { (, )| ∈ } = { , , } {( |

= , ) ∈ ℕ × ℕ = + 1} ∈ (ℕ, ℕ)

Operazioni

Le relazioni sono degli insiemi, e come tali possono definirne di nuove, attraverso gli operatori.

∪ ∶ ↔ ;

• indica l’unione di e

∩ ∶ ↔ ;

• indica l’intersezione di e

\ ∶ ↔ ;

• indica la differenza di con

( × ) \ : ↔ .

• indica il complemento di

Composizione ∶ ↔ e ∶ ↔ ;

Date due relazioni la composizione è così definita:

{(, |

; = ) ∈ × ∃ ∈ . (, ) ∈ ∧ (, ) ∈ }

Esempio:

= {, , } = {, , , } = {1, 2}

Le proprietà TUSI vengono mantenute

capizzi.valerio@outlook.com FDI 22/23 Prof. Andrea Corradini

Quantificatori

Permettono di tradurre le espressioni “esiste almeno” e “per ogni”, usate nel linguaggio naturale.

(∃ ∈ . ())

Esistenziale: “esiste almeno un elemento di A tale che la proprietà P è vera”

(∀ ∈ . ())

Universale: “per ogni elemento di A tale la proprietà P è vera”

Relazione opposta

∶ ↔ ∶ ↔

Data una relazione quella opposta è l’inversione dell’associazioni

{(; |

= ) ∈ (; ) ∈ }

Esempio:

= {(, ) ∈ × | (, ) ∈ }

= {(, ) ∈ × | = + 1}

= {(, ) ∈ × | − 1 = }

= {(, ) ∈ × | − 1 = }

= {(, ) ∈ × | = − 1}

Risultati di Dualità

Le relazioni che hanno una dualità (totale-surgettiva e univalente-iniettiva) hanno lo stesso vincolo.

Ma le prime sulla partenza, le seconde sull’arrivo.

: ↔

• R è totale se e solo se è surgettiva (o viceversa)

: ↔

• R è univalente se e solo se è iniettiva (o viceversa)

Teorema di caratterizzazione

Qualsiasi relazione deve soddisfare delle condizioni:

⊆ ;

• R Totale solo sé × ×

La congiunzione fra R cioè e il suo opposto cioè forma una relazione A X A cioè ( ).

Se R non fosse totale vorrebbe dire che alcuni elementi di R(A) non sono collegati.

; ⊆

• R Univalente solo sé

( × ) ( × )

La congiunzione fra e R forma una relazione B X B contenuto di .

⊆ ;

• R Surgettiva solo sé

( × ) ( × ),

La congiunzione tra e forma una relazione B X B sottoinsieme di .

; ⊆

• R Iniettiva solo sé

×

La congiunzione fra ed forma una relazione ( ).

capizzi.valerio@outlook.com FDI 22/23 Prof. Andrea Corradini

Proprietà Fondamentali TUSI:

(∀ ∈ . ( ∃ ∈ . (, ) ∈ )

Totale: ∈ ∈

Per tutti gli esiste almeno un

(∃ (,

(∀ ∈ . ∈ . ) ∈ ))

Surgettiva:

∈ ∈

Per tutti i esiste almeno un

′ ′ ′

(∀, (, (, ) ))

∈ . ∈ . ) ∈ ∧ ∈ ⇒ =

(∀

Univalente: ∈ ∈

Per tutti gli esiste al più un

′ ′

(∀, (, (′, ))

∈ . ∈ . ) ∈ ∧ ) ∈ ⇒ =

(∀

Iniettiva: ∈ ∈

Per tutti i esiste al più un

capizzi.valerio@outlook.com FDI 22/23 Prof. Andrea Corradini

Funzioni

∈ (, ) (, ).

È una relazione di tipo totale e univalente, l’insieme di tutte le funzioni è

: ← .

Le funzioni sono denotate con le lettere minuscole, la relazione data dall’insieme è

Relazioni Totali Univalenti Surgettive Iniettive

Funzione X X

Funzione surgettiva X X X

Funzione iniettiva X X X

Funzione parziale X

Biiezione X X X X

Proprietà funzioni

Una proprietà stabilisce se ogni elemento dell’insieme gli appartiene o meno, è quindi come una relazione.

(

() = , ) ∈

Esempio è

succ(0)=1 succ(1)=2 succ(x)=x+1

È sempre necessario, specificare l’insieme di partenza e di arrivo, altrimenti non si sa i valori che può avere.

Funzioni parziali/iniettive/surgettive

• Funzione parziale: non c’è qualche elemento per cui è definita, si dice infatti,

(,

∈ ∈ ) ∈

- Definita, quando per l’elemento esiste un tale che

- Non Definita su a, per l’elemento non c’è b.

• Funzione surgettiva: ogni elemento a può avere un solo b, più a possono avere lo stesso b.

• Funzione iniettiva: ogni elemento a può avere un solo b e viceversa.

Biiezioni

Dati due insiemi la loro relazione è una biiezione quando per ogni elemento a corrisponde un elemento b.

(, )

L’insieme delle biiezioni da a è così definito ||!

Per contare il numero di biiezioni si fa il fattoriale della cardinalità

Esempio:

= { , } 2 = { 0, 1 }

= {(, 1), (, 0)} |2|! = 2

Teorema caratterizzazione biiezioni : ↔ : ↔

Date due relazioni tra due insiemi A e B, cioè e

; =

- S è l’inversa di R sé ; (biiezione)

- R si dice invertibile quando esiste almeno una relazione inversa di R. (biietiva tutte TUSI)

capizzi.valerio@outlook.com FDI 22/23 Prof. Andrea Corradini

Insiemi in biiezione (corrispondenza uno a uno)

: → , ≅ .

Due insiemi e si dicono in biiezione quando esiste una biiezione è indicata come

Vuol dire quindi che è una relazione invertibile, e che ci si può spostare da A a B e da B ad A.

Con posso fare a->b e con i-1 b->a.

≅

- Riflessiva: ≅ ⇒ ≅

- Simmetrica:

≅ ∧ ≅ ⇒ ≅

- Transitiva:

Funzione caratteristica

Permette di stabilire quando un elemento appartiene a un dato insieme.

La funzione mette in relazione l’insieme con una proprietà o determinato valore.

Sequenza lunghezza fissa, n-uple ( )

, , … ,

Dato un insieme A, una sequenza di lunghezza n è una n-upla 0 1 −1

∈ ∈ {0,1, … , – 1}

Ogni elemento è indicizzato con un indice

L’insieme contiene tutte le sequenze nell’insieme A di lunghezza n.

= { , , … , ∣ ∀ ∈ {0, 1, … , − 1} . ∈ }

0 1 −1

La biiezione di una sequenza è così definita:

≅ × × (… )

Esempio: 0 1 2

)}

} = {( = {() , ()} = { (, ) , (, ) , (, ), (, ) }

= {, 0 1 2 3

≅ 1, ≅ , ≅ × , ≅ × ( × )

Biiezione:

Sequenze lunghezza arbitraria (Stella di Kleene)

È una sequenza sull’insieme A avente lunghezza n, per un qualsiasi numero naturale.

Questo insieme è indicato come A* ed è definito così:

∗ 0 1 2

= = ∪ ∪ ∪ …

⋃

∈ℕ

∗

,

Assegna ad ogni insieme l’insieme composto da sequenze di lunghezza arbitraria ma finita di A.

Esempio: ∗

AN (caratteri alfanumerici) contiene tutte le stringhe di caratteri alfanumerici (123, anna, Pluto3)

∗

1 ≅ ℕ

- 1 = {0}

-

capizzi.valerio@outlook.com FDI 22/23 Prof. Andrea Corradini

L’Induzione

Metodo formale per definire in modo rigoroso insiemi e funzioni, oltre a poter dimostrare proprietà.

Permette di definire gli elementi base e le regole per poter costruire altri sottoinsiemi.

Definizione di Induzione

1. Clausola base: stabilisce quali oggetti appartengono all’insieme.

2. Clausola induttiva: descrive in che modo gli elementi possono essere usati per produrne altri.

3. Clausola terminale: stabilisce quando l’insieme che si sta definendo non contiene altri elementi.

(il più piccolo insieme che soddisfa la clausola base)

ℕ

Induzione numeri naturali

ℕ

L’insieme dei naturali è definito come insieme che soddisfa le seguenti regole:

0 ∈ .

1. ∈ ( + 1) ∈ .

2. Se allora

3. Nessun altro elemento appartiene a N. (si incorpora nella induttiva)

=

Dimostro che è un elemento di N:

√ ∈

- [clausola base] sappiamo che 0 N;

∈ ∈ ∈

- [induttiva] otteniamo (0 + 1) = 1 N, applicando ancora: (1+1) = 2 N ; (2+1) = 3 N

Induzione Funzione

Si stabiliscono due condizioni fondamentali:

• () ∈ .

Clausola base: il valore di definito per alcuni

• () .