Is composition the same as unification?

No. Unification seeks a matching substitution; composition combines the effects of substitutions applied successively.

Can a later substitution change an earlier replacement term?

Yes. That interaction is one reason composition needs more than appending bindings.

Does the written order of a composition symbol always mean the same thing?

No. Conventions vary, so state which substitution is applied first or define the operation explicitly.

AI Glossary / Graphs and symbolic AI / Intermediate

Composition

Definition

Composition of substitutions combines successive variable replacements into one substitution with the same overall effect. In symbolic AI, it lets a reasoning procedure carry bindings forward as several inference steps are joined. The order matters: a later substitution can change a term introduced by an earlier one, so composition is not generally a simple union of binding lists.

What it means

A substitution maps variables to terms. For example, a substitution may replace X with Y, or replace Y with the constant cedar. Applying substitutions successively can turn an expression containing X into one containing cedar.

A composed substitution captures that sequence in a single mapping. This is useful in backward chaining and unification-based reasoning, where each successful match can add information about variables already involved in the proof.

The supplied textbook context uses composition in this substitution sense. The word also describes combining functions, relations, and software components, but those uses have their own conventions. Here the important question is which variable replacements occur first and how their effects interact.

How it works

State the order explicitly. If theta is applied first and sigma second, the composed substitution must make every expression behave exactly as it would under those two applications in sequence.

Constructing that mapping requires applying sigma to the terms that theta assigns, then retaining relevant sigma bindings for variables not already handled by theta. Identity mappings can be omitted. The precise notation for writing the composition varies across texts and software, so an example is often clearer than an unexplained symbol.

Substitution replaces variables consistently throughout the expression. When working with quantified formulas, the implementation must also respect scope and avoid variable capture. In clause-based reasoning, standardizing variables apart prevents unrelated rule instances from accidentally sharing names.

Composition itself does not prove that two expressions unify. Unification finds bindings that make expressions match; composition combines the effects of bindings obtained during a sequence of steps. A reasoner needs both operations to preserve a coherent proof state.

Three practical examples

1. A backward-chaining engine carries a variable binding from an earlier subgoal into the remaining subgoals of the same proof branch.

2. A theorem prover combines substitutions produced by successive resolution steps so the accumulated result reflects every required replacement.

3. A logic-programming debugger displays how an initially symbolic variable becomes bound to a concrete term after later matches are applied.

Think of it this way

Think of two editing passes: the first replaces a placeholder with another placeholder, and the second replaces that new placeholder with a final value. A combined edit must reproduce both passes in the correct order.

The analogy is limited. Logical substitutions operate on structured terms and scoped variables, not arbitrary character fragments, so ordinary text replacement can give the wrong result.

Worked example

Take the expression pair(X, Y). Let theta map X to f(Y), and let sigma map Y to cedar. Apply theta first. The expression becomes pair(f(Y), Y).

Now apply sigma. Both occurrences of Y are replaced, producing pair(f(cedar), cedar). A single substitution with the same effect maps X to f(cedar) and Y to cedar.

Reverse the order to see why it matters. Applying sigma first to pair(X, Y) produces pair(X, cedar). Applying theta next replaces X with f(Y), producing pair(f(Y), cedar). The newly introduced Y is not changed by the earlier pass, which has already happened.

Under the standard simultaneous-substitution convention used here, these results differ. Merely storing X mapped to f(Y) and Y mapped to cedar as an unexplained list does not tell a reader whether the implementation applies one simultaneous substitution or recursively follows bindings. The representation and application convention must agree.

Illustrative case study

Fictional case: Juniper Rules develops a teaching inference engine. One test binds a query variable to a term containing another variable, then later binds that inner variable to a constant.

The engine incorrectly returns the intermediate term because it appends the new binding without updating the earlier substitution's effect. The developers add a regression case comparing sequential application with the proposed composed result.

They also document how their engine represents chains of bindings internally. The fictional lesson is that a binding list's appearance is less important than the substitution behavior it denotes. Correct composition must preserve the effect of the full inference sequence.

Common misconceptions and mistakes

Composition is not generally commutative. Reversing the order can change which introduced variables receive later replacements, as the worked example demonstrates.

It is not simply the union of two mappings. Earlier replacement terms may themselves require transformation by the later substitution.

Do not confuse a variable name shared accidentally between rule instances with a deliberate logical connection. Renaming variables apart is often necessary before composing proof-step bindings.

Finally, substitution is not arbitrary mutation of constants or predicate symbols. Its formal domain and treatment of bound variables must be specified. An implementation that recursively dereferences bindings should be understood through its resulting substitution semantics, not assumed identical to a one-pass textual operation.

Business use

For business rule systems, substitution composition is usually an implementation detail, but errors can produce incorrect answers that look plausible. It matters when queries share variables across several conditions or use structured terms.

Validation should compare composed application with explicit sequential application on representative expressions. Include repeated variables, terms containing variables, and differently scoped rule instances. Preserve branch-local bindings so that a failed alternative does not contaminate another proof path. These checks support reliable reasoning without requiring end users to inspect internal symbolic mappings.

Check your understanding

Theta maps X to Y, and sigma maps Y to oak. What happens to X when theta is applied first and sigma second?

Answer: X becomes Y, then oak. The composed substitution must therefore map X to oak for that application sequence.

Related terms

Unification
Term
Backward-chaining
Resolution
Standardizing apart
substitution
variable binding
variable capture
function composition

Learn next

Compose two substitutions by explicitly transforming a sample term in stages. Reverse the order and compare results. Then trace a backward-chaining proof with two subgoals that share a variable, checking that later bindings are reflected consistently in the final answer.

Sources

Primary source consulted: Russell and Norvig, Inference in First-Order Logic, backward-chaining discussion and definition of substitution composition, https://aima.cs.berkeley.edu/4th-ed/pdfs/newchap09.pdf . Scope is composition of substitutions, not generic component assembly. The structured-term calculation and fictional debugger case are original.

Previous: Compositing equation Next: Compositional pattern-producing network