Fondamenti di Informatica, 20 Settembre 2022

Non e' ammesso l'uso di alcun testo, appunti, calcolatrici 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.
  • 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: (c)
    Fornire una prova in deduzione naturale a cui sia possibile associare il lambda-termine che codifica il numerale di Church 1
    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)
    Dimostrare che il linguaggio {ahbk | h,k≥0 , h>k } non e' regolare.
    (c)
    Definire una grammatica che generi il linguaggio {an bm cp | n = m ∨ m = p} e dimostrare la sua correttezza.

    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.