Fondamenti di Informatica, 1 Febbraio 2017

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.
  • 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) Fornire la definizione di grammatica formale. Fornire inoltre le definizioni di grammatica di tipo 0,1,2 e 3.
    (b) Definire una grammatica che generi il linguaggio {an bm cp | n = m ∨ m = p} e dimostrare la sua correttezza.
    (c) Costruire un automa a stati finiti che accetti il linguaggio sull'alfabeto {a,b} denotato dalla seguente espressione regolare: ((ab + a)(aa)*) + (ba)*
    Esercizio 2
    (a) Nella logica proposizionale (calcolo proposizionale), cos'e' un assegnamento proposizionale?
    Dato un assegnamento proposizionale B, definire la funzione B e la nozione di tautologia.
    (b) La seguente e' una dimostrazione non completamente specificata, nel sistema formale CL, di
    {k=sk} |-CL P=Q
    Ricopiarla inserendo le parti mancanti. 
    1.  ??            (ipotesi)
2.  ??            (assioma refl)
3.  kP = skP      (cong2)(1.2.)
4.  kPQ = kPQ     (assioma refl)
5.  kPQ = skPQ    (congr)(3.4.)
6.  ??            (Axk)
7.  ??            (symm) (5.) 
8.  skPQ = P      ??
9.  skPQ = kQ(PQ) (Axs)
10. kQ(PQ) = Q    (Axk)
11. skPQ = Q      (trans)(9.10.)
12. P = skPQ      ??
13. ??            ??
    dove gli assiomi e regole di CL sono: 
             -------(axk)   -------------(axs)
          kMN=M          sMNR=MR(NR)

  R=R'  RM=RN              M=N           M=N N=R                
---------------(cong2)    -----(symm)   ---------(trans)   ------(refl)
   RM=R'N                  N=M             M=R               M=M
    Quale proprieta' dell'insieme {k=sk} abbiamo dimostrato in questo modo?











    (c) Sia {{},{c1, g1, p2, a2}} una segnatura dove c e g sono simboli predicativi unari, mentre p e a sono simboli predicativi binari. Interpretando c(x) come "x e' un cane", g(x) come "x e' un gatto", p(x,y) come "x e' il padrone di y" e a(x,y) come "x ama y" traducete le seguenti frasi (scrivete cioe' le formule ben formate corrispondenti, avendo a disposizione entrambi i quantificatori e tutti i connettivi logici):

    (i) ogni cane non ama alcun gatto;
    (ii) tutti i cani e i gatti hanno un padrone;

    Scrivere inoltre, giustificando brevemente la risposta, la frase in italiano corrispondente alla seguente formula ben formata:
    ∀x.((c(x) ∧ ¬∃y.p(y,x)) → ∀z.¬a(z,x))

    Esercizio 3
    Calcolare la forma normale (mostrando la computazione eseguita) del lambda-termine
    and T T
    dove
    and e' λab.abF
    T e' λxy.x
    F e' λxy.y