Fondamenti di Informatica (parte Barbanera)
17 Giugno 2021

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, sulla chat pubblica di Teams del corso.

    • (a) Enunciare il teorema di Confluenza e dimostrare la proprieta' di unicita' delle forme normali per il lambda-calcolo.

    (b) La seguente e' una deduzione incompleta in deduzione naturale per la seguente proposizione:
    (A → B) → (¬¬A → ¬¬B). 
                        [A]1   [      ]4
                    ---------------- 
          [    ]2           B
        ----------------------- 
                
             --------- [1]
  [¬¬A]3      
 ------------------- 
           ⊥
        ------- [2]
          
      ----------- [3]
       ¬¬A → ¬¬B
  --------------------- [ ]
  (A → B) → (¬¬A → ¬¬B)
    Ricopiare e completare la deduzione.

    (c) Cosa significa, nel calcolo proposizionale (logica proposizionale), che una formula A e' conseguenza tautologica di un insieme di formule Γ ( Γ ⊨ A) ?
    E' vera la seguente affermazione (dove p e q sono variabili proposizionali)?
    p → (p → q) ⊨ p → q
    Giustificare la risposta.


    (d) Dimostrare in deduzione naturale la seguente fbf della logica dei predicati.
    ∀x.(A(x) → B(x)) ⊢ ¬(A(c) ∧ ¬B(c)).