Resolution in First-Order Logic (FOL): Resolution Refutation from a Simple Knowledge Base

Resolution is a rule of inference used in automated theorem proving for keywordfirst-order logic resolution[/keyword] by deriving contradictions in keywordresolution refutation[/keyword]. For first-order logic, resolution relies on keywordunification[/keyword] and the transformation of formulas into keywordclausal (CNF) form[/keyword]. The high-level refutation strategy is: negate the goal, add it to the knowledge base, convert everything to clausal form, and repeatedly resolve until the keywordempty clause[/keyword] is derived (or saturation occurs).3

Mini-knowledge base and goal

Knowledge base (KB):

1. “All humans are mortal.”
   [ \forall x;(\text{Human}(x)\rightarrow \text{Mortal}(x)) ]
2. “Socrates is a human.”
   [ \text{Human}(\text{Socrates}) ]

Query/goal:

• “Therefore, Socrates is mortal.”
  [ \text{Mortal}(\text{Socrates}) ]

We will derive the conclusion using resolution refutation.2

Footnotes

1. Resolution (logic) - Wikipedia - Overview of resolution, first-order generalization, and refutation/entailment via deriving contradiction. ↩ ↩²

2. Artificial Intelligence - Resolution in First Order Logic (FOL) - Step workflow for resolution: convert to clausal form, negate goal, resolve until empty clause. ↩ ↩²

3. Logic and Automatic Theorem Proving (Skolemization & CNF steps) - TAMU slides (logicp) - Describes converting to standard form: CNF and Skolemization to eliminate existential quantifiers. ↩

Clausal form and the key resolution rule (first-order version)

Clausal representation

In resolution theorem proving for first-order logic, we work with a set of clauses: a keywordliteral[/keyword] is either an atomic formula $P(t_1,\dots,t_k)$ or its negation. A clause is a disjunction of literals, and the entire formula is treated as a conjunction of clauses.2

Binary resolution with unification (the practical rule)

The first-order “binary” resolution step looks like:

• Clause $C_1$: $A \lor L$
• Clause $C_2$: $B \lor \neg L$

If the complementary literals $L$ and $\neg L$ are made identical by some keywordMGU[/keyword] $\theta$, then the keywordresolvent[/keyword] is:

• [ (,A \lor B,)\theta ]

This matches the general explanation of first-order resolution: choose unifiable complementary literals, compute a unifier (often the most general one), and then resolve away the complementary pair.2

Footnotes

1. Artificial Intelligence - Resolution in First Order Logic (FOL) - Step workflow for resolution: convert to clausal form, negate goal, resolve until empty clause. ↩

2. Logic and Automatic Theorem Proving (Skolemization & CNF steps) - TAMU slides (logicp) - Describes converting to standard form: CNF and Skolemization to eliminate existential quantifiers. ↩

3. Resolution (logic) - Wikipedia - Overview of resolution, first-order generalization, and refutation/entailment via deriving contradiction. ↩

4. MIT OCW PDF: Resolution Theorem Proving: First Order Logic (resolution with variables, unification, rule form) - Defines first-order resolution with unification/MGU and shows how clauses resolve to new clauses. ↩

Worked derivation (fully explicit)

Step 1: Clauses from the KB

KB statement (1): [ \forall x(\text{Human}(x)\rightarrow \text{Mortal}(x)) \equiv \forall x(\neg \text{Human}(x)\lor \text{Mortal}(x)) ] This yields clause:

• $(1)$ $\neg\text{Human}(x)\lor \text{Mortal}(x)$

KB statement (2):

• $(2)$ $\text{Human}(\text{Socrates})$

Negated goal:

• goal is $\text{Mortal}(\text{Socrates})$
• add negation: $\neg \text{Mortal}(\text{Socrates})$
• $(3)$ $\neg \text{Mortal}(\text{Socrates})$

This clause-set approach is the standard refutation workflow.2

Step 2: First resolution (derive $\neg\text{Human}(\text{Socrates})$)

Resolve (1) with (3) on the complementary pair:

• from (1): $\text{Mortal}(x)$
• from (3): $\neg \text{Mortal}(\text{Socrates})$

Unification: [ \theta={x/\text{Socrates}} ] Resolvent removes $\text{Mortal}(x)$ and $\neg \text{Mortal}(\text{Socrates})$, leaving:

• $(4)$ $\neg\text{Human}(\text{Socrates})$

Step 3: Second resolution (derive empty clause)

Resolve (4) with (2) on:

• (4): $\neg\text{Human}(\text{Socrates})$
• (2): $\text{Human}(\text{Socrates})$

They are complementary, so the resolvent is the empty clause:

• $(5)$ $\Box$

By the refutation method, deriving $\Box$ proves that the KB plus $\neg$goal is inconsistent, hence the KB entails the goal.2

Footnotes

1. Artificial Intelligence - Resolution in First Order Logic (FOL) - Step workflow for resolution: convert to clausal form, negate goal, resolve until empty clause. ↩ ↩²

2. Resolution (logic) - Wikipedia - Overview of resolution, first-order generalization, and refutation/entailment via deriving contradiction. ↩ ↩²