Simple Algorithm
Artificial Intelligence · Deep Layer · 28 min

First-Order Inference & Unification

Lifting propositional reasoning to variables.

To apply "all humans are mortal" to Socrates, a reasoner must discover that x:=Socratesx:=\mathit{Socrates} 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

Unifywithmgu
Knows(John,x)\mathit{Knows}(\mathit{John},x)Knows(John,Jane)\mathit{Knows}(\mathit{John},\mathit{Jane}){x↦Jane}\{x\mapsto\mathit{Jane}\}
Knows(John,x)\mathit{Knows}(\mathit{John},x)Knows(y,Bill)\mathit{Knows}(y,\mathit{Bill}){x↦Bill, y↦John}\{x\mapsto\mathit{Bill},\ y\mapsto\mathit{John}\}
Knows(John,x)\mathit{Knows}(\mathit{John},x)Knows(y,MotherOf(y))\mathit{Knows}(y,\mathit{MotherOf}(y)){y↦John, x↦MotherOf(John)}\{y\mapsto\mathit{John},\ x\mapsto\mathit{MotherOf}(\mathit{John})\}
Knows(John,x)\mathit{Knows}(\mathit{John},x)Knows(x,Elizabeth)\mathit{Knows}(x,\mathit{Elizabeth})none, since xx cannot be both; renamed apart to Knows(z,Elizabeth)\mathit{Knows}(z,\mathit{Elizabeth}): {x↦Elizabeth, z↦John}\{x\mapsto\mathit{Elizabeth},\ z\mapsto\mathit{John}\}
Russell and Norvig's examples. Each clause is universally quantified on its own, so variables are renamed apart ("standardized apart") before unifying.

Most general unifiers are unique up to renaming. Knows(John,x)\mathit{Knows}(\mathit{John},x) and Knows(y,z)\mathit{Knows}(y,z) have the mgu {y↦John, x↦z}\{y\mapsto\mathit{John},\ x\mapsto z\}. The unifier {y↦John, x↦John, z↦John}\{y\mapsto\mathit{John},\ x\mapsto\mathit{John},\ z\mapsto\mathit{John}\} also works but commits to more than necessary: it is the mgu followed by {z↦John}\{z\mapsto\mathit{John}\}.

Computing most general unifiers

text
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 form

The rule-based algorithm of Martelli and Montanari (1982). Constants are function symbols with no arguments; Knows(John,x)≐Knows(y,Bill)\mathit{Knows}(\mathit{John},x)\doteq\mathit{Knows}(y,\mathit{Bill}) decomposes into John≐y\mathit{John}\doteq y and x≐Billx\doteq\mathit{Bill}.

DerivationProof sketch
  1. (#unsolved variables, ∑∣terms∣, #{t≐x: t not a variable})\big(\#\text{unsolved variables},\ \textstyle\sum|\text{terms}|,\ \#\{t\doteq x:\ t\ \text{not a variable}\}\big)

    Termination. Call xx solved if it occurs exactly once, as the left side of an equation x≐tx\doteq t. Eliminate solves a variable and unsolves none (a solved variable cannot occur in tt); delete and decompose shrink the terms without unsolving anything; swap reduces the number of equations t≐xt\doteq x. So this triple decreases lexicographically:

  2. xσ=tσ,  x∈vars(t),  t≠x ⟹ ∣xσ∣<∣tσ∣=∣xσ∣x\sigma=t\sigma,\ \ x\in\mathrm{vars}(t),\ \ t\neq x\ \Longrightarrow\ |x\sigma|<|t\sigma|=|x\sigma|

    Correctness. Delete, decompose and swap preserve the set of unifiers, and so does eliminate: if xσ=tσx\sigma=t\sigma, then σ\sigma and {x↦t}σ\{x\mapsto t\}\sigma agree on every term. Failures are genuine: no substitution equates different head symbols, and a unifier of x≐tx\doteq t with xx inside t≠xt\neq x would make a term a proper subterm of itself:

  3. σ is a unifier  ⟺  σ=θσ⟹θ is an mgu\sigma\ \text{is a unifier}\iff\sigma=\theta\sigma\quad\Longrightarrow\quad\theta\ \text{is an mgu}

    Most generality. The algorithm stops at a solved form {x1≐t1,…,xk≐tk}\{x_1\doteq t_1,\dots,x_k\doteq t_k\} whose xix_i are distinct and occur nowhere else. With θ={xi↦ti}\theta=\{x_i\mapsto t_i\}, its unifiers are exactly the σ\sigma with σ=θσ\sigma=\theta\sigma, so θ\theta unifies and every unifier factors through it. ∎

Prolog omits the occurs check by default because it costs time on every binding. Then X=f(X)X=f(X) succeeds by building a cyclic term, and the system can "prove" false things: given the program clause p(Y,f(Y))p(Y,f(Y)) it answers yes to the query p(X,X)p(X,X), although ∀y p(y,f(y))⊭∃x p(x,x)\forall y\,p(y,f(y))\not\models\exists x\,p(x,x) (the Herbrand model {p(t,f(t))}\{p(t,f(t))\} has no atom p(t,t)p(t,t)). ISO Prolog offers unify_with_occurs_check/2 when soundness matters.

Naive unification can also blow up. The equations x1≐f(x0,x0), x2≐f(x1,x1), …, xn≐f(xn−1,xn−1)x_1\doteq f(x_0,x_0),\ x_2\doteq f(x_1,x_1),\ \dots,\ x_n\doteq f(x_{n-1},x_{n-1}) have an mgu in which xnx_n, written out as a tree, contains 2n2^n copies of x0x_0. 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.

Check your understanding

Do P(x,f(x))P(x,f(x)) and P(f(y),y)P(f(y),y) unify?

  1. Yes, with {x↦f(y), y↦f(x)}\{x\mapsto f(y),\ y\mapsto f(x)\}
  2. Yes, with {x↦f(y)}\{x\mapsto f(y)\}
  3. No: after x↦f(y)x\mapsto f(y) the second arguments demand y≐f(f(y))y\doteq f(f(y)), which fails the occurs check
  4. No: the predicate symbols differ
Show the answer

C. No: after x↦f(y)x\mapsto f(y) the second arguments demand y≐f(f(y))y\doteq f(f(y)), which fails the occurs check

Decompose into x≐f(y)x\doteq f(y) and f(x)≐yf(x)\doteq y. Eliminating xx turns the second equation into y≐f(f(y))y\doteq f(f(y)): yy 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 ⇒\Rightarrow and ⇔\Leftrightarrow; push ¬\neg inward, using ¬∀x φ≡∃x ¬φ\neg\forall x\,\varphi\equiv\exists x\,\neg\varphi and ¬∃x φ≡∀x ¬φ\neg\exists x\,\varphi\equiv\forall x\,\neg\varphi; rename variables apart; Skolemize, replacing each ∃y\exists y inside the scope of ∀x1,…,∀xk\forall x_1,\dots,\forall x_k by a new function term F(x1,…,xk)F(x_1,\dots,x_k); drop the universal quantifiers; distribute ∨\lor over ∧\land. Skolemization preserves satisfiability but not equivalence, which is all a refutation needs.

DerivationClausal form of "everyone who loves all animals is loved by someone"
  1. ∀x [∀y (Animal(y)⇒Loves(x,y))]⇒[∃y Loves(y,x)]\forall x\,\big[\forall y\,(\mathit{Animal}(y)\Rightarrow\mathit{Loves}(x,y))\big]\Rightarrow\big[\exists y\,\mathit{Loves}(y,x)\big]

    The sentence:

  2. ∀x [∃y (Animal(y)∧¬Loves(x,y))]∨[∃z Loves(z,x)]\forall x\,\big[\exists y\,(\mathit{Animal}(y)\land\neg\mathit{Loves}(x,y))\big]\lor\big[\exists z\,\mathit{Loves}(z,x)\big]

    Eliminate ⇒\Rightarrow, push ¬\neg inward (the negated universal becomes an existential) and rename the second yy to zz:

  3. ∀x [Animal(F(x))∧¬Loves(x,F(x))]∨Loves(G(x),x)\forall x\,\big[\mathit{Animal}(F(x))\land\neg\mathit{Loves}(x,F(x))\big]\lor\mathit{Loves}(G(x),x)

    Skolemize. Both existentials lie inside ∀x\forall x, so both become functions of xx: F(x)F(x) is an animal that xx fails to love, G(x)G(x) someone who loves xx:

  4. (Animal(F(x))∨Loves(G(x),x))∧(¬Loves(x,F(x))∨Loves(G(x),x))\big(\mathit{Animal}(F(x))\lor\mathit{Loves}(G(x),x)\big)\land\big(\neg\mathit{Loves}(x,F(x))\lor\mathit{Loves}(G(x),x)\big)

    Drop ∀\forall and distribute, leaving two clauses:

Binary resolution lifts the propositional rule: from clauses C∨LC\lor L and D∨¬L′D\lor\neg L', renamed apart, with an mgu θ\theta of LL and L′L', derive (C∨D)θ(C\lor D)\theta. Factoring derives CθC\theta when two literals of CC unify with mgu θ\theta, merging them. Both rules are needed. The set {P(x)∨P(y), ¬P(u)∨¬P(v)}\{P(x)\lor P(y),\ \neg P(u)\lor\neg P(v)\} is unsatisfiable, yet every binary resolvent of it has two literals; factoring the clauses to P(x)P(x) and ¬P(u)\neg P(u) gives □\square in one more step.

Herbrand's theorem and lifting

DerivationProof sketch, and lifting
  1. S⊨Cσfor every clause C∈S and ground σS\models C\sigma\quad\text{for every clause } C\in S \text{ and ground } \sigma

    (⇐\Leftarrow) Ground instances are consequences of SS, since each clause is universally quantified; if some set of them is unsatisfiable, so is SS.

  2. G={Cσ: C∈S, σ ground} unsatisfiable ⟹ ∃ G0⊆G finite and unsatisfiableG=\{C\sigma:\ C\in S,\ \sigma\ \text{ground}\}\ \text{unsatisfiable}\ \Longrightarrow\ \exists\,G_0\subseteq G\ \text{finite and unsatisfiable}

    (⇒\Rightarrow) If SS had a model M\mathcal M, the Herbrand interpretation making a ground atom true iff it is true in M\mathcal M would also satisfy SS, because clauses are universal. So an unsatisfiable SS has no Herbrand model: the set GG of all its ground instances, read propositionally, is unsatisfiable. By compactness of propositional logic, a finite subset already is:

  3. R′=Res(Cσ,Dτ) ⟹ R′=Rλ  for a first-order resolvent RR'=\mathrm{Res}(C\sigma,D\tau)\ \Longrightarrow\ R'=R\lambda\ \ \text{for a first-order resolvent } R

    Lifting lemma. If C′C' and D′D' are ground instances of CC and DD and R′R' is a resolvent of C′C' and D′D', then some resolvent RR of factors of CC and DD has R′R' as an instance, because an mgu is at least as general as the ground substitution:

  4. S unsatisfiable ⟹ S⊢Res□S\ \text{unsatisfiable}\ \Longrightarrow\ S\vdash_{\mathrm{Res}}\square

    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 p1′,…,pn′p_1',\dots,p_n' and a rule p1∧⋯∧pn⇒qp_1\land\dots\land p_n\Rightarrow q, with θ\theta unifying each pi′p_i' with pip_i, infer qθq\theta.

  • 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 x≐f(…x… )x\doteq f(\dots x\dots); 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.

Question 1

What is the mgu of Knows(John,x)\mathit{Knows}(\mathit{John},x) and Knows(y,MotherOf(y))\mathit{Knows}(y,\mathit{MotherOf}(y))?

  1. {x↦MotherOf(y)}\{x\mapsto\mathit{MotherOf}(y)\}
  2. {y↦John, x↦MotherOf(John)}\{y\mapsto\mathit{John},\ x\mapsto\mathit{MotherOf}(\mathit{John})\}
  3. {y↦John, x↦MotherOf(y)}\{y\mapsto\mathit{John},\ x\mapsto\mathit{MotherOf}(y)\}
  4. They do not unify
Show the answer

B. {y↦John, x↦MotherOf(John)}\{y\mapsto\mathit{John},\ x\mapsto\mathit{MotherOf}(\mathit{John})\}

Decompose into John≐y\mathit{John}\doteq y and x≐MotherOf(y)x\doteq\mathit{MotherOf}(y). Swap and eliminate yy, which turns the second equation into x≐MotherOf(John)x\doteq\mathit{MotherOf}(\mathit{John}).

Question 2

Why does first-order resolution need factoring?

  1. To rename variables apart
  2. To eliminate existential quantifiers
  3. To make unification terminate
  4. Because without it some unsatisfiable sets, such as {P(x)∨P(y), ¬P(u)∨¬P(v)}\{P(x)\lor P(y),\ \neg P(u)\lor\neg P(v)\}, have no refutation: every binary resolvent keeps two literals
Show the answer

D. Because without it some unsatisfiable sets, such as {P(x)∨P(y), ¬P(u)∨¬P(v)}\{P(x)\lor P(y),\ \neg P(u)\lor\neg P(v)\}, have no refutation: every binary resolvent keeps two literals

Factoring merges unifiable literals within one clause: P(x)∨P(y)P(x)\lor P(y) becomes P(x)P(x). In propositional logic this happens silently, because clauses are sets.

Question 3

What is the Skolem form of ∀x ∃y Loves(x,y)\forall x\,\exists y\,\mathit{Loves}(x,y)?

  1. ∀x Loves(x,A)\forall x\,\mathit{Loves}(x,A) for a new constant AA
  2. ∃y ∀x Loves(x,y)\exists y\,\forall x\,\mathit{Loves}(x,y)
  3. ∀x Loves(x,F(x))\forall x\,\mathit{Loves}(x,F(x)) for a new function symbol FF
  4. ∀x ∀y Loves(x,y)\forall x\,\forall y\,\mathit{Loves}(x,y)
Show the answer

C. ∀x Loves(x,F(x))\forall x\,\mathit{Loves}(x,F(x)) for a new function symbol FF

The witness yy may depend on xx, so it becomes a function of xx. The result is equisatisfiable with the original, not equivalent to it.

Question 4

Herbrand's theorem reduces first-order unsatisfiability to…

  1. the propositional unsatisfiability of some finite set of ground instances, though which set is not known in advance
  2. the unsatisfiability of one ground instance of each clause
  3. checking all structures with at most nn elements, for some computable nn
  4. 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 SS is unsatisfiable, some finite set of ground instances is propositionally unsatisfiable, and enumerating ever larger sets finds it. If SS 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).