Aussagenlogik – Serlo „Mathe für Nicht-Freaks“

Mathematische Symbole und Zeichen.

In den beiden vorangegangenen Kapiteln hast du Aussagen und Junktoren kennengelernt. Mit Hilfe der Junktoren kann man aus Aussagen weitere Aussagen erzeugen. Wir hatten auch gesehen, dass in der Mathematik eine formalisierte Sprache benutzt wird. Das hat mehrere Gründe:

• Zum einen ist unsere natürliche Sprache nicht eindeutig. Die Eindeutigkeit der Begriffe und Zusammenhänge ist aber für die Mathematik ganz wesentlich.
• Zum anderen werden in der Mathematik viele abstrakte Sachverhalte beschrieben und analysiert, für die neue Begriffe mit einer genau festgelegten Bedeutung benötigt werden.

Deshalb benutzt die Mathematik eine künstliche Sprache, die als formale Sprache bezeichnet wird. Wir werden diese Sprache schrittweise vorstellen und beginnen damit in diesem Kapitel. Die weiteren Schritte folgen in der Prädikatenlogik und in der Klassenlogik.

Die folgenden Definitionen erscheinen sehr formal, insbesondere dann, wenn ihr zum ersten Mal damit konfrontiert werdet. Diese formale Strenge hilft jedoch dabei, Fehlschlüsse zu vermeiden und die Mathematik auf eine sichere Grundlage zu stellen.

Die Sprache der Aussagenlogik

Für die Logik ist die formale Sprache besonders wichtig, denn mit Hilfe der Logik werden ja die mathematischen Beweise geführt. Beweise verlaufen nach ganz bestimmten Regeln. Das Einhalten dieser Regeln muss automatisiert nachprüfbar sein! Und das geht in einer formalisierten Sprache am besten. Die Sprache, in der Aussagen mit Junktoren verknüpft werden, ist die Sprache der Aussagenlogik. Wie unsere natürliche Sprache hat sie ein Alphabet:

Definition (Alphabet der Aussagenlogik)

Die Sprache der Aussagenlogik hat drei Arten von Zeichen:

1. die Aussagenkonstanten $K_{0},K_{1},K_{2},\dots$, ${\mathsf {W}}$ und ${\mathsf {F}}$,
2. die Junktoren $\neg$, $\land$, $\lor$, ${\dot {\lor }}$, $\Rightarrow$ und $\Leftrightarrow$,
3. die Klammern $($ und $)$.

Die Zeichen heißen ${\mathsf {W}}$ (Wahr) und ${\mathsf {F}}$ (Falsch), die Junktoren $\neg$ (Negation), $\land$ (Konjunktion), $\lor$ (Disjunktion), ${\dot {\lor }}$ (Kontravalenz), $\Rightarrow$ (Implikation) und $\Leftrightarrow$ (Äquivalenz).

Anmerkung: Genau genommen bestehen die Konstanten selbst aus mehreren Zeichen, dem Buchstaben $K$ und einer Zahl. Wir wollen die Konstanten hier aber als eine Einheit betrachten. Es ist nicht weiter wichtig, wie sie genau realisiert werden. Wichtig ist nur, dass wir ausreichend viele Konstanten haben und bei Bedarf immer noch ein paar neue hinzunehmen können.

Aus diesen Zeichen können nach bestimmten Regeln Wörter gebildet werden, die in diesem Zusammenhang Formeln oder wohlgeformte Zeichenreihen genannt werden. Zeichenreihen entstehen einfach dadurch, dass Zeichen aus dem Alphabet hintereinander geschrieben werden, zum Beispiel so: $(K_{3}\land {\mathsf {W}}\lor \neg K_{0}(\Rightarrow$. Aber das ist keine Formel!

Definition (Formeln der Aussagenlogik)

Die Formeln der Aussagenlogik werden nach folgenden Regeln gebildet:

1. Jede Aussagenkonstante ist eine Formel, ${\mathsf {W}}$ und ${\mathsf {F}}$ sind Formeln.
2. Ist $A$ eine Formel, so ist auch $\neg A$ eine Formel.
3. Sind $A$ und $B$ Formeln, so sind auch $(A\land B)$, $(A\lor B)$, $(A\;\;\!\!{\dot {\lor }}\;\;\!\!B)$, $(A\Rightarrow B)$ und $(A\Leftrightarrow B)$ Formeln.

Es gibt keine weiteren Formeln.

Eine solche Definition wird rekursiv (lat. zurückgehend) genannt, weil bei der Erzeugung weiterer Formeln auf bereits erzeugte Formeln zurückgegriffen wird.

Beispiel für eine Formel

Um zu zeigen, wie diese Regeln angewendet werden, zeigen wir, dass $(\neg (K_{1}\Leftrightarrow K_{2})\Leftrightarrow (K_{1}\;\;\!\!{\dot {\lor }}\;\;\!\!K_{2}))$ eine Formel der Aussagenlogik ist:

Zeile	Formel	Begründung
1	$K_{1}$	nach Regel 1, $K_{1}$ ist eine Aussagenkonstante
2	$K_{2}$	nach Regel 1, $K_{2}$ ist eine Aussagenkonstante
3	$(K_{1}\Leftrightarrow K_{2})$	nach Regel 3 angewendet auf Zeile 1 und 2
4	$\neg (K_{1}\Leftrightarrow K_{2})$	nach Regel 2 angewendet auf Zeile 3
5	$(K_{1}\;\;\!\!{\dot {\lor }}\;\;\!\!K_{2})$	nach Regel 3 angewendet auf Zeile 1 und 2
6	$(\neg (K_{1}\Leftrightarrow K_{2})\Leftrightarrow (K_{1}\;\;\!\!{\dot {\lor }}\;\;\!\!K_{2}))$	nach Regel 3 angewendet auf Zeile 4 und 5

Beweis über den Aufbau der Formeln

Die rekursive Definition der Formeln erlaubt ein besonderes Beweisverfahren. Um eine Behauptung für alle Formeln zu beweisen, genügen zwei Schritte:

1. Im ersten Schritt wird die Behauptung für die Aussagenkonstanten $K_{i}$ und für ${\mathsf {W}}$ und ${\mathsf {F}}$ gezeigt.
2. Im zweiten Schritt wird gezeigt, dass sich die Behauptung unter den Regeln vererbt. Das heißt Folgendes:
   • Wenn die Behauptung für eine Formel $A$ gilt, dann gilt sie auch für die Formel $\neg A$.
   • Wenn die Behauptung für die Formeln $A$ und $B$ gilt, dann gilt sie auch für die Formel $(A\land B)$, $(A\lor B)$, $(A\;\;\!\!{\dot {\lor }}\;\;\!\!B)$, $(A\Rightarrow B)$ und $(A\Leftrightarrow B)$.

Es ist klar, dass die Behauptung dann für alle Formeln gelten muss, denn Formeln können ja nur aufgrund dieser Regeln entstehen! Wir zeigen als Beispiel den folgenden einfachen Satz:

Satz

Jede Formel enthält genauso viele linke wie rechte Klammern.

Beweis

1. Für beliebige Aussagenkonstanten $K_{i}$ und für ${\mathsf {W}}$ und ${\mathsf {F}}$ ist das richtig, denn sie enthalten gar keine Klammern.
2. Wenn $A$ genauso viele linke wie rechte Klammern enthält, dann gilt das auch für $\neg A$, denn bei der Bildung der Negation kommen keine Klammern dazu. Haben schließlich $A$ und $B$ jeweils gleich viele linke wie rechte Klammern, so kommen bei $(A\land B)$ genau eine linke und eine rechte Klammer dazu. Also bleiben es gleich viele. So ist es auch bei den weiteren Regeln für $(A\lor B)$, $(A\;\;\!\!{\dot {\lor }}\;\;\!\!B)$, $(A\Rightarrow B)$ und $(A\Leftrightarrow B)$. ✔

Klammerersparnis, Schreibweisen

Bei der Schreibweise von Formeln lassen wir die Außenklammern in der Regel weg und erlauben uns auch andere Freiheiten. Es muss nur immer klar sein, welche Formel im Sinne der obigen Definition gemeint ist. Natürlich übernehmen wir auch die Bindungsregeln aus dem Kapitel über Junktoren, um Klammern wegzulassen:

1. Negation $\neg$
2. Konjunktion $\land$
3. Disjunktion $\lor$
4. Implikation $\Rightarrow$
5. Äquivalenz $\Leftrightarrow$

Falls es dem Verständnis dient, setzen wir auch zusätzliche Klammern.

Aussagen formalisieren

Wir greifen nun einige Aussagen auf, die wir schon im Kapitel Junktoren angesprochen haben. Wenn wir Aussagen formalisieren, dann heißt das nichts anderes, als sie in eine Formel zu übersetzen, die der Aussage möglichst gut entspricht.

Beispiel 1: Zwei Aussagen werden mit dem Junktor und verbunden.

„$2$ ist kleiner als $36$ und $5$ ist gerade.“

Zurzeit haben wir nur die Möglichkeit, die beiden Aussagen durch eine Konstante wiederzugeben, sagen wir durch $K_{1}$ („$2$ ist kleiner als $36$“) und $K_{2}$ („$5$ ist gerade“). Dann lautet die formalisierte Aussage einfach:

$K_{1}\land K_{2}$

Da es hierbei auf die Konstanten $K_{1}$ und $K_{2}$ gar nicht ankommt, verwendet man einfach auch die Variablen $A$ und $B$ und schreibt $A\land B$ für die formalisierte Aussage. Wir wissen aber aus dem Zusammenhang, dass damit eine exakte Formel der Aussagenlogik gemeint ist.

Anmerkung: Wir werden in den Kapiteln Prädikatenlogik und Klassenlogik weitere Möglichkeiten kennenlernen, Aussagen besser zu formalisieren.

Verständnisfrage: Formalisiere die folgenden Aussagen:

1. Wenn Berlin in Deutschland liegt und der Rhein durch Deutschland fließt, dann liegt Berlin am Rhein.
2. Teilt $6$ eine natürliche Zahl $n$, dann wird $n$ entweder von $2$ oder von $3$ geteilt.
3. Es gibt unendlich viele Primzahlen.

Antwort:

1. Sei $K_{1}:=$ Berlin liegt in Deutschland, $K_{2}:=$ Der Rhein fließt durch Deutschland, $K_{3}:=$ Berlin liegt am Rhein. Dann lautet die Formalisierung $(K_{1}\land K_{2})\Rightarrow K_{3}$. Die Außenklammern haben wir nach der Klammerersparnisregel weggelassen.
2. $A\Rightarrow (B\;\;\!\!{\dot {\lor }}\;\;\!\!C)$, wobei $A:=6{\text{ teilt }}n$, $B:=2{\text{ teilt }}n$ und $C:=3{\text{ teilt }}n$ bedeuten. Hier haben wir für die Konstanten einfach $A,B,C$ anstelle von $K_{1},K_{2},\dots$ verwendet, weil ja klar ist, dass damit in diesem Zusammenhang Aussagenkonstanten gemeint sind.
3. Diese Aussage enthält keine Junktoren. In der Aussagenlogik kann man sie nur durch eine Konstante formalisieren.

Teilformeln

Beim rekursiven Aufbau einer Formel $A$ erhält man zwischendurch weitere Formeln. Diese Formeln werden Teilformeln genannt. Die genaue Definition ist natürlich ebenfalls rekursiv. Teilformeln, die keine echten Teilformeln haben, heißen atomare Formeln.

Definition (Teilformeln, atomare Formeln)

1. Die Aussagenkonstanten $K_{i}$ und die Formeln ${\mathsf {W}}$ und ${\mathsf {F}}$ sind atomare Formeln und Teilformeln von sich selbst.
2. Die Teilformeln von $\neg A$ sind die Teilformeln von $A$ und $A$ selbst. Die Teilformeln von $(A\land B)$, $(A\lor B)$, $(A\;\;\!\!{\dot {\lor }}\;\;\!\!B)$, $(A\Rightarrow B)$ und $(A\Leftrightarrow B)$ sind die Teilformeln von $A$ und $B$, sowie $A$ und $B$ selbst.

Verständnisfrage: Welche Teilformeln hat die im Beispiel oben erstellte Formel $(\neg (K_{1}\Leftrightarrow K_{2})\Leftrightarrow (K_{1}\;\;\!\!{\dot {\lor }}\;\;\!\!K_{2}))$?

Antwort:

Atomere Formeln: $K_{1}$ und $K_{2}$. Weitere Teilformeln: $(K_{1}\Leftrightarrow K_{2})$, $(K_{1}\;\;\!\!{\dot {\lor }}\;\;\!\!K_{2})$, $\neg (K_{1}\Leftrightarrow K_{2})$ und die Formel $(\neg (K_{1}\Leftrightarrow K_{2})\Leftrightarrow (K_{1}\;\;\!\!{\dot {\lor }}\;\;\!\!K_{2}))$ selbst.