# Dictionary Definition

unification

### Noun

2 the state of being joined or united or linked;
"there is strength in union" [syn: union] [ant: separation]

3 the act of making or becoming a single unit;
"the union of opposing factions"; "he looked forward to the
unification of his family for the holidays" [syn: union, uniting, conjugation, jointure] [ant: disunion]

# User Contributed Dictionary

### Noun

#### Translations

- Dutch: vereniging, eenmaking
- German: Vereinigung

#### Derived terms

## French

### Noun

unification- Unification.

# Extensive Definition

In mathematical
logic, in particular as applied to computer
science, a unification of two terms is a join (in the lattice
sense) with respect to a specialisation order. That is, we suppose
a preorder on a set of
terms, for which t* ≤ t means that t* is obtained from t by
substituting some term(s) for one or more free
variables in t. The unification u of s and t, if it exists, is
a term that is a substitution instance of both s and t. If any
common substitution instance of s and t is also an instance of u, u
is called minimal unification.

For example, with polynomials, X 2 and Y 3 can
be unified to Z6 by taking X = Z3 and Y = Z2.

## Unification in logic programming

The concept of unification is one of the main
ideas behind logic
programming, best known through the language Prolog. It
represents the mechanism of binding the contents of variables and
can be viewed as a kind of one-time assignment. In Prolog, this
operation is denoted by symbol "=". It is also used in other
languages by the use of the symbol "=", but also in conjunction
with many operations including "+", "-", "*", "/".

- In traditional Prolog, a variable X which is uninstantiated—i.e. no previous unifications were performed on it—can be unified with an atom, a term, or another uninstantiated variable, thus effectively becoming its alias. In many modern Prolog dialects and in first-order logic, a variable cannot be unified with a term that contains it; this is the so called occurs check. (More generally, any type variable unifies with any type expression and is instantiated to that expression.)
- Two Prolog atoms can only be unified if they are identical. (More generally, Any two type constants unify only if they are the same type.)
- Similarly, a term can be unified with another term if the top function symbols and arities of the terms are identical and if the parameters can be unified simultaneously. Note that this is a recursive behavior. (More generally, any two type constructions unify only if they are applications of the same type constructor and all of their component types also recursively unify.)

Due to its declarative nature, the order in a
sequence of unifications is (usually) unimportant.

Note that in the terminology of first-order
logic, an atom is a basic proposition and is unified similarly
to a Prolog term.

## Examples of unification

In the convention of Prolog, atoms begin with
lowercase letters.

- A = A : Succeeds (tautology)
- A = B, B = abc : Both A and B are unified with the atom abc
- xyz = C, C = D : Unification is symmetric
- abc = abc : Unification succeeds
- abc = xyz : Fails to unify because the atoms are different
- f(A) = f(B) : A is unified with B
- f(A) = g(B) : Fails because the heads of the terms are different
- f(A) = f(B, C) : Fails to unify because the terms have different arity
- f(g(A)) = f(B) : Unifies B with the term g(A)
- f(g(A), A) = f(B, xyz) : Unifies A with the atom xyz and B with the term g(xyz)
- A = f(A) : Infinite unification, A is unified with f(f(f(f(...)))). In proper first-order logic and many modern Prolog dialects this is forbidden (and enforced by the occurs check)
- A = abc, xyz = X, A = X : Fails to unify; effectively abc = xyz

## References

- F. Baader and T. Nipkow, Term Rewriting and All That. Cambridge University Press, 1998.
- F. Baader and W. Snyder, Unification Theory. In J.A. Robinson and A. Voronkov, editors, Handbook of Automated Reasoning, volume I, pages 447–533. Elsevier Science Publishers, 2001.
- Joseph Goguen, What is Unification?.

## See also

unification in Bulgarian: Унификация

unification in German: Unifikation (Logik)

unification in French: Unification

unification in Japanese: ユニフィケーション

unification in Polish: Unifikacja

unification in Portuguese: Unificação

unification in Vietnamese: Hợp nhất (lô
gích)

unification in Chinese: 合一

# Synonyms, Antonyms and Related Words

Anschluss, addition, affiliation, agglomeration, agglutination, aggregation, agreement, alignment, alliance, amalgamation, articulation, assimilation, association, blend, blending, bond, bracketing, cabal, cahoots, cartel, centralization, clustering, coadunation, coalescence, coalition, colleagueship, collegialism, collegiality, combination, combine, combo, communication, composition, comradeship, concatenation, concourse, concurrence, confederacy, confederation, confluence, confraternity, congeries, conglomeration, conjugation, conjunction, connection, consolidation, conspiracy, convergence, copartnership, copartnery, copulation, coupling, ecumenism, embodiment, encompassment, enosis, federalization, federation, fellowship, fraternalism, fraternity, fraternization, freemasonry, fusion, gathering, hookup, identification, identity, inclusion, incorporation, individuality, indivisibility, intactness, integrality, integration, integrity, intercommunication,
intercourse,
interlinking,
interlocking,
inviolability,
irreducibility,
joinder, joining, jointure, junction, junta, knotting, league, liaison, linkage, linking, marriage, meeting, meld, melding, mergence, merger, merging, oneness, organic unity, package, package deal, pairing, particularity, partnership, purity, selfsameness, simplicity, singleness, singularity, sodality, solidarity, solidification, solidity, sorority, splice, symbiosis, syncretism, syndication, syneresis, synthesis, tie, tie-in, tie-up, undividedness, uniformity, union, uniqueness, unity, univocity, wedding, wholeness, yoking