Fondamenti di Informatica, 6 Luglio 2015

Non e' ammesso l'uso di alcun testo, appunti, calcolatrici, telefonini o smartphone. 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, comunicarlo immediatamente al docente o all'assistente in aula ed indicarlo chiaramente sull'elaborato che si consegna.
  • I risultati verranno indicati nella pagina web del corso. Date ed orari degli orali, sul Forum.


    • Esercizio 1
    (a) Cos'e' il λ-calcolo? Definire formalmente l'insieme dei λ-termini, l'insieme delle variabili libere di un termine, l'operazione di sostituzione e la relazione di β-riduzione.

    (b) Nel contesto del λ-calcolo, enunciare il Teorema di Church-Rosser ed utilizzarlo per dimostrare il Corollario di Unicita' della forma normale.

    (c) Fornire il λ-termine che rappresenta l'operatore booleano OR, in modo diretto oppure utilizzando l'operatore IF_THEN_ELSE. In entrambi i casi, giustificare la risposta.
    (Ricordiamo che l'operatore IF_THEN_ELSE si rappresenta con λz.z, il valore TRUE con λx.λy.x e il valore FALSE con λx.λy.y).
    Esercizio 2
    (a) 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: (b) Descrivere, nel linguaggio dell'aritmetica di Peano, le formule ben formate P(x) e Q(x,y,z) corrispondenti, rispettivamente, alle seguenti relazioni sui numeri naturali:
    (c) Fornire una deduzione nella logica proposizionale in deduzione naturale per il teorema `
    ((A∧B) → C)) → (A → (B → C))
    Esercizio 3
    Cosa si intende per Macchina di Turing Universale? Descriverne informalmente il comportamento.