71
Logische Programmierung Klaus Becker 2014

Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

Embed Size (px)

Citation preview

Page 1: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

Logische Programmierung

Klaus Becker

2014

Page 2: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

2 Logische Programmierung

Page 3: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

3 Teil 1

Modellierung von Wissen

Page 4: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

4

(Heaven) Uranus = Gaea (Earth)

|

---------------------------------------

| | | | |

Cronus = Rhea Coeus = Phoebe Oceanus = Tethys

| | |

---------------------- Leto = Zeus Iapetus

| | | | | | |

Hestia | Poseidon | Demeter=Zeus | ----------------

Hades Zeus = Hera | | | | |

| | Persephone | | Prometheus |

Athena | --------- | |

| | | Atlas Epimetheus

--------------- Apollo Artemis | |

| | | | |

Ares Hebe Hephaestus Zeus=Maia Zeus=Dione

| |

Hermes Aphrodite

Die Welt der griechischen Götter

AufgabeKannst du die folgenden Verwandschaftsbeziehungen klären?

(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

Page 5: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

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.

In den folgenden Abschnitten wird zunächst auf die Wissenmodellierung und die Formulierung von Anfragen an die Wissensbasis eingegangen.

Anfrage

Page 6: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

6 Modellierungsansatz

Eine (Mini-) Welt besteht aus Objekten (Personen, Gegenstände, ...), die Eigenschaften haben und in Beziehung zueinander stehen.Eine (Mini-) Welt besteht aus Objekten (Personen, Gegenstände, ...), die Eigenschaften haben und in Beziehung zueinander stehen.

Hera(weiblich)

Zeus(männlich)

Ares(männlich)

ist Kind von

Miniwelt "griechische Götter"

Page 7: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

7 Konstanten, Prädikate

Objekte werden mit Konstanten (allg. mit Termen) beschrieben, Eigenschaften und Beziehungen mit Hilfe von Prädikaten.Objekte werden mit Konstanten (allg. mit Termen) beschrieben, Eigenschaften und Beziehungen mit Hilfe von Prädikaten.

% Fakten weiblich(hera). maennlich(zeus). maennlich(ares).kind(ares, hera). kind(ares, zeus).

PrädikatKonstante

Prädikat

Hera(weiblich)

Zeus(männlich)

Ares(männlich)

ist Kind von

Miniwelt "griechische Götter"

Modellierung der Miniwelt

Page 8: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

8 Fakten

Sachverhalte der Miniwelt können direkt mit Hilfe von Fakten beschrieben werden.Sachverhalte der Miniwelt können direkt mit Hilfe von Fakten beschrieben werden.

% Fakten weiblich(hera). maennlich(zeus). maennlich(ares).kind(ares, hera). kind(ares, zeus).

Fakten

Hera(weiblich)

Zeus(männlich)

Ares(männlich)

ist Kind von

Miniwelt "griechische Götter"

Modellierung der Miniwelt

Page 9: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

9 Regeln

Sachverhalte der Miniwelt können auch indirekt mit Hilfe von Regeln beschrieben werden.Sachverhalte der Miniwelt können auch indirekt mit Hilfe von Regeln beschrieben werden.

% Fakten: maennlich(cronus).maennlich(zeus)...weiblich(rhea).weiblich(demeter)....kind(hestia, rhea).kind(hades, rhea)....

Miniwelt

% Regeln: vater(X, Y) :- kind(Y, X), maennlich(X). mutter(X, Y) :- kind(Y, X), weiblich(X).

indirekte Beschreibu

ng mit Regeln

direkte Beschreibu

ng mit Fakten

Cronus = Rhea

|

----------------------

| | | | |

Hestia | Poseidon | Demeter

Hades Zeus = Hera

% weitere Fakten: mutter(rhea, hestia).mutter(rhea, hades)....

Page 10: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

10 Regeln

Regeln sind Wenn-Dann-Aussagen.

% Regeln: mutter(X, Y) :- kind(Y, X), weiblich(X).vater(X, Y) :- kind(Y, X), maennlich(X).

Variable

Implikation

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.

Und

Regelrumpf(Bedingungen)

Regelkopf(Folgerung)

Page 11: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

11 Rekursive Regeln

Das Prädikat im Regelkopf darf im Regelrumpf vorkommen.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).

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.

Regelrumpf(Bedingungen)

Regelkopf(Folgerung)

Page 12: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

12 Aufgaben

Aufgabe 1Vervollständige die Regeln.

elternteil(X, Y) :-

sohn(X, Y) :-

oma(X, Y) :-

Aufgabe 2Warum 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 3Entwickle weitere Regeln.

onkel(X, Y) :-

tante(X, Y) :-

cousin(X, Y) :-

...

Aufgabe 1Vervollständige die Regeln.

elternteil(X, Y) :-

sohn(X, Y) :-

oma(X, Y) :-

Aufgabe 2Warum 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 3Entwickle weitere Regeln.

onkel(X, Y) :-

tante(X, Y) :-

cousin(X, Y) :-

...

Page 13: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

13 Logik-Programme

% Faktenmaennlich(cronus).maennlich(zeus)...weiblich(rhea).weiblich(demeter).weiblich(hera).weiblich(hestia).kind(hestia, rhea).kind(hades, rhea)...% Regelnvater(X, Y) :- kind(Y, X), maennlich(X).mutter(X, Y) :- kind(Y, X), weiblich(X).

?- weiblich(hera).

Ein Logik-Programm besteht aus einer Wissensbasis und einer Anfrage.

Wissensbasis

Anfrage

Page 14: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

14 SWI-Prolog-Editor

Wissensbasis

Anfrage

Page 15: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

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.

Page 16: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

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.

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.

Mit consult(<Datei>). werden aus der angegebenen Datei die Fakten und Regeln in die Wissensbasis

eingelesen.

Consultieren

Wenn der PROLOG-Compiler keine Syntaxfehler gefunden hat, bestätigt er die erfolgreiche Erzeugung der Wissensbasis mit "Yes".

Wenn der PROLOG-Compiler keine Syntaxfehler gefunden hat, bestätigt er die erfolgreiche Erzeugung der Wissensbasis mit "Yes".

Page 17: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

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.

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 PROLOG-Interpreter keine weiteren Ergebnisse, so zeigt er dies mit "No" an.

Das trennende Semikolon kann als "oder" gedeutet werden.

Findet der PROLOG-Interpreter keine weiteren Ergebnisse, so zeigt er dies mit "No" an.

Das trennende Semikolon kann als "oder" gedeutet werden.

Anfrage

AnfrageErgebnisse

Page 18: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

18 Ja-Nein-Anfragen

% Wissensbasismaennlich(cronus).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).

?- weiblich(hera).

Yes

Ist Hera weiblich?

Ist Zeus weiblich?

?- weiblich(zeus).

No

Page 19: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

19 Ergänzungsanfragen

% Wissensbasismaennlich(cronus).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, zeus).

V = cronus ;

No

Wer ist Vater von Zeus?

Wer ist Kind von Rhea?

?- kind(K, rhea).

K = hestia ;

K = hades ;

K = poseidon ;

K = zeus ;

K = hera ;

K = demeter ;

No

Page 20: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

20 Ergänzungsanfragen

% Wissensbasismaennlich(cronus).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 = rheaY = hestia ;

X = rheaY = hades ;

X = rheaY = poseidon ;

X = rheaY = zeus ;

X = rheaY = hera ;

X = rheaY = demeter ;

No

Wer ist Mutter von wem?

Page 21: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

21 Anfragen mit anonymen Variablen

% Wissensbasismaennlich(cronus).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

Wer ist Vater (von einem

Kind)?

Anonyme Variablen beginnen mit einem Unterstrich. Anonyme Variablen werden benutzt, wenn man an den Variablenwerten selbst nicht interessiert ist.

Anonyme Variablen beginnen mit einem Unterstrich. Anonyme Variablen werden benutzt, wenn man an den Variablenwerten selbst nicht interessiert ist.

Page 22: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

22 Zusammengesetzte Anfragen

% Wissensbasismaennlich(cronus).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).

?- weiblich(Tochter), vater(_Vater, Tochter).

Tochter = demeter ;

Tochter = hera ;

Tochter = hestia ;

No

Wer ist weiblich und

hat einen Vater?

Eine Anfrage kann auch aus mehreren Teilanfragen bestehen. Diese werden mit einem Komma (zu deuten als logisches Und) abgetrennt.

Eine Anfrage kann auch aus mehreren Teilanfragen bestehen. Diese werden mit einem Komma (zu deuten als logisches Und) abgetrennt.

Page 23: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

23 Fazit: Programmieren mit Logik

% Faktenmaennlich(cronus).maennlich(zeus)...weiblich(rhea).weiblich(demeter).weiblich(hera).weiblich(hestia).kind(hestia, rhea).kind(hades, rhea)...% Regelnvater(X, Y) :- kind(Y, X), maennlich(X).mutter(X, Y) :- kind(Y, X), weiblich(X).

?- weiblich(hera).

Ein Logik-Programm besteht aus einer Wissensbasis und einer Anfrage.

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.

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.

Page 24: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

24 Fazit: Programmieren mit Logik

% Faktenmaennlich(cronus)...weiblich(rhea).weiblich(demeter).weiblich(hera).weiblich(hestia).kind(hestia, rhea)...% Regelnvater(X, Y) :- kind(Y, X), maennlich(X).mutter(X, Y) :- kind(Y, X), weiblich(X).

?- weiblich(hera).

Yes

Ein Logik-Programm besteht aus einer Wissensbasis und einer Anfrage.

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.

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.

Page 25: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

25 Aufgaben

Erweitere die oben gezeigte Wissensbasis um folgende Fakten und RegelnErweitere 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?

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?

Page 26: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

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?

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.

alternativ:

Erstelle eine Wissensbasis und geeignete Anfragen zu deiner Familie.

Page 27: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

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.

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.

Page 28: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

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?

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?

Page 29: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

29 Teil 2

Auswertung von Anfragen

Page 30: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

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.

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.

sterblich(X) :- mensch(X).mensch(sokrates).

?- sterblich(X).X = sokrates;No.

Alle Menschen sind sterblich.Sokrates ist ein Mensch.

Sokrates ist sterblich.

sterblich(X) :- mensch(X).mensch(sokrates).

sterblich(sokrates).

Page 31: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

31 Modus Ponens

Wenn Kaiserslautern das Spiel gewinnt, dann kann Kaiserslautern nicht mehr absteigen.

Kaiserslautern gewinnt das Spiel.

Kaiserslautern kann nicht mehr absteigen.

Platz

MannschaftSpiele

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

α → βα

β

α → βα

β

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.

Page 32: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

32 Modus Ponens

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.

Platz

MannschaftSpiele

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

β

α1, ... αn -> βα1

...αn

β

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.

Page 33: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

33 Spezialisierung bei Allaussagen

Für alle X1, ..., Xk: γ (X1, ..., Xk)

γ(c1, ..., ck)

Für alle X1, ..., Xk: γ (X1, ..., Xk)

γ(c1, ..., ck)

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){X -> sokrates}

Spezialisierung bei

Allaussagen

{X1 -> c1, ..., Xk -> ck}

Page 34: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

34 Modus Ponens

α1(X1, ..., Xk), ... αn(X1, ..., Xk) -> β(X1, ..., Xk)α1(c1, ..., ck)...αn(c1, ..., ck)

β(c1, ..., ck)

α1(X1, ..., Xk), ... αn(X1, ..., Xk) -> β(X1, ..., Xk)α1(c1, ..., ck)...αn(c1, ..., ck)

β(c1, ..., ck)

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.

Alle Menschen sind sterblich.Sokrates ist ein Mensch.

Sokrates ist sterblich. mensch(sokrates) -> sterblich(sokrates)mensch(sokrates)

sterblich(sokrates)

Spezialisierung bei

Allaussagen

modus ponens

modus ponens bei Allaussagen

Für alle X: mensch(X) -> sterblich(X).

mensch(sokrates) -> sterblich(sokrates){X -> sokrates}

Page 35: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

35 Suche nach logischen Herleitungen

es_gibt_fleisch.es_gibt_suppe.es_gibt_pudding :- es_gibt_fleisch, es_gibt_kartoffeln.es_gibt_eis :- es_gibt_pizza.es_gibt_pudding :- es gibt pizza.es_gibt_kartoffeln :- es_gibt_suppe.

?- es_gibt_pudding.

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

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

Wissensbasis ohne Variablen

Anfrage ohne Variablen

logische Herleitung

Yes.Ergebnis der

Anfrage

logische Herleitung

Page 36: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

36 Suche nach logischen Herleitungen

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

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

logische Herleitung

?- 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

logische Herleitung

Page 37: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

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

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

Wissensbasis mit Variablen

Anfrage mit Variablen

logische Herleitung

V = zeus Ergebnis der Anfrage

Page 38: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

38 Suche nach logischen Herleitungen

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

logische Herleitung

?- 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

Page 39: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

39 Herleitungen ohne Erfolg

es_gibt_fleisch.es_gibt_suppe.es_gibt_pudding :- es_gibt_fleisch, es_gibt_kartoffeln.es_gibt_eis :- es_gibt_pizza.es_gibt_pudding :- es gibt pizza.es_gibt_kartoffeln :- es_gibt_suppe.

?- es_gibt_eis.

Wissensbasis ohne Variablen

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

Page 40: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

40 Herleitungen ohne Erfolg

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

?- 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} ?- kind(hebe, V), maennlich(V). benutze: kind(hebe, zeus). {V -> zeus} ?- maennlich(zeus). keine Fortsetzung der Rückwärtsherleitung möglich!No

Rückwärtsherleitung

maennlich(zeus).

Page 41: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

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

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

Page 42: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

42 Aufgaben

Welche Ergebnisse lassen sich hier mit logischen Herleitungen erzielen?

Verwende zunächst Vorwärtsherleitungen. Verwende anschließend auch Rückwärtsherleitungen.

Welche Ergebnisse lassen sich hier mit logischen Herleitungen erzielen?

Verwende zunächst Vorwärtsherleitungen. Verwende anschließend auch Rückwärtsherleitungen.

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

?- vorfahr(V, hebe).

Page 43: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

43

Automatisierung d. logischen Schließens

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

?- es_gibt_pudding.

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

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

Herleitung mit nichtdeterministische Auswahl

der Regeln

logische Herleitung

Yes.

logische Herleitung

Page 44: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

44

Automatisierung d. logischen Schließens

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

?- es_gibt_pudding.

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

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

Herleitung mit Auswahl der Regeln nach einer vorgegebenen

Reihenfolge (von oben nach unten)

Sackgasse

Backtracking

Page 45: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

45 Logische Herleitbarkeitkind(hera, rhea).kind(hebe, hera).vorfahr(X, Y) :- kind(Y, X).vorfahr(X, Y) :- kind(Y, Z), vorfahr(X, Z).

?- vorfahr(V, hebe).

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

{X -> rhea; Y -> hebe; Z -> hera}

vorfahr(X, Y) :- kind(Y, X).kind(hera, rhea).----------------------------vorfahr(rhea, hera).

{X -> hebe; Y -> hera}

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

?- vorfahr(V, hebe).

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

{X -> rhea; Y -> hebe; Z -> hera}

vorfahr(X, Y) :- kind(Y, X).kind(hera, rhea).----------------------------vorfahr(rhea, hera).

{X -> hebe; Y -> hera}

V = rhea V = rhea

vorfahr(X, Y) :- kind(Y, X).kind(hebe, hera).----------------------------vorfahr(hera, hebe).

{X -> hera; Y -> hebe}

V = hera

vorfahr(X, Y) :- kind(Y, X).kind(hebe, hera).----------------------------vorfahr(hera, hebe).

{X -> hera; Y -> hebe}

V = hera

hängt nicht von der Reihenfolge der Regeln, Bedingungen ab

Page 46: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

46

Herleitbarkeit bzgl. Abarbeitungsreihenf.

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

?- 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!

hängt von der Reihenfolge der Regeln, Bedingungen ab

Page 47: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

47

Herleitbarkeit bzgl. Abarbeitungsreihenf.

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

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

hängt von der Reihenfolge der Regeln, Bedingungen ab

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.

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.

Page 48: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

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

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.

Page 49: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

49 Experimente mit Prolog

Wissensbasis:Wissensbasis:

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.

?- trace.

Yes[trace] ?- es_gibt_pudding. Call: (6) es_gibt_pudding ? creep Call: (7) es_gibt_fleisch ? creep Exit: (7) es_gibt_fleisch ? creep Call: (7) es_gibt_kartoffeln ? creep Call: (8) es_gibt_suppe ? creep Exit: (8) es_gibt_suppe ? creep Exit: (7) es_gibt_kartoffeln ? creep Exit: (6) es_gibt_pudding ? creep

Yes

Prolog stellt einen sog. Trace-Modus bereit, bei dem die Zwischenschritte bei der Auswertung einer Anfrage mitprotokolliert werden. Prolog stellt einen sog. Trace-Modus bereit, bei dem die Zwischenschritte bei der Auswertung einer Anfrage mitprotokolliert werden.

Aufgabe: Gib für alle Call-Aufrufe an, welches Faktum / welche Regel angewandt wird. Aufgabe: Gib für alle Call-Aufrufe an, welches Faktum / welche Regel angewandt wird.

Page 50: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

50 Experimente mit Prolog

Aufgabe: Vergleiche das von Prolog erzeugte Herleitungsprotokoll mit dem Herleitungsprotokoll auf Folie 46. Aufgabe: Vergleiche das von Prolog erzeugte Herleitungsprotokoll mit dem Herleitungsprotokoll auf Folie 46.

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

[trace] ?- vorfahr(V, hebe). Call: (7) vorfahr(_G286, hebe) ? creep Call: (8) kind(hebe, _G286) ? creep Exit: (8) kind(hebe, hera) ? creep Exit: (7) vorfahr(hera, hebe) ? creep

V = hera ; Fail: (8) kind(hebe, _G286) ? creep Redo: (7) vorfahr(_G286, hebe) ? creep Call: (8) kind(hebe, _G341) ? creep Exit: (8) kind(hebe, hera) ? creep Call: (8) vorfahr(_G286, hera) ? creep Call: (9) kind(hera, _G286) ? creep Exit: (9) kind(hera, rhea) ? creep Exit: (8) vorfahr(rhea, hera) ? creep Exit: (7) vorfahr(rhea, hebe) ? creep

...

V = rhea ; Fail: (9) kind(hera, _G286) ? creep Redo: (8) vorfahr(_G286, hera) ? creep Call: (9) kind(hera, _G341) ? creep Exit: (9) kind(hera, rhea) ? creep Call: (9) vorfahr(_G286, rhea) ? creep Call: (10) kind(rhea, _G286) ? creep Fail: (10) kind(rhea, _G286) ? creep Redo: (9) vorfahr(_G286, rhea) ? creep Call: (10) kind(rhea, _G341) ? creep Fail: (10) kind(rhea, _G341) ? creep Fail: (9) vorfahr(_G286, rhea) ? creep Fail: (9) kind(hera, _G341) ? creep Fail: (8) vorfahr(_G286, hera) ? creep Fail: (8) kind(hebe, _G341) ? creep Fail: (7) vorfahr(_G286, hebe) ? creep

No

Wissensbasis:Wissensbasis:

Page 51: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

51 Aufgabe

Gegeben ist das folgende Logikprogramm.Gegeben ist das folgende Logikprogramm.

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

?- vorfahr(V, hebe).

Welches Ergebnis liefert die Prolog-Inferenzmaschine? Überprüfe deine Vermutung.Welches Ergebnis liefert die Prolog-Inferenzmaschine? Überprüfe deine Vermutung.

Page 52: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

52 Aufgabe

Gegeben ist das folgende Logikprogramm.Gegeben ist das folgende Logikprogramm.

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

?- vorfahr(V, hebe).

Welches Ergebnis liefert die Prolog-Inferenzmaschine? Überprüfe deine Vermutung.Welches Ergebnis liefert die Prolog-Inferenzmaschine? Überprüfe deine Vermutung.

Page 53: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

53 Teil 3

Deklarative Programmierung

Page 54: Logische Programmierung Klaus Becker 2014. 2 Logische 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.

Page 55: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

55 Graphen

Ein Graph besteht aus einer Menge von Knoten und einer Menge von Kanten (die jeweils zwei Knoten miteinander verbinden).

gerichteter, unbewerteter Graph

Page 56: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

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?

...

Page 57: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

57 Lösung des Wegsucheproblems

ALGORITHMUS: Wegsuche in gerichteten GraphenEingabe: gerichteter Graph, Startknoten, ZielknotenMarkiere 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

Page 58: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

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.

Page 59: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

59

Vereinfachung des Wegsucheproblems

Wegsucheproblem:

Zur Vereinfachung des Graphenproblems betrachten wir vorerst nur Graphen, die keine Kreise enthalten.

% Graphkante(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).

gerichteter Graph ohne Kreise

Beschreibung des Graphen mit Fakten

Page 60: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

60 Aufgabe

Aufgabe:

Entwickle geeignete Prolog-Regeln zur Festlegung des weg-Prädikats.

% Graphkante(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).

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.

Page 61: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

61 Aufgabe

% Graphkante(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, 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"?

gerichteter Graph ohne Kreise

Page 62: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

62 Aufgabe

% Graphkante(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).

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.

gerichteter Graph ohne Kreise

Page 63: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

63 Aufsammeln der Wegknoten

% Graphkante(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).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?

gerichteter Graph ohne Kreise

Page 64: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

64

Aufsammeln in einer Akkumulatorliste

% Graphkante(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).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.

gerichteter Graph ohne Kreise

Page 65: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

65 Lösung des Wegsucheproblems

% Graphkante(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).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)....

gerichteter Graph mit Kreisen

Page 66: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

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 = cY = d ;

X = cY = g ;

X = dY = c ;

X = fY = g ;

X = gY = h ;

X = hY = d ;

No

Aufgabe:

Entwickle ein geeignetes Logikprogramm zur Lösung des Tratsch-Problems. Benutze die erzielten Ergebnisse zur Lösung des Graphenproblems.

Page 67: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

67 Anwendung: Umfüllproblem

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.

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.

Page 68: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

68 Anwendung: Umfüllproblem

% Graphkante(X, Y) :- zustandsuebergang(X, Y).% 3-l-Eimer füllenzustandsuebergang((Eimer4, Eimer3), (Eimer4, 3)) :- Eimer3 \== 3.% 4-l-Eimer füllen...% 3-l-Eimer leerenzustandsuebergang((Eimer4, Eimer3), (Eimer4, 0)) :- Eimer3 \== 0.% 4-l-Eimer leeren...% 3-l-Eimer umfüllen in 4-l-Eimerzustandsuebergang((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-Eimerzustandsuebergang((Eimer4, Eimer3), (4, Eimer31)) :- Eimer4 \== 4, Eimer3 + Eimer4 >4, Eimer31 is Eimer3+Eimer4-4....

Page 69: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

69 Deklarative Programmierung

Ansatz: Beschreiben, was in der Modellwelt gelten sollAnsatz: Beschreiben, was in der Modellwelt gelten soll

Deklarative Programmierung besteht darin, den Problemkontext (Miniwelt) mit gegebenen Mitteln (hier: Fakten und Regeln) zu beschreiben.Deklarative Programmierung besteht darin, den Problemkontext (Miniwelt) mit gegebenen Mitteln (hier: Fakten und Regeln) zu beschreiben.

Inferenz-maschine

zusammenfuegen([], Y, Y). zusammenfuegen([E|RX], Y, [E|RZ]) :- fuegezusammen(RX, Y, RZ).

?- zusammenfuegen([a, b], [c, a, d], Z).

Z = [a, b, c, a, d]Ergebnis

Anfrage

Wissensbasis

Page 70: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

70 Imperative ProgrammierungAnsatz: Beschreiben, wie die Ergebnisse berechnet werden sollenAnsatz: Beschreiben, wie die Ergebnisse berechnet werden sollen

E.-Zustand

Register-maschine

A.-Zustand

Anweisungen

Z := []solange X nicht leer ist: E := erstesElement(X) Z := mitLetztem(Z, E) X := ohneEstes(X)solange Y nicht leer ist: E := erstesElement(Y) Z := mitLetztem(Z, E) Y := ohneEstes(Y)

{X: [a, b]; Y: [c, a, d]}

{Z: [a, b, c, a, d]}

Imperative Programmierung besteht darin, eine (mehr oder weniger abstrakte) Maschine mit Hilfe von Anweisungen zu steuern.Imperative Programmierung besteht darin, eine (mehr oder weniger abstrakte) Maschine mit Hilfe von Anweisungen zu steuern.

Page 71: Logische Programmierung Klaus Becker 2014. 2 Logische Programmierung

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.bildung-rp.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.