Fondamenti di Informatica, 26 Febbraio 2016

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) Nel contesto della Logica del Primo Ordine (Calcolo dei Predicati), fornire le definizioni di Segnatura, Termine e Formula Ben Formata (fbf).

    (b) Siano P e Q simboli di predicato unari. Dimostrare in deduzione naturale il teorema
    ∀x.(P(x)→Q(x)) → (∀x.P(x)→∀x.Q(x))
    Si dimostri inoltre che
    ∀x.(P(x)→Q(x)) → (∀x.P(x)→∀x.Q(x))
    non e' un teorema.

    (c) Enunciare e commentare brevemente il II Teorema di Incompletezza di Goedel

    Esercizio 2
    (a) Descrivere brevemente il modello computazionale del λ-calcolo.

    (b) Rinominare le variabili legate del seguente termine, in modo che non ci siano due astrazioni che legano variabili con lo stesso nome.

    (λx.xxy)(λxy.xyy)

    Qual e' il termine che si ottiene eseguendo due beta-riduzioni sul termine fornito?

    (c) Enunciare il Problema della fermata e dimostrarne l'insolubilita'.

    Esercizio 3
    Sia data la seguente stringa di 6 cifre binarie:

    110000

    Trovare il valore della stringa interpretata come intero senza segno (numero naturale), e come intero negativo in complemento a due. Convertire in base 8 i valori assoluti dei numeri ricavati nei due casi precedenti, e sommarli, restituendo il risultato in notazione posizionale binaria.
    Giustificare brevemente il procedimento utilizzato per ottenere i vari risultati.
    (N.B.:Risultati non giustificati non verranno valutati).