Fondamenti di Informatica, 4 Febbraio 2015
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)
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.