[Progra] Prolog, allgemeinster Unifikator

[Progra] Programmierung
[DSAL] Datenstrukturen und Algorithmen
[SWT] Softwaretechnik
[DB] Datenbanken und Informationssysteme

Prolog, allgemeinster Unifikator

Beitragvon Matthew » 21.02.10 22:04

Hey,
wenn ich gegeben habe:
h(g(X),p(Y),p(g(A)),p(A))
h(Y,Z,Z,p(X))

Ist dann
Y = g(X)
Z = p(Y)
X = A

auch ein allgemeiner Unifikator?
In der Musterlösung steht:
X = A
Y = g(A)
Z = p(g(A))

Darf es am Ende nur von der einen Variablen A abhängig sein, oder wäre meine obere Lösung auch korrekt?

Grüße
Matthew
Matthew
 
Beiträge: 37
Registriert: 14.07.09 23:14

Re: Prolog, allgemeinster Unifikator

Beitragvon seb » 21.02.10 22:19

Matthew hat geschrieben:Hey,
wenn ich gegeben habe:
h(g(X),p(Y),p(g(A)),p(A))
h(Y,Z,Z,p(X))

Ist dann
Y = g(X)
Z = p(Y)
X = A

auch ein allgemeiner Unifikator?

Möglicherweise ein allgemeiner aber kein allgemeinster :) Ich würde das so machen:
1.Schritt
Y=g(x)
Z=p(Y)=p(g(A))
X=A

2. Schritt
Y=g(X)=g(A)
Z=p(Y)=p(g(A))
X=A

Wenn man alles "ausgetauscht" hat was man austauschen kann und das nicht zu Widersprüchen geführt hat steht immer hinterm letzten Gleichheitszeichen die Lösung.
seb
 
Beiträge: 52
Registriert: 16.10.09 17:15
Studiengang: Informatik (B.Sc.)
Studiert seit: WS 09/10
Anwendungsfach: BWL

Re: Prolog, allgemeinster Unifikator

Beitragvon Matthew » 21.02.10 22:22

Danke :wink:
Matthew
 
Beiträge: 37
Registriert: 14.07.09 23:14

Re: Prolog, allgemeinster Unifikator

Beitragvon seb » 21.02.10 22:29

Vielleicht sollte ich dazu Anmerken das das meine eigene Theorie ist :D Also lieber noch mal nachhaken ... :)
seb
 
Beiträge: 52
Registriert: 16.10.09 17:15
Studiengang: Informatik (B.Sc.)
Studiert seit: WS 09/10
Anwendungsfach: BWL

Re: Prolog, allgemeinster Unifikator

Beitragvon C-Otto » 22.02.10 01:19

Wichtig ist, dass die Substitution, wenn sie auf einen Term angewendet wird, nur exakt einmal "ausgewertet" wird. Wenn also X zu A wird und Y zu f(X), wird aus dem Term Y nicht etwa f(A), sondern f(X). Dementsprechend ist im mgu-Algorithmus auch vorgesehen, dass man die bisherigen Teil-Subtstitutionen mitschleppt und bei der Konstruktion der weiteren Ergebnisse berücksichtigt.
Dr. rer. nat. Carsten Otto
http://verify.rwth-aachen.de/otto/
Benutzeravatar
C-Otto
 
Beiträge: 568
Registriert: 10.08.06 00:20
Wohnort: Schwalbach am Taunus
Studiert seit: fertig
Anwendungsfach: BWL

Re: Prolog, allgemeinster Unifikator

Beitragvon seb » 22.02.10 01:52

C-Otto hat geschrieben:Wichtig ist, dass die Substitution, wenn sie auf einen Term angewendet wird, nur exakt einmal "ausgewertet" wird. Wenn also X zu A wird und Y zu f(X), wird aus dem Term Y nicht etwa f(A), sondern f(X). Dementsprechend ist im mgu-Algorithmus auch vorgesehen, dass man die bisherigen Teil-Subtstitutionen mitschleppt und bei der Konstruktion der weiteren Ergebnisse berücksichtigt.


Verstehe ich nicht. Wenn X = A gilt und Y=f(X) dann gilt doch auch Y=f(A) wenn W=f(A) dann gilt doch auch W=Y
seb
 
Beiträge: 52
Registriert: 16.10.09 17:15
Studiengang: Informatik (B.Sc.)
Studiert seit: WS 09/10
Anwendungsfach: BWL

Re: Prolog, allgemeinster Unifikator

Beitragvon C-Otto » 22.02.10 10:17

Mit dem Zeichen "=" wird hier eine Substitution angedeutet (die ich sonst immer mit "/" schreibe). In diesem Kontext ist "=" also nicht die übliche Gleichheitsrelation, insbesondere folgt aus X=Y und Y=a nicht X=a. Im Folgenden verwende ich lieber "/", um Substitutionen anzudeuten.

Hier zwei Beispielsubstitutionen, um den Unterschied klarzumachen:

sigma1:
X/a
Y/f(X)

term: g(X, Y)

sigma1(term) = g(a, f(X))

sigma2:
X/a
Y/f(a)

sigma2(term) = g(a, f(a))

Es gilt aber sigma1(sigma1(term)) = sigma2(term) = g(a, f(a)).

Ein mgu muss aber schon nach einmaliger Anwendung "passen", es gibt hier keine Fixpunktberechnung oder ähnliches.

PS: Ich meinte jeweils a statt A

EDIT: Da stand oben mal komischer Kram zu "=". Jetzt passt es.
Dr. rer. nat. Carsten Otto
http://verify.rwth-aachen.de/otto/
Benutzeravatar
C-Otto
 
Beiträge: 568
Registriert: 10.08.06 00:20
Wohnort: Schwalbach am Taunus
Studiert seit: fertig
Anwendungsfach: BWL


Zurück zu Praktische Informatik