LbP Prädikatenlogik
Aus ProgrammingWiki
Inhaltsverzeichnis |
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.
- Konjunktion
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.