Springe zum Inhalt oder Footer
SerloDie freie Lernplattform

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,...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 aa und bb mit plus:

a+b=ca+b=c

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

a+b=b+aa+b = b + a

Diese Formel gilt immer, ganz egal, mit welchen Zahlenwerten du die Variablen aa und bb 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:

A¬Afalsetruetruefalse\def\arraystretch{1.25} \begin{array}{c|c}A & \lnot A\\\hline{\text{false}} & \text{true}\\\text{true} & \text{false}\end{array}

Anhand der Wahrheitstafel erkennst du: Wenn du die Variable AA mit dem Wahrheitswert false belegst, nimmt die Aussage ¬A\neg A den Wahrheitswert true an. Und wenn du AA mit true belegst, nimmt ¬A\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 00 und 11 zu bezeichnen. Im Folgenden stehen also die Zeichen 00 und 11 nicht für Zahlenwerte, sondern für Wahrheitswerte - die 00 für false und die 11 für true.

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

A¬A0110\def\arraystretch{1.25} \begin{array}{c|c}A & \lnot A\\\hline{0} & 1\\1 & 0\end{array}

Konjunktion - die Und-Verknüpfung

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

ABAB000010100111\def\arraystretch{1.25} \begin{array}{cc|c}A & B & A\land B\\\hline{0} & 0 & 0\\0 & 1 & 0\\1 & 0 & 0\\1 & 1 & 1 \end{array}

Der logische Operator \land bedeutet "und". Die Aussage ABA \land B wird genau dann wahr, wenn AA und BB wahr sind (letzte Zeile in der Wahrheitstafel). Denke daran: 00 bedeutet false (falsch) und 11 bedeutet true (wahr).

Disjunktion - die Oder-Verknüpfung

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

ABAB000011101111\def\arraystretch{1.25} \begin{array}{cc|c}A & B & A\lor B\\\hline{0} & 0 & 0 \\0 & 1 & 1\\1 & 0 & 1\\1 & 1 & 1\end{array}

Der logische Operator \lor bedeutet "oder". Die Aussage ABA \lor B wird genau dann wahr, wenn AA oder BB 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:

ABAB000011101110\def\arraystretch{1.25} \begin{array}{cc|c}A & B & A\oplus B\\\hline{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 AA als auch BB mit dem Wahrheitswert 11, also true, belegt sind, dann nimmt der Ausdruck ABA \oplus B, also "entweder AA oder BB", den Wahrheitswert 00, also false, an.

Implikation - die Wenn-Dann-Beziehung

ABAB001011100111\def\arraystretch{1.25} \begin{array}{cc|c}A & B & A\rightarrow B\\ \hline{0} & 0 & 1\\0 & 1 & 1\\1 & 0 & 0 \\1 & 1 & 1\end{array}

Du kannst die Wenn-Dann-Beziehung verstehen als "wenn AA, dann BB" oder auch als "aus AA folgt BB".

Wenn also AA wahr ist, dann muss auch BB wahr sein, nur dann ist ABA \rightarrow B wahr. Aber was ist, wenn AA falsch ist? Muss dann auch BB falsch sein, damit ABA \rightarrow B wahr ist? Anhand der Wahrheitstafel siehst du, dass dies nicht der Fall ist: Wenn AA falsch ist, ist die Aussage ABA \rightarrow B automatisch wahr, ganz gleich ob BB 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 AA falsch ist, dann muss auch BB falsch sein, damit die Aussage ABA \leftrightarrow B wahr wird - im Gegensatz zur Wenn-Dann-Beziehung.

ABAB001010100111\def\arraystretch{1.25} \begin{array}{cc|c}A & B & A\leftrightarrow B\\\hline{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 ABA \rightarrow B und (¬A)B(\neg A) \lor B gleichwertig sind. Du erkennst dies daran, dass die Spalte der Wahrheitswerte unter den Aussagen jeweils dieselbe ist.

AB¬A(¬A)BAB00111011111000011011\def\arraystretch{1.25} \begin{array}{cc|c|c|c}A & B & \lnot A & (\lnot A) \lor B & A\rightarrow B\\\hline{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:

(AB)  ((¬A)B)(A \rightarrow 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 \rightarrow und dann der Äquivalenzoperator \leftrightarrow.

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

AB  ¬ABA \rightarrow 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 11 (also true) sind. Dies bedeutet, dass die Aussage immer wahr ist - ganz gleich, wie du die Variablen AA und BB 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+aa+b = b+a. Es gilt immer, ganz gleich, wie du die Variablen aa und bb mit Zahlenwerten belegst. Es gilt für alle a,bRa,b \in \mathbb R.

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

ABBAABBA\def\arraystretch{1.25} \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 AA und BB mit Wahrheitswerten. Sie stellen also Tautologien dar, sie sind allgemeingültig. Entsprechendes gilt für die folgenden Gesetze.

Es gelten die Assoziativgesetze:

(AB)CA(BC)(AB)CA(BC)\def\arraystretch{1.25} \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 ABCA \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):

(AB)C(AC)(BC)(AB)C(AC)(BC)\def\arraystretch{1.25} \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:

¬(AB)(¬A)(¬B)¬(AB)(¬A)(¬B)\def\arraystretch{1.25} \begin{array}{ccc} \lnot (A\land B) & \leftrightarrow & (\lnot A)\lor (\lnot B)\\ \lnot (A\lor B) & \leftrightarrow & (\lnot A)\land (\lnot B) \end{array}

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

AAAAAA¬(¬A)A\def\arraystretch{1.25} \begin{array}{ccc} A \land A & \leftrightarrow & A\\ A \lor A & \leftrightarrow & A \\\lnot (\lnot A) & \leftrightarrow & A \end{array}

Sehr wichtige Gesetze für mathematische Beweisführungen sind

(AB)(BC)ACTransitivita¨t vonAB¬B¬AKontraposition¬A0AWiderspruch (reductio ad absurdum)\def\arraystretch{1.25} \begin{array}{rcll} (A \rightarrow B)\land (B \rightarrow C) & \rightarrow & A \rightarrow C & \text{Transitivität von} \rightarrow\\ A \rightarrow B & \leftrightarrow & \neg B \rightarrow \neg A & \text{Kontraposition}\\\lnot A \rightarrow 0 & \leftrightarrow & A &\text{Widerspruch (reductio ad absurdum)}\end{array}

Der Folgt-Pfeil \Rightarrow in mathematischen Beweisen

Ein Ausdruck wie etwa ABBAA \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

Eine Abkürzung dieser Schreibweise ist

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 AA für Anorak und BB für FußBallplatz die Aussage

¬A¬B\neg A \rightarrow \neg B

gleichbedeutend ist mit der Aussage

ABA \rightarrow 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=10 = 1 ist nach allem, was wir wissen, falsch. Nun multiplizierst du beide Seiten der Gleichung mit 00 und erhältst 0=00 = 0. Diese Gleichung ist zweifellos wahr. Muss dann nicht 0=10 = 1 auch wahr gewesen sein? Nein! Denn aus ABA \rightarrow B folgt nicht zwangsläufig BAB \rightarrow A. Oder anders gesagt: Die Aussage

(AB) (BA)(A \rightarrow B) ~\rightarrow (B \rightarrow 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 ABC...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


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