Primo parziale di Logica e Algebra per il corso di Computer Engineering presso Politecnico di Milano. Materiale proveniente dall’archivio storico Studwiz e classificato per la consultazione online.
Primo parziale di Logica e Algebra per il corso di Computer Engineering presso Politecnico di Milano. Materiale proveniente dall’archivio storico Studwiz e classificato per la consultazione online.
Qualità dell’importazione: il testo è stato estratto direttamente dal documento originale.
Passaggi rappresentativi riconosciuti nelle diverse parti del materiale. Il testo completo resta presente nella pagina per la ricerca, mentre l’anteprima compatta rende più semplice la lettura.
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…
Prima pagina del documento.
