Suche nach logischen Herleitungen

Orientierung

Wie können Anfragen an eine Wissensbasis ausgewertet werden? Im Folgenden wird gezeigt, dass dabei die verallgemeinerte modus-ponens-Schlussregel eine zentrale Rolle spielt.

In einem ersten Schritt betrachten wir eine sehr einfache Wissensbasis, bei der die Fakten und Regeln keine Variablen enthalten. Die hier gewonnenen Erkenntnisse werden dann in einem zweiten Schritt auf beliebige Wissensbasen verallgemeinert.

Eine Wissensbasis ohne Variablen

Als Beispiel betrachten wir eine Welt, in der es um die Zusammenstellung von Mittagessen geht.

es_gibt_fleisch.
es_gibt_suppe.
es_gibt_pudding    :- es_gibt_fleisch, es_gibt_kartoffeln.
es_gibt_pudding    :- es_gibt_pizza.
es_gibt_eis        :- es_gibt_pizza.
es_gibt_kartoffeln :- es_gibt_suppe.

Die Anfrage an die Wissensbasis lautet: Gibt es Pudding?

?- es_gibt_pudding.

Zur Auswertung der Anfrage beschreiben wir im Folgenden zwei Wege: Herleitung des Anfrageergebnisses durch Vorwärtsschließen bzw. durch Rückwärtsschließen.

Herleitung durch Vorwärtsschließen

Wir leiten die Aussage es_gibt_pudding. aus der Wissensbasis mit Hilfe der Schlussregel modus ponens her.

Veranschaulichung der Herleitungsschritte:

Schritt 1: Wir benutzen das Faktum es_gibt_suppe. und die Regel es_gibt_kartoffeln :- es_gibt_suppe. aus der Wissensbasis, um das Faktum es_gibt_kartoffeln. herzuleiten.

es_gibt_kartoffeln :- es_gibt_suppe.
es_gibt_suppe.
===================================
es_gibt_kartoffeln.

Schritt 2: Wir benutzen das gerade hergeleitete Faktum es_gibt_kartoffeln. sowie das Faktum es_gibt_fleisch. und die Regel es_gibt_pudding :- es_gibt_fleisch, es_gibt_kartoffeln. aus der Wissensbasis, um das Faktum es_gibt_pudding. herzuleiten.

es_gibt_pudding :- es_gibt_fleisch, es_gibt_kartoffeln.
es_gibt_fleisch.
es_gibt_kartoffeln.
======================================================
es_gibt_pudding.

Die Herleitung zeigt, dass die Aussage es_gibt_pudding. (bezogen auf die vorgegebene Wissensbasis) wahr ist. Das Ergebnis zur Anfrage lautet demnach Yes.

Herleitung durch Rückwärtsschließen

Die oben gezeigte Herleitung kann man auch durch Rückwärtsschließen erzeugen:

Veranschaulichung der Herleitungsschritte:

?- es_gibt_pudding.
    benutze: es_gibt_pudding :- es_gibt_fleisch, es_gibt_kartoffeln.
    ?- es_gibt_fleisch, es_gibt_kartoffeln. 
        benutze: es_gibt_fleisch.
        ?- es_gibt_kartoffeln. 
            benutze: es_gibt_kartoffeln :- es_gibt_suppe.
            ?- es_gibt_suppe. 
                benutze: es_gibt_suppe.
                ?-
Yes

Zeige, dass es_gibt_pudding. bzgl. der Wissensbasis wahr ist. Wegen der Regel es_gibt_pudding :- es_gibt_fleisch, es_gibt_kartoffeln. reicht es zu zeigen, dass es_gibt_fleisch, es_gibt_kartoffeln. bzgl. der Wissensbasis wahr ist. Da das Faktum es_gibt_fleisch. in der Wissensbasis gegeben ist, reicht es zu zeigen, dass es_gibt_kartoffeln. bzgl. der Wissensbasis wahr ist. Wegen der Regel es_gibt_kartoffeln :- es_gibt_suppe. reicht es zu zeigen, dass es_gibt_suppe bzgl. der Wissensbasis wahr ist. Da das Faktum es_gibt_suppe. in der Wissensbasis gegeben ist, gibt es nichts mehr zu zeigen. Die Herleitung ist damit erfolgreich abgeschlossen.

Aufgabe 1

Betrachte die folgende Wissensbasis:

es_gibt_suppe.
es_gibt_fisch      :- es_ist_freitag.
es_gibt_fisch      :- es_gibt_kartoffeln, es_gibt_salat.
es_gibt_nachtisch  :- es_ist_sonntag.
es_gibt_salat      :- es_gibt_kartoffeln.
es_gibt_kartoffeln :- es_gibt_suppe.
es_gibt_fleisch    :- es_gibt_kartoffeln.

(a) Werte die folgende Anfrage mit einer logischen Herleitung aus:

?- es_gibt_fisch.

(b) Welches Ergebnis erhält man bei der Auswertung der folgenden Anfrage? Wie zeigt sich das durch logische Herleitungen?

?- es_gibt_nachtisch.

Eine Wissensbasis mit Variablen

Wir betrachten als weiteres Beispiel einen Ausschnitt aus der Welt der griechischen Götter. Beachte, dass hier Regeln mit Variablen vorkommen.

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). 

Herleitung durch Vorwärtsschließen

Wir leiten die Aussage vater(zeus, hebe). aus der Wissensbasis mit Hilfe der verallgemeinerten Schlussregel modus ponens her.

vater(X, Y) :- kind(Y, X), maennlich(X).
kind(hebe, zeus).
maennlich(zeus).
======================================= {X -> zeus; Y -> hebe}
vater(zeus, hebe).

Die Herleitung zeigt, dass die Aussage vater(zeus, hebe). (bezogen auf die vorgegebene Wissensbasis) wahr ist. Ein mögliches Ergebnis wird also durch die Variablenbelegung {V -> zeus} gegeben, da diese Variablenbelegung die Anfrage zu einer wahren Aussage macht. Da es keine weiteren Herleitungen von Aussagen der Gestalt vater(..., hebe). gibt, liefert die Variablenbelegung {V -> zeus} das einzige mögliche Ergebnis.

Herleitung durch Rückwärtsschließen

Beim Rückwärtsschließen wird die Variablenbelegung mit erzeugt:

?- vater(V, hebe).
    benutze: vater(X, Y) :- kind(Y, X), maennlich(X). {X -> V; Y -> hebe}
    ?- kind(hebe, V), maennlich(V). 
        benutze: kind(hebe, zeus). {V -> zeus}
        ?- maennlich(zeus). 
            benutze: maennlich(zeus).
            ?-
V = zeus

Da es keine weiteren vollständigen Rückwärtsableitungen gibt, liefert die Variablenbelegung {V -> zeus} das einzige mögliche Ergebnis.

Aufgabe 2

Betrachte die folgende Wissensbasis:

kind(hebe, zeus).
kind(hebe, hera).
kind(hades, rhea).
kind(hera, rhea).
kind(zeus, rhea).
vorfahr(X, Y) :- kind(Y, X). 
vorfahr(X, Y) :- kind(Y, Z), vorfahr(X, Z). 

Die Anfrage an die Wissensbasis lautet:

?- vorfahr(V, hebe).

Welche Ergebnisse lassen sich hier mit logischen Herleitungen erzielen?

Herleitungen ohne Erfolg

Beispiel 1: Wir betrachten zunächst noch einmal die Wissensbasis zur Zusammenstellung von Mittagessen:

es_gibt_fleisch.
es_gibt_suppe.
es_gibt_pudding    :- es_gibt_fleisch, es_gibt_kartoffeln.
es_gibt_pudding    :- es_gibt_pizza.
es_gibt_eis        :- es_gibt_pizza.
es_gibt_kartoffeln :- es_gibt_suppe.

Die Anfrage an die Wissensbasis lautet jetzt: Gibt es Eis?

?- es_gibt_eis.

Es gibt keine Möglichkeit, durch Vorwärtsschließen mit der Schlussregel modus ponens zur Aussage es_gibt_eis. zu gelangen.

Man merkt das auch beim Rückwärtsschließen, wenn keine Regel zur Anwendung der Schlussregel modus ponens existiert, um eine Rückwärtsherleitung fortzusetzen.

?- es_gibt_eis.
    benutze: es_gibt_eis :- es gibt pizza.
    ?- es_gibt_pizza. 
        keine Fortsetzung der Rückwärtsherleitung möglich!
No

Die Anfage ist also mit No zu beantworten, da keine Herleitung des Faktums der Anfrage erzeugt werden kann.

Beispiel 2: Wir betrachten auch eine modifizierte Wissensbasis zur Welt der griechischen Götter. Beachte, dass vergessen wurde, das Faktum maennlich(zeus). in die Wissensbasis aufzunehmen.

weiblich(hera).
weiblich(hebe).
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 wieder: Wer ist der Vater von Hebe?

?- vater(V, hebe). 

Es gibt jetzt keine Möglichkeit, ein - mit einer Variablenbelegung konkretisiertes - Faktum zur Anfrage herzuleiten. Die folgende Rückwärtsherleitung verdeutlicht die Schwierigkeit.

?- vater(V, hebe).
    benutze: vater(X, Y) :- kind(Y, X), maennlich(X). {X -> V; Y -> hebe}
    ?- kind(hebe, V), maennlich(V). 
        benutze: kind(hebe, zeus). {V -> zeus}
        ?- maennlich(zeus). 
            keine Fortsetzung der Rückwärtsherleitung möglich!
No

Obwohl Zeus in der Götterwelt der Vater von Hebe ist, ergibt sich kein entsprechender Zusammenhang in der durch die Wissensbasis gegebenen Modellwelt.

Wenn keine erfolgreiche Herleitung der (ggf. konkretisierten) Fakten der Anfrage möglich ist, wird das Ergebnis No geliefert. Man benutzt hier die sog. closed world assumption, die besagt, dass nur das in der Modellwelt gelten soll, was durch die Wissensbasis explizit oder implizit gegeben ist.

Zusammenfassung: Auswertung von Anfragen mit logischen Herleitungen

Hier sind noch einmal die wesentlichen Ergebnisse dieses Abschnitts zusammengestellt.