Sistemi di analisi per il linguaggio naturale

3 1 Funzioni ricorsive 1.1 Introduzione di alcune nozioni di base Def.1: una funzione f da A a B (dove A e B sono insiemi) è un sottoinsieme di A× B (il prodotto cartesiano di A e B, ovvero l’insieme delle coppie ordinate, <a, b>, tali che a∈ A e b∈ B) tale che ad elementi di A corrisponde uno ed un solo elemento di B, f(a)=b. Scriveremo f(a)=b, dove a∈ A e b∈ B, per indicare che b è il valore assunto da f per a quale argomento. Una tale funzione f applica A in B, scriveremo in tal caso f : A!B. Una funzione è un assegnamento di valori ad argomenti. L’insieme di tutti gli argomenti cui la funzione assegna un valore è chiamato dominio della funzione. L’insieme di tutti quei valori che la funzione assegna ai suoi argomenti è chiamato codominio (range) della funzione. Una funzione f ⊆ A× B, definisce un insieme { <x, y>| f(x)=y} . Def. 2: Se f è tale che f(a)=b per ogni b∈ B, diciamo che la funzione è suriettiva. Def. 3: Se f è tale che per ogni a, a’∈ A, f(a)=b e f(a’)=b, allora a = a’, diremo che la funzione è iniettiva, ovvero fa corrispondere ad elementi distinti di A, elementi distinti di B. Def. 4: Una funzione che sia iniettiva e suriettiva insieme si dice biettiva, e stabilisce una corrispondenza ad uno ad uno tra A e B. Se f è una funzione biettiva, sarà sempre possibile trovare l’applicazione inversa f - 1 da B ad A. Se f : A!B è un’applicazione biettiva, si dice che c’è una corrispondenza biunivoca tra A e B. Def. 5: Due insiemi in corrispondenza biunivoca si dicono equipotenti, cioè hanno la stessa cardinalità (ovvero lo stesso numero di elementi). Se A e B sono insiemi finiti e A⊂ B, non si potrà mai stabilire una corrispondenza biunivoca tra gli elementi di A e quelli di B. Def. 6: Un insieme è infinito sse può essere messo in corrispondenza biunivoca con un suo sottoinsieme proprio. Ad esempio l’insieme dei quadrati è un sottoinsieme dei numeri naturali eppure esso è definito dalla biezione, in N× N, f(x) = x 2 .