Fondamenti di Informatica (parte Barbanera), 28 Gennaio 2020

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.

(a) Dire qual e' il risultato della seguente sostituzione:

((λy.xy)(λz.y(λy.x)))[xyz/x]

(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) Si consideri la seguente segnatura per la logica dei predicati con uguaglianza (e con tutti i quantificatori e connettivi logici): {{z⁰, exp²},{Nat¹, <²}}.
Si consideri inoltre la struttura che abbia come supporto i numeri reali ed in cui il simbolo di funzione z venga interpretato con il numero 0, exp con la funzione di elevamento a potenza, il predicato Nat con il predicato essere un numero naturale e il predicato < con minore stretto.
Si fornisca la formula ben formata la cui interpretazione in tale struttura corrisponda alla seguente affermazione.

Siano a un numero reale non negativo e n un numero naturale.
Allora esiste uno ed un solo numero reale non negativo b tale che b alla n e' uguale ad a

(d) Estendere il linguaggio WHILE con un'istruzione if then else, specificando informalmente la sua semantica e formalizzando poi questa con assiomi e/o regole di inferenza.