Programmieren mit Programmieren mit PrädikatenlogikPrädikatenlogik
Klaus Becker2004
2
KB
Log
isch
e P
rog
ram
mie
run
gProgrammieren mit LogikProgrammieren mit Logik
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).
3
KB
Log
isch
e P
rog
ram
mie
run
gTeil 1Teil 1
Fakten und Regeln
4
KB
Log
isch
e P
rog
ram
mie
run
g
(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
| |
From Edith Hamiltion's Mythology Hermes Aphrodite
Die Welt der griechischen GötterDie Welt der griechischen Götter
5
KB
Log
isch
e P
rog
ram
mie
run
gModellierungsansatzModellierungsansatz
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)
ist verheiratet mit
6
KB
Log
isch
e P
rog
ram
mie
run
gModellierungsansatzModellierungsansatz
Objekte werden mit Konstanten (Termen) beschrieben,Eigenschaften und Beziehungen mit Hilfe von Prädikaten.Objekte werden mit Konstanten (Termen) beschrieben,Eigenschaften und Beziehungen mit Hilfe von Prädikaten.
Fakten:
weiblich(hera). maennlich(zeus). verheiratet(zeus, hera).
ist verheiratet mit
Hera(weiblich)
Zeus(männlich)
Konstante
Konstante
Prädikat
7
KB
Log
isch
e P
rog
ram
mie
run
gModellierungsansatzModellierungsansatz
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). verheiratet(zeus, hera).
ist verheiratet mit
Hera(weiblich)
Zeus(männlich)
Miniwelt
8
KB
Log
isch
e P
rog
ram
mie
run
gModellierungsansatzModellierungsansatz
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:
weiblich(maia).maennlich(zeus). kind(hermes, zeus).kind(hermes, maia).
Miniwelt
Zeus=Maia Zeus=Dione | | Hermes Aphrodite
Regeln:
vater(X, Y) :- kind(Y, X), maennlich(X). mutter(X, Y) :- kind(Y, X), weiblich(X).
9
KB
Log
isch
e P
rog
ram
mie
run
gRegelnRegeln
Regeln sind Wenn-Dann-Aussagen.Regeln sind Wenn-Dann-Aussagen.
Regeln:
vater(X, Y) :- kind(Y, X), maennlich(X). mutter(X, Y) :- kind(Y, X), weiblich(X).
Variable
Implikation
informelle Beschreibung:
X ist Vater von Y, wenn Y Kind von X ist und X männlich ist. X ist Mutter von Y, wenn Y Kind von X ist und X weiblich ist.
Und
Regelrumpf(Bedingung)
Regelkopf(Folgerung)
10
KB
Log
isch
e P
rog
ram
mie
run
gRekursive RegelnRekursive Regeln
Das Prädikat im Regelkopf kann im Regelrumpf vorkommen.Das Prädikat im Regelkopf kann 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(Bedingung)
Regelkopf(Folgerung)
11
KB
Log
isch
e P
rog
ram
mie
run
gVon der Miniwelt zur ModellweltVon der Miniwelt zur Modellwelt
Miniwelt Modellwelt
Uranus|
Rhea|
Zeus|
Hebe...
vorfahr(zeus, hebe).
vorfahr(rhea, hebe).
vorfahr(uranus, hebe).
...
Beschreibung der Miniwelt
Fakten und Regeln:
kind(hebe, zeus).kind(hebe, hera).kind(zeus, rhea).kind(zeus, cronus).kind(rhea, uranus)....
vorfahr(X, Y) :- kind(Y, X).
vorfahr(X, Y) :- kind(Y, Z), vorfahr(X,
Z).
12
KB
Log
isch
e P
rog
ram
mie
run
gLogische Herleitung der ModellweltLogische Herleitung der Modellwelt
kind(hebe, zeus).kind(hebe, hera).kind(zeus, rhea).kind(zeus, cronus).kind(rhea, uranus)....
vorfahr(X, Y) :- kind(Y, X).
vorfahr(X, Y) :- kind(Y, Z), vorfahr(X, Z).
Modellwelt
vorfahr(zeus, hebe).
vorfahr(rhea, hebe).
...
Beschreibung der Miniwelt
kind(hebe, zeus). vorfahr(X, Y) :-
kind(Y, X).
vorfahr(zeus, hebe).
Logische Herleitung
kind(zeus, rhea). vorfahr(zeus, hebe). vorfahr(X, Y) :-
kind(Y, Z), vorfahr(X, Z).
vorfahr(rhea, hebe).
13
KB
Log
isch
e P
rog
ram
mie
run
gModus PonensModus Ponens
Alle Menschen sind sterblich.Sokrates ist ein Mensch.
Sokrates ist sterblich.
Für alle X: mensch(X) sterblich(X).mensch(sokrates).
sterblich(sokrates).sterblich(X) :- mensch(X).mensch(sokrates).
sterblich(sokrates).
Zur Festlegung 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 Festlegung 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.
14
KB
Log
isch
e P
rog
ram
mie
run
gModellierungskonzeptModellierungskonzept
Das gesamte Wissen über die Welt wird mit Fakten und Regeln modelliert.
In der Modellwelt gelten nur die „Sachverhalte“, die mit Hilfe der gegebenen Fakten und Regeln logisch abgeleitet werden können. Dies sind die direkt genannten Fakten und die mit Hilfe der logischen Schlussregel abgeleiteten Fakten (closed-world-assumption).
Das gesamte Wissen über die Welt wird mit Fakten und Regeln modelliert.
In der Modellwelt gelten nur die „Sachverhalte“, die mit Hilfe der gegebenen Fakten und Regeln logisch abgeleitet werden können. Dies sind die direkt genannten Fakten und die mit Hilfe der logischen Schlussregel abgeleiteten Fakten (closed-world-assumption).
15
KB
Log
isch
e P
rog
ram
mie
run
gAnfragen Anfragen
maennlich(zeus). weiblich(hera).weiblich(maia).kind(apollo, zeus).kind(hermes, maia).kind(hermes, zeus). vater(X, Y) :- kind(Y, X), maennlich(X).
?- maennlich(zeus). % Ist Zeus männlich?Yes.
?- maennlich(hera). % Ist Hera männlich?No.
Ja-Nein-Anfrage
16
KB
Log
isch
e P
rog
ram
mie
run
gAnfragen Anfragen
maennlich(zeus). weiblich(hera).weiblich(maia).kind(apollo, zeus).kind(hermes, maia).kind(hermes, zeus). vater(X, Y) :- kind(Y, X), maennlich(X).
?- vater(W, hermes). % Wer ist Vater von Hermes?W = zeus;No.?- weiblich(Frau). % Wer ist weiblich?Frau = hera;Frau = maia;No.
Ergänzungsanfrage
17
KB
Log
isch
e P
rog
ram
mie
run
gAnfragen mit anonymen Variablen Anfragen mit anonymen Variablen
maennlich(zeus). weiblich(hera).weiblich(maia).kind(apollo, zeus).kind(hermes, maia).kind(hermes, zeus). vater(X, Y) :- kind(Y, X), maennlich(X). mutter(X) :- weiblich(X), kind(_, X).
?- vater(V, _Kind) % Wer ist Vater?
?- mutter(M) % Wer ist Mutter?
Anonyme Variablen werden nicht instanziert.Anonyme Variablen werden nicht instanziert.
Anonyme Variable
18
KB
Log
isch
e P
rog
ram
mie
run
gDatenflussrichtung Datenflussrichtung
maennlich(zeus). weiblich(hera).weiblich(maia).kind(apollo, zeus).kind(hermes, maia).kind(hermes, zeus). vater(X, Y) :-
kind(Y, X), maennlich(X).
?- vater(maia, hermes). % Ist Maia der Vater von Hermes??- vater(V, hermes). % Wer ist der Vater von Hermes?
?- vater(zeus, K). % Von wem ist Zeus der Vater?
?- vater(V, K). % Wer ist Vater von wem?
19
KB
Log
isch
e P
rog
ram
mie
run
gDatenflussrichtung Datenflussrichtung
maennlich(zeus). weiblich(hera).weiblich(maia).kind(apollo, zeus).kind(hermes, maia).kind(hermes, zeus). vater(X, Y) :- % vater(?Vater, ?Kind)
kind(Y, X), maennlich(X).
?- vater(maia, hermes). % vater(+Vater, +Kind)
?- vater(V, hermes). % vater(-Vater, +Kind)
?- vater(zeus, K). % vater(+Vater, -Kind)
?- vater(V, K). % vater(-Vater, -Kind)
instanziert
offen
Kann in beiden Rollen (+ / -) verwendet
werden
Die Datenflussrichtung kann flexibel gestaltet werden. Die Datenflussrichtung kann flexibel gestaltet werden.
20
KB
Log
isch
e P
rog
ram
mie
run
gLogik-ProgrammLogik-Programm
maennlich(zeus). weiblich(hera).weiblich(maia).kind(apollo, zeus).kind(hermes, maia).kind(hermes, zeus). vater(X, Y) :- kind(Y, X), maennlich(X).
?- weiblich(Frau).
Ein Logik-Programm besteht aus einer Wissensbasis und einer Anfrage. Ein Logik-Programm besteht aus einer Wissensbasis und einer Anfrage.
Wissensbasis
Anfrage
21
KB
Log
isch
e P
rog
ram
mie
run
gHinweise zur SyntaxHinweise zur Syntax
Jede Deklaration der Wissensbasis und jede Anfrage schließt mit einem Punkt ab.
Variablenbezeichner beginnen mit einem Großbuchstaben (oder anonym mit _), Konstanten- und Prädikatenbezeichner mit Kleinbuchstaben.
Jede Deklaration der Wissensbasis und jede Anfrage schließt mit einem Punkt ab.
Variablenbezeichner beginnen mit einem Großbuchstaben (oder anonym mit _), Konstanten- und Prädikatenbezeichner mit Kleinbuchstaben.
maennlich(zeus). weiblich(hera).weiblich(maia).kind(apollo, zeus).kind(hermes, maia).kind(hermes, zeus). vater(X, Y) :- kind(Y, X), maennlich(X).
?- weiblich(Frau).
22
KB
Log
isch
e P
rog
ram
mie
run
gPROLOGPROLOG
PROLOG („Programming in Logic“): PROLOG („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 (unterrichtsgeeignete) Entwicklungsumgebung zur Erstellung von PROLOG-Programmen(Autor: G. Röhner).
23
KB
Log
isch
e P
rog
ram
mie
run
gSWI-Prolog-EditorSWI-Prolog-Editor
Wissensbasis
Anfrage
24
KB
Log
isch
e P
rog
ram
mie
run
gSWI-Prolog-EditorSWI-Prolog-Editor
Consultieren
Mit consult(<Datei>) werden aus der angegebenen Datei die Fakten und Regeln in die Wissensbasis
eingelesen.
25
KB
Log
isch
e P
rog
ram
mie
run
gÜbungenÜbungen
Aufgabe 1: FamilieAufgabe 1: Familie
Entwickeln Sie eine Wissensbasis zu einer Familien-Welt. Folgende Prädikate können festgelegt werden:
maennlich, weiblich, kind, vater, mutter, vorfahr, sohn, tochter, grossvater, grossmutter, enkel, geschwister, bruder, schwester, onkel, tante, ...
Testen Sie ihre Wissensbasis mit Hilfe geeigneter Anfragen.
26
KB
Log
isch
e P
rog
ram
mie
run
gÜbungenÜbungen
Aufgabe 2: Aufgabe 2:
Wir betrachten die unten abgebildete Blockwelt. Wie könnte man die Strukrur dieser Blockwelt mit Hilfe von Fakten und Regeln beschreiben?
p1
a
p2
e
c
p3
b
f
g
d
27
KB
Log
isch
e P
rog
ram
mie
run
gTeil 2Teil 2
Das Berechnungskonzept
28
KB
Log
isch
e P
rog
ram
mie
run
g
Gegeben: Logik-Programm (Wissensbasis + Anfrage)Gegeben: Logik-Programm (Wissensbasis + Anfrage)
BerechnungsproblemBerechnungsproblem
maennlich(zeus). weiblich(hera).weiblich(maia).kind(apollo, zeus).kind(hermes, maia).kind(hermes, zeus). vater(X, Y) :- kind(Y, X), maennlich(X). ?- vater(V, hermes).
maennlich(zeus). weiblich(hera).weiblich(maia).kind(apollo, zeus).kind(hermes, maia).kind(hermes, zeus).vater(zeus, apollo).vater(zeus, hermes)....
Problem: Wie erzeugt man systematisch Anfrageergebnisse?Problem: Wie erzeugt man systematisch Anfrageergebnisse?
V = zeus.
Gesucht: Instanzen der Anfrage, die zur Modellwelt gehörenGesucht: Instanzen der Anfrage, die zur Modellwelt gehören
29
KB
Log
isch
e P
rog
ram
mie
run
g
Wissensbasismaennlich(zeus). weiblich(hera).weiblich(maia).kind(apollo, zeus).kind(hermes, maia).kind(hermes, zeus). vater(X, Y) :- kind(Y, X), maennlich(X). ...
Anfrage?- vater(V, hermes).
Herleitung (Beweis)
kind(hermes, zeus).maennlich(zeus). vater(X, Y) :- kind(Y, X), maennlich(X). ------------------------------------vater(zeus, hermes).
ErgebnisV = zeus. /* Substitution */
BerechnungsproblemBerechnungsproblem
Problem: Wie erzeugt man systematisch logische Herleitungen?Problem: Wie erzeugt man systematisch logische Herleitungen?
30
KB
Log
isch
e P
rog
ram
mie
run
g
/*1*/ maennlich(zeus). /*2*/ weiblich(hera). /*3*/ weiblich(maia)./*4*/ kind(apollo, zeus). /*5*/ kind(hermes, maia). /*6*/ kind(hermes, zeus). /*7*/ vater(X, Y) :- kind(Y, X), maennlich(X). Substitution
X = V, Y = hermes.
Ziel
?- vater(V, hermes).
?- kind(hermes, V), maennlich(V).
Regel
7
Auswertung von Anfragen Auswertung von Anfragen
Unifikation: Suche einen Fakt / Regelkopf, der mit dem ersten Term des Ziels unifiziert (d. h. durch eine Substitution gleichgemacht werden kann).
Resolution (bei Regel):Ersetze den ersten Term des Ziels durch den Regelrumpf und wende auf alle Terme des Ziels die Substitution an.
Unifikation: Suche einen Fakt / Regelkopf, der mit dem ersten Term des Ziels unifiziert (d. h. durch eine Substitution gleichgemacht werden kann).
Resolution (bei Regel):Ersetze den ersten Term des Ziels durch den Regelrumpf und wende auf alle Terme des Ziels die Substitution an.
31
KB
Log
isch
e P
rog
ram
mie
run
g
/*1*/ maennlich(zeus). /*2*/ weiblich(hera). /*3*/ weiblich(maia)./*4*/ kind(apollo, zeus). /*5*/ kind(hermes, maia). /*6*/ kind(hermes, zeus). /*7*/ vater(X, Y) :- kind(Y, X), maennlich(X). Substitution
X = V, Y = hermes.
V = maia.
Ziel
?- vater(V, hermes).
?- kind(hermes, V), maennlich(V).
?- maennlich(maia).
Regel
7
5
Auswertung von Anfragen Auswertung von Anfragen
Unifikation: Suche einen Fakt / Regelkopf, der mit dem ersten Term des Ziels unifiziert (d. h. durch eine Substitution gleichgemacht werden kann).
Resolution (bei Regel):Ersetze den ersten Term des Ziels durch den Regelrumpf und wende auf alle Terme des Ziels die Substitution an.
Unifikation: Suche einen Fakt / Regelkopf, der mit dem ersten Term des Ziels unifiziert (d. h. durch eine Substitution gleichgemacht werden kann).
Resolution (bei Regel):Ersetze den ersten Term des Ziels durch den Regelrumpf und wende auf alle Terme des Ziels die Substitution an.
32
KB
Log
isch
e P
rog
ram
mie
run
g
/*1*/ maennlich(zeus). /*2*/ weiblich(hera). /*3*/ weiblich(maia)./*4*/ kind(apollo, zeus). /*5*/ kind(hermes, maia). /*6*/ kind(hermes, zeus). /*7*/ vater(X, Y) :- kind(Y, X), maennlich(X). Substitution
V = maia.
Ziel
?- vater(V, hermes).
?- kind(hermes, V), maennlich(V).
?- maennlich(maia).
?- kind(hermes, V), maennlich(V).
Regel
7
5
No
Auswertung von Anfragen Auswertung von Anfragen
Backtracking: Wenn der erste Term des Ziels mit keinem Fakt / Regelkopf unifiziert, dann geh zurück zu dem Ziel, bei dem als letztes eine Auswahlmöglichkeit bestand und treffe eine neue Auswahl.
Backtracking: Wenn der erste Term des Ziels mit keinem Fakt / Regelkopf unifiziert, dann geh zurück zu dem Ziel, bei dem als letztes eine Auswahlmöglichkeit bestand und treffe eine neue Auswahl.
33
KB
Log
isch
e P
rog
ram
mie
run
g
/*1*/ maennlich(zeus). /*2*/ weiblich(hera). /*3*/ weiblich(maia)./*4*/ kind(apollo, zeus). /*5*/ kind(hermes, maia). /*6*/ kind(hermes, zeus). /*7*/ vater(X, Y) :- kind(Y, X), maennlich(X). Substitution
V = maia.
V = zeus.
Ziel
?- vater(V, hermes).
?- kind(hermes, V), maennlich(V).
?- maennlich(maia).
?- kind(hermes, V), maennlich(V).
?- maennlich(zeus).
Regel
7
5
No
6
Auswertung von Anfragen Auswertung von Anfragen
34
KB
Log
isch
e P
rog
ram
mie
run
g
/*1*/ maennlich(zeus). /*2*/ weiblich(hera). /*3*/ weiblich(maia)./*4*/ kind(apollo, zeus). /*5*/ kind(hermes, maia). /*6*/ kind(hermes, zeus). /*7*/ vater(X, Y) :- kind(Y, X), maennlich(X). Substitution
V = maia.
V = zeus.
V = zeus.
Ziel
?- vater(V, hermes).
?- kind(hermes, V), maennlich(V).
?- maennlich(maia).
?- kind(hermes, V), maennlich(V).
?- maennlich(zeus).
Regel
7
5
No
6
1
Auswertung von Anfragen Auswertung von Anfragen
Ergebnis: Ist keine Zielklausel mehr vorhanden, so liefert die Substitution das gesuchte Ergebnis.
Ergebnis: Ist keine Zielklausel mehr vorhanden, so liefert die Substitution das gesuchte Ergebnis.
35
KB
Log
isch
e P
rog
ram
mie
run
g
/*1*/ maennlich(zeus). /*2*/ weiblich(hera). /*3*/ weiblich(maia)./*4*/ kind(apollo, zeus). /*5*/ kind(hermes, maia). /*6*/ kind(hermes, zeus). /*7*/ vater(X, Y) :- kind(Y, X), maennlich(X).
Beweisbaum Beweisbaum
Veranschaulichung: Die Herleitung eines Berechnungsergebnisses kann mit Hilfe eines Beweisbaumes verdeutlicht werden.
Veranschaulichung: Die Herleitung eines Berechnungsergebnisses kann mit Hilfe eines Beweisbaumes verdeutlicht werden.
vater(V, hermes)
kind(hermes, V) maennlich(V)
kind(hermes, maia) kind(hermes, zeus) maennlich(zeus)
UND-Knoten
ODER-Knoten
X = V, Y = hermes.
V = maia. V = zeus. V = zeus.
36
KB
Log
isch
e P
rog
ram
mie
run
gTrace einer Beweissuche Trace einer Beweissuche
vater(V, hermes)
kind(hermes, V) maennlich(V)
kind(hermes, maia) kind(hermes, zeus) maennlich(zeus)
UND-Knoten
ODER-Knoten
?- vater(V, hermes).
CALL: vater(V, hermes)
CALL: kind(hermes, V)
CALL: kind(hermes, maia)
EXIT: kind(hermes, maia)
CALL: maennlich(maia)
FAIL: maennlich(maia)
REDO: kind(hermes, V)
CALL: kind(hermes, zeus)
EXIT: kind(hermes, zeus)
CALL: maennlich(zeus)
EXIT: maennlich(zeus)
EXIT: vater(V, hermes)
V = zeus.
CALL: Teilziel aufrufen
EXIT: Zeilziel erfolgr. b.
REDO: Teilziel nochmal b.
FAIL: Teilziel erfolglos b.
37
KB
Log
isch
e P
rog
ram
mie
run
gDas Berechnungskonzept Das Berechnungskonzept
Das Berechnungskonzept bei der logischen Programmierung beruht auf „maschinellem“ logischen Schließen. Hierzu werden die folgenden Algorithmen von einer sog. Inferenzmaschine geeignet kombiniert:
Unifikationsalgorithmus (erzeugt Variablenbindung)
Inferenzalgorithmus (führt Resolution durch)
Suchalgorithmus (benutzt Backtracking)
Das Berechnungskonzept bei der logischen Programmierung beruht auf „maschinellem“ logischen Schließen. Hierzu werden die folgenden Algorithmen von einer sog. Inferenzmaschine geeignet kombiniert:
Unifikationsalgorithmus (erzeugt Variablenbindung)
Inferenzalgorithmus (führt Resolution durch)
Suchalgorithmus (benutzt Backtracking)
38
KB
Log
isch
e P
rog
ram
mie
run
gDas Berechnungskonzept Das Berechnungskonzept
Ergebnis
Inferenz-maschine
Anfrage
Wissensbasis
kind(hermes, maia).vorfahr(X, Y) :- kind(Y, X).vorfahr(X, Y) :- kind(Y, Z),
vorfahr(X, Z).
?- vorfahr(A, B).
X = maia, Y = hermes.
Die Inferenzmaschine versucht, logische Ableitungen zur Anfrage aus der Wissensbasis zu erstellen. Die Inferenzmaschine versucht, logische Ableitungen zur Anfrage aus der Wissensbasis zu erstellen.
39
KB
Log
isch
e P
rog
ram
mie
run
gDeklarative Semantik Deklarative Semantik
Logisches Programm (Wissensbasis + Anfrage)Logisches Programm (Wissensbasis + Anfrage)
maennlich(zeus). weiblich(hera).weiblich(maia).kind(apollo, zeus).kind(hermes, maia).kind(hermes, zeus). vater(X, Y) :- kind(Y, X), maennlich(X).
?- vater(V, hermes).
Deklarative Semantik eines Logik-Programms
Menge der Instanzen der Anfrageklausel, die zur Modellwelt gehören bzw. die aus der Wissensbasis mit Hilfe der Schlussregel „modus ponens“ hergeleitet werden können.
Deklarative Semantik eines Logik-Programms
Menge der Instanzen der Anfrageklausel, die zur Modellwelt gehören bzw. die aus der Wissensbasis mit Hilfe der Schlussregel „modus ponens“ hergeleitet werden können.
40
KB
Log
isch
e P
rog
ram
mie
run
gProzedurale Semantik Prozedurale Semantik
Logisches Programm (Wissensbasis + Anfrage)Logisches Programm (Wissensbasis + Anfrage)
maennlich(zeus). weiblich(hera).weiblich(maia).kind(apollo, zeus).kind(hermes, maia).kind(hermes, zeus). vater(X, Y) :- kind(Y, X), maennlich(X).
?- vater(V, hermes).
Prozedurale Semantik des Programms
Menge der Instanzen der Anfrageklausel, die die Inferenzmaschine mittels Unifikations-, Inferenz- und Suchalgorithmus erzeugt.
Prozedurale Semantik des Programms
Menge der Instanzen der Anfrageklausel, die die Inferenzmaschine mittels Unifikations-, Inferenz- und Suchalgorithmus erzeugt.
41
KB
Log
isch
e P
rog
ram
mie
run
gÜbungenÜbungen
Aufgabe 3: BerechnungskonzeptAufgabe 3: Berechnungskonzept
Wir betrachten das folgende Logik-Programm zur Blockwelt:auf(a, p1).auf(c, a).auf(e, p2).auf(b, p3).auf(f, b).auf(g, f).auf(d, g).ueber(X, Y) :- auf(X, Y).ueber(X, Y) :- auf(X, Z), ueber(Z, Y). p1
a
p2
e
c
p3
b
f
g
d
?- ueber(X, g).
Schalten Sie den Trace-Modus ein und verfolgen Sie die Erzeugung der Berechnungsergebnisse. Erstellen Sie auch einen Beweisbaum.
42
KB
Log
isch
e P
rog
ram
mie
run
gÜbungenÜbungen
Aufgabe 4: BerechnungskonzeptAufgabe 4: Berechnungskonzept
Wir betrachten die beiden folgenden Logik-Programme:
Welche Berechnungsergebnisse erwarten Sie? Bestimmen Sie die Ergebnisse mit Hilfe von PROLOG.Verfolgen Sie die Berechnung der Ergebnisse mit Hilfe
einer Trace.Wie lässt sich das Verhalten von PROLOG erklären?
Wissensbasis - Version 1:kind(hermes, maia).vorfahr(X, Y) :- kind(Y, X).vorfahr(X, Y) :- kind(Y, Z),
vorfahr(X, Z).
?- vorfahr(A, B).
Wissensbasis - Version 2:kind(hermes, maia).vorfahr(X, Y) :- vorfahr(X, Z),
kind(Y, Z). vorfahr(X, Y) :- kind(Y, X).
43
KB
Log
isch
e P
rog
ram
mie
run
gGrenzen der Logik Grenzen der Logik
Logisches Programm (Wissensbasis + Anfrage)Logisches Programm (Wissensbasis + Anfrage)
Wissensbasis - Version 1:kind(hermes, maia).vorfahr(X, Y) :- kind(Y, X).vorfahr(X, Y) :- kind(Y, Z),
vorfahr(X, Z).
?- vorfahr(A, B).
Wissensbasis - Version 2:kind(hermes, maia).vorfahr(X, Y) :- vorfahr(X, Z),
kind(Y, Z). vorfahr(X, Y) :- kind(Y, X).
kind(hermes, maia). vorfahr(X, Y) :- kind(Y, X).
vorfahr(maia, hermes).
Die Modellierungen sind logisch äquivalent – die Logik-Programme haben dieselbe deklarative Semantik. Die Modellierungen sind logisch äquivalent – die Logik-Programme haben dieselbe deklarative Semantik.
44
KB
Log
isch
e P
rog
ram
mie
run
gGrenzen der Logik Grenzen der Logik
Logisches Programm (Wissensbasis + Anfrage)Logisches Programm (Wissensbasis + Anfrage)
Wissensbasis - Version 1:/*1*/ kind(hermes, maia)./*2*/ vorfahr(X, Y) :- kind(Y, X). /*3*/ vorfahr(X, Y) :- kind(Y, Z), vorfahr(X, Z).
Substitution
X = A, Y = B
B = hermes, A = maia.
Ziel
?- vorfahr(A, B).
?- kind(B, A).
Regel
2
1
45
KB
Log
isch
e P
rog
ram
mie
run
gGrenzen der Logik Grenzen der Logik
Logisches Programm (Wissensbasis + Anfrage)Logisches Programm (Wissensbasis + Anfrage)
Wissensbasis - Version 2:/*1*/ kind(hermes, maia)./*2*/ vorfahr(X, Y) :- vorfahr(X, Z), kind(Y, Z). /*3*/ vorfahr(X, Y) :- kind(Y, X).
Substitution
X = A, Y = B
X = A, Y = Z.
...
Ziel
?- vorfahr(A, B).
?- vorfahr(A, Z), kind(B, Z).
?- vorfahr(A, U), kind(Z, U), kind...
...
Regel
2
2
2
Die Inferenzmaschine liefert unterschiedliche Berechnungsergebnisse – die Logik-Programme haben eine unterschiedliche prozedurale Semantik.
Die Inferenzmaschine liefert unterschiedliche Berechnungsergebnisse – die Logik-Programme haben eine unterschiedliche prozedurale Semantik.
46
KB
Log
isch
e P
rog
ram
mie
run
gGrenzen der Logik Grenzen der Logik
Logisches Programm (Wissensbasis + Anfrage)Logisches Programm (Wissensbasis + Anfrage)
Wissensbasis - Version 1:kind(hermes, maia).vorfahr(X, Y) :- kind(Y, X).vorfahr(X, Y) :- kind(Y, Z),
vorfahr(X, Z).
?- vorfahr(A, B).
Wissensbasis - Version 2:kind(hermes, maia).vorfahr(X, Y) :- vorfahr(X, Z),
kind(Y, Z). vorfahr(X, Y) :- kind(Y, X).
Beachte: Die prozedurale Semantik wird durch die Algorithmen der Inferenzmaschine festgelegt. Die Reihenfolge der Programmklauseln und Zielklauseln können hierbei eine entscheidende Rolle spielen.
Beachte: Die prozedurale Semantik wird durch die Algorithmen der Inferenzmaschine festgelegt. Die Reihenfolge der Programmklauseln und Zielklauseln können hierbei eine entscheidende Rolle spielen.
47
KB
Log
isch
e P
rog
ram
mie
run
gDeklarative ProgrammierungDeklarative Programmierung
Beschreiben, was in der Modellwelt gelten soll Beschreiben, was in der Modellwelt gelten soll
Ergebnis
Inferenz-maschine
Anfrage
Wissensbasis
kind(hermes, maia).vorfahr(X, Y) :- kind(Y, X).vorfahr(X, Y) :- kind(Y, Z),
vorfahr(X, Z).
?- vorfahr(A, B).
X = maia, Y = hermes.
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.
48
KB
Log
isch
e P
rog
ram
mie
run
gImperative ProgrammierungImperative Programmierung
Beschreiben, wie die Ergebnisse berechnet werden sollenBeschreiben, wie die Ergebnisse berechnet werden sollen
E.-Zustand
Register-maschine
A.-Zustand
Anweisungenz := x; x := y; y := z;
{x: 3; y: 5}
{x: 5; y: 3; z: ...}
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.
49
KB
Log
isch
e P
rog
ram
mie
run
gTeil 3Teil 3
Anwendung: Datenbanken
50
KB
Log
isch
e P
rog
ram
mie
run
gEine einfache BibliotheksweltEine einfache Bibliothekswelt
51
KB
Log
isch
e P
rog
ram
mie
run
gER-ModellierungER-Modellierung
Leser Ausleihe Buch
Name AutorSigDatum... ...
LNr: 3Name: MüllerVorname: Peter...
LNr: 6Name: SchmittVorname: Otto...LNr: 1Name: MeierVorname: Karla...
Sig: Rel1Autor: Titel: Bibel...
Sig: M1Autor: Euklid Titel: Elemente...
Sig: P1Autor: Einstein Titel: Relativität...
8.1.2002
16.2.2002
LNr
52
KB
Log
isch
e P
rog
ram
mie
run
gRelationales DatenmodellRelationales Datenmodell
LNr Name Vorname GebJahr Stammkursleit0 Christ Benjamin 83 ROE
1 Eberle Gerrit 84 TM2 Friedrich Andy 83 HB3 Frisch Johannes 84 TM...13 Teubner Ruth 84 HEI14 Thielen Clemens 84 TM15 Wollenweber Lisa 84 TM
Sig Autor Titel Jahr Fachbereich D1 Goethe Faust 1973 Deutsch D2 Mann Dr. Faustus 1937 Deutsch D3 Mann Der Zauberberg 1940 Deutsch ... Ph1 Garder Sofies Welt 1995 Philosophie Ph2 Kant Kritik der reinen Vernunft 1958 Philosophie Ph3 Russell Geschichte der
Philosophie 1952 Philosophie
LNr Sig Datum
4 D2 29.10.018 M1 03.11.01
11 P1 16.08.0113 D5 12.09.0113 Ph2 12.09.0114 D1 06.12.0115 M3 12.10.01
Leser
Buch
Ausleihe
53
KB
Log
isch
e P
rog
ram
mie
run
gBeschreibung mit FaktenBeschreibung mit Fakten
% Leser...leser(15, 'Wollenweber', 'Lisa', 84, tm)....
% Bücher...buch('ph1', 'Garder', 'Sofies Welt', 1995, 'Philosophie')....
% Ausleihen...ausleihe(15, 'm3', datum(12,10,2001))....
54
KB
Log
isch
e P
rog
ram
mie
run
gEine AnfrageEine Anfrage
% Welche Leser haben ein Buch ausgeliehen?
?- ausleihe(Nr, Sig, _Datum), leser(Nr, Name, Vorname, _GebJahr, _StK).
Nr = 3Sig = 'Ph1'Name = 'Frisch'Vorname = 'Johannes' ;
Nr = 4Sig = 'D2'Name = 'Frölich'Vorname = 'Daniel' ;
Nr = 4Sig = 'P2'Name = 'Frölich'Vorname = 'Daniel' ;
...
55
KB
Log
isch
e P
rog
ram
mie
run
gÜbungenÜbungen
Aufgabe 5: BibliothekAufgabe 5: Bibliothek
Laden Sie die Fakten zur Beschreibung der Bibliothekswelt.Erstellen Sie zu den folgenden Aufgaben entsprechende Abfragen.- Welche Leser gibt es?- Welche Leser sind 84 geboren?- Welche Leser sind vor 84 geboren?- Welche Bücher von Goethe sind in der Bibliothek vorhanden?- Welche Bücher sind ausgeliehen? - Welche Bücher hat die Leserin Lisa Wollenweber ausgeliehen?- Welche Leser haben ein Buch ausgeliehen?...
56
KB
Log
isch
e P
rog
ram
mie
run
gEine Regel für MahnungenEine Regel für Mahnungen
% Lesermahnung(Name, Vorname, Sig, datum(Takt, Makt, Jakt)) :- leser(LNr, Name, Vorname, _, _), ausleihe(LNr, Sig, datum(Taus, Maus, Jaus)), monatspaeter(datum(Taus, Maus, Jaus), datum(Takt, Makt, Jakt)).
Ein Leser soll eine Mahnung erhalten, wenn er/sie ein Buch länger als einen Monat ausgeliehen hat.
57
KB
Log
isch
e P
rog
ram
mie
run
gEine Regel für MahnungenEine Regel für Mahnungen
Spezifikation:
monatspaeter(datum(Taus, Maus, Jaus), datum(Takt, Makt, Jakt))soll gelten, wenn das Datum „Takt.Makt.Jakt“ mehr als ein Monat später als das Datum „Taus.Maus.Jaus“ ist.
Beispiele:monatspaeter(datum(11, 7, 2001), datum(20, 9, 2001)) monatspaeter(datum(17, 4, 2001), datum(1, 1, 2002))...
58
KB
Log
isch
e P
rog
ram
mie
run
gEine Regel für MahnungenEine Regel für Mahnungen
monatspaeter(datum(T1,M1,J1), datum(T2,M2,J2)) :- T2 >= T1, M2 >= M1+1, J2 >= J1.
monatspaeter(datum(T1,M1,J1), datum(T2,M2,J2)) :- M2 >= M1+2, J2 >= J1.
monatspaeter(datum(T1,M1,J1), datum(T2,M2,J2)) :- T2 >= T1, J2 >= J1+1.
monatspaeter(datum(T1,M1,J1), datum(T2,M2,J2)) :- (12-M1)+M2 >= 2, J2 >= J1+1.
monatspaeter(datum(T1,M1,J1), datum(T2,M2,J2)) :- J2 >= J1+2.
59
KB
Log
isch
e P
rog
ram
mie
run
gAusleihen und ZurückgebenAusleihen und Zurückgeben
Bücher können ausgeliehen und zurückgegeben werden.
% Ausleihenausleihe(3,'Ph1',datum(30,12,2001)).ausleihe(4,'D2',datum(16,9,2001)).ausleihe(4,'P2',datum(30,12,2001)).ausleihe(6,'D3',datum(30,12,2001)).ausleihe(8,'M1',datum(23,10,2001)).ausleihe(11,'P1',datum(14,12,2001)). % löschenausleihe(12,'M2',datum(30,12,2001)).ausleihe(13,'D5',datum(30,8,2001)).ausleihe(13,'Ph2',datum(11,7,2001)).ausleihe(14,'D1',datum(13,12,2001)).ausleihe(15,'M3',datum(1,11,2001)).ausleihe(2,'P1',datum(10,1,2002)). % einfügen
60
KB
Log
isch
e P
rog
ram
mie
run
gVeränderung der WissensbasisVeränderung der Wissensbasis
% Ausleihen:- dynamic ausleihe/3. % Achtungausleihe(3,'Ph1',datum(30,12,2001)).ausleihe(4,'D2',datum(16,9,2001)).ausleihe(4,'P2',datum(30,12,2001)).ausleihe(6,'D3',datum(30,12,2001)).ausleihe(8,'M1',datum(23,10,2001)).ausleihe(11,'P1',datum(14,12,2001)). ausleihe(12,'M2',datum(30,12,2001)).ausleihe(13,'D5',datum(30,8,2001)).ausleihe(13,'Ph2',datum(11,7,2001)).ausleihe(14,'D1',datum(13,12,2001)).ausleihe(15,'M3',datum(1,11,2001)).
Beachte: Damit die Prädikate verändert werden können, müssen sie als dynamisch deklariert werden.Beachte: Damit die Prädikate verändert werden können, müssen sie als dynamisch deklariert werden.
61
KB
Log
isch
e P
rog
ram
mie
run
gVeränderung der WissensbasisVeränderung der Wissensbasis
asserta(+Klausel)fügt die Klausel vor den bereits bestehenden Klauseln ein
assertz(+Klausel)fügt die Klausel hinter die bereits bestehenden Klauseln ein
retract(+Klausel)löscht die Klausel
Prädikate zur Manipulation der Wissensbasis:Prädikate zur Manipulation der Wissensbasis:
62
KB
Log
isch
e P
rog
ram
mie
run
gVeränderung der WissensbasisVeränderung der Wissensbasis
% zurueckgebenzurueckgeben(Sig) :- retract(ausleihe(LNr, Sig, datum(T,M,J))).
% ausleihenausleihen(LNr, Sig, Tag, Monat, Jahr) :- assertz(ausleihe(LNr, Sig, datum(Tag,Monat,Jahr)))
63
KB
Log
isch
e P
rog
ram
mie
run
gLaden und SpeichernLaden und Speichern
consult(+Dateiname)liest die Fakten und Regeln der Datei ein und ergänzt die aktuelle Wissensbasis
listinglistet alle Klauseln auf
listing(+Prädikat)listet alle Fakten zum betreffenden Prädikat auf
tell(+Dateiname)legt das Ausgabemedium fest
toldschließt das aktuelle Ausgabemedium
Prädikate zur Verwaltung der Wissensbasis:Prädikate zur Verwaltung der Wissensbasis:
64
KB
Log
isch
e P
rog
ram
mie
run
gLaden und SpeichernLaden und Speichern
% Bibliotheksdaten laden:- consult('BibliothekDaten.pl').
% Bibliotheksdaten speichernspeichern :- tell('BibliothekDaten.pl'), listing(leser), listing(buch), listing(ausleihe), told.
65
KB
Log
isch
e P
rog
ram
mie
run
gTeil 4Teil 4
Listenverarbeitung
66
KB
Log
isch
e P
rog
ram
mie
run
g
Petra Schmitt [email protected]
Walter Meier [email protected], [email protected]
Sandra Roth [email protected], [email protected],[email protected]
...
email-Adressbuchemail-Adressbuch
67
KB
Log
isch
e P
rog
ram
mie
run
g
Miniwelt: Adressbuch
Petra Schmitt [email protected]
Walter Meier [email protected], [email protected]
Sandra Roth [email protected], [email protected], [email protected]
...
Beschreibung der Miniwelt
email(petraSchmitt, [ '[email protected]' ] ).
email(walterMeier, [ '[email protected]', '[email protected]' ] ).
email(sandraRoth, [ '[email protected]', 'sandra@roth', '[email protected]' ] ).
...
% addemail(...).
% delemail(...).
...
Email-AdressbuchEmail-Adressbuch
68
KB
Log
isch
e P
rog
ram
mie
run
g
Beispiele:
[ '[email protected]', '[email protected]', '[email protected]' ]
...
ListenListen
Eine Liste ist eine geordnete Folge von Elementen beliebiger Länge. Die Elemente der Liste können beliebige Terme sein: Konstanten, Zahlen, Variablen, Strukturen und auch wieder Listen. Die Listenelemente können dabei unterschiedliche Datentypen aufweisen.
Eine Liste ist eine geordnete Folge von Elementen beliebiger Länge. Die Elemente der Liste können beliebige Terme sein: Konstanten, Zahlen, Variablen, Strukturen und auch wieder Listen. Die Listenelemente können dabei unterschiedliche Datentypen aufweisen.
69
KB
Log
isch
e P
rog
ram
mie
run
g
Beispiel: . (a, . (b, . (c, []))) [a, b, c]
. (c, []) [c]
. (b, [c]) [b, c]
. (a, [b, c]) [a, b, c]
ListenkonstruktorenListenkonstruktoren
Alle Listen können mit Hilfe der beiden Konstruktoren
[] („leere Liste“) und . („Einfügoperator“)
aufgebaut werden.
Alle Listen können mit Hilfe der beiden Konstruktoren
[] („leere Liste“) und . („Einfügoperator“)
aufgebaut werden.
Struktur: .(Element, Liste) NeueListeStruktur: .(Element, Liste) NeueListe
70
KB
Log
isch
e P
rog
ram
mie
run
g
Beispiele:
[K | R] = [a, b, c] K = a, R = [b, c]
[K | R] = [5] K = 5, R = []
[K | R] = [[1], [3]] K = [1], R = [[3]]
[E1, E2 | R] = [a, b, c] E1 = a, E2 = b, R = [c]
[E1, E2 | R] = [a] Unifikation nicht möglich
...
Unifikation bei ListenUnifikation bei Listen
Jede Liste lässt sich in der Form [Kopfelement | Restliste] darstellen. Jede Liste lässt sich in der Form [Kopfelement | Restliste] darstellen.
71
KB
Log
isch
e P
rog
ram
mie
run
g
Es soll ein Prolog-Programm entwickelt werden, mit dessen Hilfe ein Element in eine Liste eingefügt werden kann.
Semantik:add1(E, AlteListe, NeueListe) gilt in der Modellwelt, wenn NeueListe = [E | AlteListe].
Beispiel: add1(a, [b, c, d], [a, b, c, d])
HinzufügenHinzufügen
Aufgabe:Aufgabe:
Spezifikation: add1/3Spezifikation: add1/3
72
KB
Log
isch
e P
rog
ram
mie
run
g
Programm (Version1: mit Regel):
add1(E, AlteListe, NeueListe) :- NeueListe = [E | AlteListe].
HinzufügenHinzufügen
Programm (Version2: mit Faktum):
add1(E, AlteListe, [E | AlteListe]).
Semantik:add1(E, AlteListe, NeueListe) gilt in der Modellwelt, wenn NeueListe = [E | AlteListe].
Beispiel: add1(a, [b, c, d], [a, b, c, d])
Spezifikation: add1/3Spezifikation: add1/3
73
KB
Log
isch
e P
rog
ram
mie
run
g
Programmtest:
?- add1(a, [b, c, d], L).
L = [a, b, c, d] ;
No
?- add1(b, [b, c, d], L).
L = [b, b, c, d] ;
No
?- add1(c, [b, c, d], L).
L = [c, b, c, d] ;
No
Programm (Version1: mit Regel):
add1(E, AlteListe, NeueListe) :- NeueListe = [E | AlteListe].
HinzufügenHinzufügen
Programm (Version2: mit Faktum):
add1(E, AlteListe, [E | AlteListe]).
74
KB
Log
isch
e P
rog
ram
mie
run
g
Es soll ein Prolog-Programm entwickelt werden, mit dessen Hilfe ein Element in eine Liste eingefügt werden kann, die das Element eventuell bereits enthält.
Semantik:
add2(E, AlteListe, NeueListe) gilt in der Modellwelt, wenn entweder AlteListe E bereits enthält und dann NeueListe = AlteListe gilt, oder wenn AlteListe E nicht enthält und NeueListe sowohl E als auch alle Elemente von AlteListe enthält.
HinzufügenHinzufügen
Aufgabe:Aufgabe:
Spezifikation: add2/3Spezifikation: add2/3
75
KB
Log
isch
e P
rog
ram
mie
run
g
% Einfügen in eine leere Liste:add2(E, [], [E]).
% Einfügen in eine nichtleere Liste, deren erstes Element dem einzufügenden entspricht:add2(E, [E|X], [E|X]).
% Einfügen in eine nichtleere Liste, deren erstes Element dem einzufügenden nicht entspricht:add2(E, [A|X], L) :- ???
HinzufügenHinzufügen
Fallunterscheidung gemäß der Struktur der Liste, in die das neue Element eingefügt werden soll:Fallunterscheidung gemäß der Struktur der Liste, in die das neue Element eingefügt werden soll:
76
KB
Log
isch
e P
rog
ram
mie
run
gRekursive ProblemreduktionRekursive Problemreduktion
E eingefügt in [A|X] ergibt [A|M], wenn E \= A und wenn E eingefügt in X die Liste M ergibt.
% Einfügen in eine nichtleere Liste, deren erstes Element dem einzufügenden nicht entspricht:
add2(E, [A|X], L) :- ???
Rekursives Problemreduktion: Rekursives Problemreduktion:
% Einfügen in eine nichtleere Liste, deren erstes Element dem einzufügenden nicht entspricht:
add2(E, [A|X], [A|M]) :- E \= A, add2(E, X, M).
77
KB
Log
isch
e P
rog
ram
mie
run
g
Anfrage:
?- add(a, [b, c], L).
Wissensbasis (mit rekursiver Problemreduktion):
/* 1 */ add2(E, [], [E])./* 2 */ add2(E, [E|X], [E|X]). /* 3 */ add2(E, [A|X], [A|M]) :- E \= A, add2(E, X, M).
Auswertung einer AnfrageAuswertung einer Anfrage
Substitution
E0 = a, A0 = b, X0 = [c], L = [A0|M0].
E1 = a, A1 = c, X1 = [], M0 = [A1|M1]
E2 = a, M1 = [E2]
Ziel
?- add2(a, [b, c], L).
?- add2(a, [c], M0).
?- add2(a, [], M1).
Regel
3
3
1
Ergebnis:
?- L = [A0|M0] = [b|[A1|M1]] = [b|[c|[E2]]] = [b|[c|[a]]] = [b, c, a]
78
KB
Log
isch
e P
rog
ram
mie
run
g
Anfrage:
?- add(a, [b, c], L).
Wissensbasis (mit rekursiver Problemreduktion):
/* 1 */ add2(E, [], [E])./* 2 */ add2(E, [E|X], [E|X]). /* 3 */ add2(E, [A|X], [A|M]) :- E \= A, add2(E, X, M).
Deklaratives Denken Deklaratives Denken
Substitution
E0 = a, A0 = b, X0 = [c], L = [A0|M0].
E1 = a, A1 = c, X1 = [], M0 = [A1|M1]
E2 = a, M1 = [E2]
Ziel
?- add2(a, [b, c], L).
?- add2(a, [c], M0).
?- add2(a, [], M1).
Regel
3
3
1
Wird von der Inferenzmaschine geleistet
Muss vom Entwickler geleistet werden
Man beschreibt nicht Schritt für Schritt einen Einfügevorgang, sondern man beschreibt das Ergebnis eines Einfügevorgangs.
Man beschreibt nicht Schritt für Schritt einen Einfügevorgang, sondern man beschreibt das Ergebnis eines Einfügevorgangs.
79
KB
Log
isch
e P
rog
ram
mie
run
g
Es soll ein Prolog-Programm entwickelt werden, mit dessen Hilfe ein Element aus einer Liste gelöscht werden kann.
Semantik:
del(E, AlteListe, NeueListe) gilt in der Modellwelt, wenn entweder AlteListe E nicht enthält und dann NeueListe = AlteListe gilt, oder wenn AlteListe E enthält und NeueListe aus AlteListe durch Entfernen von E entsteht.
LöschenLöschen
Aufgabe:Aufgabe:
Spezifikation: del/3Spezifikation: del/3
80
KB
Log
isch
e P
rog
ram
mie
run
gÜbungenÜbungen
Aufgabe 6: ListenverarbeitungAufgabe 6: Listenverarbeitung
Entwerfen Sie zunächst eine Fallunterscheidung gemäß der Struktur der Liste, aus der das Element gelöscht werden soll. Entwickeln Sie dann passende Fakten und Regeln zur Beschreibung des Ergebnisses eines Löschvorgangs.
81
KB
Log
isch
e P
rog
ram
mie
run
g
% Löschen aus einer leeren Liste:del(E, [], ).
% Löschen aus einer (nichtleeren) Liste, deren erstes Element dem zu löschenden entspricht:del(E, [E|X], ).
% Löschen aus einer (nichtleeren) Liste, deren erstes Element dem zu löschenden nicht entspricht: del(E, [A|X], ) :- E \= A, .
ÜbungenÜbungen
Aufgabe 7: ListenverarbeitungAufgabe 7: Listenverarbeitung
Ergänzen Sie die Fakten bzw. Regeln. Lösen Sie Fall 3 mit Hilfe einer rekursiven Problemreduktion
82
KB
Log
isch
e P
rog
ram
mie
run
g
Wissensbasis (mit rekursiver Problemreduktion):
del(E, [], []).
del(E, [E|X], X).
del(E, [A|X], [A|M]) :- E \= A, del(E, X, M).
LösungLösung
83
KB
Log
isch
e P
rog
ram
mie
run
gSortierenSortieren
Es soll ein Prolog-Programm entwickelt werden, mit dessen Hilfe eine Liste (bestehend aus Konstanten) sortiert werden kann.
Semantik:
inssort(AlteListe, NeueListe) gilt in der Modellwelt, wenn NeueListe aus AlteListe durch Sortieren der Elemente entsteht.
Aufgabe:Aufgabe:
Spezifikation: inssort/2Spezifikation: inssort/2
84
KB
Log
isch
e P
rog
ram
mie
run
g
Test:
?- name(hallo, L).
L = [104, 97, 108, 108, 111] ;
No
?- name(N, [104, 97, 108, 108, 111]).
N = hallo ;
No
VorbereitungVorbereitung
Bearbeitung von Atomen:Bearbeitung von Atomen:
name(?Atom, ?ASCIIListe)wandelt ein Atom in eine Liste von ASCII-Codes um und umgekehrt
85
KB
Log
isch
e P
rog
ram
mie
run
g
% ASCII-Listen vergleichenkleiner([], L) :- kleiner([K|R], [K1|R1]) :-kleiner([K|R], [K1|R1]) :-
% Atome vergleichenvor(A, B) :- name(A, LA), name(B, LB), kleiner(LA, LB).
ÜbungenÜbungen
Aufgabe 8: ListenvergleichAufgabe 8: Listenvergleich
Entwickeln Sie die Fakten bzw. Regeln, mit denen man zwei Listen mit ASCII-Codes (Zahlen) vergleichen kann. Überlegen Sie sich hierzu, in welchen Fällen eine Liste „kleiner“ ist als eine andere.
86
KB
Log
isch
e P
rog
ram
mie
run
gÜbungenÜbungen
Aufgabe 9: Einfügen in eine sortierte ListeAufgabe 9: Einfügen in eine sortierte Liste
ins(E, AlteListe, NeueListe) gilt in der Modellwelt, wenn NeueListe aus einer sortierten Liste AlteListe entsteht, indem das Element E an der „richtigen“ Stelle einsortiert wird.
87
KB
Log
isch
e P
rog
ram
mie
run
g
% ASCII-Listen vergleichenkleiner([], L) :- L \= [].kleiner([K|R], [K1|R1]) :- K < K1.kleiner([K|R], [K1|R1]) :- K = K1, kleiner(R, R1).
% Atome vergleichenvor(A, B) :- name(A, LA), name(B, LB), kleiner(LA, LB).
LösungLösung
Aufgabe 8: ListenvergleichAufgabe 8: Listenvergleich
Entwickeln Sie die Fakten bzw. Regeln, mit denen man zwei Listen mit ASCII-Codes (Zahlen) vergleichen kann. Überlegen Sie sich hierzu, in welchen Fällen eine Liste „kleiner“ ist als eine andere.
88
KB
Log
isch
e P
rog
ram
mie
run
g
% Einfügenins(E, [], [E]).ins(E, [E|R], [E | [E |R]]).ins(E, [K|R], [E | [K |R]]) :- vor(E, K).ins(E, [K|R], [K|M]) :- vor(K, E), ins(E, R, M).
LösungLösung
Aufgabe 9: Einfügen in eine sortierte ListeAufgabe 9: Einfügen in eine sortierte Liste
ins(E, AlteListe, NeueListe) gilt in der Modellwelt, wenn NeueListe aus einer sortierten Liste AlteListe entsteht, indem das Element E an der „richtigen“ Stelle einsortiert wird.
89
KB
Log
isch
e P
rog
ram
mie
run
g
% Sortieren durch Einfügeninssort([], []).inssort([K|R], L) :- inssort(R, M), ins(K, M, L).
ÜbungenÜbungen
Aufgabe 10: Sortieren durch EinfügenAufgabe 10: Sortieren durch Einfügen
Erklären Sie die aufgelisteten Fakten und Regeln. Erklären Sie insbesondere auch die rekursive Problemreduktion.
%Test?- inssort([kain, abel, eva, adam], L).
L = [abel, adam, eva, kain] ;
No
90
KB
Log
isch
e P
rog
ram
mie
run
g
% ASCII-Listen vergleichenkleiner([], L) :- L \= [].kleiner([K|R], [K1|R1]) :- K < K1.kleiner([K|R], [K1|R1]) :- K = K1, kleiner(R, R1).
% Atome vergleichenvor(A, B) :- name(A, LA), name(B, LB), kleiner(LA, LB).
% Einfügenins(E, [], [E]).ins(E, [E|R], [E | [E |R]]).ins(E, [K|R], [E | [K |R]]) :- vor(E, K).ins(E, [K|R], [K|M]) :- vor(K, E), ins(E, R, M).
% Sortieren durch Einfügeninssort([], []).inssort([K|R], L) :- inssort(R, M), ins(K, M, L).
SortierprogrammSortierprogramm
91
KB
Log
isch
e P
rog
ram
mie
run
gTeil 4Teil 4
Anwendung: Formale Sprachen
92
KB
Log
isch
e P
rog
ram
mie
run
g
S aSBC
S aBC
CB BC
aB ab
bB bb
bC bc
cC cc
Parser
aabbcc
yes
WortproblemWortproblem
93
KB
Log
isch
e P
rog
ram
mie
run
g
S aSBC
S aBC
CB BC
aB ab
bB bb
bC bc
cC cc
aabbcc
yes
WorterzeugungWorterzeugung
S aSBC aaBCBC aaBBCC aabBCC aabbCC aabbcC aabbcc
94
KB
Log
isch
e P
rog
ram
mie
run
gRepräsentation der GrammatikRepräsentation der Grammatik
startsymbol([vS]).produktion([vS], [a,vS,vB,vC]).produktion([vS], [a,vB,vC]).produktion([vC,vB], [vB,vC]).produktion([a,vB], [a,b]).produktion([b,vB], [b,b]).produktion([b,vC], [b,c]).produktion([c,vC], [c,c]).
S aSBC
S aBC
CB BC
aB ab
bB bb
bC bc
cC cc
95
KB
Log
isch
e P
rog
ram
mie
run
gAbleitungsschrittAbleitungsschritt
S aSBC aaB(CB)C aaB(BC)C aabBCC aabbCC aabbcC aabbcc
CB BC
ableitungsschritt(AltesWort, NeuesWort) gilt in der Modellwelt, wenn NeuesWort aus AltesWort entsteht, indem ein Teilwort mit Hilfe einer Produktion ersetzt wird. Z. B.:
ableitungsschritt([a,a,vB,vC,vB,vC], [a,a,vB,vB,vC,vC])
Spezifikation: ableitungsschritt/2Spezifikation: ableitungsschritt/2
96
KB
Log
isch
e P
rog
ram
mie
run
gAbleitungsschrittAbleitungsschritt
S aSBC aaB(CB)C aaB(BC)C aabBCC aabbCC aabbcC aabbcc
CB BC
ableitungsschritt(AltesWort, NeuesWort) :- produktion(L,R), append(L,RestWort,AltesWort), append(R,RestWort,NeuesWort).
ableitungsschritt([B|AltesWort], [B|NeuesWort]) :- ableitungsschritt(AltesWort, NeuesWort).
97
KB
Log
isch
e P
rog
ram
mie
run
gAbleitungsketteAbleitungskette
S aSBC aaBCBC aaBBCC aabBCC aabbCC aabbcC aabbcc
ableitungskette(NeuesWort, AltesWort) gilt in der Modellwelt, wenn NeuesWort sich aus AltesWort mit Hilfe von Ableitungsschritten erzeugen lässt. Z. B.:
ableitungskette([a,a,b,b,c,c], [vS])
Spezifikation: ableitungskette/2Spezifikation: ableitungskette/2
98
KB
Log
isch
e P
rog
ram
mie
run
gSuche im AbleitungsbaumSuche im Ableitungsbaum
aabbcc
aaBbcc
aabbCC
aabBcc aabbCc aabbcC
aabBCC
aaBBCC
aaBCBC
aSBC
S
aaBbcc
aaBbCc
... ...
99
KB
Log
isch
e P
rog
ram
mie
run
gAbleitungsketteAbleitungskette
S aSBC aaBCBC aaBBCC aabBCC aabbCC aabbcC aabbcc
ableitungskette(NeuesWort, AltesWort) :- NeuesWort = AltesWort.
ableitungskette(NeuesWort, AltesWort) :- ableitungsschritt(ZwischenWort, NeuesWort), ableitungskette(ZwischenWort, AltesWort).
100
KB
Log
isch
e P
rog
ram
mie
run
gAbleitungAbleitung
S aSBC aaBCBC aaBBCC aabBCC aabbCC aabbcC aabbcc
ableitung(Wort) :- ableitungskette(Wort, S), startsymbol(S).
101
KB
Log
isch
e P
rog
ram
mie
run
gAusgabe der Ableitungskette Ausgabe der Ableitungskette
ableitungsschritt(AltesWort, L, R, NeuesWort) :- produktion(L,R), append(L,B,AltesWort), append(R,B,NeuesWort).
ableitungsschritt([E|AltesWort], L, R, [E|NeuesWort]) :- ableitungsschritt(AltesWort, L, R, NeuesWort).
ableitungskette(NeuesWort, AltesWort,[]) :- AltesWort = NeuesWort.
ableitungskette(NeuesWort, AltesWort, [regel(L,R), ZwischenWort |A]) :- ableitungsschritt(ZwischenWort, L, R, NeuesWort), ableitungskette(ZwischenWort, AltesWort, A.
ableitung(Wort) :- ableitungskette(Wort, S, A), startsymbol(S), write(A).
102
KB
Log
isch
e P
rog
ram
mie
run
gAusgabe der Ableitungskette Ausgabe der Ableitungskette
?- ableitung([a, a,b, b, c, c]).
[
regel([c, vC], [c, c]), [a, a, b, b, c, vC],
regel([b, vC], [b, c]), [a, a, b, b, vC, vC],
regel([b, vB], [b, b]), [a, a, b, vB, vC, vC],
regel([a, vB], [a, b]), [a, a, vB, vB, vC, vC],
regel([vC, vB], [vB, vC]), [a, a, vB, vC, vB, vC],
regel([vS], [a, vB, vC]), [a, vS, vB, vC],
regel([vS], [a, vS, vB, vC]), [vS]
]
Yes
103
KB
Log
isch
e P
rog
ram
mie
run
gAusgabe aller Ableitungsversuche Ausgabe aller Ableitungsversuche
ableitungsschritt(AltesWort, L, R, NeuesWort) :- produktion(L,R), append(L,B,AltesWort), append(R,B,NeuesWort).
ableitungsschritt([E|AltesWort], L, R, [E|NeuesWort]) :- ableitungsschritt(AltesWort, L, R, NeuesWort).
ableitungskette(NeuesWort, AltesWort,[]) :- AltesWort = NeuesWort.
ableitungskette(NeuesWort, AltesWort, [regel(L,R), ZwischenWort |A]) :- ableitungsschritt(ZwischenWort, L, R, NeuesWort), ableitungskette(ZwischenWort, AltesWort, A, write([regel(L,R), ZwischenWort |A]), nl.
ableitung(Wort) :- ableitungskette(Wort, S, _), startsymbol(S).
104
KB
Log
isch
e P
rog
ram
mie
run
g
105
KB
Log
isch
e P
rog
ram
mie
run
gTeil 5Teil 5
Anwendung: While-Interpreter
106
KB
Log
isch
e P
rog
ram
mie
run
g
BEGINp := 1;WHILE u > 0 DO BEGIN IF u mod 2 = 1 THEN BEGIN u := u – 1; p := p * b; END; u := u div 2; b := b* b; ENDEND
Interpreter
{b: 2; u: 5}
{b: 256; u: 0; p: 32}
While-InterpreterWhile-Interpreter
107
KB
Log
isch
e P
rog
ram
mie
run
g BEGINp := 1;WHILE u > 0 DO BEGIN IF u mod 2 = 1 THEN BEGIN u := u – 1; p := p * b; END; u := u div 2; b := b* b; ENDEND
Wertzuweisung
Wiederholung
Fallunterscheidung
Sequenzbildung
While-ProgrammeWhile-Programme
108
KB
Log
isch
e P
rog
ram
mie
run
g
ausfuehren(+Programm, +Ausgangszustand, -Endzustand)
BEGINp := 1;WHILE u > 0 DO BEGIN IF u mod 2 = 1 THEN BEGIN u := u – 1; p := p * b; END; u := u div 2; b := b* b; ENDEND
Interpreter
Ausgangs-zustand {b: 2; u: 5}
{b: 256; u: 0; p: 32}End-zustand
While-Programm
Interpreter-PrädikatInterpreter-Prädikat
109
KB
Log
isch
e P
rog
ram
mie
run
g BEGINz := x;x := y;y := zEND
Interpreter
Ausgangs-zustand {x: 2; y: 5}
{x: 5; y: 2; z: 5}End-zustand
Zuweisungs-programm
Wir betrachten zunächst nur sehr einfache Programme:
Sequenzen von Zuweisungen vom Typ <Var> := <Var>.
ProblemvereinfachungProblemvereinfachung
110
KB
Log
isch
e P
rog
ram
mie
run
g
Repräsentation von Variablenzuständen:
[wert(x, 2), wert(y, 5)] % Ausgangszustand
[wert(x, 5), wert(y, 2), wert(z, 5)] % Endzustand
Liste mit Termen
VariablenzuständeVariablenzustände
BEGINz := x;x := y;y := zEND
Interpreter
Ausgangs-zustand {x: 2; y: 5}
{x: 5; y: 2; z: 5}End-zustand
Zuweisungs-programm
111
KB
Log
isch
e P
rog
ram
mie
run
g
Spezifikation der Prädikate
varWert(+Variable, +Zustand, -Variablenwert)
?- varWert(y, [wert(x, 2), wert(y, 5)], W).
W = 5
VariablenzuständeVariablenzustände
BEGINz := x;x := y;y := zEND
Interpreter
Ausgangs-zustand {x: 2; y: 5}
{x: 5; y: 2; z: 5}End-zustand
Zuweisungs-programm
112
KB
Log
isch
e P
rog
ram
mie
run
g
Spezifikation der Prädikate
neuerZustand(+Variable, +Wert, +ZAlt, -ZNeu)
?- neuerZustand(y, 4, [wert(x, 2), wert(y, 5)], Z).
Z = [wert(x, 2), wert(y, 4)]
VariablenzuständeVariablenzustände
BEGINz := x;x := y;y := zEND
Interpreter
Ausgangs-zustand {x: 2; y: 5}
{x: 5; y: 2; z: 5}End-zustand
Zuweisungs-programm
113
KB
Log
isch
e P
rog
ram
mie
run
g
Spezifikation der Prädikate
neuerZustand(+Variable, +Wert, +ZAlt, -ZNeu)
?- neuerZustand(z, 2, [wert(x, 2), wert(y, 5)], Z).
Z = [wert(x, 2), wert(y, 5), wert(z, 2)]
BEGINz := x;x := y;y := zEND
Interpreter
Ausgangs-zustand {x: 2; y: 5}
{x: 5; y: 2; z: 5}End-zustand
Zuweisungs-programm
VariablenzuständeVariablenzustände
114
KB
Log
isch
e P
rog
ram
mie
run
g
Fakten und Regeln:
varWert(_, [], 'undefiniert').
varWert(V, [wert(V, W) | _R], W).
varWert(V, [wert(X, _W) | R], W) :- V \= X, varWert(V, R, W).
Problemreduktionen:
varWert(u, [], 'undefiniert').
varWert(x, [wert(x, W) | _R], W).
varWert(y, [wert(x, 2) | R], W) :- varWert(x, R, W).
VariablenzuständeVariablenzustände
115
KB
Log
isch
e P
rog
ram
mie
run
g
Fakten und Regeln:
neuerZustand(V, W, [], [wert(V, W)]).
neuerZustand(V, W, [wert(V, _) | R], [wert(V, W) | R]).
neuerZustand(V, W, [wert(X, WAlt) | R], [wert(X, WAlt) | RNeu]) :-
V \= X, neuerZustand(V, W, R, RNeu).
Problemreduktionen:
neuerZustand(z, 2, [], [wert(z, 2)]).
neuerZustand(y, 4, [wert(y, 5) | R], [wert(y, 4) | R]).
neuerZustand(y, 4, [wert(x, 2) | R], [wert(x, 2) | RNeu]) :-neuerZustand(y, 4, R, RNeu).
VariablenzuständeVariablenzustände
116
KB
Log
isch
e P
rog
ram
mie
run
g
Repräsentation von primitiven Zuweisungsprogrammen:
[let(z, x), let(x, y), let(y, z)] % Zuweisungssequenz
Liste mit Termen
ZuweisungsinterpreterZuweisungsinterpreter
BEGINz := x;x := y;y := zEND
Interpreter
Ausgangs-zustand {x: 2; y: 5}
{x: 5; y: 2; z: 5}End-zustand
Zuweisungs-programm
117
KB
Log
isch
e P
rog
ram
mie
run
g
Spezifikation der Prädikate
ausfuehren(+Programm, +ZAlt, -ZNeu)
?- ausfuehren([let(z,x), let(x,y), let(y,z)], [wert(x,2), wert(y,5)], Z).
Z = [wert(x,5), wert(y,2), wert(z,2)]
ZuweisungsinterpreterZuweisungsinterpreter
BEGINz := x;x := y;y := zEND
Interpreter
Ausgangs-zustand {x: 2; y: 5}
{x: 5; y: 2; z: 5}End-zustand
Zuweisungs-programm
118
KB
Log
isch
e P
rog
ram
mie
run
g
Fakten und Regeln:
% Zuweisung ausführen
ausfuehren(let(X, Y), ZAlt, ZNeu) :- varWert(Y, ZAlt, W), neuerZustand(X, W, ZAlt, ZNeu).
% Sequenz ausführen
ausfuehren([], ZAlt, ZAlt).
ausfuehren([Anw | R], ZAlt, ZNeu) :- ausfuehren(Anw, ZAlt, Z), ausfuehren(R, Z, ZNeu).
ZuweisungsinterpreterZuweisungsinterpreter
119
KB
Log
isch
e P
rog
ram
mie
run
g
Testprogramm:
testprogramm1 :- ausfuehren([let(z, x), let(x, y), let(y, z)], [wert(x,2), wert(y,5)], Z), write(Z).
Programmtest:
?- testprogramm1.
[wert(x, 5), wert(y, 2), wert(z, 2)]
ZuweisungsinterpreterZuweisungsinterpreter
120
KB
Log
isch
e P
rog
ram
mie
run
g
Spezifikation der Prädikate
termWert(+Term, +Zustand, -Wert)
?- termWert(x-y, [wert(x, 2), wert(y, 5)], W).
W = -3
TerminterpreterTerminterpreter
Interpreter
Ausgangs-zustand
End-zustand
Zuweisungs-programm
BEGINx := x-y;y := x+y;x := y-xEND
{x: 2; y: 5}
{x: 5; y: 2}
121
KB
Log
isch
e P
rog
ram
mie
run
g
Fakten und Regeln:
termWert(V, _Z, V) :- integer(V).
termWert(V, Z, W) :- atom(V), varWert(V, Z, W).
termWert(T1 + T2, Z, W) :- termWert(T1, Z, W1), termWert(T2, Z, W2), W is W1+W2.
...
termWert(-T, Z, W) :- termWert(T, Z, W1), W is -W1.
TerminterpreterTerminterpreter
122
KB
Log
isch
e P
rog
ram
mie
run
g
Fakten und Regeln:
% Zuweisung ausführen
ausfuehren(let(X, T), ZAlt, ZNeu) :- termWert(T, ZAlt, W), neuerZustand(X, W, ZAlt, ZNeu).
% Sequenz ausführen
ausfuehren([], ZAlt, ZAlt).
ausfuehren([Anw | R], ZAlt, ZNeu) :- ausfuehren(Anw, ZAlt, Z), ausfuehren(R, Z, ZNeu).
TerminterpreterTerminterpreter
123
KB
Log
isch
e P
rog
ram
mie
run
g
Testprogramm:
testprogramm2 :- ausfuehren([let(x, x-y), let(y, x+y), let(x, y-x)], [wert(x,2), wert(y,5)], Z), write(Z).
Programmtest:
?- testprogramm2.
[wert(x, 5), wert(y, 2)]
TerminterpreterTerminterpreter
124
KB
Log
isch
e P
rog
ram
mie
run
g
Spezifikation der Prädikate
ausfuehren(+Programm, +ZAlt, -ZNeu)
?- ausfuehren( if(x > y, let(betrag, x-y), let(betrag, y-x)),[wert(x,2), wert(y,5)], Z ).
Z = [wert(x, 2), wert(y, 5), wert(betrag, 3)]
AnweisungsinterpreterAnweisungsinterpreter
Interpreter
Ausgangs-zustand
End-zustand
Programm
IF x > y THEN betrag := x – yELSE betrag := y – x
{x: 2; y: 5}
{x: 5; y: 2; betrag: 3}
125
KB
Log
isch
e P
rog
ram
mie
run
gAnweisungsinterpreterAnweisungsinterpreter
Interpreter
Ausgangs-zustand
End-zustand
Programm
WHILE n > 0 DO BEGIN p := p*b; n := n-1 END
{b: 2; n: 3, p: 1}
{b: 2; n: 3, p: 8}
Spezifikation der Prädikate
ausfuehren(+Programm, +ZAlt, -ZNeu)
?- ausfuehren( while(n > 0, [let(p, p*b), let(n, n-1)]), [wert(b,2), wert(n,3), wert(p,1)], Z ).
Z = [wert(b, 2), wert(n, 0), wert(p, 8)]
126
KB
Log
isch
e P
rog
ram
mie
run
gAnweisungsinterpreterAnweisungsinterpreter
Interpreter
Ausgangs-zustand
End-zustand
Programm
IF x > y THEN betrag := x – yELSE betrag := y – x
{x: 2; y: 5}
{x: 5; y: 2; betrag: 3}
Spezifikation der Prädikate
booleWert(+Term, +Zustand)
?- booleWert(x > y, [wert(x, 2), wert(y, 5)]).
No
127
KB
Log
isch
e P
rog
ram
mie
run
g
booleWert(T1 = T2, Z) :- termWert(T1, Z, W1), termWert(T2, Z, W2), W1 =:= W2.
booleWert(T1 =\= T2, Z) :- termWert(T1, Z, W1), termWert(T2, Z, W2), W1 =\= W2.
booleWert(T1 < T2, Z) :- termWert(T1, Z, W1), termWert(T2, Z, W2), W1 < W2.
booleWert(T1 > T2, Z) :- termWert(T1, Z, W1), termWert(T2, Z, W2), W1 > W2.
booleWert(T1 =< T2, Z) :- termWert(T1, Z, W1), termWert(T2, Z, W2), W1 =< W2.
booleWert(T1 >= T2, Z) :- termWert(T1, Z, W1), termWert(T2, Z, W2), W1 >= W2.
AnweisungsinterpreterAnweisungsinterpreter
128
KB
Log
isch
e P
rog
ram
mie
run
g
ausfuehren(let(X, T), ZAlt, ZNeu) :- termWert(T, ZAlt, W), neuerZustand(X, W, ZAlt, ZNeu).
ausfuehren([], ZAlt, ZAlt).ausfuehren([Anw | R], ZAlt, ZNeu) :- ausfuehren(Anw, ZAlt, Z), ausfuehren(R, Z, ZNeu).
ausfuehren(if(Bed, Anw1, _Anw2), ZAlt, ZNeu) :- booleWert(Bed, ZAlt), ausfuehren(Anw1, ZAlt, ZNeu).ausfuehren(if(Bed, _Anw1, Anw2), ZAlt, ZNeu) :- not(booleWert(Bed, ZAlt)), ausfuehren(Anw2, ZAlt, ZNeu).
ausfuehren(while(Bed, Anw), ZAlt, ZNeu) :- booleWert(Bed, ZAlt), ausfuehren(Anw, ZAlt, Z), ausfuehren(while(Bed, Anw), Z, ZNeu).ausfuehren(while(Bed, _Anw), ZAlt, ZAlt) :- not(booleWert(Bed, ZAlt)).
AnweisungsinterpreterAnweisungsinterpreter
129
KB
Log
isch
e P
rog
ram
mie
run
g
Testprogramm:
testprogramm5 :- ausfuehren( [let(p,1), while(u > 0, [if(u:2 = 1, [let(u, u-1), ... % siehe oben [wert(b,2), wert(u,5)], Z), write(Z).
Programmtest:
?- testprogramm5.
[wert(b, 256), wert(u, 0), wert(p, 32)]
AnweisungsinterpreterAnweisungsinterpreter
130
KB
Log
isch
e P
rog
ram
mie
run
gLiteraturhinweiseLiteraturhinweise
Uwe Schöning: Logik für Informatiker. BI-Wissenschaftsverlag 1987.
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. http://informatikag.bildung-rp.de/assets/download/Prolog.pps
Herbert Drumm u. Hermann Stimm: Wissensverarbeitung mit PROLOG – Ein Einstieg in die Algorithmik. Handreichung zum Lehrplan Informatik 1995.