Modelli simulativiper le Scienze Cognitive

Paolo Bouquet(Università di Trento)

Marco Casarotti(Università di Padova)

Funzioni e calcolabilità

Lezione 2

Cos’è una funzione

Una funzione f è una corrispondenza tra due insiemi D e C tale che, ad ogni elemento x di D preso come argomento, f associa uno e un solo elemento y di C come valore.

Di solito si scrive f(x) = y per indicare la corrispondenza tra un elemento xD e un elemento yC

Funzioni: Dominio e Codominio

Dominio: l’insieme D da cui una funzione f assume i suoi argomenti

Codominio: l’insieme C da cui una funzione f assume i suoi valori

f : D C

D C

Esempi

Le seguenti corrispondenze sono funzioni:– Data una persona, associare l’altezza– Data una regione italiana, associare il capoluogo

di regione

Le seguenti corrispondenze non sono funzioni:– Data una persona, associarle i suoi nonni– Data una regione Italiana, associarle le città

capoluogo di provincia che si trovano nel suo territorio

Specifica di una funzione

● Una funzione non è determinata soltanto dall’operazione richiesta per associare un argomento a un valore, ma anche dalla determinazione di dominio e codominio

● Per esempio, la funzione

f(x) = x2 + 4

Può essere di tipo R R o di tipo N N

Funzioni a più argomenti

Ovviamente una funzione può avere più di un argomento.

Per esempio, la somma è una funzione che associa a una coppia di numeri un valore che corrisponde alla loro somma:

f(x,y) = x + y

e si scrive f : N × N N o anche f : N2 N (da coppie di numeri a numeri)

Definizione insiemistica delle funzioni

Una funzione può essere vista come un insieme di coppie ordinate:

f D ×C

In altri termini, una funzione è un insieme di coppie (x,y) tali che:– xD– yC– f(x) = y

Esempio

Prendiamo la seguente funzione N N:

f(x) = 2x

Essa può essere descritta come il seguente insieme di coppie ordinate:

(0,0), (1,2), (2,4), (3,6), (4,8), …

Problemi

● A che funzione corrisponde l’insieme di coppie seguente?

(0,4), (1,4), (2,4), (3,4), (4,4), …

● I seguenti insiemi di coppie corrispondono a una funzione o no?

(0,1), (1,2), (2,3), (2,4), (3,5)

(0,1), (1,2), (3,2), (4,1)

Rango di una funzione

Chiamiamo rango l’insieme dei valori di una funzione.

D C

Dominio Codominio

Rango

Funzioni suriettive

Definizione. Una funzione f : D × C si dice suriettiva sse il suo rango coincide con l’intero codominio C, ovvero:

per ogni y C esiste sempre un x D

tale che f(x) = y

Funzioni iniettive

Definizione. Una funzione f : D × C si dice iniettiva sse a elementi distinti del dominio corrispondono elementi distinti del codominio, ovvero:

per ogni x1, x2 D,

se x1 x2 allora f(x1) f(x2 )

Funzioni biiettive

Definizione. Una funzione suriettiva e iniettiva si dice biiettiva (o corrispondenza biunivoca)

Esercizio: dimostrare che una funzione suriettiva e iniettiva non può non essere una corrispondenza biunivoca.

Funzione inversa

Definizione. Data una funzione biiettiva f : D × C, si dice funzione inversa di f (e si scrive f-1) la funzione f-1 : C × D tale che:

f-1(y) = x sse f(x) = y

Dimostrare che una funzione non biiettiva in genere non può avere una funzione inversa.

Funzione identità

Definizione. Dato un qualsiasi insieme D, la funzione f : D × D si dice funzione identità sse:

f(x) = x

La funzione identità di indica con ιD

Funzione composta

Definizione. Date due funzioni f : A B e g : B C (ovvero, il codominio della prima è dominio della seconda), si può definire una funzione h : A C tale che, per ogni a A, h(a) = g(f(a)).

Tale funzione h è chiamata funzione composta di f e g.

La funzione composta di f e g si indica anche con la notazione f g

Osservazione

Data una funzione biiettiva f : D C, essa può sempre essere composta con a sua inversa f-1 e si ottiene quanto segue:

f-1 f = ιD e f f-1 = ιC

Funzioni calcolabili

Definizione. Dato un algoritmo A, si dice che esso calcola una funzione f : D C sse, per ogni x D, f(x) = y sse A produce l’output y dato x come input.

Definizione. Si dice che una funzione è calcolabile in modo algoritmico (o effettivamente calcolabile) sse esiste un algoritmo che la calcola.

Funzioni e algoritmi

● Una funzione non va confusa con l’algoritmo che la calcola!

● La stessa funzione può essere calcolata da molti algoritmi diversi.

Esercizio: scrivere almeno due algoritmi per riordinare un array di elementi.

Predicati e relazioni come funzioni

Cos’è una proprietà? Cos’è una relazione tra oggetti? Domande che hanno torturato i logici per millenni …

G. Frege ha dato una risposta che ha rivoluzionato la logica del ‘900.

Proprietà come funzioni

Dato un dominio D di oggetti, una proprietà può essere definita come:

P : D V, F

Intuizione: per ogni x D– se P(x) = V, allora x ha la proprietà P– se P(x) = F, allora x non ha la proprietà P

Proprietà come sottoinsiemi di D

Ma allora una proprietà coincide con il sottoinsieme A di D tale che:

A = x D | P(x) = V

Una funzione come P(x) viene chiamata una funzione proposizionale.

NB: se D è infinito, le proprietà sono strettamente più numerose delle funzioni proposizionali!

Relazioni come funzioni

Dati due insiemi D1 e D2, una relazione può essere definita come una funzione:

P : D1 × D2 V, F

Intuizione: per ogni <d1,d2> D1 × D2,

– se R(d1,d2) = V, allora d1 è in relazione R con d2

– se R(d1,d2) = F, allora d1 non è in relazione R con d2

Relazioni come sottoinsiemi di D1 × D2

Ma allora una proprietà coincide con il sottoinsieme A di D1 × D2 tale che:

A = <d1,d2> D1 × D2 | R(d1,d2) = V

Se D1 e D2 sono lo stesso insieme, allora si dice che R D2

Il tutto si può generalizzare a funzioni n-arie.

Decidibilità di proprietà

Definizione. Una proprietà è decidibile rispetto a un insieme D sse esiste un algoritmo che, per ogni x D, sia in grado di stabilire se x ha non ha la proprietà in questione.

Esempi di proprietà decidibili:– n è un numero pari, n è un numero primo, …

– x è una tautologia in logica proposizionale

Decidibilità di relazioni

Definizione. Una relazione è decidibile rispetto a un dominio D sse esiste un algoritmo che, per ogni x,y D, sia in grado di stabilire se x e y sono o non sono nella relazione in questione.

Esempi di proprietà decidibili:– Nel dominio dei numeri naturali: m è maggiore di maggiore

di n, m è il quadrato di n, …

– In logica proposizionale: x è conseguenza logica di Γ

Decidibilità di insiemi

Definizione. Una insieme A in un dominio D è decidibile sse lo è la relazione di appartenenza ad A, cioè se esiste un algoritmo che, per ogni x D, sia in grado di stabilire se x appartiene o meno all’insieme A.

Osservazione

La decidibilità di proprietà e relazioni è riconducibile alla decidibilità dei corrispondenti insiemi.

Esempi:– “x è pari” è decidibile sse lo è l’insieme:

P = x N | x è pari– “x è minore di y” è decidibile sse lo è l’insieme:

M = <x,y> N2 | x è minore di y

Decidibilità e calcolabilità

Esiste un’ovvia relazione tra calcolabiltà delle funzioni e decidibilità dei predicati (relazioni).

Infatti, il problema di stabilire se un predicato (o una relazione) è decidibile può essere ricondotto alla calcolabilità della corrispondente funzione caratteristica.

Funzioni caratteristiche

Sia R(x1, …, xn) una relazione a n argomenti.

La sua funzione caratteristica è una funzione fR

con lo stesso numero di argomenti, avente come codominio l’insieme 0,1, così definita:

0 se R(x1, …, xn) è verafR (x1, …, xn) = 1 se R(x1, …, xn) è falsa

Se R è decidibile, allora fR è calcolabile (e viceversa)

… e perciò …

… è sufficiente limitarsi a trattare il problema della calcolabilità delle funzioni. Infatti:

Un predicato è decidibile

sse

la sua funzione caratteristica è calcolabile

Funzioni di codifica

Definizione. Dato un insieme A, si dice codifica di A una qualsiasi funzione φ : A N che sia iniettiva, calcolabile e tale che sia calcolabile anche la funzione inversa φ-1

Iniettività: garantisce che a elementi diversi di A corrispondano diversi numeri naturali

Calcolabilità: garantisce che la codifica (decodifica) sia effettiva.

Calcolabilità e funzioni aritmetiche

Una funzione è calcolabile sse lo è la funzione aritmetica sui rispettivi codici.

φ φ-1codifica decodifica

dominio valori di

numericodice

funzione generica

funzione aritmeticaχ

valori di χ

Funzioni parzialiDefinizione. Una funzione φ : D C si

dice parziale sse associa uno ed un solo elemento di C a ciascun elemento di un sottoinsieme E di D, detto campo di esistenza.

D C

Dominio Codominio

Rango

Campodi

esistenza

… inoltre …

● Se x D – E, si dice che φ è indefinita in x, e si scrive φ(x) =

● Se φ(x) = , allora si dice che φ diverge in x

● Se x E, allora φ(x) apparterrà a C e si dice che φ converge in x

…

● Le funzioni totali sono funzioni parziali il cui E coincide con D

● La funzione totalmente indefinita è una funzione il cui campo di esistenza è

● L’inversa di una funzione iniettiva φ è normalmente una funzione parziale in cui E coincide con il rango di φ [questo è il tipico caso delle funzioni di codifica!]

Calcolabilità delle funzioni parziali

Definizione. Una funzione parziale φ : D C con campo di esistenza E è effettivamente calcolabile sse esiste un algoritmo A tale che:

a) se x E e φ(x) = y, allora A con input x produce y come output

b) se x D - E (ossia φ(x) = ), allora A con input x non produce alcun output

Cosa vuol dire “non produce nessun output”?Se x D - E (cioè φ(x) = ), un

algoritmo A per φ con input x può comportarsi in due modi diversi:

i. A termina senza dare alcun risultato

ii. A non termina mai

Cfr. esempi in Figura 2.7 (pag. 79).

Conseguenza

Una funzione parziale per la quale esiste un algoritmo che termina sempre sui valori indefiniti può sempre essere trasformata in una funzione totale come segue:

1. se x E e φ(x) = y, allora l’output di un algoritmo A che calcola φ sarà y

2. se x D – E, allora l’output di A sarà un qualsiasi valore convenzionale *

Se tutte le funzioni parziali fossero così, non ci sarebbe bisogno di introdurre le funzioni parziali!!

Invece …

… non sempre questo “gioco” si può fare.

Immaginiamo di estendere una funzione parziale calcolabile φ a una funzione totale φ’ che:

1. Se φ è definita per x, e φ(x) = y, allora φ’(x) = y

2. Se φ è indefinita per x, e quindi φ(x) = , allora φ’(x) = *

Problema: φ’ potrebbe non essere più calcolabile!

Com’è possibile?

Immaginiamo che il campo di esistenza E corrisponda a un insieme di numeri non decidibile

Allora, stabilire se un certo input x appartiene o non appartiene ad E non è un problema decidibile

Come vedremo meglio, esistono insiemi di numeri che non sono decidibili

Per cui in generale non è possibile ridurre le funzioni parziali a funzioni totali

Insiemi effettivamente enumerabili

Definizione. Un insieme I contenuto in un dominio D si dice effettivamente enumerabile sse (i) I è l’insieme vuoto, oppure (ii) I è il rango di una funzione calcolabile totale di tipo φ : N I.

Cioè, φ associa ad ogni numero naturale un elemento di I (le ripetizioni sono ammesse). Pertanto, la successione φ(1), φ(2), φ(3), … contiene tutti e soli gli elementi di I.

Si dice che φ enumera in modo effettivo gli elementi di I.

Predicati effettivamente enumerabili

Definizione. Un predicato P(x) è effettivamente enumerabile se lo è l’insieme A = x D | P(x)

Questa definizione si può facilmente estendere alle relazioni con qualunque numero di argomenti

Osservazione

● Se un insieme I (o un predicato P) è decidibile, allora è anche effettivamente enumerabile

… tuttavia …

… non necessariamente vale il viceversa!!

Esistono infatti insiemi I effettivamente enumerabili che non sono decidibili.

[Esempi saranno presentati più avanti]

Semi-decidibilità

Un insieme A è effettivamente enumerabile sse la sua funzione caratteristica fA è calcolabile parziale con campo di esistenza A:

0 se x AfA (x) =

se x A (indefinito)

Siccome il corrispondente algoritmo calcola un valore solo nel caso positivo, si dice che gli insiemi (predicati) effettivamente enumerabili sono semi-decidibili.