LbP Grundlagen
Aus ProgrammingWiki
Inhaltsverzeichnis |
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.
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: weiblich/1.
Fakten kann man erfragen (Anfrage) und erhält erwartungsgemäß eine Bestätigung:
Gerhard ist jedoch ein Mann, so dass das Ergebnis der Anfrage false lautet:
Zweistellige Prädikate (ohne Variablen) stellen Beziehungen zwischen Objekten dar, z.B. "Die Mutter von Doris ist Anna."
Ebensogut wäre mutter(anna, doris), mit der Interpretation "Anna ist die Mutter von Doris.", möglich. Auch dieser Fakt kann durch Anfrage leicht bestätigt werden:
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.
In unserem Beispiel wird bestätigt, dass Christine Martins Großmutter ist.
Aufgabe: Fügen Sie den oben angegebenen Regeln noch weitere für die Definition des Großvater-Begriffs (Prädikat opa/2) 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.
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 findall ist es möglich, sämtliche Variablen-Belegungen als Ergebnisliste, nämlich Momas = [anna,christine] zusammenzufassen, die das Beweisziel erfüllen.
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 true 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 oma(martin,MartinOma) und der Fakt oma(martin,anna) zusammen passen:
Wir beschreiben unsere Beobachtungsergebnisse:
- Die Klammerstrukturen stimmen überein.
- oma steht in beiden Termen an erster Stelle.
- martin steht jeweils an erster Stelle innerhalb der Klammer.
Die Variable MartinsOma an zweiter Stelle in der Klammer und anna 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.
