Fondamenti di Informatica, 13 Dicembre 2014

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.
Occorre essersi prenotati sul portale studenti del nostro ateneo. Se cio' non e' stato fatto, comunicarlo immediatamente al docente o all'assistente in aula ed indicarlo chiaramente sull'elaborato che si consegna.

I risultati verranno indicati nella pagina web del corso. Date ed orari degli orali, sul Forum.

Esercizio 1
(a) Data una segnatura Σ per la logica dei predicati del primo ordine, definire l'insieme dei termini sulla segnatura Σ (Term_Σ) e l'insieme delle formule ben formate (Fbf_Σ).
Data inoltre una struttura A_Σ ed una formula ben formata α in Fbf_Σ, si dica quando α e' soddisfacibile in A_Σ, α e' vera in A_Σ (valida in A_Σ), α e' valida (o vera), α e' contradittoria.

(b) Sia {{I⁰, F⁰}, {f¹, s², a²} } una segnatura dove 'I' e 'F' sono simboli di costante, 'f' e' un simbolo di relazione unario, e 's' e 'a' sono simboli di relazione binari. Interpretando I e F come "Italia" e "Francia", f(x) come "x e' un film", s(x, y) come "x e' uno spettatore del paese y", a (x, y) come "x ama y", si traducano le seguenti frasi (si scrivano cioe' le formule ben formate corrispondenti):

ogni film non e' amato da uno spettatore italiano o francese;
nessuno spettatore francese ama tutti i film;
qualche spettatore italiano ama solo film che la Francia non ama.

(c) 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.

Esercizio 2
(a) Fornire la definizione di codice in complemento a due per numeri interi ed un semplice algoritmo per passare dalla rappresentazione in complemento a due di un numero n a quella di -n.

(b) Definire alcuni codici ad espansione.

(c) Giustificare formalmente la correttezza del seguente algoritmo di conversione da base 4 a base 2:
Si sostituisce ogni cifra della rappresentazione in base 4 con la coppia di cifre binarie che rappresenta, in base 2 il numero associato alla cifra della base 4. (Es.: (322)₄ = (111010)₄)

Esercizio 3
Cos'e' la Logica di Hoare? A cosa serve? Descrivere qualche regola della logica di Hoare per il linguaggio WHILE, fornendone una giustificazione informale.