7.7. Question 13

Try these first

1. 1.

   What is the definition of a clause?

   Hint

   Consider the component parts of a logical statement.

2. 2.

   Identify a pair of complementary literals.

   Hint

   Think about variables and their negations.

3. 3.

   What does the resolution method help determine?

   • Satisfiability of a single clause
   • Whether a compound proposition is true
   • Satisfiability of a set of clauses

   Hint

   Think about the purpose of adding multiple clauses.

4. 4.

   True or False: A set of clauses is unsatisfiable if they cannot all be true at the same time.

   • True
   • False

   Hint

   Envision cases where truth values lead to contradictions.

5. 5.

   Prove unsatisfiability of the compound proposition formed by the clauses: { (p ∨ q), (¬p), (¬q) } using resolution.

   Hint

   Start with deriving conclusions iteratively.

6. 6.

   Given the clauses: { (p ∨ r), (¬r ∨ q), (¬q ∨ ¬p) }, show how they lead to unsatisfiability.

   Hint

   Be consistent with tracking the literals.