Fondamenti di Informatica, 31 Gennaio 2012

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)
    Descrivere il sistema formale del Calcolo Proposizionale (Logica Proposizionale) e descrivere brevemente come si puo dimostrare nel Calcolo proposizionale che Γ |- α, dove α e'una fbf e Γ un insieme di fbf.
    (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: Sia R la seconda relazione. E' vera la seguente affermazione?
    (n,m,p)∈R   se e solo se   PA|- Q(n,m,p)
    Perche?

    (c)
    Fornire una prova in deduzione naturale a cui sia possibile associare il lambda-termine che codifica il numerale di Church 2
    Esercizio 2
    (a)
    Costruire un automa a stati finiti che accetti il linguaggio sull'alfabeto {a,b} denotato dalla seguente espressione regolare:
    ((ab + a)(aa)*) + (ba)*
    (b)
    Costruire una MT che calcoli la seguente funzione sui numeri naturali:    f(n) = n div 2
    Dove div e' la divisione intera.
    (c)
    Dimostrare che, dato un alfabeto non vuoto, esiste almeno un linguaggio su tale alfabeto non generabile da una grammatica di Chomsky.

    Esercizio 3
    Dato il seguente termine, cerchiare le sue variabili libere e collegare, utilizzando delle frecce, le sue variabili legate con i lambda relativi.

    λz.( ((λx.λx.yx)x)(vλz.λw.v) )

    Sottolinare inoltre i redessi (redex) presenti in tale lambda-termine.