First-Order Inference & Unification
Lifting propositional reasoning to variables.
To apply "all humans are mortal" to Socrates, a reasoner must discover that makes two expressions identical. Robinson's 1965 insight was that this matching can be done lazily and in the most general way possible, and that a single rule, resolution with unification, then proves every first-order consequence, given enough time.
What you’ll learn
- Define substitutions, unifiers and most general unifiers, and run a unification algorithm with the occurs check.
- Prove that unifiable terms have a most general unifier, and compare naive and linear-time unification.
- Convert first-order sentences to clausal form with Skolemization, and apply binary resolution with factoring.
- State Herbrand's theorem and the lifting lemma, and derive the refutation completeness of first-order resolution.
- Contrast forward chaining (Datalog), SLD resolution (Prolog) and saturation provers.
Substitutions and unifiers
| Unify | with | mgu |
|---|---|---|
| none, since cannot be both; renamed apart to : |
Most general unifiers are unique up to renaming. and have the mgu . The unifier also works but commits to more than necessary: it is the mgu followed by .
Computing most general unifiers
function UNIFY(E) returns an mgu of the set of equations E, or failure
while some rule applies to E do
pick an equation s ≐ t in E and apply:
delete t ≐ t remove it
decompose f(s1..sn) ≐ f(t1..tn) replace by s1 ≐ t1, ..., sn ≐ tn
conflict f(...) ≐ g(...), f ≠ g return failure
swap t ≐ x, t not a variable replace by x ≐ t
occurs x ≐ t, x occurs in t ≠ x return failure
eliminate x ≐ t, x not in t, x elsewhere apply {x ↦ t} to every other equation
return {x ↦ t : x ≐ t in E} // E is now in solved formThe rule-based algorithm of Martelli and Montanari (1982). Constants are function symbols with no arguments; decomposes into and .
Termination. Call solved if it occurs exactly once, as the left side of an equation . Eliminate solves a variable and unsolves none (a solved variable cannot occur in ); delete and decompose shrink the terms without unsolving anything; swap reduces the number of equations . So this triple decreases lexicographically:
Correctness. Delete, decompose and swap preserve the set of unifiers, and so does eliminate: if , then and agree on every term. Failures are genuine: no substitution equates different head symbols, and a unifier of with inside would make a term a proper subterm of itself:
Most generality. The algorithm stops at a solved form whose are distinct and occur nowhere else. With , its unifiers are exactly the with , so unifies and every unifier factors through it. ∎
Prolog omits the occurs check by default because it costs time on every binding. Then succeeds by building a cyclic term, and the system can "prove" false things: given the program clause it answers yes to the query , although (the Herbrand model has no atom ). ISO Prolog offers unify_with_occurs_check/2 when soundness matters.
Naive unification can also blow up. The equations have an mgu in which , written out as a tree, contains copies of . Sharing subterms in a DAG avoids this: Paterson and Wegman (1978) unify in linear time, and Martelli and Montanari's algorithm runs in near-linear time with union–find.
Do and unify?
- Yes, with
- Yes, with
- No: after the second arguments demand , which fails the occurs check
- No: the predicate symbols differ
Show the answer
C. No: after the second arguments demand , which fails the occurs check
Decompose into and . Eliminating turns the second equation into : occurs inside its own binding, so no finite unifier exists.
Clausal form and first-order resolution
Resolution needs clauses. Converting a first-order sentence takes six steps: eliminate and ; push inward, using and ; rename variables apart; Skolemize, replacing each inside the scope of by a new function term ; drop the universal quantifiers; distribute over . Skolemization preserves satisfiability but not equivalence, which is all a refutation needs.
The sentence:
Eliminate , push inward (the negated universal becomes an existential) and rename the second to :
Skolemize. Both existentials lie inside , so both become functions of : is an animal that fails to love, someone who loves :
Drop and distribute, leaving two clauses:
Binary resolution lifts the propositional rule: from clauses and , renamed apart, with an mgu of and , derive . Factoring derives when two literals of unify with mgu , merging them. Both rules are needed. The set is unsatisfiable, yet every binary resolvent of it has two literals; factoring the clauses to and gives in one more step.
Herbrand's theorem and lifting
() Ground instances are consequences of , since each clause is universally quantified; if some set of them is unsatisfiable, so is .
() If had a model , the Herbrand interpretation making a ground atom true iff it is true in would also satisfy , because clauses are universal. So an unsatisfiable has no Herbrand model: the set of all its ground instances, read propositionally, is unsatisfiable. By compactness of propositional logic, a finite subset already is:
Lifting lemma. If and are ground instances of and and is a resolvent of and , then some resolvent of factors of and has as an instance, because an mgu is at least as general as the ground substitution:
Herbrand gives a finite unsatisfiable ground set, propositional completeness gives a ground refutation of it, and lifting turns every ground step into a first-order step. That is Robinson's theorem: resolution with factoring is refutation-complete for first-order logic. ∎
Chaining, Prolog and modern provers
For definite clauses, resolution specializes to generalized modus ponens: from facts and a rule , with unifying each with , infer .
- Forward chaining applies rules to known facts until nothing new appears. Without function symbols (Datalog) the Herbrand base is finite, so it terminates: entailment is decidable, P-complete in the size of the data for a fixed program, and EXPTIME-complete when the program is part of the input.
- Backward chaining is SLD resolution (Kowalski, 1974), the engine of Prolog: it reduces the query to subgoals depth-first, left to right. That makes Prolog fast but incomplete (a left-recursive rule loops forever) and, without the occurs check, unsound. Tabling, as in XSB, restores termination for Datalog-like programs.
Equality is where naive approaches drown: axioms for reflexivity, symmetry, transitivity and substitution flood the search. Paramodulation (Robinson & Wos, 1969) and its ordered refinement, the superposition calculus (Bachmair & Ganzinger, 1994), build equality into the inference rules. With a given-clause saturation loop, term indexing and redundancy elimination, superposition powers provers such as Vampire, E and SPASS; the yearly CASC competition compares provers on problems from the TPTP library. SMT solvers such as Z3 and cvc5 pair a CDCL core with decision procedures for theories like arithmetic and arrays.
Key takeaways
- A unifier makes terms identical. When one exists, a most general unifier exists, unique up to renaming, and the Martelli–Montanari rules compute it.
- The occurs check rejects ; omitting it, as Prolog does by default, is fast but unsound. With shared subterms, unification takes linear time.
- Clausal form needs Skolemization (equisatisfiable, not equivalent), and first-order resolution needs mgus, renaming apart and factoring.
- Herbrand's theorem plus the lifting lemma make first-order resolution refutation-complete (Robinson, 1965), but only as a semi-decision procedure.
- Datalog forward chaining is decidable; Prolog's SLD resolution is fast but incomplete; superposition provers and SMT solvers handle equality and background theories.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
What is the mgu of and ?
- They do not unify
Show the answer
B.
Decompose into and . Swap and eliminate , which turns the second equation into .
Why does first-order resolution need factoring?
- To rename variables apart
- To eliminate existential quantifiers
- To make unification terminate
- Because without it some unsatisfiable sets, such as , have no refutation: every binary resolvent keeps two literals
Show the answer
D. Because without it some unsatisfiable sets, such as , have no refutation: every binary resolvent keeps two literals
Factoring merges unifiable literals within one clause: becomes . In propositional logic this happens silently, because clauses are sets.
What is the Skolem form of ?
- for a new constant
- for a new function symbol
Show the answer
C. for a new function symbol
The witness may depend on , so it becomes a function of . The result is equisatisfiable with the original, not equivalent to it.
Herbrand's theorem reduces first-order unsatisfiability to…
- the propositional unsatisfiability of some finite set of ground instances, though which set is not known in advance
- the unsatisfiability of one ground instance of each clause
- checking all structures with at most elements, for some computable
- the satisfiability of the Herbrand base
Show the answer
A. the propositional unsatisfiability of some finite set of ground instances, though which set is not known in advance
If is unsatisfiable, some finite set of ground instances is propositionally unsatisfiable, and enumerating ever larger sets finds it. If is satisfiable, the enumeration may never end: a semi-decision procedure.
Further reading
- J. A. Robinson, "A machine-oriented logic based on the resolution principle," Journal of the ACM 12(1) (1965), 23–41.
- A. Martelli & U. Montanari, "An efficient unification algorithm," ACM Transactions on Programming Languages and Systems 4(2) (1982), 258–282.
- M. S. Paterson & M. N. Wegman, "Linear unification," Journal of Computer and System Sciences 16(2) (1978), 158–167.
- L. Bachmair & H. Ganzinger, "Rewrite-based equational theorem proving with selection and simplification," Journal of Logic and Computation 4(3) (1994), 217–247.
- A. Robinson & A. Voronkov (eds.), Handbook of Automated Reasoning (Elsevier and MIT Press, 2001).