Az egyesítési algoritmus

A VIK Wikiből
(PrologElm3 szócikkből átirányítva)
  • 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 B}.
  3. Egyébként, ha B változó, akkor az egyesítés sikeres és σ = {B A}.
  4. Egyébként, ha A és B azonos nevű és argumentumszámú összetett kifejezések és argumentumlistáik A1, ..., AN ill. B1, ..., BN, és
    1. A1 és B1 legáltalánosabb egyesítője σ1,
    2. A2σ1 és B2σ1 legáltalánosabb egyesítője σ2,
    3. A3σ1σ2 és B3σ1σ2 legáltalánosabb egyesítője σ3,
    4. ...


akkor az egyesítés sikeres és σ = σ1 σ2 σ3 ...

  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 ?