##  [Unification (Logic)](/unification-logic-0) 

 Definition

The algorithmic process of finding a substitution (mapping from variables to terms) that makes two symbolic expressions identical up to syntactic equality (or equality modulo a theory); central to automated reasoning, type inference, and logic programming.

 

 

 

 

 

 





## Principle

Principle

Search for a most general unifier (mgu) that solves the matching equations between corresponding subterms without introducing unnecessary instantiations; the occur-check prevents cyclic substitutions, and variants include syntactic first-order unification, E‑unification (modulo equational theories), and higher-order unification with dramatically different decidability and complexity profiles.

 

 

 

 

 





## Demonstration

Demonstration

First‑order example: unify f(x,a) and f(b,y) — the mgu is {x↦b, y↦a}. Occur‑check example: unifying x and f(x) fails because any solution would be cyclic (in first‑order unification the occur‑check rejects this). Higher‑order example: unification in λ-calculus (higher-order) is undecidable in general and requires different algorithms (e.g., Huet's semi-decision procedures) or restrictions for decidability.

 

 

 

 

## Misapplication

Misapplication

Omitting the occur‑check in implementations yields unsound substitutions that permit infinite terms and wrong answers. Applying first‑order unification algorithms to problems involving associative/commutative operators or higher-order binders without using the appropriate E‑unification or higher-order machinery leads to incorrect or incomplete unification.

 

 

 

 

 





## Consequence

Consequence

Unification yields the substitutions needed for resolution in first‑order theorem proving, for type inference in programming languages, and for matching in rewrite systems; when mgus exist they enable general, reusable solutions, while the intractability or undecidability in more expressive settings constrains automated reasoning and requires heuristics or restricted fragments.

 

 

 

 

## Reversal

Reversal

Matching (one-sided unification) restricts variables to one expression and is computationally simpler; anti-unification (generalization) computes least general generalizers rather than most general unifiers. Reversing unification conceptually shifts from solving equations to finding schematic abstractions.

 

 

 

 

 





## Boundary

Boundary

First‑order syntactic unification is decidable and has most general unifiers when solvable; unification modulo theories (AC, associative-commutative, etc.) or higher-order unification can be undecidable or of much higher complexity. Exact properties depend on the logic and theory in which unification is performed.

 

 

 

 

 





## Semantic Tension

Semantic Tension

Tension between syntactic unification (pure term structure) and semantic unification (modulo theories) affects both completeness and performance; trade-offs arise between richer equational reasoning and algorithmic tractability.

 

 

 

 

 





## Synthesis

Synthesis

Unification is the process of computing substitutions that make terms equal under a chosen notion of equality; as a core operation in automated deduction and type systems it balances the desire for most general, reusable solutions against limitations imposed by occurrences, equational theories, and higher-order features, which alter decidability and complexity.