1. Formalizzare le seguenti proposizioni, utilizzando la seguente interpretazione:
   

   Lettera proposizionale	Interpretazione
   A	Ada esce
   B	Bice esce
   C	Carla esce
   D	Daria esce

   1. Ada non esce
   2. Ada esce, ma non Bice
   3. Se Ada esce, anche Bice esce
   4. Ada esce se Bice esce
   5. Ada esce solo se Bice esce
   6. Ada esce se e solo se Bice esce
   7. Né Ada né Bice escono
   8. Ada e Bice non escono
   9. Ada non esce oppure Bice non esce
   10. Ada non esce se Bice esce
   11. Ada esce oppure Bice e Carla escono
   12. Se Ada esce, allora sia Bice che Carla escono
   13. Ada rimane a casa, ma Carla e Bice escono
   14. Se Carla esce, allora Ada rimane a casa e Bice esce
   15. Se né Carla né Bice escono, allora Ada esce
   16. Carla esce se e solo se Bice e Carla rimangono a casa
   17. Carla e Bice escono, sebbene Ada e Daria rimangono a casa
   18. Se né Carla né Bice escono, allora Ada esce e Daria rimane a casa
   19. Carla e Bice escono se e solo se Ada oppure Sara escono
   20. Se Daria esce, allora Carla oppure Ada escono, e se Daria non esce, allora sia Ada che Bice escono.
   
   
   
2. Determinare quali tra le seguenti espressioni sono fbf e quali no, motivando la risposta opportunamente (per ovvi motivi, in questo esercizio si deve usare la definizione "ufficiale" di fbf):
   1. not (not (P))
   2. (not (not (P)))
   3. P not Q
   4. (P implies Q)
   5. P implies Q
   6. ((P implies Q))
   7. (P and)
   
   
   
3. Dimostrare utilizzando le tavole di verità che le seguenti fbf sono tautologie:
   1. (not P or Q) implies not (P and not Q)
   2. ((P implies Q) and (P implies not Q)) implies not P
   3. ((P implies Q) and (P implies R)) implies (P implies (Q and R))
   4. (P implies Q) implies ((P and R) implies (Q and R))
   5. (P implies Q) implies ((P or R) implies (Q or R))
   6. (not P implies P) implies P
   7. not P implies (P implies Q)
   8. (P and Q) implies (P implies Q)
   
   
   
4. Svolgere il precedente esercizio utilizzando il sistema dei tableaux proposizionali al posto delle tavole di verità.
   
   
5. Per ciascuna delle seguenti formule, determinare se si tratta di tautologia, di contraddizione, oppure se si tratta di formula che non è né una tautologia né una contraddizione, giustificando opportunamente le risposte:
   1. not P implies (P implies not P)
   2. (P or Q) implies (P and Q)
   3. (P implies not Q) implies not (P and Q)
   4. P implies ((P implies (Q and P)) implies (P and Q))
   5. ((P or Q) and not P and not Q) implies R
   6. (((Q and R) implies P) and not Q and not R) implies not P
   7. ((P implies (R or S)) and ((R and S) implies Q)) implies (P implies Q)
   
   
   
6. Costruire gli alberi di derivazione e sintattici relativi alle fbf dell'esercizio III.
   
   
7. Trasformare le formule dell'esercizio III sia in forma normale congiuntiva che in forma normale disgiuntiva.
   
   
8. Definire per ricorsione strutturale una funzione che conti il numero di parentesi aperte e chiuse presenti in ciascuna fbf.
   
   
9. Definire per ricorsione strutturale una funzione che per ciascuna fbf X vale 1 se X non contiene alcun connettivo di negazione not, 0 altrimenti.
   
   
10. Dimostrare per induzione strutturale che in una qualunque fbf proposizionale, il numero di parentesi aperte in essa contenute è uguale al numero di connettivi proposizionali presenti in essa.