Fondamenti di Informatica, 5 Ottobre 2011

Non e' ammesso l'uso di alcun testo, appunti o calcolatrici. Le risposte vanno scritte nel foglio di bella copia. Si raccomanda la massima SINTETICITA'. L'eccessiva verbosita' verra' considerata negativamente.
Occorre essersi prenotati sul portale studenti del nostro ateneo. Se cio' non e' stato fatto, comunicatelo immediatamente al docente o all'assistente in aula.

I risultati verranno indicati nella pagina web del corso. Date ed orari degli orali, sul Forum.

Esercizio 1
(a)
Sia {{a,b},{c²,p²} una segnatura dove a e b sono simboli di costante, mentre c e p sono simboli predicativi binari. Interpretando a come "Antonella", b come "Bruno", c(x, y) come "x conosce y", p(x, y) come "x e' parente di y", traducete le seguenti frasi (scrivete cioe' le formule ben formate corrispondenti):
(i) Bruno ha un parente che conosce qualcuno;
(ii) un parente di Bruno conosce tutti quelli che non sono conosciuti da Antonella;
(iii) se un parente di Antonella conosce Bruno, Bruno conosce tutti quelli che conoscono Antonella.
(b)
Sia α una formula ben formata della logica dei predicati del prim'ordine (calcolo dei predicati) rispetto una data segnatura Σ e sia A_Σ una struttura.
Dare le definizioni di:

α e' soddisfacibile in A_Σ
α e' vera in A_Σ
α e' soddisfacibile
α e' valida (o vera)
α e' contraddittoria

(c)
Consideriamo la segnatura Σ={{},{r²}}.
Sia α la formula ben formata ∀x. ∃y. (r(x, y) ∧ ¬r(y, x)) .
(i) Dimostrate che non esiste una struttura A_Σ tale che il supporto di A_Σ sia l'insieme {0,1} e tale che α sia vera in A_Σ
(ii) Costruite un'interpretazione A_Σ tale che α sia vera in A_Σ

Esercizio 2
(a)
Cos'e' la Teoria della Ricorsivita'? Enunciare inoltre la Tesi di Church.
(b)
Definire la classe delle funzione primitive ricorsive e quella delle funzioni parziali ricorsive.
(c)
Enunciare il Problema della fermata e dimostrarne l'insolubilita'.

Esercizio 3
Dimostrare che il linguaggio {aⁿbⁿ | n ≥0} non e' regolare