Logische Programmierung
Klaus Becker
2014
2
Logische Programmierung
3
Teil 1
Modellierung von Wissen
4
Die Welt der griechischen Götter
(Heaven) Uranus = Gaea (Earth)
|
--------------------------------------|
|
|
Cronus = Rhea
|
Coeus = Phoebe
|
|
|
|
Iapetus
|
|
|
Zeus = Hera
|
|
Hebe
|
|
|
|
---------
|
|
---------------
Ares
----------------
Persephone
|
|
|
|
Athena |
|
|
Leto = Zeus
Hestia | Poseidon | Demeter=Zeus
Hades
Oceanus = Tethys
|
---------------------|
|
Apollo
|
|
Prometheus
Atlas
Epimetheus
|
|
|
Zeus=Maia
Zeus=Dione
|
|
Hermes
Aufgabe
Kannst du die folgenden Verwandschaftsbeziehungen klären?
|
|
Artemis |
|
Hephaestus
|
Aphrodite
(a) Wer ist ein Cousin von Zeus?
(b) Hat Zeus auch mit Cousinen Kinder gezeugt?
(c) Welche Halbbrüder und Halbschwestern hat Hermes?
Quelle:
http://www.desy.de/gna/interpedia/
greek_myth/godsFT.html
5
Orientierung
Wissensbasis
Ziel ist es, mit einem Informatiksystem
das Wissen über eine Miniwelt (wie die
Welt der griechischen Götter) so zu
erfassen, dass Anfragen an die Welt (wie
"Wer ist ein Cousin von Hermes?") von
diesem Informatiksystem automatisiert
ausgewertet werden können.
Wir benutzen die Programmiersprache
Prolog zur Wissensmodellierung und zur
Formulierung von Anfragen an die
Wissensbasis.
Anfrage
In den folgenden Abschnitten wird
zunächst auf die Wissenmodellierung und
die Formulierung von Anfragen an die
Wissensbasis eingegangen.
6
Modellierungsansatz
Eine (Mini-) Welt besteht aus Objekten (Personen, Gegenstände, ...), die Eigenschaften haben
und in Beziehung zueinander stehen.
Zeus
(männlich)
Hera
(weiblich)
ist Kind
von
Ares
(männlich)
Miniwelt "griechische Götter"
7
Konstanten, Prädikate
Objekte werden mit Konstanten (allg. mit Termen) beschrieben, Eigenschaften und
Beziehungen mit Hilfe von Prädikaten.
Prädikat
Zeus
(männlich)
Hera
(weiblich)
ist Kind
von
Ares
(männlich)
Miniwelt "griechische Götter"
% Fakten
weiblich(hera).
maennlich(zeus).
maennlich(ares).
kind(ares, hera).
kind(ares, zeus).
Konstante
Prädikat
Modellierung der Miniwelt
Fakten
8
Sachverhalte der Miniwelt können direkt mit Hilfe von Fakten beschrieben werden.
Zeus
(männlich)
Hera
(weiblich)
ist Kind
von
% Fakten
weiblich(hera).
maennlich(zeus).
maennlich(ares).
kind(ares, hera).
kind(ares, zeus).
Fakten
Ares
(männlich)
Miniwelt "griechische Götter"
Modellierung der Miniwelt
Regeln
9
Sachverhalte der Miniwelt können auch indirekt mit Hilfe von Regeln beschrieben werden.
Cronus = Rhea
|
---------------------|
|
|
|
|
Hestia | Poseidon | Demeter
Hades
Zeus = Hera
Miniwelt
% Fakten:
maennlich(cronus).
maennlich(zeus).
..
weiblich(rhea).
weiblich(demeter).
...
kind(hestia, rhea).
kind(hades, rhea).
...
direkte
Beschreibung
mit Fakten
% weitere Fakten:
mutter(rhea, hestia).
mutter(rhea, hades).
...
indirekte
Beschreibung
mit Regeln
% Regeln:
vater(X, Y) :- kind(Y, X), maennlich(X).
mutter(X, Y) :- kind(Y, X), weiblich(X).
Regeln
10
Regeln sind Wenn-Dann-Aussagen.
Implikation
Und
Variable
% Regeln:
mutter(X, Y) :- kind(Y, X), weiblich(X).
vater(X, Y) :- kind(Y, X), maennlich(X).
Regelkopf
(Folgerung)
Regelrumpf
(Bedingungen)
informelle Beschreibung:
X ist Mutter von Y, wenn Y Kind von X ist und X weiblich ist.
X ist Vater von Y, wenn Y Kind von X ist und X männlich ist.
Rekursive Regeln
11
Das Prädikat im Regelkopf darf im Regelrumpf vorkommen.
% Regeln:
vorfahr(X, Y) :- kind(Y, X).
vorfahr(X, Y) :- kind(Y, Z), vorfahr(X, Z).
Regelkopf
(Folgerung)
Regelrumpf
(Bedingungen)
informelle Beschreibung:
X ist Vorfahr von Y, wenn Y Kind von X ist.
X ist Vorfahr von Y, wenn Y Kind von Z und X Vorfahr von Z ist.
12
Aufgaben
Aufgabe 1
Vervollständige die Regeln.
elternteil(X, Y) :sohn(X, Y) :-
oma(X, Y) :Aufgabe 2
Warum muss man in der folgenden Regel die Bedingung X \== Y (für X und Y sind ungleich)
mit aufnehmen?
bruder(X, Y) :maennlich(X), elternteil(E, X), elternteil(E, Y), X \== Y.
Aufgabe 3
Entwickle weitere Regeln.
onkel(X, Y) :tante(X, Y) :-
cousin(X, Y) :...
13
Logik-Programme
Ein Logik-Programm besteht aus einer Wissensbasis und einer Anfrage.
% Fakten
maennlich(cronus).
maennlich(zeus).
..
weiblich(rhea).
weiblich(demeter).
weiblich(hera).
weiblich(hestia).
kind(hestia, rhea).
kind(hades, rhea).
..
% Regeln
vater(X, Y) :- kind(Y, X), maennlich(X).
mutter(X, Y) :- kind(Y, X), weiblich(X).
Wissensbasis
?- weiblich(hera).
Anfrage
14
SWI-Prolog-Editor
Wissensbasis
Anfrage
15
PROLOG
PROLOG steht für „Programming in Logic“.
Die Programmiersprache PROLOG wurde Anfang der siebziger Jahre (des 20. Jahrhunderts)
von Alain Colmerauer und Robert Kowalski konzipiert.
SWI-PROLOG ist ein freies und professionelles PROLOG-System, das seit 1987 an der
Universität Amsterdam entwickelt und gepflegt wird.
Der SWI-PROLOG-Editor ist eine für den Unterricht geeignete Entwicklungsumgebung zur
Erstellung von PROLOG-Programmen, die von G. Röhner entwickelt wurde.
Installationshinweise:
Installieren Sie zunächst SWI-PROLOG.
Installieren Sie anschließend den SWI-PROLOG-Editor.
16
Eine Wissensbasis erzeugen
Geben Sie die Fakten und Regeln zur Beschreibung der Miniwelt ein oder laden Sie die
entsprechende Quelldatei. Bevor Sie Anfragen an die Wissensbasis stellen können, muss diese
Wissensbasis erst erzeugt werden. Rufen Sie hierzu das Systemprädikat "consult" auf.
Consultieren
Wenn der PROLOG-Compiler
keine Syntaxfehler gefunden hat,
bestätigt er die erfolgreiche
Erzeugung der Wissensbasis mit
"Yes".
Mit consult(<Datei>). werden aus der angegebenen Datei die
Fakten und Regeln in die Wissensbasis eingelesen.
17
Eine Anfrage stellen
Geben Sie jetzt die Anfrage im unteren Fenster (hinter "?-") ein. Mit der "Return"-Taste erhält
man das erste Ergebnis (falls es eines gibt), mit jedem weiteren "Return" ggf. weitere
Ergebnisse.
Findet der PROLOGInterpreter keine weiteren
Ergebnisse, so zeigt er dies
mit "No" an.
Das trennende Semikolon
kann als "oder" gedeutet
werden.
Anfrage
Ergebnisse
Anfrage
18
Ja-Nein-Anfragen
% Wissensbasis
Ist Hera
maennlich(cronus).
weiblich?
maennlich(zeus).
maennlich(poseidon).
maennlich(hades).
Ist Zeus
weiblich(rhea).
weiblich?
weiblich(demeter).
weiblich(hera).
weiblich(hestia).
kind(hestia, rhea).
kind(hades, rhea).
kind(poseidon, rhea).
kind(zeus, rhea).
kind(hera, rhea).
kind(demeter, rhea).
kind(hestia, cronus).
kind(hades, cronus).
kind(poseidon, cronus).
kind(zeus, cronus).
kind(hera, cronus).
kind(demeter, cronus).
mutter(X, Y) :- kind(Y, X), weiblich(X).
vater(X, Y) :- kind(Y, X), maennlich(X).
?- weiblich(hera).
Yes
?- weiblich(zeus).
No
19
Ergänzungsanfragen
% Wissensbasis
Wer ist Vater von
maennlich(cronus).
Zeus?
maennlich(zeus).
maennlich(poseidon).
maennlich(hades).
weiblich(rhea).
weiblich(demeter).
Wer ist Kind von
weiblich(hera).
Rhea?
weiblich(hestia).
kind(hestia, rhea).
kind(hades, rhea).
kind(poseidon, rhea).
kind(zeus, rhea).
kind(hera, rhea).
kind(demeter, rhea).
kind(hestia, cronus).
kind(hades, cronus).
kind(poseidon, cronus).
kind(zeus, cronus).
kind(hera, cronus).
kind(demeter, cronus).
mutter(X, Y) :- kind(Y, X), weiblich(X).
vater(X, Y) :- kind(Y, X), maennlich(X).
?- vater(V, zeus).
V = cronus ;
No
?- kind(K, rhea).
K = hestia ;
K = hades ;
K = poseidon ;
K = zeus ;
K = hera ;
K = demeter ;
No
20
Ergänzungsanfragen
% Wissensbasis
Wer ist Mutter
maennlich(cronus).
von wem?
maennlich(zeus).
maennlich(poseidon).
maennlich(hades).
weiblich(rhea).
weiblich(demeter).
weiblich(hera).
weiblich(hestia).
kind(hestia, rhea).
kind(hades, rhea).
kind(poseidon, rhea).
kind(zeus, rhea).
kind(hera, rhea).
kind(demeter, rhea).
kind(hestia, cronus).
kind(hades, cronus).
kind(poseidon, cronus).
kind(zeus, cronus).
kind(hera, cronus).
kind(demeter, cronus).
mutter(X, Y) :- kind(Y, X), weiblich(X).
vater(X, Y) :- kind(Y, X), maennlich(X).
?- mutter(X, Y).
X = rhea
Y = hestia ;
X = rhea
Y = hades ;
X = rhea
Y = poseidon ;
X = rhea
Y = zeus ;
X = rhea
Y = hera ;
X = rhea
Y = demeter ;
No
21
Anfragen mit anonymen Variablen
% Wissensbasis
Wer ist Vater
maennlich(cronus).
(von einem Kind)?
maennlich(zeus).
maennlich(poseidon).
maennlich(hades).
weiblich(rhea).
weiblich(demeter).
weiblich(hera).
weiblich(hestia).
kind(hestia, rhea).
kind(hades, rhea).
kind(poseidon, rhea).
kind(zeus, rhea).
kind(hera, rhea).
kind(demeter, rhea).
kind(hestia, cronus).
kind(hades, cronus).
kind(poseidon, cronus).
kind(zeus, cronus).
kind(hera, cronus).
kind(demeter, cronus).
mutter(X, Y) :- kind(Y, X), weiblich(X).
vater(X, Y) :- kind(Y, X), maennlich(X).
?- vater(V, _Kind).
V = cronus ;
V = cronus ;
V = cronus ;
V = cronus ;
V = cronus ;
V = cronus ;
No
Anonyme Variablen beginnen mit
einem Unterstrich. Anonyme
Variablen werden benutzt, wenn
man an den Variablenwerten
selbst nicht interessiert ist.
22
Zusammengesetzte Anfragen
% Wissensbasis
Wer ist weiblich
maennlich(cronus).
und
maennlich(zeus).
hat einen Vater?
maennlich(poseidon).
maennlich(hades).
weiblich(rhea).
weiblich(demeter).
weiblich(hera).
weiblich(hestia).
kind(hestia, rhea).
kind(hades, rhea).
kind(poseidon, rhea).
kind(zeus, rhea).
kind(hera, rhea).
kind(demeter, rhea).
kind(hestia, cronus).
kind(hades, cronus).
kind(poseidon, cronus).
kind(zeus, cronus).
kind(hera, cronus).
kind(demeter, cronus).
mutter(X, Y) :- kind(Y, X), weiblich(X).
vater(X, Y) :- kind(Y, X), maennlich(X).
?- weiblich(Tochter),
vater(_Vater, Tochter).
Tochter = demeter ;
Tochter = hera ;
Tochter = hestia ;
No
Eine Anfrage kann auch aus
mehreren Teilanfragen bestehen.
Diese werden mit einem Komma
(zu deuten als logisches Und)
abgetrennt.
23
Fazit: Programmieren mit Logik
Ein Logik-Programm besteht aus einer Wissensbasis und einer Anfrage.
% Fakten
maennlich(cronus).
maennlich(zeus).
..
weiblich(rhea).
weiblich(demeter).
weiblich(hera).
weiblich(hestia).
kind(hestia, rhea).
kind(hades, rhea).
..
% Regeln
vater(X, Y) :- kind(Y, X), maennlich(X).
mutter(X, Y) :- kind(Y, X), weiblich(X).
?- weiblich(hera).
Bei der Programmentwicklung steht logische Modellierung im Vordergrund. Aufgabe des
Programmentwicklers ist es, das Wissen und die Anfragen an das Wissen in der Sprache der
Logik zu modellieren.
24
Fazit: Programmieren mit Logik
Ein Logik-Programm besteht aus einer Wissensbasis und einer Anfrage.
% Fakten
maennlich(cronus).
..
weiblich(rhea).
weiblich(demeter).
weiblich(hera).
weiblich(hestia).
kind(hestia, rhea).
..
% Regeln
vater(X, Y) :- kind(Y, X), maennlich(X).
mutter(X, Y) :- kind(Y, X), weiblich(X).
?- weiblich(hera).
Yes
Zur Auswertung von Logikprogrammen benötigt man eine sog. Inferenzmaschine, die in der
Lage ist, aus der Wissensbasis und der Anfrage an die Wissenbasis die Ergebnisse mit Hilfe
logischer Schlüsse zu erschließen.
25
Aufgaben
Erweitere die oben gezeigte Wissensbasis um folgende Fakten und Regeln
...
maennlich(ares).
weiblich(hebe).
maennlich(hephaestus).
kind(ares, hera).
kind(ares, zeus).
kind(hebe, hera).
kind(hebe, zeus).
kind(hephaestus, hera).
kind(hephaestus, zeus).
vorfahr(X, Y) :- kind(Y, X).
vorfahr(X, Y) :- kind(Y, Z), vorfahr(X, Z).
Entwickle geeignete Anfragen und teste sie.
(a) Wer ist ein männlicher Vorfahr von Hebe?
(b) Wer ist Mutter und hat einen weiblichen Vorfahr?
(c) Wer ist Vorfahr eines Vaters?
26
Aufgaben
Vervollständige die Wissensbasis und kläre mit geeigneten Anfragen die folgenden
Verwandschaftsbeziehungen:
(a) Wer ist ein Cousin von Zeus?
(b) Hat Zeus auch mit Cousinen Kinder gezeugt?
(c) Welche Halbbrüder und Halbschwestern hat Hermes?
alternativ:
Erstelle eine Wissensbasis und geeignete Anfragen zu deiner Familie.
27
Aufgaben
Eine Miniwelt "Unterricht" ist wie folgt gegeben:
Petra Schmitt (Kürzel: scm) unterrichtet die 6b in Mathematik. Der Unterricht findet montags
in 6. Stunde, dienstags in der 3. Stunde, mittwochs in der 1. Stunde und freitags in der 3.
Stunde statt.
Wolfgang Degen (Kürzel: deg) unterrichtet die 6b in Deutsch. Der Unterricht findet dienstags
in der 5. und 6. Stunde, donnerstags in der 2. Stunde und freitags in der 5. Stunde statt.
Karin Engel (Kürzel: eng) unterrichtet die 6b in Musik. Der Unterricht findet mittwochs in der
4. Stunde und freitags in der 6. Stunde statt.
...
Der Unterricht in einer Klasse in einem zweistündigen Fach ist "verteilt", wenn die beiden
Stunden nicht am selben Tag stattfinden.
Mögliche Anfragen wären hier:
Wer unterrichtet die 6b? Wann findet der Deutschunterricht statt? Hat die 6b freitags in der 6.
Stunde Sport? Ist der Musikunterricht in der 6b verteilt? ...
(a) Entwickle zunächst eine geeignete Wissensbasis, in der die oben beschriebenen
Sachverhalte gelten. Entwickle anschließend Anfragen an die wissensbasis.
(b) Erweitere die Wissensbasis in sinnvoller Weise. Formuliere selbst in Worten weitere
Anfragen und übersetze sie dann in die Sprache von Prolog.
28
Aufgaben
Wir betrachte eine Miniwelt "Sitzplan":
Entwickle eine Wissensbasis zu diesem Sitzplan. Folgende Anfragen soll dann gestellt werden:
(a) Wer sitzt direkt neben Pia?
(b) Welches Mädchen sitzt neben einem Jungen?
(c) Wer sitzt in derselben Reihe wie Anja?
29
Teil 2
Auswertung von Anfragen
30
Modus Ponens
Zur Herleitung der Sachverhalte der Modellwelt wird die logische Schlussregel modus ponens
benutzt. Regeln werden dabei als Wenn-Dann-Aussagen interpretiert. Die in der Regel
vorkommenden Variablen sind Platzhalter für alle Objekte der Modellwelt.
Alle Menschen sind sterblich.
Sokrates ist ein Mensch.
Sokrates ist sterblich.
sterblich(X) :- mensch(X).
mensch(sokrates).
sterblich(sokrates).
sterblich(X) :- mensch(X).
mensch(sokrates).
?- sterblich(X).
X = sokrates;
No.
Modus Ponens
31
Die Schlussregel modus ponens erlaubt es, aus wahren Aussagen weitere
wahre Aussagen herzuleiten. Man schließt dabei folgendermaßen:
Wenn die Aussage α → β wahr ist und wenn zusätzlich die Aussage α
wahr ist, dann muss auch die Aussage β wahr sein.
Platz
Mannschaft
Spiele
Punkte
...
...
...
...
11
1.FC Kaiserslautern
32
33
...
...
...
...
α→β
α
β
Wenn Kaiserslautern das Spiel gewinnt,
dann kann Kaiserslautern nicht mehr absteigen.
Kaiserslautern gewinnt das Spiel.
16
FC St. Pauli
32
29
17
VfL Wolfsburg
32
28
18
1.FC Nürnberg
32
26
Kaiserslautern kann nicht mehr absteigen.
Modus Ponens
32
Verallgemeinerung der Schlussregel modus ponens:
Hier geht man von einer Wenn-Dann-Aussage mit mehreren, durch ein
logisches Und verknüpften Bedingungen aus. Die Schlussregel besagt:
Wenn die Wenn-Dann-Aussage wahr ist und alle Bedingungen dieser
Aussage wahr sind, dann ist auch die Folgerung dieser Aussage wahr.
Platz
Mannschaft
Spiele
Punkte
...
...
...
...
11
1.FC Kaiserslautern
32
33
...
...
...
...
16
FC St. Pauli
32
29
17
VfL Wolfsburg
32
28
18
1.FC Nürnberg
32
26
α1, ... αn -> β
α1
...
αn
β
Wenn St. Pauli verliert und
Wolfburg unentschieden spielt,
dann kann Kaiserslautern nicht mehr absteigen.
St. Pauli verliert das vorletzte Spiel.
Wolfburg spielt nur uentschieden.
Kaiserslautern kann nicht mehr absteigen.
33
Spezialisierung bei Allaussagen
Allaussagen machen - wie der Name es sagt - Aussagen für alle (in dem Gegenstandsbereich
erlaubten) Objekte. Die folgende Schlussregel besagt, dass man aus einer wahren Allaussage
eine wahre Aussage erhält, wenn man sie nur für spezielle Objekte formuliert.
Für alle X: mensch(X) -> sterblich(X).
mensch(sokrates) -> sterblich(sokrates)
Für alle X1, ..., Xk: γ (X1, ..., Xk)
γ(c1, ..., ck)
Spezialisierung
bei Allaussagen
{X -> sokrates}
{X1 -> c1, ..., Xk -> ck}
Modus Ponens
34
Häufig (wie im Beispiel unten) tritt die
Situation ein, dass man zwei
Schlussregeln - Regel zur
Spezialisierung von Allaussagen und die
modus-ponens-Regel - bei einer
logischen Herleitung anwenden muss.
Zur Vereinfachung von logischen
Herleitungen ist es daher sinnvoll, aus
den beiden Regeln eine zusätzliche
logische Schlussregel zu formulieren.
α1(X1, ..., Xk), ... αn(X1, ..., Xk) -> β(X1, ..., Xk)
α1(c1, ..., ck)
...
αn(c1, ..., ck)
β(c1, ..., ck)
modus ponens
bei Allaussagen
Spezialisierung
bei Allaussagen
Für alle X: mensch(X) -> sterblich(X).
Alle Menschen sind sterblich.
Sokrates ist ein Mensch.
Sokrates ist sterblich.
modus ponens
mensch(sokrates) -> sterblich(sokrates)
mensch(sokrates) -> sterblich(sokrates)
mensch(sokrates)
sterblich(sokrates)
{X -> sokrates}
35
Suche nach logischen Herleitungen
es_gibt_fleisch.
es_gibt_suppe.
es_gibt_pudding
es_gibt_eis
es_gibt_pudding
es_gibt_kartoffeln
::::-
es_gibt_fleisch, es_gibt_kartoffeln.
es_gibt_pizza.
es gibt pizza.
Wissensbasis ohne Variablen
es_gibt_suppe.
?- es_gibt_pudding.
es_gibt_kartoffeln :- es_gibt_suppe.
es_gibt_suppe.
-----------------------------------es_gibt_kartoffeln.
Anfrage ohne Variablen
logische Herleitung
es_gibt_pudding
:- es_gibt_fleisch, es_gibt_kartoffeln.
es_gibt_fleisch.
es_gibt_kartoffeln.
---------------------------------------------------------logische Herleitung
es_gibt_pudding.
Yes.
Ergebnis der Anfrage
36
Suche nach logischen Herleitungen
es_gibt_kartoffeln :- es_gibt_suppe.
es_gibt_suppe.
-----------------------------------es_gibt_kartoffeln.
logische Herleitung
es_gibt_pudding
:- es_gibt_fleisch, es_gibt_kartoffeln.
es_gibt_fleisch.
es_gibt_kartoffeln.
---------------------------------------------------------logische Herleitung
es_gibt_pudding.
?- 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
Rückwärtsherleitung
37
Suche nach logischen Herleitungen
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).
?- vater(V, hebe).
Wissensbasis mit Variablen
Anfrage mit Variablen
vater(X, Y) :- kind(Y, X), maennlich(X).
logische Herleitung
kind(hebe, zeus).
maennlich(zeus).
---------------------------------------- {X -> zeus; Y -> hebe}
vater(zeus, hebe).
V = zeus
Ergebnis der Anfrage
38
Suche nach logischen Herleitungen
vater(X, Y) :- kind(Y, X), maennlich(X).
logische Herleitung
kind(hebe, zeus).
maennlich(zeus).
---------------------------------------- {X -> zeus; Y -> hebe}
vater(zeus, hebe).
?- 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
Rückwärtsherleitung
39
Herleitungen ohne Erfolg
es_gibt_fleisch.
es_gibt_suppe.
es_gibt_pudding
es_gibt_eis
es_gibt_pudding
es_gibt_kartoffeln
?- es_gibt_eis.
::::-
es_gibt_fleisch, es_gibt_kartoffeln.
es_gibt_pizza.
es gibt pizza.
Wissensbasis ohne Variablen
es_gibt_suppe.
Anfrage ohne Variablen
?- es_gibt_eis.
benutze: es_gibt_eis :- es gibt pizza.
?- es_gibt_pizza.
keine Fortsetzung der Rückwärtsherleitung möglich!
No
Rückwärtsherleitung
40
Herleitungen ohne Erfolg
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).
?- vater(V, hebe).
Wissensbasis mit Variablen
Anfrage mit Variablen
?- vater(V, hebe).
benutze: vater(X, Y) :- kind(Y, X), maennlich(X).
{X -> V; Y -> hebe}
Rückwärtsherleitung
?- kind(hebe, V), maennlich(V).
benutze: kind(hebe, zeus). {V -> zeus}
?- maennlich(zeus).
keine Fortsetzung der Rückwärtsherleitung möglich!
No
41
Zwischenfazit: Auswertung v. Anfragen
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 (negation by failure!).
?- 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
Aufgaben
42
kind(hera,
kind(hebe,
vorfahr(X,
vorfahr(X,
rhea).
hera).
Y) :- kind(Y, X).
Y) :- kind(Y, Z), vorfahr(X, Z).
?- vorfahr(V, hebe).
Welche Ergebnisse lassen sich hier mit
logischen Herleitungen erzielen?
Verwende zunächst Vorwärtsherleitungen.
Verwende anschließend auch
Rückwärtsherleitungen.
43
Automatisierung d. logischen Schließens
es_gibt_fleisch.
es_gibt_suppe.
es_gibt_pudding
es_gibt_pudding
es_gibt_eis
es_gibt_kartoffeln
::::-
es_gibt_pizza.
es_gibt_fleisch, es_gibt_kartoffeln.
es_gibt_pizza.
es_gibt_suppe.
?- es_gibt_pudding.
es_gibt_kartoffeln :- es_gibt_suppe.
es_gibt_suppe.
-----------------------------------es_gibt_kartoffeln.
Herleitung mit nichtdeterministische
Auswahl der Regeln
logische Herleitung
es_gibt_pudding
:- es_gibt_fleisch, es_gibt_kartoffeln.
es_gibt_fleisch.
es_gibt_kartoffeln.
---------------------------------------------------------logische Herleitung
es_gibt_pudding.
Yes.
44
Automatisierung d. logischen Schließens
es_gibt_fleisch.
es_gibt_suppe.
es_gibt_pudding
es_gibt_pudding
es_gibt_eis
es_gibt_kartoffeln
?- es_gibt_pudding.
::::-
es_gibt_pizza.
es_gibt_fleisch, es_gibt_kartoffeln.
es_gibt_pizza.
es_gibt_suppe.
Herleitung mit Auswahl der Regeln
nach einer vorgegebenen Reihenfolge
(von oben nach unten)
?- es_gibt_pudding.
benutze: es_gibt_pudding :- es gibt pizza.
Sackgasse
?- es_gibt_pizza.
keine Fortsetzung der Rückwärtsherleitung möglich!
Backtracking
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
Logische Herleitbarkeit
45
kind(hera,
kind(hebe,
vorfahr(X,
vorfahr(X,
rhea).
hera).
Y) :- kind(Y, X).
Y) :- kind(Y, Z), vorfahr(X, Z).
kind(hera,
kind(hebe,
vorfahr(X,
vorfahr(X,
rhea).
hera).
Y) :- vorfahr(X, Z), kind(Y, Z).
Y) :- kind(Y, X).
?- vorfahr(V, hebe).
?- vorfahr(V, hebe).
vorfahr(X, Y) :- kind(Y, X).
kind(hebe, hera).
---------------------------vorfahr(hera, hebe).
vorfahr(X, Y) :- kind(Y, X).
kind(hebe, hera).
---------------------------vorfahr(hera, hebe).
{X -> hera;
Y -> hebe}
V = hera
V = hera
vorfahr(X, Y) :- kind(Y, X).
kind(hera, rhea).
---------------------------vorfahr(rhea, hera).
vorfahr(X, Y) :- kind(Y, X).
kind(hera, rhea).
---------------------------vorfahr(rhea, hera).
{X -> hebe;
Y -> hera}
{X -> hera;
Y -> hebe}
{X -> hebe;
Y -> hera}
vorfahr(X, Y) :- kind(Y, Z), vorfahr(X, Z).
kind(hebe, hera).
vorfahr(rhea, hera).
{X -> rhea;
---------------------------Y -> hebe;
vorfahr(rhea, hebe).
Z -> hera}
vorfahr(X, Y) :- kind(Y, Z), vorfahr(X, Z).
vorfahr(rhea, hera).
kind(hebe, hera).
{X -> rhea;
---------------------------Y -> hebe;
vorfahr(rhea, hebe).
Z -> hera}
V = rhea
V = rhea
hängt nicht von der Reihenfolge der
Regeln, Bedingungen ab
46
Herleitbarkeit bzgl. Abarbeitungsreihenf.
kind(hera,
kind(hebe,
vorfahr(X,
vorfahr(X,
rhea).
hera).
Y) :- kind(Y, X).
Y) :- kind(Y, Z), vorfahr(X, Z).
hängt von der Reihenfolge der Regeln,
Bedingungen ab
?- 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!
47
Herleitbarkeit bzgl. Abarbeitungsreihenf.
kind(hera,
kind(hebe,
vorfahr(X,
vorfahr(X,
rhea).
hera).
Y) :- vorfahr(X, Z), kind(Y, Z).
Y) :- kind(Y, X).
hängt von der Reihenfolge der Regeln,
Bedingungen ab
?- 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).
...
endlose Regelanwendung
Die Logik-Programme sind logisch äquivalent. Aus beiden Programmen lassen sich dieselben
logischen Herleitungen erzeugen.
Die Herleitung bzgl. einer Abarbeitungsreihenfolge liefert jedoch unterschiedliche
Berechnungsergebnisse. Diese werden durch die Algorithmen zur automatisierten Erzeugung
von logischen Herleitungen festgelegt. Die Reihenfolge der Regeln und der beteiligten
Bedingungen spielen hierbei eine entscheidende Rolle.
48
Fazit: Auswertung von Anfragen
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 modusponens-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.
Experimente mit Prolog
49
Wissensbasis:
es_gibt_fleisch.
es_gibt_suppe.
es_gibt_pudding
es_gibt_pudding
es_gibt_eis
es_gibt_kartoffeln
::::-
es_gibt_fleisch, es_gibt_kartoffeln.
es_gibt_pizza.
es_gibt_pizza.
es_gibt_suppe.
Prolog stellt einen sog. Trace-Modus bereit, bei dem die Zwischenschritte bei der Auswertung
einer Anfrage mitprotokolliert werden.
?- trace.
Yes
[trace]
Call:
Call:
Exit:
Call:
Call:
Exit:
Exit:
Exit:
?- es_gibt_pudding.
(6) es_gibt_pudding ? creep
(7) es_gibt_fleisch ? creep
(7) es_gibt_fleisch ? creep
(7) es_gibt_kartoffeln ? creep
(8) es_gibt_suppe ? creep
(8) es_gibt_suppe ? creep
(7) es_gibt_kartoffeln ? creep
(6) es_gibt_pudding ? creep
Yes
Aufgabe: Gib für alle Call-Aufrufe an, welches Faktum / welche Regel angewandt wird.
Experimente mit Prolog
50
Wissensbasis:
kind(hera,
kind(hebe,
vorfahr(X,
vorfahr(X,
rhea).
hera).
Y) :- kind(Y, X).
Y) :- kind(Y, Z), vorfahr(X, Z).
[trace]
Call:
Call:
Exit:
Exit:
?- vorfahr(V, hebe).
(7) vorfahr(_G286, hebe) ? creep
(8) kind(hebe, _G286) ? creep
(8) kind(hebe, hera) ? creep
(7) vorfahr(hera, hebe) ? creep
V = hera
Fail:
Redo:
Call:
Exit:
Call:
Call:
Exit:
Exit:
Exit:
;
(8)
(7)
(8)
(8)
(8)
(9)
(9)
(8)
(7)
...
kind(hebe, _G286) ? creep
vorfahr(_G286, hebe) ? creep
kind(hebe, _G341) ? creep
kind(hebe, hera) ? creep
vorfahr(_G286, hera) ? creep
kind(hera, _G286) ? creep
kind(hera, rhea) ? creep
vorfahr(rhea, hera) ? creep
vorfahr(rhea, hebe) ? creep
V = rhea
Fail:
Redo:
Call:
Exit:
Call:
Call:
Fail:
Redo:
Call:
Fail:
Fail:
Fail:
Fail:
Fail:
Fail:
;
(9) kind(hera, _G286) ? creep
(8) vorfahr(_G286, hera) ? creep
(9) kind(hera, _G341) ? creep
(9) kind(hera, rhea) ? creep
(9) vorfahr(_G286, rhea) ? creep
(10) kind(rhea, _G286) ? creep
(10) kind(rhea, _G286) ? creep
(9) vorfahr(_G286, rhea) ? creep
(10) kind(rhea, _G341) ? creep
(10) kind(rhea, _G341) ? creep
(9) vorfahr(_G286, rhea) ? creep
(9) kind(hera, _G341) ? creep
(8) vorfahr(_G286, hera) ? creep
(8) kind(hebe, _G341) ? creep
(7) vorfahr(_G286, hebe) ? creep
No
Aufgabe: Vergleiche das von Prolog erzeugte Herleitungsprotokoll mit dem
Herleitungsprotokoll auf Folie 46.
Aufgabe
51
Gegeben ist das folgende Logikprogramm.
kind(hera,
kind(hebe,
vorfahr(X,
vorfahr(X,
rhea).
hera).
Y) :- kind(Y, Z), vorfahr(X, Z).
Y) :- kind(Y, X).
?- vorfahr(V, hebe).
Welches Ergebnis liefert die Prolog-Inferenzmaschine? Überprüfe deine Vermutung.
Aufgabe
52
Gegeben ist das folgende Logikprogramm.
kind(hera,
kind(hebe,
vorfahr(X,
vorfahr(X,
rhea).
hera).
Y) :- kind(Y, X).
Y) :- vorfahr(X, Z), kind(Y, Z).
?- vorfahr(V, hebe).
Welches Ergebnis liefert die Prolog-Inferenzmaschine? Überprüfe deine Vermutung.
53
Teil 3
Deklarative Programmierung
54
Ein Graphenproblem
"Die Leute vom Planeten Chator schreiben
gern Schlechtes übereinander. Wer vielen über
andere Schlechtes schreibt, gilt als besonders
charmant. Aber natürlich nur, wenn die
Kompromittierten nichts davon erfahren.
Chatonen schreiben nur an Leute, die ihnen
sympathisch sind. Doch die können den
Tratsch weitertragen, und eventuell genau an
den Falschen. Ein Chatone muss also gut
aufpassen, dass er keinen Charmefehler
macht. Dieses Missgeschick passierte unlängst
Ator, als er Btor Schlechtes über Dtor schrieb.
Zu dumm: Dtor ist dem Ctor sympathisch, der
wiederum Btor sympathisch ist. Und so
landete der Tratsch bei Dtor, der über Ator
verständlicherweise sehr verärgert war. Dies
hätte Ator mit ein wenig Übersicht vermeiden
können, denn schließlich wissen alle Chatonen
voneinander, wer wem sympathisch ist."
(Quelle: Bundeswettbewerb Informatik 2004/2005 - 1.
Runde)
(a) Stelle die Sympathiebeziehungen
der Chatonen mit einem gerichteten
Graphen dar.
(b) Welches Problem muss hier gelöst
werden. Beschreibe es mit Hilfe der
Graphenterminologie.
55
Graphen
Ein Graph besteht aus einer Menge von
Knoten und einer Menge von Kanten (die
jeweils zwei Knoten miteinander verbinden).
gerichteter, unbewerteter Graph
56
Das Wegsucheproblem
Wegsucheproblem:
Gibt es einen Weg von einem vorgegebnenen
Startknoten zu einem vorgegebenen
Zielknoten?
Spezielle Probleme:
(a) Darf A etwas Schlechtes über D
an B schreiben? Gibt es einen Weg
(längs der Kanten des Graphen) vom
Startknoten B zum Zielknoten D?
(b) Über wen H etwas Schlechtes an
D schreiben? Zu welchen Zielknoten
gibt es einen Weg vom Startknoten
D?
...
57
Lösung des Wegsucheproblems
ALGORITHMUS: Wegsuche in gerichteten Graphen
Eingabe: gerichteter Graph, Startknoten, Zielknoten
Markiere den Startknoten.
Füge den Startknoten in eine leere Liste ein.
Solange die Liste nicht leer ist und den Zielknoten nicht enthält:
Wähle einen Knoten aus der Liste aus.
Für alle Nachbarknoten des gewählten Knotens:
Falls der Nachbarknoten noch nicht markiert ist:
Markiere ihn,
vermerke als Herkunft den gewählten Knoten und ..
füge ihn in die Liste ein.
Entferne den gewählten Knoten aus der Liste.
Starte mit einem "leeren Weg".
Wenn die Liste den Zielknoten enthält:
Aktueller Knoten ist der Zielknoten.
Solange der Startknoten nicht erreicht ist:
Der Weg wird um d. Verbindung zwischen d. aktuellen Knoten ..
und dem vermerkten Herkunftsknoten erweitert.
Aktueller Knoten ist der vermerkte Herkunftsknoten ..
des bisherigen aktuellen Knotens.
Ausgabe: Weg
imperative Lösung: Beschreibung, wie man einen Weg findet
58
Lösung des Wegsucheproblems
Regel 1:
Ein Weg zwischen einem Startknoten und einem Zielknoten besteht aus
der Verbindung Startknoten - Zielknoten,
wenn der Zielknoten ein Nachbarknoten des Startknotens ist.
Regel 2:
Ein Weg zwischen einem Startknoten und einem Zielknoten besteht
(für einen bestimmten Nachbarknoten des Startknotens) aus
der Verbindung Startknoten - Nachbarknoten und
einem Weg zwischen dem Nachbarknoten und dem Zielknoten.
deklarative Lösung: Beschreibung, was einen Weg ausmacht
Imperative Problemlöseverfahren schreiben vor, wie man zu einer Lösung gelangt.
Deklarative Problemlöseverfahren beschreiben, was das Problem ausmacht.
59
Vereinfachung des Wegsucheproblems
Wegsucheproblem:
Zur Vereinfachung des Graphenproblems
betrachten wir vorerst nur Graphen, die keine
Kreise enthalten.
% Graph
kante(a,
kante(a,
kante(b,
kante(b,
kante(c,
kante(c,
kante(d,
kante(d,
kante(f,
kante(f,
kante(h,
kante(h,
kante(i,
kante(i,
b).
c).
d).
e).
e).
f).
g).
e).
b).
i).
e).
b).
e).
h).
gerichteter Graph ohne Kreise
Beschreibung des Graphen mit Fakten
Aufgabe
60
% Graph
kante(a,
kante(a,
kante(b,
kante(b,
kante(c,
kante(c,
kante(d,
kante(d,
kante(f,
kante(f,
kante(h,
kante(h,
kante(i,
kante(i,
Aufgabe:
b).
c).
d).
e).
e).
f).
g).
e).
b).
i).
e).
b).
e).
h).
Entwickle geeignete Prolog-Regeln zur
Festlegung des weg-Prädikats.
Regel 1:
Es gibt einen Weg zwischen einem Knoten X und einem Knoten Y,
wenn es eine Kante von X nach Y gibt.
Regel 2:
Es gibt einen Weg zwischen einem Knoten X und einem Knoten Y,
wenn es eine Kante von X zu einem Knoten Z und
einen Weg vom Knoten Z zum Knoten Y gibt.
Aufgabe
61
% Graph
kante(a, b).
gerichteter Graph ohne Kreise
kante(a, c).
kante(b, d).
kante(b, e).
kante(c, e).
kante(c, f).
kante(d, g).
kante(d, e).
kante(f, b).
kante(f, i).
kante(h, e).
kante(h, b).
kante(i, e).
kante(i, h).
weg(X, Y) :- kante(X, Y), print(Y).
weg(X, Y) :- kante(X, Z), print(Z), weg(Z, Y).
?- weg(a, h).
bdgeecefbdgeeih
Yes
Aufgabe:
Kannst du erklären, wie die Ausgaben zu Stande kommen?
Warum bezeichnet man die Suche hier auch als "Tiefensuche"?
62
Aufgabe
% Graph
kante(a, b).
kante(a, c).
kante(b, d).
kante(b, e).
kante(c, e).
kante(c, f).
kante(d, g).
kante(d, e).
kante(f, b).
kante(f, i).
kante(h, e).
kante(h, b).
kante(i, e).
kante(i, h).
weg(X, X).
weg(X, Y) :- kante(X, Z), weg(Z, Y).
gerichteter Graph ohne Kreise
Aufgabe:
Teste auch die oben gezeigte Festlegung des weg-Prädikats.
Warum funktioniert die Tiefensuche mit den bisher gezeigten Regeln nicht bei Graphen mit
Kreisen? Probiere es ggf. aus, indem du eine zusätzliche Kante im Graphen einführst.
63
Aufsammeln der Wegknoten
% Graph
kante(a, b).
gerichteter Graph ohne Kreise
kante(a, c).
kante(b, d).
kante(b, e).
kante(c, e).
kante(c, f).
kante(d, g).
kante(d, e).
kante(f, b).
kante(f, i).
kante(h, e).
kante(h, b).
kante(i, e).
kante(i, h).
weg0(X, X, []).
weg0(X, Y, [Z|W]) :- kante(X, Z), weg0(Z, Y, W).
?- weg0(a, b, W).
...
Aufgabe:
Teste zunächst die Regeln mit Anfragen wie der folgenden.
Kannst du erklären, wie die Ausgaben zu Stande kommen?
64
Aufsammeln in einer Akkumulatorliste
% Graph
kante(a, b).
gerichteter Graph ohne Kreise
kante(a, c).
kante(b, d).
kante(b, e).
kante(c, e).
kante(c, f).
kante(d, g).
kante(d, e).
kante(f, b).
kante(f, i).
kante(h, e).
kante(h, b).
kante(i, e).
kante(i, h).
weg1(X, X, W, W).
weg1(X, Y, A, W) :- kante(X, Z), weg1(Z, Y, [Z|A], W).
weg(X, Y, W) :- weg1(X, Y, [X], W).
?- weg1(a, b, [a], W).
...
Aufgabe:
Teste zunächst das weg1-(Hilfs-)Prädikat mit Anfragen.
Beschreibe die "Logik" der beiden Regeln in Worten.
65
Lösung des Wegsucheproblems
% Graph
kante(a, b).
gerichteter Graph mit Kreisen
kante(a, c).
kante(b, d).
kante(b, e).
kante(c, e).
kante(c, f).
kante(d, g).
kante(d, e).
kante(f, b).
kante(f, i).
kante(h, e).
kante(h, b).
kante(i, e).
kante(i, h).
weg2(X, X, W, W).
weg2(X, Y, A, W) :kante(X, Z), not(member(Z, A)), weg2(Z, Y, [Z|A], W).
weg(X, Y, W) :- weg2(X, Y, [X], W).
?- weg(a, b, [a], W).
...
66
Lösung des Tratsch-Problems
% Anfrage: Wer darf an wen etwas Schlechtes über Btor schreiben?
?- darf_tratschen_wer_anwen_ueberwen(X, Y, b).
X = c
Y = d ;
X = c
Y = g ;
X = d
Y = c ;
X = f
Y = g ;
X = g
Y = h ;
X = h
Y = d ;
No
Aufgabe:
Entwickle ein geeignetes Logikprogramm zur Lösung des
Tratsch-Problems. Benutze die erzielten Ergebnisse zur
Lösung des Graphenproblems.
67
Anwendung: Umfüllproblem
Zum Nudelkochen im Ferienlager werden
genau 2 Liter Wasser benötigt. Zum
Abmessen stehen nur ein kleiner Eimer,
der 3 Liter fasst, und einen etwas größerer
Eimer, der 4 Liter fasst, zur Verfügung.
Kann das funktionieren?
Um systematisch alle durch Umfüllen
erzeugbaren Wassermengen zu
bestimmen, kann man einen
Zustandsgraphen erstellen. Die Knoten des
Graphen sind die aktuellen Füllinhalte der
beiden Eimer. Die Kanten des Graphen
stellen die Umfüllvorgänge dar.
Aufgabe:
Entwickle ein geeignetes Logikprogramm zur Lösung des Umfüllproblems. Die folgende
Wissensbasis zeigt einen Weg auf, wie man die Umfüllvorgänge modellieren kann. Es fehlen
aber noch eine Reihe von Regeln.
68
Anwendung: Umfüllproblem
% Graph
kante(X, Y) :- zustandsuebergang(X, Y).
% 3-l-Eimer füllen
zustandsuebergang((Eimer4, Eimer3), (Eimer4, 3)) :Eimer3 \== 3.
% 4-l-Eimer füllen
...
% 3-l-Eimer leeren
zustandsuebergang((Eimer4, Eimer3), (Eimer4, 0)) :Eimer3 \== 0.
% 4-l-Eimer leeren
...
% 3-l-Eimer umfüllen in 4-l-Eimer
zustandsuebergang((Eimer4, Eimer3), (Eimer41, 0)) :Eimer3 \== 0, Eimer3 + Eimer4 =< 4, Eimer41 is Eimer3+Eimer4.
% 4-l-Eimer umfüllen in 3-l-Eimer
...
% 4-l-Eimer teilw. umfüllen in 3-l-Eimer
...
% 3-l-Eimer teilw. umfüllen in 3-l-Eimer
zustandsuebergang((Eimer4, Eimer3), (4, Eimer31)) :Eimer4 \== 4, Eimer3 + Eimer4 >4, Eimer31 is Eimer3+Eimer4-4.
...
69
Deklarative Programmierung
Ansatz: Beschreiben, was in der Modellwelt gelten soll
Anfrage
?- zusammenfuegen([a, b], [c, a, d], Z).
Wissensbasis
zusammenfuegen([], Y, Y).
zusammenfuegen([E|RX], Y, [E|RZ]) :fuegezusammen(RX, Y, RZ).
Ergebnis
Z = [a, b, c, a, d]
Inferenzmaschine
Deklarative Programmierung besteht darin, den Problemkontext (Miniwelt) mit gegebenen
Mitteln (hier: Fakten und Regeln) zu beschreiben.
70
Imperative Programmierung
Ansatz: Beschreiben, wie die Ergebnisse berechnet werden sollen
A.-Zustand
{X: [a, b]; Y: [c, a, d]}
Z := []
solange X nicht leer ist:
E := erstesElement(X)
Z := mitLetztem(Z, E)
X := ohneEstes(X)
Anweisungen
solange Y nicht leer ist:
E := erstesElement(Y)
Z := mitLetztem(Z, E)
Y := ohneEstes(Y)
E.-Zustand
Registermaschine
{Z: [a, b, c, a, d]}
Imperative Programmierung besteht darin, eine (mehr oder weniger abstrakte) Maschine mit
Hilfe von Anweisungen zu steuern.
71
Literaturhinweise
Gerhard Röhner: Informatik mit Prolog. Hessisches Landesinstitut für Pädagogik 2002. (HeLP
Best.-Nr.: 06000).
Rüdeger Baumann: PROLOG Einführungskurs. Klett-Verlag 1991.
H. M. Otto: ProLog-Puzzles. Dümmler-Verlag 1991.
Gregor Noll: PROLOG – eine Einführung in deklaratives Programmieren.
https://informatik.bildung-rp.de/fileadmin/user_upload/informatik.bildungrp.de/InformatikAG/pps/DI-Prolog.pps
Herbert Drumm u. Hermann Stimm: Wissensverarbeitung mit PROLOG – Ein Einstieg in die
Algorithmik. Handreichung zum Lehrplan Informatik 1995.
Klaus Merkert: Prolog. siehe
http://www.hsg-kl.de/faecher/inf/prolog/index.php
Uwe Schöning: Logik für Informatiker. BI-Wissenschaftsverlag 1987.

ppt - Informatik