LbP Grundlagen

Wiki-Quelltext dieser Seite.

<language>Prolog</language>
=== Grundlegende Ideen === 
: program = set of axioms
: computation = constructive proof of a goal statement from the program

=== Fundamentale Beiträge ===
: 1920: HILBERT und viele andere glaubten, dass alle Sätze der Mathematik aus den Axiomen der Zahlentheorie und Logik ableitbar sind. (FALSCH)
: 1940: GÖDEL, TURING lieferten Beweise der Unvollständigkeit bzw. Unentscheidbarkeit. (Beginn des modernen Computerzeitalters!)
: 1965: ROBINSON stellte das Herzstück der Logikprogrammierung bereit. --> Unifikationsalgorithmus; --> Resolutionsprinzip
: 1969: HEWITT erkannte die Möglichkeit, Kontrollstrukturen einer traditionellen PS mit den Operationen eines Logiksystems zu kombinieren.
: 1971/73: WINOGRAD / COLMERAUER entwickelten am MIT bzw. in Marseille automatische Theorembeweiser, z.T. in Fortran, und regelbasierte Systeme zur Bearbeitung natürlicher Sprache.
: 1973/79: KOWALSKI (in Edinburgh) erkannte, dass die Ausführung eines Prologprogramms als Durchführung eines Beweises interpretiert werden kann. (Prozedurale Interpretation von Horn-Klauseln)
: Mitte/Ende 1970: WARREN stellte eine sehr effiziente Implementation eines Prolog-Compilers (Prolog-10) zur Verfügung; WAM ... Warrens abstract machine

=== Standardisierungen ===
: Prolog ist nicht gleich Logikprogrammierung, sondern die populärste Programmiersprache, die die Theorie der Logik-orientierten Programmierung verwendet.
: Edinburgh Prolog
: Entwicklungen in Japan?

=== Grundbegriffe ===
: Fakten
: Anfragen
: Pattern matching
: Variable
: Term
: Unifikation
: Substitution
: konjunktive Anfragen
: Regeln
: Daten-/Wissensbasis
: HORN-Klauseln
: Modus ponens
: Prozedur
: Logikprogramm

=== Einführung mit PROLOG ===

Wir wählen einen intuitiven Zugang zur Logik-basierten Programmierung, indem wir einfache Beispiele betrachten, kommentieren und mit ihnen experimentieren. Die o.g. Begriffe werden dabei schrittweise mit Leben erfüllt. Weiter unter werden sie dann formal eingeführt und theoretisch fundiert. 

Dies gilt auch für die Grundlagen aus der Aussagen- und vor allem der Prädikatenlogik. Wir werden im Folg. von Prädikaten sprechen, den Begriff selbt (sofern nicht aus der mathematischen Grundbildung bekannt) erst weiter unten behandeln.  

=== Fakten und Anfragen ===

Die folgenden Angaben bilden die Faktenbasis, auf die wir uns im Folg. immer wieder beziehen werden.
<code id="4b8bd289a8a7c">
/* Fakten */

weiblich(christine).
weiblich(anna).
weiblich(doris).
maennlich(hans).
maennlich(gerhard).
maennlich(christian).
maennlich(martin).
</code>

Einstellige Prädikate (ohne Variablen) sind ''Fakten'', genauer: ''Eigenschaften'' von Objekten, wie z.B. "Christine ist weiblich." Da gerade die Stelligkeit dieser Prädikate für deren Verwendung von großer Bedeutung ist, gibt man diese durch einen Schrägstrich getrennt nach dem Prädikatnamen an: <tt>weiblich/1</tt>. 

Fakten kann man erfragen (''Anfrage'') und erhält erwartungsgemäß eine Bestätigung:

<run id="4b8bd289aa5b8">weiblich(christine).</run>

Gerhard ist jedoch ein Mann, so dass das Ergebnis der Anfrage <tt>false</tt> lautet:

<run id="4b8bd289ab144">weiblich(gerhard).</run>

Zweistellige Prädikate (ohne Variablen) stellen ''Beziehungen'' zwischen Objekten dar, z.B. "Die Mutter von Doris ist Anna." 
<code id="4b8bd289a9619">
mutter(doris, anna).  /* Die Mutter von Doris ist Anna. */
mutter(christian, christine).
mutter(martin, doris).

vater(doris, gerhard).
vater(christian, hans).
vater(martin, christian).
</code>

Ebensogut wäre <tt>mutter(anna, doris)</tt>, mit der Interpretation "Anna ist die Mutter von Doris.", möglich. Auch dieser Fakt kann durch Anfrage leicht bestätigt werden:

<run id="4b8bd289ab925">mutter(doris, anna).</run>

Um dem System etwas komplexere "Tatbestände" mitteilen zu können, benötigen wir Ausdrucksmittel, die über die elementare Natur von Fakten hinausgegen. 

''Aufgabe'': Erklären Sie einer Person den Begriff "Großmutter". Verwenden Sie dabei ggf. die Begriffe Mutter und Vater. Beginnen Sie zunächst mit einem konkreten Beispiel, das Sie anschließend verallgemeinern.

''Lösung'': Die Großmutter von Martin ist Christine, denn die Mutter von Christian ist Christine und der Vater von Martin ist Christian. Verallgemeinerung: Die Oma von X ist Y, wenn Y die Mutter von Z ist und Z ist der Vater von X. Dies gilt analog für die Oma mütterlicherseits: Die Oma von X ist Y, wenn Y die Mutter von Z ist und Z ist die Mutter von X.

=== Variablen und Regeln ===

Zur Formulierung sog. Regeln sind also Platzhalter, d.h. Variablen, erforderlich. Variablen erkennt man am großen Anfangsbuchstaben.

<code id="4b8bd289a9db6">
/* Regeln */

oma(X,Y) :- mutter(Z,Y), mutter(X,Z).  /* Die Oma von X ist Y. */
oma(X,Y) :- mutter(Z,Y), vater(X,Z).

/* opa(X,Z) :-   ...  */
</code>

In unserem Beispiel wird bestätigt, dass Christine Martins Großmutter ist.
<run id="4b8bd289ac4ab">oma(martin,christine).</run>

''Aufgabe'': Fügen Sie den oben angegebenen Regeln noch weitere für die Definition des Großvater-Begriffs (Prädikat <tt>opa/2</tt>) hinzu und erproben Sie sie für unser Beispiel.

Fakten und Regeln zusammen bilden die Daten- oder Wissensbasis unseres Programmiersystems. Alles was da drin steht gilt. Und alles, was in der Wissensbasis nicht vorkommt, gilt nicht. Insbesondere Letzteres ist nicht selbstverständlich. Man nennt es ''closed world assumption''. 

=== Daten-/Wissensbasis ===

Um neues Wissen in die Daten-/Wissensbasis einzubringen, gibt es zwei Möglichkeiten:
(a) explizit: Der Fakt wird in der oben verwendeten Form notiert.
(b) implizit: Es werden Regeln angegeben, die es gestatten, das Wissen aus der (so erweiterten) Wissensbasis abzuleiten. Man sagt, dass deduzierbares Wissen implizit in der Datenbasis enthalten ist. Hieraus erschließt sich ein modernes Anwendungsgebiet: Information retrieval! Regeln sind also nötig.

=== Antworten ===

Variablen sind nicht nur zur Formulierung von Regeln notwendig, sie können auch in Anfragen eingesetzt werden. Auf diese Weise können wir beispielsweise nach dem Namen von Martins Oma fragen. Das ist weit mehr, als nur den (bekannten) Namen zu verifizieren.

<run id="4b8bd289ad0a3">oma(martin,MartinsOma).</run>

Das Ergebnis überrascht uns etwas: Hätten wir nicht Christine erwartet. Ein Blick auf obige Faktenbasis zeigt, dass auch Anna Martins Großmutter ist. Offensichtlich gibt es mehrere korrekte Antworten auf die Frage. Warum nun gerade Anna ausgewählt wurde, ist noch zu klären.

Mit dem Prädikat <tt>findall</tt> ist es möglich, sämtliche Variablen-Belegungen als Ergebnisliste, nämlich <tt>Momas = [anna,christine]</tt> zusammenzufassen, die das ''Beweisziel erfüllen''. 

<run id="4b8bd289adc1d">findall(MartinOma,oma(martin,MartinOma),Momas).</run>

Nicht alle Zeilen der Ausgabe von Prolog können wir mit dem bisherige Wissen interpretieren. Trotz unseres eigentlichen Interesses an den Namen von Martins Großmüttern wird am Ende ein <tt>true</tt> ausgegeben. Wir oben bereits angemerkt, versucht das Prolog-System die jeweilige Frage zu beantworten, oder anders gesagt: das vorgegebene Ziel (goal) zu beweisen. 

=== Term ===

Die Ausdrücke, die wir zum Schreiben von Fakten, Regeln und Anfragen verwendet haben, sind Terme. Deren formaler Definition werden wir uns weiter unten zuwenden. Die Idee des Beweisprozesses besteht darin, Terme passend zu machen. Das dabei angewandte Verfahren heißt ''Pattern Matching''. Es ist aus anderen Zusammenhängen bekannt.

Ganz intuitiv können wir erkennen, dass beispielsweise die Anfrage <tt>oma(martin,MartinOma)</tt> und der Fakt <tt>oma(martin,anna)</tt> zusammen passen: 
<run id="4b8bd289ae7d8">oma(martin,MartinsOma).</run>
Wir beschreiben unsere Beobachtungsergebnisse:
* Die Klammerstrukturen stimmen überein. 
* <tt>oma</tt> steht in beiden Termen an erster Stelle. 
* <tt>martin</tt> steht jeweils an erster Stelle innerhalb der Klammer.
Die Variable <tt>MartinsOma</tt> an zweiter Stelle in der Klammer und <tt>anna</tt> können aneinander gebunden werden, dann passt alles! Das Herstellen solcher Bindungen (hier: Konstante - Konstante, Variable - Konstante) werden wir später ''Unifikation'' nennen.

Das Vorhaben, ein Beweisziel zu erfüllen, besteht also letztlich in einer Suche (genauer: Tiefe-zuerst-Suche) nach Teilausdrücken in der Datenbasis, mit denen die die auftretenden Terme in gewissem Sinne passend gemacht werden können. Die in den Regeln definierten Prädikate werden auf die zu deren Definition verwendeten Terme auf der jeweiligen rechten Regelseite zurückgeführt.