LbP Prädikatenlogik

Aus ProgrammingWiki

Inhaltsverzeichnis 1 Logik und Programmierung 1.1 Aussagenlogik 1.2 Prädikatenlogik 1.3 PK(1), HORN-Klausel-Logik und Prolog

Logik und Programmierung

Aussagenlogik

Eine Aussage ist ein Satz, der entweder wahr oder falsch ist. Man spricht auch von einer zweiwertigen Logik. Dabei kommt es nicht darauf an, dass eine den Satz beurteilende Person zu einem gegebenen Zeitpunkt weiss, ob der Satz wahr ist oder nicht (Interpretation). Entscheidend ist die Zuordnung genau eines Wahrheitswertes (entweder oder ; niemals beides, niemals keines) zu einem Satz.

Aussagen enthalten keine Variablen. Es ist etwas ganz anderes, wenn wir Variablen benutzen, um damit Aussagen zu bezeichnen, so wie man das für andere Werte in vielen Bereichen der Mathematik ebenfalls tut. Aussagenvariablen werden benutzt, um insbesondere komplexe Aussagen übersichtlich darzustellen und mit ihnen rechnen zu können. Dabei werden die Variablen mit Wahrheitswerten belegt.

Komplexe Aussagen werden aus Aussagen (einfache und komplexe) zusammengesetzt. Dafür stehen Verknüpfungsoperatoren (Junktoren) zur Verfügung:

• eine einstellige Operation: die Negation
• die zweistelligen Operationen
  • Konjunktion
  • Disjunktion
  • Subjunktion
  • Bijunktion.

Neben den Definitionen dieser Operationen, sind Bindungsverhältnisse (Vorrangbeziehungen) und Klammersetzungen zu berücksichtigen, wenn man für eine konkrete Belegung der aussagenlogischen Variablen den Wert eines zusammengesetzten Ausdrucks bestimmen möchte.

Manchmal fragt man auch umgekehrt nach der sog. Erfüllungsmenge: Für welche Belegungen wird eine vorgegebene (komplexe) Aussage wahr? Mit der Frage nach der Erfüllungsmenge begibt man sich in den metasprachlichen Bereich, d.h. wir formulieren Aussagen über solche Aussagen, deren Aufbau wir gerade definiert haben. Die Sprache der Ausdrücke nennen wir Objektsprache, die Sprache, in der wir über Ausdrücke sprechen, heisst Metasprache.

Auch die Frage nach der Allgemeingültigkeit einer Aussage ist eine metasprachliche Formulierung: ist allgemeingültig, wenn für alle Belegungen wahr wird. Beispielsweise ist leicht zu zeigen, dass für alle Belegungen von wahr wird, d.h. die angegebene Aussage ist allgemeingültig, und man schreibt allgemein .

Zwei Aussagen und nennt man äquivalent, kurz , wenn ist. Diese Schreibweise hebt den metasprachlichen Unterschied zwischen der Bijektion und der Äquivalenz hervor.

Eine wichtige Ordnungsrelation für Aussagen ist die Implikation . gilt genau dann, wenn .

Es gibt eine Reihe aussagenlogischer Regeln, die äquivalente Umformungen von Ausdrücken gestatten, ohne die Äquivalenz durch Betrachtung aller Belegungen nachweisen zu müssen. Häufig benutzt man ein DeMorgansches Gesetz oder Regeln für das aussagenlogische Schliessen, wie etwa die Abtrennungsregel (modus ponens): .

Prädikatenlogik

Der entscheidende Unterschied zur Aussagenlogik ist die Hinzunahme von Variablen zu Aussagen, so dass Aussageformen entstehen. Ansonsten gelten die gleichen Junktoren wie oben. In Analogie zur Aussagenlogik verwendet man Symbole, um Prädikate zu benennen.

Die Belegung von Variablen in prädikatenlogischen Ausdrücken erfolgt mit Werten aus wohldefinierten Grundmengen. Beispielsweise wird das einstellige Prädikat " ist teilbar durch 3", kurz , durch die natürlichen Zahlen erfüllt.

Eine Variable in einem prädikatenlogischen Ausdruck darf nur dann mit einem konkreten Wert belegt werden, wenn sie nicht im Einflussbereich eines Quantors steht. Anders ausgedrückt: Quantoren binden Variablen und machen eine Aussageform zur Aussage, wenn keine freien Variablen vorkommen. Es gibt den Allquantor und den Existenzquantor . Dann liest man das für natürliche Zahlen definierte Prädikat folgendermassen. Für alle gilt: teilt genau dann, wenn es ein derart gibt, dass . Die Aussageform muss für alle Belegungen von wahr werden, um allgemeingültig zu sein. Es reicht also nicht aus, ein oder zwei Werte für auszuprobieren. Dies macht die Sache schwierig! Die Berechnung des Wahrheitswertes ist also nicht immer ohne Weiteres möglich, denn wir müssten unendlich viele Fälle untersuchen.

In der Prädikatenlogik erster Stufe, kurz PK(1) für Prädikatenkalkül 1. Ordnung, können nur die genannten Variablen quantifiziert werden. In der zweiten Stufe quantifiziert man ausserdem Prädikatenvariablen. Aus der theoretischen Informatik ist bekannt, dass die Prädikatenlogik aufzählbar aber nicht entscheidbar ist. Mit anderen Worten: Es gibt keinen Algorithmus, der für jede beliebige vorgegebene Aussage in endlicher Zeit entscheidet, ob sie aus einer Menge geltender Aussagen (Axiomsystem) ableitbar ist oder nicht.

PK(1), HORN-Klausel-Logik und Prolog

Eine Teilmenge der Prädikatenlogik, die die Entscheidbarkeit garantiert, ist die Hornklausellogik. PROgramming in LOGig (Prolog) basiert darauf.

Eine Klausel ist eine Disjunktion negierter und nichtnegierter logischer Ausdrücke. Darin enthaltene Variablen sind grundsätzlich universell quantifiziert, d.h. im Einflussbereich von -Quantoren. Die Allquantoren werden aber nicht extra angegeben. Wendet man die Rechengesetze der Prädikatenlogik an, nämlich und , so erhält man den dazu äquivalenten Ausdruck .

Jeder prädikatenlogische Ausdruck kann in eine äquivalente Konjunktion von Klauseln übertragen werden. Hornklauseln haben eine eingeschränkte Klauselgestalt: Die Disjunktion darf nur höchstens einen unnegierten Ausdruck enthalten, d.h. oder äquivalent dazu .

gilt, wenn und usw. und gelten. Unter Benutzung von Hornklauseln können Aussagen effizient abgeleitet werden. Die zugehörige Prolog-Klausel lautet: .

Jede Klausel obiger allgemeiner Gestalt kann in eine Hornklausel transformiert werden. Unnegierte Aussagen müssen ggf. doppelt negiert werden, z.B. . Um es ganz deutlich zu sagen: Jeder prädikentlogische Ausdruck kann in einen äquivalenten Hornklauselausdruck übertragen werden.

Dabei ergibt sich allerdings ein Problem, denn die Negation erweist sich als ein sog. Metaprädikat, also ein Prädikat, dessen Argument ein Prädikat ist. Dies verstösst gegen die logische Grundlage von Prolog. Der Preis für diesen Verstoss wird weiter unten an einem Beispiel illustriert. Im Allgemeinen ist die Fehleranfälligkeit eines Prologprogramms bei kontrolliertem Einsatz der Negation gering.

Prozedural gedeutet, wird ein Beweisziel berechnet, indem alle Aussagen bis berechnet werden. Dieser Prozess setzt sich rekursiv solange fort, bis man passende variablen-freie Klauseln (Axiome) in der Datenbasis findet.