Fondamenti di Informatica, 3 Ottobre 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) Data una segnatura Σ per la logica dei predicati, definire cosa e' una struttura AΣ per Σ.

    (b) Si consideri la seguente segnatura per la logica dei predicati con uguaglianza (e con tutti i quantificatori e connettivi logici): {{z0, exp2},{Nat1, <2}}.
    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


    (c) Fornire in deduzione naturale una derivazione per
    ∀x.(A(x)→B(x)), ∃x.¬B(x) |- ∃x.¬A(x)
    Esercizio 2
    (a) Sia G1 = {{a,b,c},{S,A,B},P,S} dove P = { S → AAdcc, S → bbScc, A → cc }
    Sia G2 = {{a,b},{S,A,B},P,S} dove P = { S → AAd, S → bbScc, aa → cAc }
    Sia G3 = {{a,b,c},{S,A,B},P,S} dove P = { S → AAaa, ccSaa → bbScc, A → cAc }
    Sia G4 = {{a,b,c},{S,A,B},P,S} dove P = { A → AAaa, B → bbScc, A → cBc }
    Dire se quelle sopra definite sono grammatiche di Chomsky. Dire eventualmente a quale classe di grammatiche appartengono. Giustificare le risposte. Risposte prive di giustificazione non verranno valutate.

    (b) Si consideri un insieme numerabile di simboli A e di dimostri che l'insieme delle stringhe di lunghezza finita di simboli di A e' un insieme numerabile. Lo si faccia descrivendo come sia possibile enumerare (cioe' come sia possibile costruire una lista infinita di) tutte e sole le strighe in questione.

    (c) Usare il metodo di Diagonalizzazione per dimostrare che ci sono funzioni calcolabili, da N in N, che non sono primitive ricorsive.
    Esercizio 3
    Definire formalmente il codice in complemento a due per i numeri interi.