Aussagenlogik/Sprache/Einführung/Textabschnitt
Die formallogische Sprache der Aussagenlogik wird ausgehend von einer Variablenmenge und einer einfachen Menge an Junktoren rekursiv aufgebaut. Die Aussagenvariablen werden wir zumeist mit etc. bezeichnen. Sie repräsentieren Aussagen, haben aber keinen eigenen Inhalt, sondern teilen mit Aussagen lediglich gewisse syntaktische Eigenschaften (semantische Eigenschaften werden hier noch nicht besprochen). Beispiele für solche syntaktischen Eigenschaften sind, dass man zu einer Aussage eine Negation bilden kann, oder dass man zwei Aussagen durch „und“ verknüpfen kann. Die Aussagenvariablen repräsentieren Grundaussagen, die durch solche Verknüpfungen zu komplexeren Aussagen zusammengesetzt werden können, die selbst wiederum zu weiter verschachtelten Aussagen verbunden werden können. Die folgende Definition fixiert die formale Sprache der Aussagenlogik; es handelt sich um eine rekursive Definition, wobei die Aussagenvariablen die Startelemente sind und die logischen Operationen als Generierungsregeln auftreten. Das dieser rekursiven Definition zugrunde liegende Alphabet besteht neben einer Menge an Aussagenvariablen aus den Symbolen
die als
nicht, und, oder, impliziert, genau dann, wenn, Klammer auf, Klammer zu
gelesen werden; die zugehörigen Substantive sind Negation, Konjunktion, Disjunktion, Implikation und Äquivalenz. Die Bezeichnungen orientieren sich natürlich an den später einzuführenden Bedeutungen, im Moment sind es lediglich Wörter für bestimmte Symbole. Die Sprache der Aussagenlogik wird als Teilmenge von realisiert, wobei ist.
Es sei eine Menge (deren Elemente wir als Aussagenvariable bezeichnen). Dann wird die zugehörige Sprache der Aussagenlogik (zu ) rekursiv durch folgende Regeln definiert.
- Jedes gehört zu .
- Wenn ist, so ist auch .
- Wenn sind, so sind auch .
Häufig verwendet man weniger Symbole, beispielsweise verzichtet man auf . Die Klammerungen werden oft auch anders gesetzt. Z.B. erlaubt man manchmal (ohne Klammer) oder man macht die Klammern außen, also . Sehr oft lässt man Klammern, um die Lesbarkeit der Aussagen zu erhöhen, einfach weg, obwohl dies vom syntaktischen Standpunkt aus ein schweres Vergehen ist.
Es seien Aussagenvariablen. Dann sind beispielsweise
korrekt gebildete Aussagen, d.h. sie gehören zu . Dagegen sind
keine Aussagen in (aber natürlich Wörter über dem gegebenen Alphabet).
Der Nachweis, dass ein gegebenes Wort eine korrekt gebildete Aussage ist, erfolgt über eine Ableitungskette oder einen Aussagestammbaum. Bei einer Ableitungskette listet man Zeile für Zeile korrekt gebildete Aussagen auf, wobei diese Aussagen entweder Aussagenvariablen oder aber mittels einer Rekursionsregel aus vorhergehenden Aussagen entstanden sind. Die letzte Zeile enthält die Aussage, deren Korrektheit man zeigen will.
Eine Ableitungskette für
sieht folgendermaßen aus.
- (Aussagenvariable),
- (Aussagenvariable),
- (Aussagenvariable),
- (Negation auf 2),
- (Konjunktion auf 1 und 3),
- (Disjunktion auf 4 und 3),
- (Implikation auf 5 und 6).
Ein Aussagenstammbaum ist eine graphisch übersichtliche Version einer Ableitungskette. Er beginnt mit den verwendeten Aussagenvariablen als Blättern und erzeugt dann Schritt für Schritt durch Vereinigungen von Zweigen die beteiligten Teilaussagen, bis schließlich die in Frage stehende Aussage als Stamm erzeugt ist.
Wir wollen uns anhand eines Stammbaumes klar machen, dass die Zeichenkette
eine Aussage ist, also gemäß den Regeln korrekt gebildet ist. Der Abstammungsbaum entsteht ausgehend von den Blättern, die die vorkommenden Aussagenvariablen (mit ihrer Häufigkeit) repräsentieren, indem man Schritt für Schritt komplexere Teilaussagen zusammensetzt.
Jede Aussage hat eine eindeutige „rekursive Geschichte“, d.h. es gibt für jede Aussage nur eine Abfolge von Rekursionsschritten (bis auf die Reihenfolge), um sie aus Aussagenvariablen aufzubauen, siehe Aufgabe.