1. This question is about logic and proof. (a) Explain how a SAT algorithm (such as...

 

Transcribed Image Text:

1. This question is about logic and proof. (a) Explain how a SAT algorithm (such as DPLL) can be used to verify whether a model (in propositional logic) of a system conforms to a specification, or to find a counter example if the model does not conform to the specification. (b) Give a natural deduction proof that: P VQ +P→ Q (c) Recall the following equation of first-order logic: x= x. ¬P Give an equational proof of the following derived property in first- order logic: ((3x. Q(x)) VP) ^ ((vz.Q(z)) V P) = P Label each step in your sequence of equational reasoning. [3 marks] [6 marks] [5 marks] 1. This question is about logic and proof. (a) Explain how a SAT algorithm (such as DPLL) can be used to verify whether a model (in propositional logic) of a system conforms to a specification, or to find a counter example if the model does not conform to the specification. (b) Give a natural deduction proof that: P VQ +P→ Q (c) Recall the following equation of first-order logic: x= x. ¬P Give an equational proof of the following derived property in first- order logic: ((3x. Q(x)) VP) ^ ((vz.Q(z)) V P) = P Label each step in your sequence of equational reasoning. [3 marks] [6 marks] [5 marks]

Answer rating: 100% (QA)

aA SAT algorithm can be used to verify whether a model of a system conforms to a specification by ch... View the full answer