Fondamenti di Informatica, 02 Febbraio 2011 A.A. 2010/11

Non e' ammesso l'uso di alcun testo, appunti o calcolatrici. 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, comunicatelo immediatamente al docente o all'assistente in aula.
  • I risultati verranno indicati nella pagina web del corso. Date ed orari degli orali, sul Forum.


    • Esercizio 1
    (a) Fornire la definizione di sistema formale e di regola di inferenza ammissibile.
    __________
    (b) Cosa significa, nel calcolo proposizionale (logica proposizionale), che una formula A e' conseguenza tautologica di un insieme di formule Gamma ( Gamma |= A) ?
    E' vera la seguente affermazione?
    p -> (p -> q) |= p -> q
    dove p e q sono variabili proposizionali.
    Giustificare la risposta. Risposte senza giustificazione non verranno valutate.
    __________
    (c) Consideriamo la segnatura che non abbia alcun simbolo di funzione e che abbia i seguenti simboli di predicato (relazione): {P,Q}, dove P e' binario e Q e' ternario.
    Si consideri la struttura che ha come supporto l'insieme dei numeri naturali ed in cui P corrisponda alla relazione "≤" tra naturali e Q corrisponda alla seguente relazione ternaria tra numeri naturali: {(n,m,p) | n+m=p}.
    Quali delle seguenti formule sono vere nella struttura data? 
    forall x. forall y. forall z.(Q(x,y,z) -> Q(y,x,z))

(forall x. exists y. P(x,y)) -> forall x. Q(x,x,c)
    Giustificare la risposta. Risposte senza giustificazione non verranno valutate.
    Esercizio 2
    (a) Fornire la definizione di espressione regolare e di automa a stati finito deterministico.
    __________
    (b) Scrivere l'espressione regolare, sull'alfabeto {0,1}, che denota il linguaggio L formato da tutte le stringhe che contengono la stringa 00 come prefisso oppure la stringa 110 come suffisso.
    Costruire l'automa a stati finiti che riconosce L.
    Definire la grammatica regolare che genera L.
    __________
    (c) Fissato un numero k qualsiasi, il seguente linguaggio e' regolare?
    {anbm | n ≥k, m≥ k}
    E questo?
    {akbncm | n ≥0, k≤ n, n≤ m}
    Giustificare le risposta. Risposte senza giustificazione non verranno valutate.
    Esercizio 3
    Dimostrare che nella codifica in complemento a due dei numeri interi la rappresentazione dei i numeri positivi ha "0" come cifra piu' a sinistra, mentre quella dei numeri negativi "1".