3. Aussagenlogik

In der Aussagenlogik geht es darum, Aussagen mathematisch präzise zu fassen und mithilfe von logischen Verknüpfungen zu neuen Aussagen zu kombinieren.

DefinitionAussage

Eine Aussage ist ein Satz, dem eindeutig einer der Wahrheitswerte true (wahr) oder false (falsch) zugeordnet werden kann.

Beispiele für einfache Aussagen sind etwa:

Die Erde ist eine Scheibe.
1 plus 1 ergibt 2.
Kurt ist klug.

Beispiele für kompliziertere Aussagen sind:

Morgen stehe ich früh auf oder ich schlafe ein bisschen länger.
Wenn die Erde eine Scheibe ist, dann bin ich der Kaiser von China.
Wenn der Hahn kräht auf dem Mist, ändert sich das Wetter oder es bleibt wie es ist.

In der mathematischen Logik kommt es zunächst nicht auf den Sachverhalt an, der durch die Aussage ausgedrückt wird. Stattdessen werden Variablen $A, B, C, . . .$ verwendet, die für Aussagen stehen, und die mit Wahrheitswerten belegt werden können. Und diese Variablen werden mit logischen Operatoren verknüpft. Untersucht wird dann, welcher Wahrheitswert herauskommt, wenn die Variablen mit bestimmten Wahrheitswerten belegt werden. Und es wird untersucht, welche allgemeinen Gesetze gelten, unabhängig davon, wie die Variablen mit Wahrheitswerten belegt werden.

Es ist ein bisschen so ähnlich wie in der Arithmetik: Du verknüpfst zwei Variablen $a$ und $b$ mit plus:

$a + b = c$

Dann schaust du, was für $c$ herauskommt, wenn du beispielsweise die Variable $a$ mit dem Zahlenwert 17 und die Variable $b$ mit dem Zahlenwert 4 belegst. Richtig interessant wird es aber erst dann, wenn du die Gesetze der Arithmetik entdeckst, beispielsweise

$a + b = b + a$

Diese Formel gilt immer, ganz egal, mit welchen Zahlenwerten du die Variablen $a$ und $b$ belegst.

Logische Verknüpfungen

Negation - die Nicht-Verknüpfung

Die Negation ist die einfachste logische Verknüpfung, da sie nur einen Operanden hat. Die folgende Verknüpfungstafel (Wahrheitstafel) zeigt dir, wie die Verknüpfung auf die Wahrheitswerte der Operanden wirkt:

$\begin{array}{cc} A & \neg A \\ false & true \\ true & false \end{array}$

Anhand der Wahrheitstafel erkennst du: Wenn du die Variable $A$ mit dem Wahrheitswert false belegst, nimmt die Aussage $\neg A$ den Wahrheitswert true an. Und wenn du $A$ mit true belegst, nimmt $\neg A$ den Wert false an.

Der Operator $\neg$ bedeutet "nicht". Wenn etwas nicht falsch ist, dann ist es wahr, und wenn etwas nicht wahr ist, dann ist es falsch. Dies ist die Grundannahme der mathematischen (zweiwertigen) Logik: "tertium non datur" - etwas Drittes gibt es nicht. Es gibt nur entweder wahr oder falsch.

Andere Formen der Logik (z.B. die fuzzy logic) erlauben durchaus auch mehr als zwei Wahrheitswerte, etwa noch Abstufungen zwischen wahr und falsch. Dies wird hier im Folgenden jedoch nicht betrachtet.

Schreibweise

Es ist einfacher und übersichtlicher, die Wahrheitswerte false und true mit den Zeichen $0$ und $1$ zu bezeichnen. Im Folgenden stehen also die Zeichen $0$ und $1$ nicht für Zahlenwerte, sondern für Wahrheitswerte - die $0$ für false und die $1$ für true.

Damit erhältst du folgende Wahrheitstafel für die Negation:

$\begin{array}{cc} A & \neg A \\ 0 & 1 \\ 1 & 0 \end{array}$

Konjunktion - die Und-Verknüpfung

Die Und-Verknüpfung verknüpft zwei Operanden miteinander mit folgender Wirkung:

$\begin{array}{ccc} A & B & A \land B \\ 0 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \end{array}$

Der logische Operator $\land$ bedeutet "und". Die Aussage $A \land B$ wird genau dann wahr, wenn $A$ und $B$ wahr sind (letzte Zeile in der Wahrheitstafel). Denke daran: $0$ bedeutet false (falsch) und $1$ bedeutet true (wahr).

Disjunktion - die Oder-Verknüpfung

Die Oder-Verknüpfung verknüpft zwei Operanden miteinander mit folgender Wirkung:

$\begin{array}{ccc} A & B & A \lor B \\ 0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 1 \end{array}$

Der logische Operator $\lor$ bedeutet "oder". Die Aussage $A \lor B$ wird genau dann wahr, wenn $A$ oder $B$ wahr sind -- oder beide.

Dieses sind die wichtigsten logischen Verknüpfungen. Alle anderen logischen Verknüpfungen kannst du mithilfe dieser drei Verknüpfungen "nicht", "und" und "oder" ausdrücken.

Die Entweder-Oder-Verknüpfung

In der Umgangssprache verstehst du "oder" häufig als "entweder oder": Wenn du sagst: "Morgen stehe ich früh auf oder ich schlafe ein bisschen länger" meinst du eigentlich "entweder oder" - denn beides gleichzeitig geht nicht. Die folgende Wahrheitstafel zeigt die Wirkung der Entweder-Oder-Verknüpfung (auch Exklusiv-Oder-Verknüpfung genannt). Als Operator wird das Zeichen $\oplus︎$ verwendet:

$\begin{array}{ccc} A & B & A \oplus︎ B \\ 0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{array}$

Du siehst den Unterschied zum normalen "Oder" in der letzten Zeile der Wahrheitstafel: Wenn sowohl $A$ als auch $B$ mit dem Wahrheitswert $1$ , also true, belegt sind, dann nimmt der Ausdruck $A \oplus︎ B$ , also "entweder $A$ oder $B$ ", den Wahrheitswert $0$ , also false, an.

Implikation - die Wenn-Dann-Beziehung

$\begin{array}{ccc} A & B & A \to B \\ 0 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \end{array}$

Du kannst die Wenn-Dann-Beziehung verstehen als "wenn $A$ , dann $B$ " oder auch als "aus $A$ folgt $B$ ".

Wenn also $A$ wahr ist, dann muss auch $B$ wahr sein, nur dann ist $A \to B$ wahr. Aber was ist, wenn $A$ falsch ist? Muss dann auch $B$ falsch sein, damit $A \to B$ wahr ist? Anhand der Wahrheitstafel siehst du, dass dies nicht der Fall ist: Wenn $A$ falsch ist, ist die Aussage $A \to B$ automatisch wahr, ganz gleich ob $B$ wahr oder falsch ist.

Vielleicht kommt dir dies zunächst sonderbar vor - vielleicht liegt es daran, dass in der Umgangssprache "wenn dann" häufig als "genau dann, wenn" verstanden wird (siehe nächsten Abschnitt zur Genau-Dann-Wenn-Beziehung).

Für die Wenn-Dann-Beziehung gilt: Aus etwas Wahren kann nur etwas Wahres folgen. Aus etwas Falschem kann dagegen alles folgen, etwas Falsches oder auch etwas Wahres.

Logische Äquivalenz - die Genau-Dann-Wenn-Beziehung

In der Genau-Dann-Wenn-Beziehung ist es so: Wenn $A$ falsch ist, dann muss auch $B$ falsch sein, damit die Aussage $A \leftrightarrow B$ wahr wird - im Gegensatz zur Wenn-Dann-Beziehung.

$\begin{array}{ccc} A & B & A \leftrightarrow B \\ 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \end{array}$

Wahrheitstafeln

Die Gesetzmäßigkeiten der mathematischen Logik zeigst du sehr einfach durch Aufstellen der Wahrheitstafeln für die vorkommenden Teilaussagen.

Zum Beispiel zeigst du mithilfe einer Wahrheitstafel, dass die Aussagen $A \to B$ und $(\neg A) \lor B$ gleichwertig sind. Du erkennst dies daran, dass die Spalte der Wahrheitswerte unter den Aussagen jeweils dieselbe ist.

$\begin{array}{ccccc} A & B & \neg A & (\neg A) \lor B & A \to B \\ 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 \end{array}$

Wenn zwei Aussagen dieselbe Spalte von Wahrheitswerten in der Wahrheitstafel aufweisen, dann sind sie logisch äquivalent. Dies bedeutet für das Beispiel:

$(A \to B) \leftrightarrow ((\neg A) \lor B)$

Präzedenz der Operatoren

In der Arithmetik gilt "Punktrechnung geht vor Strichrechnung". Dies bedeutet, dass bei der Auswertung von Ausdrücken die Multiplikation und die Division eine höhere Präzedenz als die Addition und die Subtraktion haben. Du kannst auch sagen: Der Multiplikationsoperator $\cdot$ bindet stärker als der Additionsoperator $+$ .

Ähnliches gilt für die logischen Operatoren. Der Nicht-Operator $\neg$ bindet am stärksten, dann kommt der Und-Operator $\land$ , dann der Oder-Operator $\lor$ , dann der Implikationsoperator $\to$ und dann der Äquivalenzoperator $\leftrightarrow$ .

\begin{array}{c} Präzedenz \\ \neg \\ \land \\ \lor \\ \to \\ \leftrightarrow \end{array}

Bei der obigen Aussage sparst du also etliche Klammern, wenn du die Präzedenz der Operatoren berücksichtigst:

$A \to B \leftrightarrow \neg A \lor B$

Tautologie - allgemeingültige Aussage

Wenn du die Wahrheitstafel für die obige Aussage aufstellst, dann erhältst du darunter eine Spalte von Wahrheitswerten, die alle $1$ (also true) sind. Dies bedeutet, dass die Aussage immer wahr ist - ganz gleich, wie du die Variablen $A$ und $B$ mit Wahrheitswerten belegst. Eine solcher Aussage heißt allgemeingültige Aussage. Ein anderes Wort für eine allgemeingültige Aussage ist Tautologie. Die allgemeingültigen Aussagen stellen die Gesetze der Logik dar.

Die Gesetze der Logik

Du kennst das Kommutativgesetz aus der Arithmetik: $a + b = b + a$ . Es gilt immer, ganz gleich, wie du die Variablen $a$ und $b$ mit Zahlenwerten belegst. Es gilt für alle $a, b \in ℝ$ .

In der Logik gelten entsprechende Kommutativgesetze für die Operatoren $\land$ und $\lor$ :

$\begin{array}{ccc} A \land B & \leftrightarrow & B \land A \\ A \lor B & \leftrightarrow & B \lor A \end{array}$

Diese Gesetze gelten für jede Belegung der Variablen $A$ und $B$ mit Wahrheitswerten. Sie stellen also Tautologien dar, sie sind allgemeingültig. Entsprechendes gilt für die folgenden Gesetze.

Es gelten die Assoziativgesetze:

$\begin{array}{ccc} (A \land B) \land C & \leftrightarrow & A \land (B \land C) \\ (A \lor B) \lor C & \leftrightarrow & A \lor (B \lor C) \end{array}$

Es ist also egal, ob du eine Aussage wie $A \lor B \lor C$ von links nach rechts oder von rechts nach links auswertest.

Des Weiteren gelten zwei Distributivgesetze; die Operatoren $\land$ und $\lor$ sind also in dieser Hinsicht gleichwertig (anders als die Operatoren $+$ und $\cdot$ in der Arithmetik):

$\begin{array}{lll} (A \land B) \lor C & \leftrightarrow & (A \lor C) \land (B \lor C) \\ (A \lor B) \land C & \leftrightarrow & (A \land C) \lor (B \land C) \end{array}$

Sehr wichtig sind die Gesetze von De Morgan:

$\begin{array}{ccc} \neg (A \land B) & \leftrightarrow & (\neg A) \lor (\neg B) \\ \neg (A \lor B) & \leftrightarrow & (\neg A) \land (\neg B) \end{array}$

Es gibt noch einige weitere Gesetze wie die Idempotenz-Gesetze und die doppelte Negation:

$\begin{array}{ccc} A \land A & \leftrightarrow & A \\ A \lor A & \leftrightarrow & A \\ \neg (\neg A) & \leftrightarrow & A \end{array}$

Sehr wichtige Gesetze für mathematische Beweisführungen sind

$\begin{array}{rcll} (A \to B) \land (B \to C) & \to & A \to C & Transitivität von \to \\ A \to B & \leftrightarrow & \neg B \to \neg A & Kontraposition \\ \neg A \to 0 & \leftrightarrow & A & Widerspruch (reductio ad absurdum) \end{array}$

Der Folgt-Pfeil $\Rightarrow$ in mathematischen Beweisen

Ein Ausdruck wie etwa $A \land B \leftrightarrow B \land A$ ist zunächst einfach nur eine logische Formel. Wenn du sagen willst, dass es sich um eine Tautologie handelt, dass dieser Ausdruck voraussetzungslos wahr ist, dann schreibst du in der mathematischen Logik korrekterweise

⊨ A \land B \leftrightarrow B \land A

Eine Abkürzung dieser Schreibweise ist

A \land B \Leftrightarrow B \land A

In mathematischen Beweisen drückt der doppelte Pfeil $\Rightarrow$ aus, dass es sich um eine Tatsache handelt, die voraussetzungslos wahr ist, oder die unter stillschweigender Einbeziehung der bekannten mathematischen Gesetze wahr ist. Entsprechendes gilt für den Pfeil $\Leftrightarrow$ .

Vorsicht bei logischen Folgerungen

Wenn-dann und Genau-dann-wenn

Sicher klingen dir noch die Worte deines Vaters beim Abholen aus dem Kindergarten im Ohr: "Wenn du jetzt nicht sofort deinen Anorak anziehst, dann gehen wir heute Nachmittag nicht auf den Fußballplatz". Du hast dann widerwillig deinen Anorak angezogen und geglaubt, dass dein Vater dann mit dir auf den Fußballplatz geht, und du warst enttäuscht, dass er es dann doch nicht tat.

Du hast geglaubt, dass mit $A$ für Anorak und $B$ für FußBallplatz die Aussage

$\neg A \to \neg B$

gleichbedeutend ist mit der Aussage

$A \to B$

also "Wenn du deinen Anorak anziehst, dann gehen wir auf den FußBallplatz". Das aber hat dein Vater nicht gesagt. Die Aussagen sind keineswegs äquivalent, wie du heute, dem Kindergartenalter entwachsen, mithilfe einer Wahrheitstafel zeigen kannst. Dein Vater hat "wenn dann" gesagt, du hast aber "genau dann, wenn" verstanden...

Etwas Wahres kann aus etwas Falschem folgen

Die Gleichung $0 = 1$ ist nach allem, was wir wissen, falsch. Nun multiplizierst du beide Seiten der Gleichung mit $0$ und erhältst $0 = 0$ . Diese Gleichung ist zweifellos wahr. Muss dann nicht $0 = 1$ auch wahr gewesen sein? Nein! Denn aus $A \to B$ folgt nicht zwangsläufig $B \to A$ . Oder anders gesagt: Die Aussage

$(A \to B) \to (B \to A)$

ist keine Tautologie! Wie du mithilfe einer Wahrheitstafel leicht zeigen kannst...

Wenn du also in mathematischen Beweise irgendwelche Gleichungen schrittweise umformst, achte darauf, dass du nur äquivalente Umformungen vornimmst - dass du also $A \Leftrightarrow B \Leftrightarrow C . . .$ zeigst. Wenn dann am Ende etwas Wahres herauskommt, dann muss am Anfang der Schlusskette auch etwas Wahres gestanden haben.

Aufgaben

Laden

Dieses Werk steht unter der freien Lizenz
CC BY-SA 4.0 → Was bedeutet das? serlo.org