Az egyesítési algoritmus

A VIK Wikiből
A lap korábbi változatát látod, amilyen (vitalap) 2012. október 21., 21:09-kor történt szerkesztése után volt. (Új oldal, tartalma: „{{GlobalTemplate|Infoalap|PrologElm3}} * fejezetek: 3.2.2. ==Egyesítés és behelyettesítés fogalma== * bemenő paraméteradás: <pre> hívás: nagyszülője('I…”)
(eltér) ← Régebbi változat | Aktuális változat (eltér) | Újabb változat→ (eltér)
Ugrás a navigációhoz Ugrás a kereséshez

Ez az oldal a korábbi SCH wiki-ről lett áthozva. Az eredeti változata itt érhető el.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor kérlek javíts rajta egy rövid szerkesztéssel.

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót


  • 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 [math]\leftarrow[/math] B}.
  3. Egyébként, ha B változó, akkor az egyesítés sikeres és σ = {B [math]\leftarrow[/math] 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 [math]\otimes[/math] σ2 [math]\otimes[/math] σ3 [math]\otimes[/math] ...

  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 ?