How Unification Finds the Most General Unifier in Logic AI

What a most general unifier is, a worked example, the occurs check in Prolog, and how unification speed improved after Robinson's 1965 paper.

Guide: AI BasicsLast verified: October 20266 min read

Unification is the procedure that finds a substitution making two logical expressions identical, and the most general unifier (MGU) is the substitution that commits to as little as possible, so every other solution is a special case of it. J. A. Robinson published the algorithm in his 1965 paper on the resolution principle, and the same idea now sits inside Prolog's matching step and inside Hindley-Milner type inference.

Key takeaways

  • A unifier replaces variables with terms so that two expressions become equal; the MGU is the least committal such replacement.
  • For first-order terms a solvable problem has one MGU, unique up to renaming of variables.
  • The occurs check rejects cases such as X = f(X); many Prolog systems skip it by default for speed.
  • Robinson's original method can take exponential time; later algorithms by Paterson and Wegman (1978) and Martelli and Montanari (1982) are far faster.
  • Unification is syntactic matching with variables. It does not learn, and it does not integrate databases on its own.

What a unifier is

A term in first-order logic is a constant (ann), a variable (X), or a function applied to terms (mother(X)). A substitution maps variables to terms. Applying one to an expression replaces every occurrence of each variable at once. Two expressions unify when some substitution makes them syntactically identical, and that substitution is called a unifier.

Many unifiers usually exist. Take likes(X, Y) and likes(ann, Z). Binding X to ann and Y to Z works, and so does binding X to ann, Y to bob, and Z to bob. The second answer is correct but needlessly specific, because it fixes Y and Z to a value that the two expressions never demanded. The first answer is the MGU: any other unifier can be obtained from it by a further substitution. For syntactic first-order unification, the MGU is unique up to renaming variables, so binding Y to Z or Z to Y counts as the same answer.

A worked example, step by step

The method of Martelli and Montanari treats unification as solving a set of equations and applies a few rewrite rules until nothing is left to simplify. The example below is illustrative and uses made-up predicate names.

Problem: unify edge(X, g(Y)) with edge(h(Z), g(Z)).

StepEquationsRule applied
Startedge(X, g(Y)) = edge(h(Z), g(Z))Same predicate and same number of arguments
OneX = h(Z); g(Y) = g(Z)Decompose: split into one equation per argument
TwoX = h(Z); Y = ZDecompose again: g(Y) = g(Z) reduces to its arguments
ThreeX = h(Z); Y = ZEach left side is a variable that does not occur on its right side, so the equations are solved

The MGU is the substitution that sends X to h(Z) and Y to Z. If the second argument had been a constant, such as edge(X, a) against edge(h(Z), g(Z)), the rule called conflict would stop the process: the constant a can never equal a term that starts with g, so no unifier exists and the match fails.

The occurs check

One case needs special care. Unifying X with f(X) asks for a term that contains itself. No finite term satisfies that equation, so a correct algorithm must fail. Testing for it is the occurs check, and it costs time because every variable binding requires scanning the other term.

Prolog systems often leave the test out. The SWI-Prolog manual describes unify_with_occurs_check/2, which fails on A = f(A), while the ordinary = operator succeeds by building a cyclic term. The manual's flag section lists the occurs_check flag with the values false (the default), true, and error, and warns that changing it globally may break libraries. The trade-off is deliberate: skipping the test makes ordinary programs faster and lets cyclic data exist, at the price of answers that are not strictly sound.

Speed and the history of the algorithm

Robinson's 1965 paper in the Journal of the ACM (volume 12, issue 1, pages 23 to 41) is titled "A Machine-Oriented Logic Based on the Resolution Principle". It combined substitution and truth-functional reasoning into one inference rule, resolution, and unification is the part of resolution that matches literals. Jacques Herbrand had described related ideas in 1930, but the machine-oriented formulation is credited to Robinson.

The straightforward implementation has a weakness: applying each new binding to the remaining terms copies subterms, and the copies can multiply. Constructed examples make the result grow exponentially in the size of the input. Representing terms as graphs that share identical subterms removes the blow-up. Paterson and Wegman described an algorithm whose time and space are linear in the input size (Journal of Computer and System Sciences, 1978). Martelli and Montanari published their equation-based algorithm in ACM Transactions on Programming Languages and Systems in 1982, with an embedded acyclicity test. A later paper noted that the Paterson-Wegman method has the best worst-case bound but carries notable implementation overhead, and that the overhead is milder for Martelli and Montanari's method.

Where unification is used

  • Resolution theorem provers use it to decide which clauses can be combined.
  • Prolog uses it to match a goal against rule heads and to pass values through variables.
  • Type checkers for ML-family languages use it to solve equations between type variables. Milner's 1978 paper on type polymorphism notes that Hindley recognized Robinson's algorithm as the right tool for the problem, and a failure to unify signals a type error.
  • Martelli and Montanari's paper lists equation languages, production-based database systems, type checkers, and critical pair computation in term rewriting as further uses.

Limits and common misconceptions

Unification works on the form of symbols, not on their meaning. It cannot tell that cost and price are synonyms, and two database fields with different names do not unify unless a rule links them. Describing it as a solution for integrating data across systems goes beyond what the sources support: it is one building block that logic-based systems use after the data has been mapped into terms.

It is also not machine learning. The result is exact: the algorithm either returns the MGU or reports failure, and nothing is estimated from examples. Variants exist for harder settings. Higher-order unification, where terms can contain functions as arguments, is undecidable in general, and unification modulo equational theories such as commutativity needs different algorithms. This article covers only the first-order syntactic case.

FAQ

Is the most general unifier always unique?

For first-order syntactic terms, yes, up to renaming variables. Two answers that differ only by swapping which variable stands for the shared value describe the same MGU.

Why do Prolog systems usually skip the occurs check?

The check adds work to every binding. SWI-Prolog documents unify_with_occurs_check/2 and an occurs_check flag so programs can request sound unification when needed, and the default flag value is false.

Who invented the unification algorithm?

Herbrand sketched related ideas in 1930. Robinson's 1965 resolution paper is the usual credit for the algorithm in its machine-oriented form.

Does unification have anything to do with neural networks?

Not directly. Unification belongs to symbolic reasoning and returns exact answers. Research that combines the two approaches exists, but it is outside the scope of this explainer.

Last verified: October 2026

Sources

  • Robinson JA, A Machine-Oriented Logic Based on the Resolution Principle, Journal of the ACM 12(1), 1965
  • Martelli A, Montanari U, An Efficient Unification Algorithm, ACM Transactions on Programming Languages and Systems 4(2), 1982
  • Paterson MS, Wegman MN, Linear Unification, Journal of Computer and System Sciences 16(2), 1978
  • Milner R, A Theory of Type Polymorphism in Programming, Journal of Computer and System Sciences 17(3), 1978
  • unify_with_occurs_check/2 and the occurs_check flag, SWI-Prolog manual, 2026

New to artificial intelligence?

Start with the basics, then follow the guides to tools, rules, and effects on society.

Start with AI Basics