Automatisierung des logischen Schließens
Festlegungen zur Durchführung der Suche nach Herleitungen
Im letzten Abschnitt wurde gezeigt, dass Anfragen an eine Wissensbasis ausgewertet werden können, indem man Herleitungen der (ggf. konkretisierten) Fakten der Anfrage mit Hilfe der verallgemeinerten modus-ponens-Regel erzeugt.
Die Vorgehensweise bei der Suche nach Herleitungen war bisher nichtdeterministisch. Es wurde nicht festgelegt, nach welchen Kriterien die Auswahl der zu benutzenden Fakten und Regeln erfolgen soll.
Wenn man das logische Schließen mit der verallgemeinerten modus-ponens-Regel automatisiert durchführen möchte, dann müssen zusätzliche Vereinbarungen getroffen werden: In welcher Reihenfolge werden die Fakten und Regeln der Wissensbasis bei Suche nach Herleitungen berücksichtigt? In welcher Reihenfolge werden Bedingungen einer Regel bearbeitet.
Wir benutzen im Folgenden die (auch von Prolog benutzte) Standardfestlegung: Fakten und Regeln der Wissensbasis werden immer der Reihe nach (von oben nach unten) bearbeitet. Bedingungen von Regeln werden ebenfalls immer der Reihe nach (von links nach rechts) bearbeitet. Wir sprechen im Folgenden von logischen Herleitungen bzgl. einer Bearbeitungsreihenfolge, wenn die Festlegungen hinsichtlich der Bearbeitungsreihenfolge beachtet werden.
Herleitungssackgassen und Backtracking
Wie sich die getroffenen Festlegungen auswirken, soll am folgenden Beispiel verdeutlicht werden. Die Wissensbasis ist wie folgt gegeben:
weiblich(hera).
weiblich(hebe).
maennlich(zeus).
maennlich(ares).
maennlich(hephaestus).
kind(ares, hera).
kind(hebe, hera).
kind(hephaestus, hera).
kind(ares, zeus).
kind(hebe, zeus).
kind(hephaestus, zeus).
vater(X, Y) :- kind(Y, X), maennlich(X).
mutter(X, Y) := kind(Y, X), weiblich(X).
Die Anfrage an die Wissensbasis lautet: Wer ist der Vater von Hebe?
?- vater(V, hebe).
Zur Auswertung der Anfrage erzeugen wir eine Rückwärtsherleitung.
?- vater(V, hebe).
benutze: vater(X, Y) :- kind(Y, X), maennlich(X). {X -> V; Y -> hebe}
?- kind(hebe, V), maennlich(V).
benutze: kind(hebe, hera). {V -> hera}
?- maennlich(hera).
keine Fortsetzung der Rückwärtsherleitung möglich!
benutze: kind(hebe, zeus). {V -> zeus}
?- maennlich(zeus).
benutze: maennlich(zeus).
?-
V = zeus
Bei der Bearbeitung der Bedingung kind(hebe, V) wird zunächst das Faktum
kind(hebe, hera). der Wissensbasis benutzt. Beachte, dass dieses Faktum
das erste in der Wissensbasis ist, das zur Bearbeitung herangezogen werden kann.
Wenn man die verallgemeinerte modus-ponens-Regel mit dem ersten gefundenen Faktum durchführt, ergibt sich eine Situation, in der die Herleitung nicht weiter fortsetzbar ist. Wir sind in eine Herleitungssackgasse geraten.
Eine solche Herleitungssackgasse bedeutet aber nicht unbedingt, dass die Anfrage kein Ergebnis hat. Vielmehr muss man jetzt nach anderen Herleitungsmöglichkeiten suchen.
Man benutzt hier eine Strategie, die Backtracking genannt wird. Durch systematisches Zurückgehen wird versucht, bereits begonnene Herleitungen mit anderen Fakten und Regeln fortzusetzen.
Im oben gezeigten Beispiel wird bei der Bearbeitung der Bedingung kind(hebe, V)
als nächstes das Faktum kind(hebe, zeus). benutzt.
Dieser Herleitungsweg erweist sich als günstig, da die Herleitung anschließend
erfolgreich abgeschlossen werden kann.
Denkbar wäre, dass es weitere Anwendungsmöglichkeiten von Fakten und Regeln im oben gezeigten Beispiel geben könnte. Diese müssten dann systematisch alle durchgespielt werden. Eine genauere Analyse ergibt jedoch, dass es solche weiteren Anwendungsmöglichkeiten nicht gibt.
Endlose Herleitungsversuche
Weitere Konsequenzen der oben getroffenen Festlegungen sollen am Beispiel der folgenden Wissensbasis aufgezeigt werden.
kind(hera, rhea).
kind(hebe, hera).
vorfahr(X, Y) :- kind(Y, X).
vorfahr(X, Y) :- kind(Y, Z), vorfahr(X, Z).
Die Anfrage an die Wissensbasis lautet: Wer ist ein Vorfahr von Hebe?
?- vorfahr(V, hebe).
Zur Auswertung der Anfrage erzeugen wir eine Rückwärtsherleitung.
?- vorfahr(V, hebe).
benutze: vorfahr(X, Y) :- kind(Y, X). {X -> V; Y -> hebe}
?- kind(hebe, V).
benutze: kind(hebe, hera). {V -> hera}
?-
V = hera
benutze: vorfahr(X, Y) :- kind(Y, Z), vorfahr(X, Z). {X -> V; Y -> hebe}
?- kind(hebe, Z), vorfahr(V, Z).
benutze: kind(hebe, hera). {Z -> hera}
?- vorfahr(V, hera).
benutze vorfahr(X, Y) :- kind(Y, X). {X -> V; Y -> hera}
?- kind(hera, V).
benutze kind(hera, rhea). {V -> rhea}
?-
V = rhea
benutze vorfahr(X, Y) :- kind(Y, Z), vorfahr(X, Z). {X -> V; Y -> hera}
?- kind(hera, Z), vorfahr(V, Z).
benutze kind(hera, rhea). {Z -> rhea}
?- vorfahr(V, rhea).
benutze vorfahr(X, Y) :- kind(Y, X). {X -> V; Y -> rhea}
?- kind(rhea, V).
keine Fortsetzung der Rückwärtsherleitung möglich!
benutze vorfahr(X, Y) :- kind(Y, Z), vorfahr(X, Z). {X -> V; Y -> rhea}
?- kind(rhea, Z), vorfahr(V, Z).
keine Fortsetzung der Rückwärtsherleitung möglich!
Hier ist alles soweit in Ordnung. Es werden die Ergebnisse V = hera und V = rhea
erzeugt.
Aber was geschieht, wenn wir die Reihenfolge von Regeln und Bedingungen abändern?
kind(hera, rhea).
kind(hebe, hera).
vorfahr(X, Y) :- vorfahr(X, Z), kind(Y, Z).
vorfahr(X, Y) :- kind(Y, X).
Die Anfrage an die Wissensbasis lautet: Wer ist ein Vorfahr von Hebe?
?- vorfahr(V, hebe).
Zur Auswertung der Anfrage erzeugen wir eine Rückwärtsherleitung.
?- vorfahr(V, hebe).
benutze: vorfahr(X, Y) :- vorfahr(X, Z), kind(Y, Z). {X -> V; Y -> hebe}
?- vorfahr(V, Z), kind(hebe, Z).
benutze: vorfahr(X, Y) :- vorfahr(X, Z1), kind(Y, Z1). {X -> V; Y -> Z}
?- vorfahr(V, Z1), kind(Z, Z1), kind(hebe, Z).
benutze: vorfahr(X, Y) :- vorfahr(X, Z2), kind(Y, Z2). {X -> V; Y -> Z1}
?- vorfahr(V, Z2), kind(Z1, Z2), kind(Z, Z1), kind(hebe, Z).
...
Es ergibt sich eine endlose Herleitung, bei der immer die (teils umbenannte) Regel
vorfahr(X, Y) :- vorfahr(X, Z), kind(Y, Z). benutzt wird.
Logisch herleitbar / logisch herleitbar bzgl. einer Auswertungsreihenfolge
Das gezeigte Beispiel zeigt eine Diskrepanz zwischen "logisch herleitbar" und "logisch herleitbar bzgl. einer Auswertungsreihenfolge" auf.
Aus der Wissensbasis
kind(hera, rhea).
kind(hebe, hera).
vorfahr(X, Y) :- vorfahr(X, Z), kind(Y, Z).
vorfahr(X, Y) :- kind(Y, X).
ist z.B. das Faktum vorfahr(hera, hebe).
durchaus logisch herleitbar. Man muss nur jeweils die "richtigen" Fakten und Regeln bei der Herleitung benutzen.
Die Ausführungen oben zeigen, dass eine entsprechende Herleitung unter Beachtung der getroffenen Festlegungen zur Auswertungsreihenfolge nicht möglich ist, da die Auswertung von Bedingungen zu einer endlosen - und damit nicht erfolgreichen - Herleitung führt.
Zusammenfassung: Automatisierung des logischen Schließens
Ergebnisse zu Anfragen an eine Wissensbasis lassen sich durch systematisches Erzeugen von logischen Herleitungen bestimmen.
Im Zentrum steht dabei eine logische Schlussregel. Mit Hilfe der verallgemeinerten modus-ponens-Schlussregel (und der Schlussregel zur Spezialisierung von Allaussagen) werden die logischen Herleitungen erzeugt.
Zur Automatisierung der Anwendung von Schlussregeln werden Vereinbarungen zur Auswertungsreihenfolge getroffen.
Zur Anwendung von Regeln mit Variablen benötigt man zusätzlich einen Algorithmus zur Erzeugung von Variablenbindungen. Wir haben Variablenbindungen in den bisher gezeigten Beispielen jeweils vorgegeben und uns um die systematische Erzeugung und Verwaltung dieser Bindungen nicht gekümmert.
Schließlich benötigt man ein Verfahren zur Bearbeitung von Herleitungssackgassen. Man benutzt hier Backtracking, um systematisch an geeignete Verzweigungspunkte von Herleitungen zurückzugehen.
Ein Softwaresystem, das alle diese Verfahren zur automatisierten Erzeugung von logischen herleitungen umsetzt, nennt man auch Inferenzmaschine.
Beachte die Grenzen dieser Vorgehensweise. Zum Einen muss man darauf achten, durch ungünstig gewählte Reihenfolgen keine endlosen Herleitungen zu erzeugen. Zum Anderen muss man die closed-world-assumption beachten, nach der nur Ergebnisse erzielt werden können, die aus der Wissensbasis herleitbar sind. Insbesondere sind "negative Aussagen" wie "... gilt nicht" hier nicht möglich.
Aufgabe 1
(a) Gegeben ist die folgende Wissensbasis.
kind(hera, rhea).
kind(hebe, hera).
vorfahr(X, Y) :- kind(Y, Z), vorfahr(X, Z).
vorfahr(X, Y) :- kind(Y, X).
Die Anfrage an die Wissensbasis lautet: Wer ist ein Vorfahr von Hebe?
?- vorfahr(V, hebe).
Welches Ergebnis erhält man hier?
(b) Gegeben ist jetzt die Wissensbasis:
kind(hera, rhea).
kind(hebe, hera).
vorfahr(X, Y) :- kind(Y, X).
vorfahr(X, Y) :- vorfahr(X, Z), kind(Y, Z).
Die Anfrage an die Wissensbasis lautet: Wer ist ein Vorfahr von Hebe?
?- vorfahr(V, hebe).
Welches Ergebnis erhält man jetzt?