Can an MGU contain variables in replacement terms?

Yes. The worked binding x to hub(z) preserves z because the match does not determine it.

Is an MGU always a fully concrete answer?

No. A ground answer assigns all relevant variables to variable-free terms; an MGU may intentionally remain more general.

Can two different-looking substitutions both be MGUs?

Yes. Equivalent choices of variable names or orientation can express the same general solution. Literal textual identity is not the criterion.

AI Glossary / Graphs and symbolic AI / Intermediate

Most general unifier

Definition

A most general unifier, or MGU, is a substitution that makes two symbolic expressions identical while imposing no unnecessary restrictions on their variables. Every other unifier of those expressions can be obtained by further specializing the MGU. For ordinary first-order syntactic unification, an MGU exists whenever the expressions are unifiable and is unique up to equivalent variable renaming.

What it means

Unification finds variable replacements that make structured expressions match. The “most general” part preserves choices that the match does not force. For example, matching a delivery pattern to another pattern may require the same destination in both without requiring any particular destination yet.
This is structural matching, not approximate language similarity. Predicate names, function names, argument positions, and repeated variables matter. Constants are not freely replaceable variables. The standard notion here concerns finite first-order terms without additional equations such as commutativity; more specialized forms of unification can have different properties.

How it works

A unification procedure compares corresponding structures. Matching function or predicate symbols must have compatible argument counts. Variables can be bound to terms, and those bindings must be respected in later comparisons. Conflicting constants or incompatible structures cause failure.
For finite first-order terms, an occurs check prevents binding a variable to a term that contains that same variable, such as x to f(x). An MGU leaves unconstrained variables available rather than assigning arbitrary constants. In a proof procedure, this lets one inference step represent a family of possible instances instead of prematurely committing to one specific instance.

Three practical examples

A first-order theorem prover can match complementary literals before applying a resolution step.
A logic-programming system can match a query with a rule head, carrying consistent variable bindings into the rule body.
A symbolic rule engine can connect structured facts with general patterns while preserving variables that later premises still need to constrain.

Think of it this way

Think of fitting two partly completed forms together and filling only the blanks needed to make them agree. If both forms leave a destination unspecified, there is no reason to invent one. The analogy is limited because logical terms have strict syntax and shared variables impose exact relationships; ordinary forms may permit informal equivalence that syntactic unification does not recognize.

Worked example

Consider the expressions Route(x, hub(y), y) and Route(hub(z), hub(A), A). Lowercase x, y, and z are variables; A is a constant; hub is a function symbol. The first arguments require x = hub(z). The second arguments require y = A. The third arguments confirm that same binding y = A.
An MGU is therefore {x maps to hub(z), y maps to A}. Applying it to both expressions produces Route(hub(z), hub(A), A). Variable z remains free because nothing forces its value.
Adding z maps to B also yields a unifier, producing Route(hub(B), hub(A), A), but it is less general: it adds a restriction not required by the original match. Conversely, Pair(x,x) and Pair(A,B), with distinct constants A and B, cannot unify because x would need to be both constants. Finally, x and hub(x) have no finite-term unifier, which illustrates the purpose of the occurs check.

Illustrative case study

In a fictional equipment-rule prototype, a developer matches maintenance patterns against component descriptions. An early implementation fills every remaining variable with a default component identifier. It succeeds on one demonstration but misses later matches that require another identifier.
The team changes the implementation to preserve unconstrained variables and checks how bindings flow across multiple premises. It also tests repeated variables and cyclic-looking terms separately. The example illustrates why generality matters in symbolic reasoning; it does not report a particular commercial system or a benchmark improvement.

Common misconceptions and mistakes

“Most general” does not mean most likely, most common, or most semantically similar. It refers to the specialization relationship among substitutions. Do not rename constants to make a match succeed, and do not assign different values to separate occurrences of the same variable.
Keep variables from independent rules distinct before combining them; accidentally reusing a name can create a false constraint. Also state the term model. Some programming systems permit cyclic structures under different semantics, so behavior without an occurs check should not automatically be described as ordinary finite first-order unification. Avoid broad claims that every language or implementation handles this identically.

Business use

An MGU is usually an internal mechanism rather than a feature business users directly select. Its value appears in rule matching, formal verification, and explainable symbolic derivations. Correct handling prevents a rule engine from applying a pattern inconsistently or excluding legitimate matches through arbitrary choices.
For an implementation review, use examples that exercise shared variables, nested terms, failed constant matches, and variables that should remain unbound. Explanations should show the substitution supporting a conclusion. That makes it possible to distinguish a modeling error in a rule from an error in the matching procedure itself.

Check your understanding

For Pair(x,y) and Pair(A,z), is {x maps to A, y maps to z, z maps to B} most general?

Answer: No. Binding z to B is unnecessary. The substitution {x maps to A, y maps to z} already makes the expressions identical and retains the option to specialize z later.

Related terms

Learn next

Unify Triple(x,f(x),y) with Triple(A,f(A),z). Check that x must become A and y can be linked to z without choosing a constant. Then change the middle term on the second side to g(A) and explain why distinct function symbols make the structural match fail.

Term

Sources

Sources: Russell and Norvig, Artificial Intelligence: A Modern Approach, Inference in First-Order Logic, section 9.2 on unification, generality, and the occurs check: https://aima.cs.berkeley.edu/4th-ed/pdfs/newchap09.pdf . The Route, Pair, and Triple examples and equipment case are original illustrations.

Previous: Mosaic effect Next: Most likely state