LOGICA MATEMATICA

Claudia Malvenuto e Roberto Maieli^{∗} Canale E-O - a.a 2003/04 Scheda di esercizi n. 12

17 novembre 2003

Tableaux Semantici: caso proposizionale

Esercizio 1 Per ciascuna equivalenza A ≡ B presente nella scheda degli esercizi n.10, mostrare, ⊧ A ↔ B, via:

1. il teorema sull’equivalenza logica

A ≡ B se e solo se ⊧ A ↔ B,

2. ed usando il metodo dei tableaux, come procedura di decisione per la validità.

Esercizio 2 Verificare, usando il metodo dei tableaux, che i seguenti insiemi di enunciati non sono soddisfacibili:

{A ∨ B → C ∧ D, ¬C, A}, {A → B, (A → C) → D ∧ B, A ∧ B → C, ¬D, A}, {A ∨ B → C, B ∨ C → (A → (D ↔ E)), A ∧ D, ¬(D ↔ E)}, {(A ∨ ¬B) ∨ C, ¬A ∨ (¬A ∧ B), ¬(B → C)}, {A → B, B → (A → C ∨ D), C ↔ D, ¬(C ∧ D), A}, {A ∧ B → ¬C, C ∨ (D ∨ E), A ↔ B, ¬(A → D)}, {(A ∨ B) ∧ C, ¬D → ¬(B ∧ C), ¬B → (A → ¬E), E ∧ ¬D}.

∗Dipartimento di Informatica, Università di Roma “La Sapienza”, Via Salaria, 113.

E-mail: claudia, maieli@dsi.uniroma1.it.

Esercizio 3 Verificare, usando il metodo dei tableaux, che i seguenti insiemi di enunciati sono soddisfacibili:

{A, B ∨ (¬A ∧ C)}, {A → (C ↔ B), ¬(C → A)}, {A ↔ ¬B, C ↔ B, ¬A}, {A → B, C ↔ B, ¬C ∨ A}, {(A ↔ B) ∨ ¬(B ∧ C), ¬A → ¬B, ¬A, ¬C → ¬(B ∧ C)}.