Programmieren mit Prädikatenlogik Klaus Becker 2004

Programmieren mit Programmieren mit PrädikatenlogikPrädikatenlogik

Klaus Becker2004

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

gTeil 1Teil 1

Fakten und Regeln

(Heaven) Uranus = Gaea (Earth)

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

| | | | |

Cronus = Rhea Coeus = Phoebe Oceanus = Tethys

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

| | | | | | |

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

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

gModellierungsansatzModellierungsansatz

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

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

Prädikat

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

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

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.

Regelrumpf(Bedingung)

Regelkopf(Folgerung)

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)

gVon der Miniwelt zur ModellweltVon der Miniwelt zur Modellwelt

Miniwelt Modellwelt

Uranus|

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,

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

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

kind(Y, X).

Logische Herleitung

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

kind(Y, Z), vorfahr(X, Z).

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.

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

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

gAnfragen Anfragen

?- vater(W, hermes). % Wer ist Vater von Hermes?W = zeus;No.?- weiblich(Frau). % Wer ist weiblich?Frau = hera;Frau = maia;No.

Ergänzungsanfrage

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

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?

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

Kann in beiden Rollen (+ / -) verwendet

werden

Die Datenflussrichtung kann flexibel gestaltet werden. Die Datenflussrichtung kann flexibel gestaltet werden.

gLogik-ProgrammLogik-Programm

?- weiblich(Frau).

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

Wissensbasis

Anfrage

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.

?- weiblich(Frau).

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

gSWI-Prolog-EditorSWI-Prolog-Editor

Wissensbasis

Anfrage

gSWI-Prolog-EditorSWI-Prolog-Editor

Consultieren

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

eingelesen.

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.

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?

gTeil 2Teil 2

Das Berechnungskonzept

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

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?

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

?- vater(V, hermes).

?- kind(hermes, V), maennlich(V).

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.

X = V, Y = hermes.

V = maia.

?- maennlich(maia).

V = maia.

?- maennlich(maia).

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.

V = maia.

V = zeus.

?- maennlich(maia).

?- maennlich(zeus).

V = maia.

V = zeus.

?- maennlich(maia).

?- maennlich(zeus).

Ergebnis: Ist keine Zielklausel mehr vorhanden, so liefert die Substitution das gesuchte Ergebnis.

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

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.

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

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.

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)

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.

gDeklarative Semantik Deklarative Semantik

Logisches Programm (Wissensbasis + Anfrage)Logisches Programm (Wissensbasis + Anfrage)

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.

gProzedurale Semantik Prozedurale Semantik

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.

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

?- ueber(X, g).

Schalten Sie den Trace-Modus ein und verfolgen Sie die Erzeugung der Berechnungsergebnisse. Erstellen Sie auch einen Beweisbaum.

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

gGrenzen der Logik Grenzen der Logik

vorfahr(X, Z).

?- vorfahr(A, B).

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.

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.

?- vorfahr(A, B).

?- kind(B, A).

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.

?- vorfahr(A, B).

?- vorfahr(A, Z), kind(B, Z).

?- vorfahr(A, U), kind(Z, U), kind...

Die Inferenzmaschine liefert unterschiedliche Berechnungsergebnisse – die Logik-Programme haben eine unterschiedliche prozedurale Semantik.

vorfahr(X, Z).

?- vorfahr(A, B).

Beachte: Die prozedurale Semantik wird durch die Algorithmen der Inferenzmaschine festgelegt. Die Reihenfolge der Programmklauseln und Zielklauseln können hierbei eine entscheidende Rolle spielen.

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.

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.

gTeil 3Teil 3

Anwendung: Datenbanken

gEine einfache BibliotheksweltEine einfache Bibliothekswelt

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

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

Ausleihe

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

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

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

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.

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

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.

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

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.

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:

% zurueckgebenzurueckgeben(Sig) :- retract(ausleihe(LNr, Sig, datum(T,M,J))).

% ausleihenausleihen(LNr, Sig, Tag, Monat, Jahr) :- assertz(ausleihe(LNr, Sig, datum(Tag,Monat,Jahr)))

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:

gLaden und SpeichernLaden und Speichern

% Bibliotheksdaten laden:- consult('BibliothekDaten.pl').

% Bibliotheksdaten speichernspeichern :- tell('BibliothekDaten.pl'), listing(leser), listing(buch), listing(ausleihe), told.

gTeil 4Teil 4

Listenverarbeitung

Petra Schmitt pm@aol.com

Walter Meier meier@t-online.de, walter@gmx.de

Sandra Roth sroth@gmx.de, sandra@roth.de,rosa@web.de

email-Adressbuchemail-Adressbuch

Miniwelt: Adressbuch

Petra Schmitt pm@aol.com

Walter Meier meier@t-online.de, walter@gmx.de

Sandra Roth sroth@gmx.de, sandra@roth.de, rosa@web.de

email(petraSchmitt, [ 'pm@aol.com' ] ).

email(walterMeier, [ 'meier@t-online.de', 'walter@gmx.de' ] ).

email(sandraRoth, [ 'sroth@gmx.de', 'sandra@roth', 'rosa@web.de' ] ).

% addemail(...).

% delemail(...).

Email-AdressbuchEmail-Adressbuch

Beispiele:

[ 'lisa@gmx.de', 'lisa@wollenweber.de', 'lw@web.de' ]

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.

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

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.

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

Programm (Version1: mit Regel):

add1(E, AlteListe, NeueListe) :- NeueListe = [E | AlteListe].

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

Programmtest:

?- add1(a, [b, c, d], L).

L = [a, b, c, d] ;

?- add1(b, [b, c, d], L).

L = [b, b, c, d] ;

?- add1(c, [b, c, d], L).

L = [c, b, c, d] ;

Programm (Version1: mit Regel):

add1(E, AlteListe, NeueListe) :- NeueListe = [E | AlteListe].

Programm (Version2: mit Faktum):

add1(E, AlteListe, [E | AlteListe]).

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.

Aufgabe:Aufgabe:

% 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) :- ???

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:

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

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]

?- add2(a, [b, c], L).

?- add2(a, [c], M0).

?- add2(a, [], M1).

Ergebnis:

?- L = [A0|M0] = [b|[A1|M1]] = [b|[c|[E2]]] = [b|[c|[a]]] = [b, c, a]

Anfrage:

?- add(a, [b, c], L).

/* 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]

?- add2(a, [b, c], L).

?- add2(a, [c], M0).

?- add2(a, [], M1).

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.

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

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.

% 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

del(E, [], []).

del(E, [E|X], X).

del(E, [A|X], [A|M]) :- E \= A, del(E, X, M).

LösungLösung

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

?- name(hallo, L).

L = [104, 97, 108, 108, 111] ;

?- name(N, [104, 97, 108, 108, 111]).

N = hallo ;

VorbereitungVorbereitung

Bearbeitung von Atomen:Bearbeitung von Atomen:

name(?Atom, ?ASCIIListe)wandelt ein Atom in eine Liste von ASCII-Codes um und umgekehrt

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

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.

% ASCII-Listen vergleichenkleiner([], L) :- L \= [].kleiner([K|R], [K1|R1]) :- K < K1.kleiner([K|R], [K1|R1]) :- K = K1, kleiner(R, R1).

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.

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

% 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] ;

% ASCII-Listen vergleichenkleiner([], L) :- L \= [].kleiner([K|R], [K1|R1]) :- K < K1.kleiner([K|R], [K1|R1]) :- K = K1, kleiner(R, R1).

% 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

gTeil 4Teil 4

Anwendung: Formale Sprachen

S aSBC

Parser

aabbcc

WortproblemWortproblem

S aSBC

aabbcc

WorterzeugungWorterzeugung

S aSBC aaBCBC aaBBCC aabBCC aabbCC aabbcC aabbcc

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

gAbleitungsschrittAbleitungsschritt

S aSBC aaB(CB)C aaB(BC)C aabBCC aabbCC aabbcC aabbcc

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

gAbleitungsschrittAbleitungsschritt

S aSBC aaB(CB)C aaB(BC)C aabBCC aabbCC aabbcC aabbcc

ableitungsschritt(AltesWort, NeuesWort) :- produktion(L,R), append(L,RestWort,AltesWort), append(R,RestWort,NeuesWort).

ableitungsschritt([B|AltesWort], [B|NeuesWort]) :- ableitungsschritt(AltesWort, NeuesWort).

gAbleitungsketteAbleitungskette

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

gSuche im AbleitungsbaumSuche im Ableitungsbaum

aabbcc

aaBbcc

aabbCC

aabBcc aabbCc aabbcC

aabBCC

aaBBCC

aaBCBC

aaBbcc

aaBbCc

... ...

gAbleitungsketteAbleitungskette

ableitungskette(NeuesWort, AltesWort) :- NeuesWort = AltesWort.

ableitungskette(NeuesWort, AltesWort) :- ableitungsschritt(ZwischenWort, NeuesWort), ableitungskette(ZwischenWort, AltesWort).

gAbleitungAbleitung

ableitung(Wort) :- ableitungskette(Wort, S), startsymbol(S).

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

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]

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

gTeil 5Teil 5

Anwendung: While-Interpreter

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

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

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

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

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

Zuweisungs-programm

Spezifikation der Prädikate

varWert(+Variable, +Zustand, -Variablenwert)

?- varWert(y, [wert(x, 2), wert(y, 5)], W).

Interpreter

Zuweisungs-programm

neuerZustand(+Variable, +Wert, +ZAlt, -ZNeu)

?- neuerZustand(y, 4, [wert(x, 2), wert(y, 5)], Z).

Z = [wert(x, 2), wert(y, 4)]

Interpreter

Zuweisungs-programm

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

Interpreter

Zuweisungs-programm

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

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

Repräsentation von primitiven Zuweisungsprogrammen:

[let(z, x), let(x, y), let(y, z)] % Zuweisungssequenz

Liste mit Termen

ZuweisungsinterpreterZuweisungsinterpreter

Interpreter

Zuweisungs-programm

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

Interpreter

Zuweisungs-programm

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

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

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}

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.

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

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

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

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}

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

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}

booleWert(+Term, +Zustand)

?- booleWert(x > y, [wert(x, 2), wert(y, 5)]).

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.

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

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

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.

Programmieren mit Prädikatenlogik Klaus Becker 2004

Documents

Programmieren-Aufgabenkatalog · Programmieren-Aufgabenkatalog für die Lehrveranstaltungen: Programmieren I und II sowie Grundlagen und Vertiefung der Programmierung 12. Juni 2014

ABC-Listen zum Fmilienbuch rk. Lorscheid 1723-1899 · BECKER Angela 1883 Lorscheid BECKER Anna 1812 BECKER Anna +1888, Lorscheid ¥NN ... BECKER Marga. Gertrud 1866 BECKER Marga

Hochschule Mittweida (FH)Dipl.-Ing. Falk Neuner 1 Programmieren von Formularen Grafikprogrammierung Programmieren von Netzwerkkommunikation Programmieren

Programmieren mit JAVA

08.02.00GK Prolog: Prolog und Prädikatenlogik II 1 Prolog und Prädikatenlogik II Prolog Grundkurs WS 99/00 Christof Rumpf rumpf@uni-duesseldorf.de

Kapitel 4: Aussagen-, Prädikatenlogik

07.02.00GK Prolog: Prolog und Prädikatenlogik I 1 Prolog und Prädikatenlogik I Prolog Grundkurs WS 99/00 Christof Rumpf rumpf@uni-duesseldorf.de

Dipl.-Ing.Werner Becker Becker · 2018-04-18 · Automatikgetriebe feucht. Stabilisatoren stark angerostet. INGENIEURGEMEINSCHAFT BECKER, 47228 Duisburg, Hochstr. 204 ... Microsoft

Wolfgang becker

Becker, Judith

Programmieren mit Delphi2 - · PDF fileGrundlagen Delphi Susanne Kulling und Thomas Schneider 3 10.02.2005 Immanuel- Kant- Gymnasium Programmieren mit Delphi2 1. Programmieren mit

Becker Umweltdienste GmbH. Sandstr. 116. 09114 Chemnitz. 0371 9160-0. 0371 9160-111. info@becker-umweltdienste.de. info@becker-umweltdienste.de

Logik Teil 2: Prädikatenlogik Grundlagen

Becker 6021

Programmieren mit Prädikatenlogik

Entrevista Becker

Programmieren mit Go

Logik für Informatiker Wintersemester 2012/13 · Logik für Informatiker Wintersemester 2012/13 2 Prädikatenlogik In der Prädikatenlogik kann man die in der Aussagenlogik bereits

Logik Teil 2: Prädikatenlogik Grundlagen - Uni Bremen · Prädikatenlogik 2 Für viele Zwecke in der Informatik und Mathematik abstrahiert die Aussagenlogik zu stark Alle Menschen

JavaKara programmieren: Wiederholungen