Fondamenti di Informatica, 12 Dicembre 2017

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.
Per sostenere l'esame e' obbligatorio essersi prenotati sul portale studenti del nostro ateneo. Elaborati di studenti non prenotati NON verranno valutati.

I risultati verranno indicati nella pagina web del corso. Date ed orari degli orali, sul Forum.

Esercizio 1
(a) Fornire le definizioni, nella logica proposizionale (calcolo proposizionale), di tautologia e conseguenza tautologica.
Accennare brevemente a come si puo' decidere se una formula e' una tautologia o meno.

(b) Fornire una deduzione nella logica proposizionale in deduzione naturale per il teorema

((A∧B) → C)) → (A → (B → C))

(c) Dimostrare che se Γ∪{α} e' contraddittorio allora Γ|- ¬α.

Esercizio 2
(a) Sia data la rete stradale in figura.

        a       b      c
   A------->o------->o---->B
    \       |        ^\           
     \      |       /  |      
      \d    |     f/   |
       \   e|     /    |
        \   |    /     |
         \  |   /     g|
          \ |  /       |
           v| /        |
            v/    h    v
            o<---------o

Fornire l'espressione regolare che rappresenta il linguaggio di tutti i percorsi da A a B (inclusi i cicli).

(b) Si consideri la grammatica G = <{a,b,c},{S,A},P,S>, dove P e'

S  → aSc | A
Ac → bA | ε

Dimostrare che L(G) = {aⁿb^mc^n-m | n>0, m>0, n≥m}

(c) Dimostrare che, dato un alfabeto non vuoto, esiste almeno un linguaggio su tale alfabeto non generabile da una grammatica di Chomsky.

Esercizio 3
Fornire la definizione di codice in complemento alla base B per i numeri interi.