Post on 01-May-2015
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.