Fondamenti di Informatica, 6 Settembre 2021

Non e' ammesso l'uso di alcun testo, appunti, calcolatrici, telefonini o smartphone (questi ultimi vanno riposti lontano dalla propria persona). 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, sulla chat pubblica di Teams del corso.

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.