Modelli simulativi
per 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 xD e un
elemento yC
Funzioni: Dominio e Codominio
D
C
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
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:
–
xD
–
yC
–
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
Rango
Dominio
Codominio
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:
fR (x1, …, xn) =
0

1
se R(x1, …, xn) è vera
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.
dominio
φ
funzione generica

codifica
numeri
codice
valori di 
decodifica
funzione aritmetica
χ
φ-1
valori di χ
Funzioni parziali
Definizione. 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
Campo
di
esistenza
Dominio
Rango
Codominio
… 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:
fA (x) =

0
se x  A

se x  A (indefinito)
Siccome il corrispondente algoritmo calcola un valore
solo nel caso positivo, si dice che gli insiemi
(predicati) effettivamente enumerabili sono semidecidibili.