Resolution and refutation in AI

Introduction

• Resolution is a powerful and efficient inference rule used in many AI systems. It’s a core technique for automated reasoning and logic-based AI.  
• Refutation is a proof technique where we prove a statement by demonstrating that its negation leads to a contradiction. This is the core idea behind how resolution is used.

The Resolution Rule

• The resolution rule is a single inference rule that can be used to derive all entailed sentences from a knowledge base. It’s a complete inference procedure when coupled with a complete search algorithm.  
• It operates on clauses, which are disjunctions of literals.  
• Two clauses can be resolved if they contain complementary literals (one literal unifies with the negation of the other).  
• The resolvent is a new clause containing all the literals of the two original clauses except the two complementary literals.

Refutation with Resolution

• We use the resolution rule to prove a sentence α by showing that its negation ¬α leads to a contradiction. This is called proof by refutation or proof by contradiction.  
• Steps:
  1. Negate the sentence α to be proved.
  2. Add the negated sentence to the knowledge base.
  3. Convert the knowledge base to conjunctive normal form (CNF).
  4. Repeatedly apply the resolution rule to the clauses in the knowledge base.
  5. If a contradiction (the empty clause) is derived, then the original sentence α is proven.  

Example

• Consider the knowledge base:
  • A ⇒ B
  • B ⇒ C
  • A
• We want to prove C.
• Steps:
  1. Negate the goal: ¬C
  2. Convert to CNF: ¬A ∨ B, ¬B ∨ C, A, ¬C
  3. Apply resolution:
     • Resolve ¬A ∨ B and A to get B
     • Resolve ¬B ∨ C and B to get C
     • Resolve C and ¬C to get the empty clause (contradiction)
• Therefore, C is proven.

Efficiency Considerations

• Resolution can be computationally expensive due to the many possible ways to apply the rule.
• Several strategies can improve efficiency:
  • Unit resolution: Prefer resolutions involving unit clauses (clauses with one literal).  
  • Set of support: Restrict resolution to clauses derived from the negated goal.  
  • Subsumption: Eliminate redundant clauses.  

Conclusion

• Resolution is a fundamental inference method in AI.
• It’s used in various applications, including theorem proving, question-answering systems, and logic programming.
• Understanding resolution is crucial for anyone interested in the foundations of AI and automated reasoning.

References:

• Russell, S., and Norvig, P. Artificial Intelligence: A Modern Approach, 4th Edition, 2020, Pearson.
• Rich, E., Knight, K., & Nair, S. B. Artificial Intelligence. McGraw-Hill International.
• Nilsson, N. J. Artificial Intelligence: A New Synthesis. Morgan Kaufmann.

Note: This content was generated with the assistance of Google’s Gemini AI.