7.7.1. Unsatisfiability Proof via Resolution

Try these first

1. 1.

   Define Functional Completeness.

   Hint

   Think about what it means to be able to express all logical relationships.

2. 2.

   What is a clause in logic?

   Hint

   Consider how you might use clauses in logical expressions.

3. 3.

   What does functional completeness mean?

   • Ability to represent all logical statements
   • Ability to represent only simple statements
   • Ability to represent temporal logic

   Hint

   Think about logic as a complete system.

4. 4.

   True or False: All logical expressions can be transformed using a combination of negation and disjunction.

   • True
   • False

   Hint

   Consider functional completeness again.

5. 5.

   Demonstrate how the expression (p ∨ q), (¬p), and (¬q) leads to unsatisfiability using resolution.

   Hint

   Track all resolutions carefully to find contradictions.

6. 6.

   Construct a logical expression that uses only disjunction and negation, proving its functional completeness through resolution.

   Hint

   Think about how to represent conjunction using the operators available.