10 Questions
0 Views

# Logic and Proof: Resolution Lecture

Created by
@VibrantLitotes

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)?

<p>To prove that if F is unsatisfiable, then there is a derivation of 2 from F</p> Signup and view all the answers

### What is the base case in the proof of Theorem 8 (Completeness)?

<p>When n = 0, i.e., F does not mention any propositional variables</p> Signup and view all the answers

### What is the result of F [true/p3 ] when F = {{p1 , p3 }, {¬p1 , p2 }, {¬p2 , p3 }, {¬p3 }}?

<p>{{¬p1 , p2 }, 2}</p> Signup and view all the answers

### What is the induction step in the proof of Theorem 8 (Completeness)?

<p>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 ]</p> Signup and view all the answers

### What is the consequence of F being unsatisfiable in the proof of Theorem 8 (Completeness)?

<p>F0 is also unsatisfiable</p> Signup and view all the answers

### What is the purpose of defining F0 and F1 in the proof of Theorem 8 (Completeness)?

<p>To apply the induction hypothesis and derive the empty clause from F</p> Signup and view all the answers

### What is the result of the induction step in the proof of Theorem 8 (Completeness)?

<p>A resolution proof C0 , C1 ,..., Cm = 2 that derives the empty clause from F0</p> Signup and view all the answers

## More Quizzes Like This

8 questions
8 questions
10 questions
10 questions
Use Quizgecko on...
Browser
Information:
Success:
Error: