Resolution Method - Logical Inference

What is Resolution?

Resolution is a single, powerful inference rule that forms the basis of automated theorem proving. Rather than using many inference rules (modus ponens, modus tollens, hypothetical syllogism, etc.), resolution provides one complete rule that can derive any valid conclusion from premises in clausal form. This simplicity makes it ideal for computer implementation.

The resolution method was introduced by J. Alan Robinson in 1965 and became the foundation of Prolog, logic programming, and modern SAT solvers. If you can represent knowledge in clausal form, resolution can mechanically determine whether a query is entailed by the knowledge base.

The Resolution Rule

Propositional Resolution

Clause 1	A ∨ B ∨ C
Clause 2	¬B ∨ D ∨ E
Resolvent	A ∨ C ∨ D ∨ E

General Form

Example

C₁ = L ∨ α (clause containing literal L) C₂ = ¬L ∨ β (clause containing complement ¬L) ───────────────── Resolvent = α ∨ β (remove L and ¬L, combine rest)

Key Properties

- Sound	resolvent is a logical consequence of parent clauses
- Refutation-complete	can always derive empty clause (□) from
- NOT generatively complete	can't derive all consequences

Resolution Refutation: Proof by Contradiction

To prove KB ⊨ α (knowledge base entails query α):

2. Negate the query	add ¬α (also in CNF)
4. If empty clause □ derived	KB ⊨ α (proved!)
5. If no new resolvents possible	cannot prove

Worked Example: Propositional Resolution

Problem

1. P	Q (If it rains, ground is wet)
2. Q	R (If ground wet, road slippery)
Prove	R (Road is slippery)

Step-by-Step Resolution

Step 1	Convert to CNF
P	Q ≡ ¬P ∨ Q Clause: {¬P, Q}
Q	R ≡ ¬Q ∨ R Clause: {¬Q, R}
P Clause	{P}
Step 2	Negate the goal
¬R Clause	{¬R}
Step 3	Clause set = {{¬P, Q}, {¬Q, R}, {P}, {¬R}}
Step 4	Resolve
Step 5: Empty clause derived	R is PROVED!

Resolution Proof Tree

{¬P, Q} {¬Q, R} {P} {¬R}

\ / \

{¬Q,R} + {¬R} {P} + ?

\ / |

{¬Q} {P}

\ /

{¬P,Q} + {¬Q} {P}

\ /

{¬P} + {P}

\ /

□

First-Order Resolution (with Variables)

Unification Required

In predicate logic, we must unify terms before resolving:

Clause 1	¬Human(x) ∨ Mortal(x) (all humans are mortal)
Clause 2	Human(socrates) (Socrates is human)
Unify: Human(x) with Human(socrates)	{x/socrates}
Apply substitution to clause 1	¬Human(socrates) ∨ Mortal(socrates)
Resolvent	Mortal(socrates) ✓

Full First-Order Example

∀x (Dog(x)	Animal(x)) CNF: {¬Dog(x), Animal(x)}
∀x (Animal(x)	Breathes(x)) CNF: {¬Animal(x), Breathes(x)}
Dog(fido) CNF	{Dog(fido)}
Prove	Breathes(fido)
Add negation	{¬Breathes(fido)}
Unify: x=fido	{¬Animal(fido)}
Unify: x=fido	{¬Dog(fido)}

Converting to CNF

Steps for Predicate Logic

1. Eliminate implications: P	Q becomes ¬P∨Q
2. Move negation inward (De Morgan's): ¬(P∧Q)	¬P∨¬Q
3. Standardize variables	each quantifier uses unique variable
4. Skolemize	remove ∃ by introducing Skolem functions
∃x P(x)	P(c) (Skolem constant)
∀x ∃y P(x,y)	P(x,f(x)) (Skolem function)

Skolemization Example

Original: ∀x ∃y (Loves(x, y)) "Everyone loves someone"

Step 4: Replace y with f(x): Loves(x, f(x))

f(x) = "the person that x loves" (Skolem function)

This preserves satisfiability but not equivalence.

Sufficient for refutation proofs.

Resolution Strategies

Unit Resolution

Example

Prefer resolving with unit clauses (single-literal clauses) Unit: {P} resolves quickly Reduces clause length fastest

Set-of-Support Strategy

Example

Only resolve if at least one parent is derived from ¬Goal Prevents resolving KB clauses with each other (useless work) Focuses search on goal-relevant inferences

Linear Resolution

Example

Each resolvent uses the previous resolvent as one parent Creates a linear chain of deductions Basis of Prolog's SLD-resolution

Limitations and Practical Concerns

1. Combinatorial explosion	Many possible pairs to resolve
2. Factor generation	Need to unify literals within a clause
4. Non-termination	May loop on satisfiable inputs

Interview Questions

Q: Why proof by contradiction instead of direct proof? A: Resolution is refutation-complete (can always derive □ from unsatisfiable sets) but not generatively complete (can't derive all consequences directly). By negating the goal and showing contradiction, we leverage refutation-completeness to prove anything that's entailed.

Q: What is the relationship between resolution and SAT solving? A: SAT solvers essentially implement propositional resolution with clever heuristics (DPLL + conflict-driven clause learning). When a conflict occurs, the solver learns a new clause by resolution from the conflicting assignments—this "learned clause" prunes future search.

Q: How does Prolog use resolution? A: Prolog uses SLD-resolution: a restriction of resolution where one parent is always the current goal clause and the other is a program clause (fact or rule head). This depth-first, left-to-right strategy is incomplete but efficient and forms the basis of logic programming.

What is Resolution?

The Resolution Rule

Propositional Resolution

Clause 1	A ∨ B ∨ C
Clause 2	¬B ∨ D ∨ E
Resolvent	A ∨ C ∨ D ∨ E

General Form

Example

Key Properties

- Sound	resolvent is a logical consequence of parent clauses
- Refutation-complete	can always derive empty clause (□) from
- NOT generatively complete	can't derive all consequences

Resolution Refutation: Proof by Contradiction

To prove KB ⊨ α (knowledge base entails query α):

2. Negate the query	add ¬α (also in CNF)
4. If empty clause □ derived	KB ⊨ α (proved!)
5. If no new resolvents possible	cannot prove

Worked Example: Propositional Resolution

Problem

1. P	Q (If it rains, ground is wet)
2. Q	R (If ground wet, road slippery)
Prove	R (Road is slippery)

Step-by-Step Resolution

Step 1	Convert to CNF
P	Q ≡ ¬P ∨ Q Clause: {¬P, Q}
Q	R ≡ ¬Q ∨ R Clause: {¬Q, R}
P Clause	{P}
Step 2	Negate the goal
¬R Clause	{¬R}
Step 3	Clause set = {{¬P, Q}, {¬Q, R}, {P}, {¬R}}
Step 4	Resolve
Step 5: Empty clause derived	R is PROVED!

Resolution Proof Tree

{¬P, Q} {¬Q, R} {P} {¬R}

\ / \

{¬Q,R} + {¬R} {P} + ?

\ / |

{¬Q} {P}

\ /

{¬P,Q} + {¬Q} {P}

\ /

{¬P} + {P}

\ /

□

First-Order Resolution (with Variables)

Unification Required

In predicate logic, we must unify terms before resolving:

Clause 1	¬Human(x) ∨ Mortal(x) (all humans are mortal)
Clause 2	Human(socrates) (Socrates is human)
Unify: Human(x) with Human(socrates)	{x/socrates}
Apply substitution to clause 1	¬Human(socrates) ∨ Mortal(socrates)
Resolvent	Mortal(socrates) ✓

Full First-Order Example

∀x (Dog(x)	Animal(x)) CNF: {¬Dog(x), Animal(x)}
∀x (Animal(x)	Breathes(x)) CNF: {¬Animal(x), Breathes(x)}
Dog(fido) CNF	{Dog(fido)}
Prove	Breathes(fido)
Add negation	{¬Breathes(fido)}
Unify: x=fido	{¬Animal(fido)}
Unify: x=fido	{¬Dog(fido)}

Converting to CNF

Steps for Predicate Logic

1. Eliminate implications: P	Q becomes ¬P∨Q
2. Move negation inward (De Morgan's): ¬(P∧Q)	¬P∨¬Q
3. Standardize variables	each quantifier uses unique variable
4. Skolemize	remove ∃ by introducing Skolem functions
∃x P(x)	P(c) (Skolem constant)
∀x ∃y P(x,y)	P(x,f(x)) (Skolem function)

Skolemization Example

Original: ∀x ∃y (Loves(x, y)) "Everyone loves someone"

Step 4: Replace y with f(x): Loves(x, f(x))

f(x) = "the person that x loves" (Skolem function)

This preserves satisfiability but not equivalence.

Sufficient for refutation proofs.

Resolution Strategies

Unit Resolution

Example

Prefer resolving with unit clauses (single-literal clauses) Unit: {P} resolves quickly Reduces clause length fastest

Set-of-Support Strategy

Example

Only resolve if at least one parent is derived from ¬Goal Prevents resolving KB clauses with each other (useless work) Focuses search on goal-relevant inferences

Linear Resolution

Example

Each resolvent uses the previous resolvent as one parent Creates a linear chain of deductions Basis of Prolog's SLD-resolution

Limitations and Practical Concerns

1. Combinatorial explosion	Many possible pairs to resolve
2. Factor generation	Need to unify literals within a clause
4. Non-termination	May loop on satisfiable inputs

What is Resolution?

The Resolution Rule

Propositional Resolution

General Form

Key Properties

Resolution Refutation: Proof by Contradiction

Worked Example: Propositional Resolution

Problem

Step-by-Step Resolution

Resolution Proof Tree

First-Order Resolution (with Variables)

Unification Required

Full First-Order Example

Converting to CNF

Steps for Predicate Logic

Skolemization Example

Resolution Strategies

Unit Resolution

Set-of-Support Strategy

Linear Resolution

Limitations and Practical Concerns

Interview Questions

Continue learning this concept

What is Resolution?

The Resolution Rule

Propositional Resolution

General Form

Key Properties

Resolution Refutation: Proof by Contradiction

Worked Example: Propositional Resolution

Problem

Step-by-Step Resolution

Resolution Proof Tree

First-Order Resolution (with Variables)

Unification Required

Full First-Order Example

Converting to CNF

Steps for Predicate Logic

Skolemization Example

Resolution Strategies

Unit Resolution

Set-of-Support Strategy

Linear Resolution

Limitations and Practical Concerns

Interview Questions

Continue learning this concept