Corso di Logica Matematica
Anno accademico 2009/2010
Tableau proposizionali
Esercizi
1. Sulla base dei risultati di correttezza e completezza enunciati a lezione, il metodo dei tableau proposizionali risulta essere un metodo effettivo per decidere se una proposizione `e una tautologia o meno.
Usando il metodo dei tableau proposizionali, risolvere gli esercizi seguen- ti (tali esercizi erano stati precedentemente proposti nell’ambito del cal- colo proposizionale mediante tavole di verit`a o derivazione nel sistema formale K):
(a) Esercizio Foglio 1 N.o 3 (b) Esercizio Foglio 1 N.o 4 (c) Esercizio Foglio 1 N.o 5 (d) Esercizio Foglio 1 N.o 6 (e) Esercizio Foglio 2 N.o 1
(risulta qui utile il teorema di deduzione del sistema formale K) 2. Usando il metodo dei tableau proposizionali, stabilire se le seguenti
conseguenze logiche sono corrette:
(a) P ∨ ¬R, P → Q, R |= Q (b) ¬P ∧ ¬Q, P ∨ Q |= R
1
(c) P → (Q → (P → Q)) |= Q → (P → (Q → P )) (d) (P → Q) → (Q → P ) |= (P ↔ Q) ∨ (¬Q ∨ P )
(e) (P ↔ Q) ∨ (¬Q ∨ P ) |= (P → Q) → (Q → P )
(f) P → Q, P ∨ (R ∧ Q), S → ¬R, ¬(P ∧ Q) |= ¬S ∨ ¬Q
3. Usando il metodo dei tableau proposizionali, stabilire se i seguenti ragionamenti sono logicamente corretti:
(a) Se Paolo `e il colpevole, allora almeno uno tra Andrea e Sergio era assente. Se Andrea era assente, allora Paolo non `e il colpevole. Se Luca era sveglio, allora Sergio non era assente. Quindi, se Paolo
`e il colpevole, allora Luca non era sveglio.
(b) Esercizio Foglio 1 N.o 7 (c) Esercizio Foglio 1 N.o 8 (d) Esercizio Foglio 1 N.o 9
2