02 05 2011

Page 1

LOGICA ED ALGEBRA I PROVA IN ITINERE 2 maggio 2011 ESERCIZIO 1 Si consideri la seguente tavola di verità A B C f (A, B, C ) _________________________________________ 1 1 1 0 1 1 0 0 1 0 1 1 1 0 0 0 0 1 1 1 0 1 0 0 0 0 1 1 0 0 0 0 a) Si trovi una formula f(A,B,C) che contenga solo i connettivi ∼ e ⇒ che abbia come tavola di verità quella data. b) Si dica se esiste la deduzione f(A,B,C) |- L (A ⇒ ∼B) ∧ ( B ⇒ C ) c) Si dica se l’insieme {f(A,B,C) , ∼ ( B ⇒ C )} è insoddisfacibile. d) Si dimostrino i risultati trovati ai punti b) e c) utilizza ndo la risoluzione. Si può affermare che esiste una risoluzione lineare di questi risultati? Ed una risoluzione lineare per input? Traccia di soluzione a) f(A,B,C) ≡ (A ∧ ∼B ∧ C) ∨ ( ∼A ∧ B ∧ C) ∨ ( ∼A ∧ ∼B ∧ C) ≡ ≡( (A ∧ ∼B) ∨ ( ∼A ∧ B) ∨ ( ∼A ∧ ∼B) ) ∧ C ≡ ( (A ∧ ∼B) ∨ ( ∼A ∧ (B ∨ ∼B) ) ) ∧ C ≡ ( (A ∧ ∼B) ∨ ∼A) ∧ C ≡ ( (A ∨ ∼A) ∧ ( ∼B ∨ ∼A) ) ∧ C ≡ ( ∼B ∨ ∼A) ∧ C ≡ ≡ ∼ ( ∼ ( ∼B ∨ ∼A) ∨ ∼C) ≡ ∼ ( ∼ (A ⇒ ∼B) ∨ ∼C) ≡ ∼ ((A ⇒ ∼B) ⇒ ∼C) b) Per il teorema di correttezza e completezza forte vale f(A,B,C) |-L (A ⇒ ∼B) ∧ ( B ⇒ C ) se e solo se f(A,B,C) |= (A ⇒ ∼B) ∧ ( B ⇒ C ). Costruiamo allora la tavola di verità della formula (A ⇒ ∼B) ∧ ( B ⇒ C ) e confrontiamola con quella di f(A,B,C): A B C f (A, B, C ) (A ⇒ ∼B) ∧ ( B ⇒ C ) ___________________________________ 1 1 1 0 0 1 1 0 0 0 1 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 0 0 0 0 0 1 1 1 0 0 0 0 1 Risulta che ogni modello di f (A, B, C ) è modello anche per (A ⇒ ∼B) ∧ ( B ⇒ C ) che quindi è conseguenza semantica di f (A, B, C ). Pertanto esiste la deduzione nella teoria L f(A,B,C) |-L (A ⇒ ∼B) ∧ ( B ⇒ C ). c) L’insieme {f(A,B,C) , ∼(B⇒ C )} è insoddisfacibile in quanto non esiste un’interpretazione che sia modello sia per f(A,B,C) che per ∼(B⇒ C). Infatti, indicati con v 1, v 2, v 3 gli unici…