Fondamenti di Informatica, 4 Aprile 2023

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:

• x e' un numero dispari
• z e' il minimo comune multiplo di x e y

(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 {a^hb^k | h,k≥0 , h>k } non e' regolare.
(c)
Definire una grammatica che generi il linguaggio {aⁿ b^m c^p | 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.