10 Questions
What is the result of deleting P from all clauses in F that contain P?
F [false/P ]
How is F [true/P ] defined?
By deleting all clauses containing P and removing ¬P from all clauses containing ¬P
What is the result of F [false/p3 ] when F = {{p1 , p3 }, {¬p1 , p2 }, {¬p2 , p3 }, {¬p3 }}?
{{p1 }, {¬p1 , p2 }, {¬p2 }}
What is the purpose of Theorem 8 (Completeness)?
To prove that if F is unsatisfiable, then there is a derivation of 2 from F
What is the base case in the proof of Theorem 8 (Completeness)?
When n = 0, i.e., F does not mention any propositional variables
What is the result of F [true/p3 ] when F = {{p1 , p3 }, {¬p1 , p2 }, {¬p2 , p3 }, {¬p3 }}?
{{¬p1 , p2 }, 2}
What is the induction step in the proof of Theorem 8 (Completeness)?
Suppose that F is an unsatisfiable set of clauses that mentions variables p1 , p2 ,..., pn and let F0 := F [false/pn ] and F1 := F [true/pn ]
What is the consequence of F being unsatisfiable in the proof of Theorem 8 (Completeness)?
F0 is also unsatisfiable
What is the purpose of defining F0 and F1 in the proof of Theorem 8 (Completeness)?
To apply the induction hypothesis and derive the empty clause from F
What is the result of the induction step in the proof of Theorem 8 (Completeness)?
A resolution proof C0 , C1 ,..., Cm = 2 that derives the empty clause from F0
This lecture introduces a proof calculus for propositional logic, specifically the resolution method, which has a single rule of inference, making it suitable for automation and theoretical analysis.
Make Your Own Quizzes and Flashcards
Convert your notes into interactive study material.
Get started for free
