Fondamenti di Informatica, 28 Febbraio 2022

· 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.