Resolution is a core technique in automated theorem proving. Instead of directly proving a goal, we prove that denying the goal leads to a contradiction. If a knowledge base really entails a statement, then the knowledge base plus the negation of that statement cannot be satisfied together. Resolution is designed to detect that unsatisfiability, which is why it appears in many discussions of logic-based AI, including an artificial intelligence course in Delhi.
From First-Order Logic to a Set of Clauses
Resolution operates on clauses: disjunctions of literals, treated as a conjunction when we have a set. To reach this form, we convert first-order formulas into clause normal form (CNF) while preserving satisfiability:
- Rewrite away → and ↔, and push negations inward.
- Standardise variable names.
- Skolemise existential quantifiers (replace them with Skolem constants/functions).
- Drop universal quantifiers (implicit in clauses) and distribute ∨ over ∧ to obtain a clause set.
Skolemisation matters because it preserves satisfiability, which is exactly what refutation proofs rely on. This clause-conversion workflow is commonly practised in an artificial intelligence course in Delhi.
The Resolution Rule with Unification
In propositional logic, resolution removes complementary literals that match exactly. In first-order logic (FOL), literals can match after a substitution found by unification.
From:
- (L ∨ A)
- (¬L′ ∨ B)
if there is a unifier θ with Lθ = L′θ, we infer the resolvent:
- (A ∨ B)θ
Example: P(x) ∨ Q(x) resolved with ¬P(a) ∨ R yields Q(a) ∨ R using θ = {x/a}. The rule is sound, meaning it never derives a clause that is not implied by the parents. Completeness is the stronger claim: if a contradiction is logically forced, resolution can derive it.
What Completeness Means
Resolution is typically refutation-complete:
If a clause set S is unsatisfiable, then resolution can derive the empty clause □ from S in finitely many steps.
To prove a goal G from KB, we:
- convert KB to clauses S, 2) add clauses for ¬G, 3) refute the combined set. If □ is derived, then KB ⊨ G. This “prove by refutation” pattern is a standard milestone in an artificial intelligence course in Delhi because it turns semantic entailment into a mechanical search procedure.
Proof Sketch: Why First-Order Resolution Is Complete
A classic completeness argument has three linked parts.
1) Herbrand’s Theorem: Focus on Ground Instances
If S is unsatisfiable, Herbrand’s theorem implies there exists a finite set of ground (variable-free) instances of clauses from S that is already unsatisfiable. Call that finite ground set G(S). Once everything is ground, we can treat each ground atom like a propositional variable.
2) Propositional Resolution Completeness Refutes G(S)
Propositional resolution is complete: any unsatisfiable propositional clause set has a resolution refutation deriving □. Since G(S) is an unsatisfiable ground set, there is a propositional resolution derivation of □ from G(S).
3) The Lifting Lemma: Lift the Ground Refutation Back to FOL
The lifting lemma shows that if two ground instances of first-order clauses resolve in the propositional refutation, then the original non-ground clauses can also be resolved using unification, producing a resolvent that generalises the ground resolvent. By lifting each propositional resolution step in the refutation of G(S), we obtain a first-order resolution refutation of S. Therefore S ⊢ □, which establishes completeness.
Why It Matters in Practice
Completeness guarantees that a refutation exists when the entailment is true, but it does not promise speed. Proof search can still be large, so provers use strategies (set-of-support, unit preference, subsumption, term indexing) to reduce branching while trying to preserve the completeness guarantee. If you are learning automated reasoning in an artificial intelligence course in Delhi, this distinction helps: resolution gives the theoretical guarantee, while search control makes it practical.
Conclusion
First-order resolution is complete in the refutation sense because unsatisfiable clause sets have finite unsatisfiable ground instances (Herbrand), propositional resolution can refute those ground instances, and each ground inference can be lifted to a valid first-order resolution inference via unification (lifting lemma). As a result, any valid conclusion can be proved by adding the negation of the goal and using resolution until the empty clause is derived.