Syntax der Aussagenlogik


Download PDF

 

Motivation

In den nachfolgenden Abschnitten geht es zunächst um die Syntax und die Semantik der Aussagenlogik. Mit der Syntax definieren wir, was wir überhaupt notieren dürfen. In der Mathematik z.B. ist \(3+4\) ein syntaktisch korrekter Term (man spricht auch von wohlgeformt), die Zeichenkette \(3 ++ 4\) hingegen nicht. Ähnliches wollen wir nun für die Aussagenlogik definieren und damit dann die wohlgeformten Formeln der Aussagenlogik definieren. Dies wird uns dann Notationen wie \(A \wedge B\) erlauben, nicht aber \(\wedge A \wedge B\). Im Anschluss werden wir dann die Semantik definieren. Ziel dabei ist es, jeder Formel einen eindeutigen Wahrheitswert (also eine Bedeutung) zuzuweisen. In der Aussagenlogik kann eine Formel wahr oder falsch ein. Das Ziel ist es ausgehend von Wahrheitswerten für die atomaren Formeln wie \(A\) oder \(B\) und einer Definition für die einzelnen Verknüpfungen, zu einem Wahrheitswert für die ganze Formel (z.B. \(A \wedge B\)) zu kommen.

 

Aussagenlogische Formeln werden aus einer Menge von Aussagensymbolen (den atomaren Formeln) \(A_1, A_2, A_3, \ldots\) und den Junktoren \(\neg\),\(\wedge\),\(\vee\),\(\Rightarrow\),\(\Leftrightarrow\) (nicht, und, oder, Implikation und Biimplikation) gebildet.

Zunächst ist jedes Aussagensymbol auch eine (atomare) Formel. Ferner kann man, gegeben zwei Formeln \(F\) und\(G\), diese durch die Junktoren zu einer neuen Formel kombinieren. So sind dann auch \(\neg F, (F \wedge G), (F \vee G), (F \Rightarrow G)\) und \((F \Leftrightarrow G)\) (komplexe) Formeln. Damit ist man mit der Definition der Syntax der Aussagenlogik, also damit, wie Formeln „aussehen“ dürfen, auch schon fertig. Eine den obigen Regeln entsprechend gebildete Formel nennt man dann auch wohlgeformt. Wir fassen dies noch einmal in folgender Definition zusammen:

 

Aussagensymbole ...

Die Menge der Aussagensymbole ist (abzählbar) unendlich. Dies deutet oben die fortlaufende Indizierung \(A_1, A_2, A_3, \ldots\) an. In jeder Formel treten aber nur endlich viele Aussagensymbole auf. Statt \(A_1\) etc. nimmt man gerne auch Buchstaben am Anfang des Alphabets, also \(A, B, C, \ldots\).

Definition 2.1

Mit \(AS_{AL} = \{A_1, A_2, \ldots\}\) sei die (abzählbar unendliche) Menge der Aussagensymbole der Aussagenlogik bezeichnet.

Die Menge \(\mathcal{L}_{AL}\) der (wohlgeformten) Formeln der Aussagenlogik definieren wir mittel

  1. Jedes \(A \in AS_{AL}\) ist eine (atomare) Formel.
  2. Ist \(F\) eine Formel, so ist auch\(\neg F\) eine (komplexe) Formel.
  3. Sind \(F\) und\(G\) Formeln, so sind auch\((F \vee G), (F \wedge G), (F \Rightarrow G)\) und \((F \Leftrightarrow G)\) (komplexe) Formeln.
  4. Es gibt keine anderen Formeln, als die, die durch endliche Anwendungen der Schritte 1-3 erzeugt werden.

Hinweis zur Definition 2.1

Wir wollen die Definition noch einmal genauer betrachten. Zunächst sind alle Aussagensymbole Formeln. \(A_1\),\(A_2\) usw. sind also Formeln. Dann wird gesagt, wenn \(F\) und \(G\) Formeln sind (und bisher können \(F\) und \(G\) also nur atomare Formeln sein), dann auch z.B. \((F \vee G)\). Sei also z.B. \(F\) die atomare Formel \(A_1\) und \(G\) die atomare Formel \(A_{15}\), dann ist nun \((A_1 \vee A_{15})\) eine Formel. Dies kann man nun weiter fortführen. Nimmt man nun für \(F\) die eben erstellte Formel \((A_1 \vee A_{15})\) und für \(G\) die atomare Formel \(A_6\), so ist z.B. auch \(((A_1 \vee A_{15}) \wedge A_6)\) eine Formel (da im dritten Punkt der Definition oben gesagt wird, wenn \(F\) und \(G\) Formeln sind, dann auch \((F \wedge G))\). Der zweite Punkt der Definition erlaubt noch mit einer Formel \(F\) und dem Symbol \(\neg\) die Formel \(\neg F\) zu konstruieren (also z.B. mit \((A_1 \vee A_{15})\) als \(F\) die Formel \(\neg (A_1 \vee A_{15}))\). Der vierte Punkt sagt dann noch, dass man nur endlich oft so verfahren darf (also keine unendlich langen Formeln entstehen können). Die Definition sagt, dass wir auf diese Weise gerade alle Formeln der Aussagenlogik erhalten.

Nutzen wir die weit verbreitete Konvention, Buchstaben am Anfang des Alphabets für atomare Formeln zu nutzen (also \(A, B, C, \ldots\)), so sind weitere wohlgeformte (d.h. korrekt gebildete) Formeln dann z.B.\(((A \vee B) \Rightarrow C)\) oder \((\neg A \wedge B \wedge \neg C) \vee (A \wedge \neg B \wedge \neg C)\), wobei bei letzterem bereits an mehreren Stellen Klammerersparnisregeln angewandt wurden, d.h. nicht nötige Klammern wurden weggelassen. Dies betraf hier die äusseren Klammern und Klammern, die durch das mehrfache \(\wedge\) aufgetreten wären. Wir kommen später noch auf die Klammerersparnisregeln zu sprechen.
Nicht wohlgeformte Ausdrücke entstehen z.B. durch falsche Klammerung wie in \((F \vee G(\) oder aneinandergereihte Junktoren wie in \(F \vee \vee G\).

 

Klammerung ...

In der Mathematik schreibt man ja auch lieber \(3+4+5\) und eher selten \((3+4)+5\) oder gar \(((3+4)+5)\).

 

Wohlgeformt ...

Die Syntax definiert also, wie Formeln aussehen dürfen. Darauf aufbauend ist es dann möglich die Semantik zu definieren. Wenn man gar nicht so genau wüsste, wie die Formeln aussehen (sprich: Es nicht wie hier geschehen mit einigen wenigen Konstruktionsvorschriften angeben könnte), könnte man das nämlich nicht machen. Die formale Definition der Syntax wird uns außerdem später in der strukturellen Induktion noch einmal begegnen.

 
Noch ein paar Begrifflichkeiten. Wir hatten bereits den Begriff des Aussagesymbols und den des Junktors (die \(\neg\), \(\vee\) usw.). Weitere gebräuchliche Begriffe sind Alphabet für die Menge der benutzbaren Symbole. Das Alphabet besteht bei uns also aus den Aussagesymbolen, den Junktoren und den Klammern. Weiterhin nennt man eine Formel, die beim Aufbau einer Formel \(F\) verwendet wird, eine Teilformel von \(F\). Außerdem ist \(F\) Teilformel von sich selbst. Den Junktor, der im letzten Konstruktionsschritt verwendet wurde nennt man den Hauptoperator. Nach dem Hauptoperator werden komplexe Formeln oft benannt. Zum Beispiel ist in der Formel \(F = (A \vee (B \wedge C))\) \((B \wedge C)\) eine Teilformel. Der Hauptoperator ist \(\vee\), weswegen \(F\) auch als Disjunktion bezeichnet wird (im Falle von \(\wedge\) spricht man von einer Konjuktion, bei \(\Rightarrow\) von einer Implikation und bei \(\Leftrightarrow\) von einer Biimplikation).

 
 

Hier ein paar Fragen zur Syntax der Aussagenlogik.