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.
Anfragen an eine Wissensbasis lassen sich über logische Herleitungen mit der verallgemeinerten modus-ponens-Schlussregel (und der Regel zur Spezialisierung von Allaussagen) auswerten.
Eine Ja-Nein-Anfrage liefert das Ergebnis Yes genau dann,
wenn es eine Herleitung zu den Fakten der Anfrage aus der Wissensbasis gibt.
Eine Variablenbelegung ist ein Ergebnis zu einer Anfrage mit Variablen genau dann, wenn es eine Herleitung aus der Wissensbasis zu den - mit der Variablenbelegung konkretisierten - Fakten der Anfrage gibt.
Wenn keine erfolgreiche Herleitung der (ggf. konkretisierten) Fakten der Anfrage möglich ist,
wird das Ergebnis No geliefert.