130
Programmieren mit Programmieren mit Prädikatenlogik Prädikatenlogik Klaus Becker 2004

Programmieren mit Prädikatenlogik Klaus Becker 2004

Embed Size (px)

Citation preview

Page 1: Programmieren mit Prädikatenlogik Klaus Becker 2004

Programmieren mit Programmieren mit PrädikatenlogikPrädikatenlogik

Klaus Becker2004

Page 2: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 3: Programmieren mit Prädikatenlogik Klaus Becker 2004

3

KB

Log

isch

e P

rog

ram

mie

run

gTeil 1Teil 1

Fakten und Regeln

Page 4: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 5: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 6: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 7: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 8: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 9: Programmieren mit Prädikatenlogik Klaus Becker 2004

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)

Page 10: Programmieren mit Prädikatenlogik Klaus Becker 2004

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)

Page 11: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 12: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 13: Programmieren mit Prädikatenlogik Klaus Becker 2004

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.

Page 14: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 15: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 16: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 17: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 18: Programmieren mit Prädikatenlogik Klaus Becker 2004

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?

Page 19: Programmieren mit Prädikatenlogik Klaus Becker 2004

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.

Page 20: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 21: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 22: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 23: Programmieren mit Prädikatenlogik Klaus Becker 2004

23

KB

Log

isch

e P

rog

ram

mie

run

gSWI-Prolog-EditorSWI-Prolog-Editor

Wissensbasis

Anfrage

Page 24: Programmieren mit Prädikatenlogik Klaus Becker 2004

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.

Page 25: Programmieren mit Prädikatenlogik Klaus Becker 2004

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.

Page 26: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 27: Programmieren mit Prädikatenlogik Klaus Becker 2004

27

KB

Log

isch

e P

rog

ram

mie

run

gTeil 2Teil 2

Das Berechnungskonzept

Page 28: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 29: Programmieren mit Prädikatenlogik Klaus Becker 2004

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?

Page 30: Programmieren mit Prädikatenlogik Klaus Becker 2004

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.

Page 31: Programmieren mit Prädikatenlogik Klaus Becker 2004

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.

Page 32: Programmieren mit Prädikatenlogik Klaus Becker 2004

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.

Page 33: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 34: Programmieren mit Prädikatenlogik Klaus Becker 2004

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.

Page 35: Programmieren mit Prädikatenlogik Klaus Becker 2004

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.

Page 36: Programmieren mit Prädikatenlogik Klaus Becker 2004

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.

Page 37: Programmieren mit Prädikatenlogik Klaus Becker 2004

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)

Page 38: Programmieren mit Prädikatenlogik Klaus Becker 2004

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.

Page 39: Programmieren mit Prädikatenlogik Klaus Becker 2004

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.

Page 40: Programmieren mit Prädikatenlogik Klaus Becker 2004

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.

Page 41: Programmieren mit Prädikatenlogik Klaus Becker 2004

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.

Page 42: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 43: Programmieren mit Prädikatenlogik Klaus Becker 2004

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.

Page 44: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 45: Programmieren mit Prädikatenlogik Klaus Becker 2004

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.

Page 46: Programmieren mit Prädikatenlogik Klaus Becker 2004

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.

Page 47: Programmieren mit Prädikatenlogik Klaus Becker 2004

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.

Page 48: Programmieren mit Prädikatenlogik Klaus Becker 2004

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.

Page 49: Programmieren mit Prädikatenlogik Klaus Becker 2004

49

KB

Log

isch

e P

rog

ram

mie

run

gTeil 3Teil 3

Anwendung: Datenbanken

Page 50: Programmieren mit Prädikatenlogik Klaus Becker 2004

50

KB

Log

isch

e P

rog

ram

mie

run

gEine einfache BibliotheksweltEine einfache Bibliothekswelt

Page 51: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 52: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 53: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 54: Programmieren mit Prädikatenlogik Klaus Becker 2004

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' ;

...

Page 55: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 56: Programmieren mit Prädikatenlogik Klaus Becker 2004

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.

Page 57: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 58: Programmieren mit Prädikatenlogik Klaus Becker 2004

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.

Page 59: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 60: Programmieren mit Prädikatenlogik Klaus Becker 2004

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.

Page 61: Programmieren mit Prädikatenlogik Klaus Becker 2004

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:

Page 62: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 63: Programmieren mit Prädikatenlogik Klaus Becker 2004

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:

Page 64: Programmieren mit Prädikatenlogik Klaus Becker 2004

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.

Page 65: Programmieren mit Prädikatenlogik Klaus Becker 2004

65

KB

Log

isch

e P

rog

ram

mie

run

gTeil 4Teil 4

Listenverarbeitung

Page 66: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 67: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 68: Programmieren mit Prädikatenlogik Klaus Becker 2004

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.

Page 69: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 70: Programmieren mit Prädikatenlogik Klaus Becker 2004

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.

Page 71: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 72: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 73: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 74: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 75: Programmieren mit Prädikatenlogik Klaus Becker 2004

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:

Page 76: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 77: Programmieren mit Prädikatenlogik Klaus Becker 2004

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]

Page 78: Programmieren mit Prädikatenlogik Klaus Becker 2004

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.

Page 79: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 80: Programmieren mit Prädikatenlogik Klaus Becker 2004

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.

Page 81: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 82: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 83: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 84: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 85: Programmieren mit Prädikatenlogik Klaus Becker 2004

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.

Page 86: Programmieren mit Prädikatenlogik Klaus Becker 2004

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.

Page 87: Programmieren mit Prädikatenlogik Klaus Becker 2004

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.

Page 88: Programmieren mit Prädikatenlogik Klaus Becker 2004

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.

Page 89: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 90: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 91: Programmieren mit Prädikatenlogik Klaus Becker 2004

91

KB

Log

isch

e P

rog

ram

mie

run

gTeil 4Teil 4

Anwendung: Formale Sprachen

Page 92: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 93: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 94: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 95: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 96: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 97: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 98: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

... ...

Page 99: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 100: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 101: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 102: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 103: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 104: Programmieren mit Prädikatenlogik Klaus Becker 2004

104

KB

Log

isch

e P

rog

ram

mie

run

g

Page 105: Programmieren mit Prädikatenlogik Klaus Becker 2004

105

KB

Log

isch

e P

rog

ram

mie

run

gTeil 5Teil 5

Anwendung: While-Interpreter

Page 106: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 107: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 108: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 109: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 110: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 111: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 112: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 113: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 114: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 115: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 116: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 117: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 118: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 119: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 120: Programmieren mit Prädikatenlogik Klaus Becker 2004

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}

Page 121: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 122: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 123: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 124: Programmieren mit Prädikatenlogik Klaus Becker 2004

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}

Page 125: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 126: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 127: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 128: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 129: Programmieren mit Prädikatenlogik Klaus Becker 2004

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

Page 130: Programmieren mit Prädikatenlogik Klaus Becker 2004

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.