Fondamenti di Informatica, 12 Dicembre 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 NECESSARIAMENTE essersi prenotati sul portale studenti del nostro ateneo.
  • I risultati verranno indicati nella pagina web del corso. Date ed orari degli orali, sul Forum.


    • Esercizio 1
    (a) Si fornisca la definizione di formula ben formata valida nella logica del primo ordine.
    Si dimostri che la seguente formula, su una segnatura che contenga i simboli di predicato unari A e B, non e' valida:

    (∃x.A(x)→∃x.B(x)) →(∃x.A(x)∧B(x))

    (b) Si consideri il linguaggio con uguaglianza su una segnatura che abbia {00, succ1,+2, ∗2} come simboli di funzione. Supponendo che questi simboli di funzione siano interpretati col loro significato standard sul dominio dei numeri naturali, si fornisca una formula ben formata che abbia z ed y come variabili libere e che esprima la seguente frase
    “z e' dispari e minore di y”.
    (si osservi che < non fa parte del linguaggio).

    (c) Dimostrare nella logica dei predicati, nel sistema di deduzione naturale, che
    (∀x. (A→B)) → ( (∀x.A) → (∀y.B))
    Esercizio 2
    (a) Fornire formalmente la definizione di derivazione diretta in una grammatica, quella di derivazione e quella di linguaggio generato da una grammatica.
    (b) Fornire l'automa a stati finiti che riconosca il seguente linguaggio
    {s∈{0,1}* | s rappresenta un numero dispari in notazione posizionale binaria}.

    (c) Dimostrare che il linguaggio {ahbk | h,k≥0 , h>k } non e' regolare.
    Esercizio 3
    Fornire la rappresentazione in base nove del numero rappresentato in base tre dalla seguente sequenza di cifre
    10002102
    Non si deve passare dalla rappresentazione in base 10.
    Giustificare la risposta nel modo piu' completo possibile.