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(hephaistos).
kind(ares, hera).
kind(hebe, hera).
kind(hephaistos, hera).
kind(ares, zeus).
kind(hebe, zeus).
kind(hephaistos, 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.

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?