Az egyesítési algoritmus

• fejezetek: 3.2.2.

Egyesítés és behelyettesítés fogalma

• bemenő paraméteradás:

	hívás: nagyszülője('Imre', Nsz)
	fej:	nagyszülője(Gy, N)
	=> behelyettesítés: Gy='Imre', N=Nsz.
	

• kimenő paraméter:

	hívás: szülője('Imre', Sz)
	fej:	szülője('Imre', 'István')
	=> behelyettesítés: Sz='István'.
	

3.2.2 Az egyesítési algoritmus

A és B kifejezések egyesíthetőek, ha létezik egy olyan σ behelyettesítés, hogy Aσ = Bσ. Ezt a σ behelyettesítést A és B egyesítőjének nevezzük. A és B legáltalánosabb egyesítője σ (mgu(A,B) = σ), ha σ A és B minden egyesítőjénél általánosabb.

A Prolog egyesítési algoritmusa

a bemenete két Prolog kifejezés: A és B ha a két kifejezés egyesíthető, akkor előállítja a legáltalánosabb egyesítőt (mgu(A,B))

1. Ha A és B azonos változók vagy konstansok, akkor az egyesítés sikeres és σ = {} (üres behelyettesítés, nem változtat semmit).
2. Egyébként, ha A változó, akkor az egyesítés sikeres és σ = {A $\leftarrow$ B}.
3. Egyébként, ha B változó, akkor az egyesítés sikeres és σ = {B $\leftarrow$ A}.
4. Egyébként, ha A és B azonos nevű és argumentumszámú összetett kifejezések és argumentumlistáik A₁, ..., A_N ill. B₁, ..., B_N, és
   1. A₁ és B₁ legáltalánosabb egyesítője σ₁,
   2. A₂σ₁ és B₂σ₁ legáltalánosabb egyesítője σ₂,
   3. A₃σ₁σ₂ és B₃σ₁σ₂ legáltalánosabb egyesítője σ3,
   4. ...

akkor az egyesítés sikeres és σ = σ₁ $\otimes$ σ₂ $\otimes$ σ₃ $\otimes$ ...

1. Minden más esetben A és B nem egyesíthető.

Pl.:

	?- 3--(4--5) = Left--Right.
		 Left=3, Right=4--5 ?
	?- X*Y=1+2*3.
		 no			  % ugyanis kanonikus alakja: *(X,Y) != +(1,*(2,3))
	?- f(a, 3/Y-X, Y) = f(U, B-U, 3).
		 B=3/3, U=a, X=a, Y=3 ?