Fondamenti di Informatica, 11 Settembre 2019

Non e' ammesso l'uso di alcun testo, appunti, calcolatrici, telefonini o smartphone (questi ultimi vanno riposti lontano dalla propria persona). Le risposte vanno scritte nel foglio di bella copia. Si raccomanda la massima SINTETICITA'. L'eccessiva verbosita' verra' considerata negativamente.
Per sostenere l'esame e' obbligatorio essersi prenotati sul portale studenti del nostro ateneo. Elaborati di studenti non prenotati NON verranno valutati.
I risultati verranno indicati nella pagina web del corso. Date ed orari degli orali, sul Forum.

Esercizio 1
(a) Cos'e' un modello computazionale? Definire il modello computazionale delle Macchine di Turing.
(b) Sia data la rete stradale in figura.

        a       b      c
   A------->o------->o---->B
    \       |        ^\           
     \      |       /  |      
      \d    |     f/   |
       \   e|     /    |
        \   |    /     |
         \  |   /     g|
          \ |  /       |
           v| /        |
            v/    h    v
            o<---------o

Fornire l'espressione regolare che rappresenta il linguaggio di tutti i percorsi da A a B (inclusi i cicli).
(c) I termini

(λxxxx.xx)(λx.xx)(λx.x)y((λx.x)x)

(λb.λa.λc.λd.λx.xx)(λx.xx)(λx.x)z((λw.w)x)

possono essere considerati identici? Giustificare la risposta.

Esercizio 2
(a) Enunciare e dimostrare il Teorema di Deduzione di Herbrand.
(b) Nella logica dei predicati del primo ordine (calcolo dei predicati), si specifichi una segnatura Σ, una struttura A_Σ e le due formule ben formate vere in A_Σ, corrispondenti alle due seguenti affermazioni:

Il quadrato di un numero naturale maggiore di due è maggiore del suo doppio

Alcuni parenti di Carlo sono anche parenti di Bruno, ma non di Alberto

(c) Quella che segue e' una dimostrazione incompleta, in logica proposizionale (calcolo proposizionale), di P, che utilizza l'ipotesi ¬¬P ed il teorema, che supponiamo gia' dimostrato, ¬P→¬P.
Ricopiare e completare tale dimostrazione.

1. .............             (Ak)
2. .............             ipotesi
3. .............             MP(1,2)
4. .............             (A¬)
5. .............             MP(3,4)
6. ¬P→¬P                     teorema
7. .............             MP(5,6)

Ricordiamo che gli assiomi (Ak) e (A¬)sono:
(Ak) α → (β→α)
(A¬) (¬β →¬α)→((¬β →α) →β)

Esercizio 3
Fornire la rappresentazione in base nove del numero rappresentato in base tre dalla seguente sequenza di cifre

10002102

Non si deve passare dalla rappresentazione in base 10.
Giustificare la risposta nel modo piu' completo possibile.