Einer der Grundbausteine, auf denen die modernen Kommunikations- und Informationstechnologien beruhen, ist Logik. Daher ist es höchst empfehlenswert, zumindest einen groben Blick auf die mathematische Logik zu werfen.

In diesem Kurs lernst du, dass eine Aussage nicht zwingend immer nur zum Deutschunterricht oder einer Gerichtsverhandlung gehört. Du untersuchst, ob Kombinationen oder Veränderungen von Aussagen gültig sind. Dieser Kurs bietet dabei nur einen kurzen und einfachen Einstieg in die einfachen Bausteine.

Insbesondere wirst du in diesem Kurs zunächst nur Aussagen kennenlernen, das sind Behauptungen, deren Wahrheitsgehalt feststellbar ist.

In manchen Situationen ist das nicht ausreichend: willst du z.B. feststellen, ob der "Schluss" gültig ist, musst du das Konzept der Aussageformen verwenden - du kannst ja nicht feststellen, ob eine wahre Aussage ist, weil darin die Variable $xx$ enthalten ist.

Eine kurze Einführung in Aussageformen findest du in den letzten Kapiteln des Kurses, eine ausführliche Diskussion dieses Themas in Grundlagen der Mathematik.

Hier lernst du, verschiedene Aussagen zu kombinieren und den Wahrheitsgehalt der Kombination abhängig von den Wahrheitsgehalten der einzelnen Teilaussagen zu bestimmen.

In der Logik geht es darum, verschiedene Aussagen zu kombinieren.

Daher wird der zentrale Begriff der Aussage erklärt:

Das bedeutet, dass jeder Aussage genau einer der Wahrheitswerte wahr oder falsch zugeordnet werden kann. Dabei kommt es nicht darauf an, dass der Wahrheitswert direkt ersichtlich ist, sondern nur, dass dies prinzipiell möglich ist.

Beispiele

• $1+1=1(w)1+1=1\backslash quad\; (w)$

• $f:x\mapsto x^{3}f:x\backslash mapsto\; x^3$ ist streng monoton steigend $(w)(w)$

• $3^{100}>{1000}^{16}3^\{100\}>1000^\{16\}$

Der vierten Aussage kann man nicht unbedingt direkt einen Wahrheitswert zuordnen. Es ist aber prinzipiell möglich: es ist $3^{100}\approx 5\cdot {10}^{47}3^\{100\}\backslash approx\; 5\backslash cdot\; 10^\{47\}$ und ${1000}^{16}={10}^{48}1000^\{16\}=10^\{48\}$. Die Aussage ist also falsch.

Ein Gegenbeispiel ist "Pudding schmeckt gut", weil der Wahrheitsgehalt hiervon nicht objektiv bestimmbar ist.

Aussagen werden oft durch Großbuchstaben bezeichnet, also z.B.

$A:1+1=2A:\backslash ,\; 1+1=2$

Eine Aussage lässt sich einfach verneinen (man sagt auch "negieren"). Sprachlich geschieht das meistens durch das Wort "nicht":

$A:A:$ "Es regnet." wird nach der Verneinung zu $\mathrm{\neg }A\backslash neg\; A$ (oder auch $\bar{A}\backslash overline\{A\}$): "Es regnet nicht."

$\mathrm{\neg }A\backslash neg\; A$ nennt man Verneinung oder Negation von $AA$.

Das, was vorher gegolten hat, gilt jetzt genau nicht mehr. In Zweifelsfällen ist es oft am sichersten, der Aussage $AA$ den Satzteil "Es ist nicht so, dass. . . " voranzustellen.

Dabei gelten die Regeln:

• Ist $AA$ wahr, so ist $\mathrm{\neg }A\backslash neg\; A$ falsch.

• Ist $AA$ falsch, so ist $\mathrm{\neg }A\backslash neg\; A$ wahr.

• $\mathrm{\neg }(\mathrm{\neg }A)\backslash neg(\backslash neg\; A)$ hat denselben Wahrheitswert wie $AA$

Die dritte Regel hat den Namen "Gesetz der doppelten Negation".

Beispiele

• Ist A die wahre Aussage "$66$ ist durch $33$ teilbar", so ist $\mathrm{\neg }A\backslash neg\; A$ die falsche Aussage "Es ist nicht so, dass $66$ durch $33$ teilbar ist". Das lässt sich auch als "$66$ ist nicht durch $33$ teilbar" formulieren.

• Die Negation von "$55$ ist eine gerade Zahl" ist "$55$ ist eine ungerade Zahl".

• Ist $AA$ die (falsche) Aussage "Alle Zahlen sind gerade", so ist die Negation von $AA$ zunächst "Es ist nicht so, dass alle Zahlen gerade sind". Das kannst du zu "Es gibt mindestens eine ungerade Zahl" umformulieren. Die Aussage "Alle Zahlen sind ungerade" ist nicht die Negation von $AA$, was man schon daran merken kann, dass diese Aussage genauso falsch wie $AA$ ist.

Mehrere Aussagen lassen sich durch ein logisches "Und" (Symbol: $\wedge \backslash wedge$) miteinander verknüpfen. Das logische Und bedeutet dabei eigentlich "und gleichzeitig". Damit der Ausdruck als wahr ausgewertet wird, muss also jede der Aussagen wahr sein.

Anders formuliert: Die Aussageverknüpfung $A\wedge BA\backslash wedge\; B$ ist schon falsch, wenn auch nur eine der beiden Aussagen $AA$ und $BB$ falsch ist.

Die Aussageverknüpfung "Und" heißt auch Konjunktion.

Für $AA$: "" und $BB$: "$55$ ist ungerade" kann man $A\wedge BA\backslash wedge\; B$ formulieren als "5 ist kleiner als $77$ und ungerade". Da $AA$ und $BB$ wahr sind, ist auch $A\wedge BA\backslash wedge\; B$ wahr.

In der Umgangssprache bezeichnet "und" oft eine zeitliche Abfolge:

"Sie trank ihr Glas leer und ging".

Mathematisch bedeutet $A\wedge BA\backslash wedge\; B$ das gleichzeitige Erfülltsein der beiden Aussagen.

Weitere Beispiele:

• $\mathbb{N}\subset \mathbb{Q}\subset \mathbb{R}\backslash mathbb\{N\}\backslash subset\backslash mathbb\{Q\}\backslash subset\backslash mathbb\{R\}$ ist die (wahre) Aussage $(\mathbb{N}\subset \mathbb{Q})\wedge (\mathbb{Q}\subset \mathbb{R})(\backslash mathbb\{N\}\backslash subset\backslash mathbb\{Q\})\backslash wedge(\backslash mathbb\{Q\}\backslash subset\backslash mathbb\{R\})$

• Analog bedeutet genauer - eine wahre Aussage, da beide Teile wahr sind.

• ist falsch, da der zweite Teil falsch ist.

Rechenregeln

Es gilt das Assoziativ- und das Kommutativgesetz:

$A\wedge BA\backslash wedge\; B$ und $B\wedge AB\backslash wedge\; A$ haben denselben Wahrheitswert

$(A\wedge B)\wedge C(A\backslash wedge\; B)\backslash wedge\; C$ und $A\wedge (B\wedge C)A\backslash wedge\; (B\backslash wedge\; C)$ haben denselben Wahrheitswert. Diese Regel überträgt sich natürlich sofort auf mehr als drei Aussagen: Eine Und-Kombination von mehreren Aussagen ist nur dann wahr, wenn alle Aussagen wahr sind. Ist auch nur eine der Aussagen falsch, ist auch die Kombination falsch.

Das logische "Oder" $\vee \backslash vee$ für zwei Aussagen kannst du dir vorstellen als: entweder die eine oder die andere oder beide Aussagen sind erfüllt. Es muss also mindestens eine der beteiligten Aussagen gelten, damit der Ausdruck als wahr gewertet werden kann.

Anders formuliert: die Verknüpfung $A\vee BA\backslash vee\; B$ ist nur dann falsch, wenn $AA$ und $BB$ beide falsch sind.

Die Aussageverknüpfung "Oder" heißt auch Disjunktion.

ist wahr, da der erste Teil wahr ist. Dass der zweite Teil falsch ist, ändert nichts.

Die (nicht ganz so mathematische) Aussage "Sein oder nicht Sein" ist also unproblematisch, weil sie immer wahr ist.

ist falsch, weil beide Klammern falsch sind.

Rechenregeln

Es gilt das Assoziativ- und das Kommutativgesetz:

$A\vee BA\backslash vee\; B$ und $B\vee AB\backslash vee\; A$ haben denselben Wahrheitswert

$(A\vee B)\vee C(A\backslash vee\; B)\backslash vee\; C$ und $A\vee (B\vee C)A\backslash vee\; (B\backslash vee\; C)$ haben denselben Wahrheitswert. Diese Regel überträgt sich natürlich sofort auf mehr als drei Aussagen: eine Oder-Verknüpfung ist wahr, wenn mindestens eine der Aussagen wahr ist. Anders formuliert: eine Oder-Verknüpfung ist nur dann falsch, wenn alle Aussagen falsch sind.

Um dir einen Überblick über die Bedeutung von Aussagekombinationen zu verschaffen, sind Wahrheitswerttabellen ein gutes Mittel.

Dazu schreibst du (möglichst systematisch) alle möglichen Wahrheitswerte der beteiligten Aussagen in eine Spalte und untersuchst den Wahrheitswert einer Kombination.

Je nach Anzahl der Aussagen musst du eine passende Anzahl von Fällen unterscheiden. Bei einer Aussage sind es zwei (es gibt ja nur $\left(w\right)\backslash left(w\backslash right)$ und $\left(f\right)\backslash left(f\backslash right)\backslash$), bei zwei Aussagen vier, bei drei Aussagen acht und allgemein bei $nn$ Aussagen $2^{n}2^n$.

Das ist die einfachste Tabelle, die für $\mathrm{\neg }A\backslash neg\; A$:

In der linken Spalte stehen die beiden Möglichkeiten der Wahrheitswerte von $AA$, in der rechten die entsprechenden von $\mathrm{\neg }A\backslash neg\; A$.

Wahrheitswerttabellen haben aber den Vorteil, dass man mehrere Kombinationen gleichzeitig untersuchen kann. Das wird sofort mit "Und" und "Oder" ausprobiert:

Links sind alle Kombinationen der möglichen Wahrheitswerte von $AA$ und $BB$ aufgeschrieben, in der Spalten unter $A\wedge BA\backslash wedge\; B$ und $A\vee BA\backslash vee\; B$ stehen die entsprechenden Wahrheitswerte der Verknüpfungen.

Man nennt zwei logische Ausdrücke $AA$ und $BB$ äquivalent (Schreibweise: $A\iff BA\backslash Leftrightarrow\; B$), wenn beide wahr oder beide falsch sind.

Zwei Aussageverknüpfungen nennt man äquivalent, wenn der Wahrheitswert der Verknüpfungen für jede Kombination der Wahrheitswerte der einzelnen beteiligten Aussagen gleich ist. Als Schreibweise wird wieder $\iff \backslash Leftrightarrow$ verwendet.

Die Äquivalenz von Aussageverknüpfungen kannst du mit Wahrheitswerttabellen nachweisen. Wenn du alle Möglichkeiten der einzelnen Wahrheitswerte auflistest und die fraglichen Ausdrücke immer denselben Wahrheitswert haben, sind sie äquivalent.

Eine andere Möglichkeit ist die Verwendung von logischen Regeln wie den de Morganschen Regeln oder der Distributivgesetze.

Beispiel: $((A\wedge \mathrm{\neg }B)\vee (\mathrm{\neg }A\wedge B))\iff (A\vee B)\wedge (\mathrm{\neg }A\vee \mathrm{\neg }B))\backslash left((A\backslash wedge\; \backslash neg\; B)\backslash vee(\backslash neg\; A\backslash wedge\; B)\backslash right)\backslash Leftrightarrow\backslash left(A\backslash vee\; B)\backslash wedge(\backslash neg\; A\backslash vee\; \backslash neg\; B)\backslash right)$

Als Abkürzung kann man $C:\iff (A\wedge \mathrm{\neg }B)\vee (\mathrm{\neg }A\wedge B)C:\backslash Leftrightarrow\; (A\backslash wedge\backslash neg\; B)\backslash vee(\backslash neg\; A\backslash wedge\; B)$ und $D:\iff (A\vee B)\wedge (\mathrm{\neg }A\vee \mathrm{\neg }B)D:\backslash Leftrightarrow\; (A\backslash vee\; B)\backslash wedge(\backslash neg\; A\backslash vee\backslash neg\; B)$ verwenden, du musst also $C\iff DC\backslash Leftrightarrow\; D$ nachweisen.

Also sind die Ausdrücke äquivalent.

Diese Verknüpfung ist also genau dann wahr, wenn eine der Aussagen $AA$ und $BB$ wahr sind, aber nicht beide.

Jetzt kannst du einfache Regeln aufstellen. $ww$ soll dabei eine wahre, $ff$ eine falsche Aussage bedeuten.

Idempotenz

$A\wedge A\iff AA\backslash wedge\; A\backslash Leftrightarrow\; A$ und $A\vee A\iff AA\backslash vee\; A\backslash Leftrightarrow\; A$

Absorbtion

$A\wedge w\iff AA\backslash wedge\; w\backslash Leftrightarrow\; A$ und $A\vee w\iff wA\backslash vee\; w\backslash Leftrightarrow\; w$

$A\wedge f\iff fA\backslash wedge\; f\backslash Leftrightarrow\; f$ und $A\vee f\iff AA\backslash vee\; f\backslash Leftrightarrow\; A$

Diese Regeln kannst du direkt einsehen, aber auch zur Übung mit einer Wahrheitswerttabelle beweisen.

Diese Regeln kennst du schon, sie sind hier nur zur Vollständigkeit noch einmal aufgeschrieben:

Kommutativgesetze

$A\vee B\iff B\vee AA\backslash vee\; B\; \backslash Leftrightarrow\; B\; \backslash vee\; A$ und $A\wedge B\iff B\wedge AA\backslash wedge\; B\; \backslash Leftrightarrow\; B\; \backslash wedge\; A$

Assoziativgesetze

$(A\wedge B)\wedge C\iff A\wedge (B\wedge C)(A\backslash wedge\; B)\backslash wedge\; C\; \backslash Leftrightarrow\; A\; \backslash wedge\; (B\backslash wedge\; C)$ und $(A\vee B)\vee C\iff A\vee (B\vee C)(A\backslash vee\; B)\backslash vee\; C\; \backslash Leftrightarrow\; A\; \backslash vee\; (B\backslash vee\; C)$

Weitere Regeln

$A\vee \mathrm{\neg }A\iff wA\backslash vee\; \backslash neg\; A\; \backslash Leftrightarrow\; w$

$A\wedge \mathrm{\neg }A\iff fA\backslash wedge\; \backslash neg\; A\; \backslash Leftrightarrow\; f$

Was bedeutet es, wenn man eine "Und"-Aussage negiert? Probiere das an einem Beispiel aus und nimm die Gleichung $(x-1)(x-2)=0(x-1)(x-2)=0$. Dann haben wir zwei Aussagen:

$AA$: $11$ ist eine Lösung der Gleichung

$BB$: $22$ ist eine Lösung der Gleichung

Dann ist - da $AA$ und $BB$ beide wahr sind, $A\wedge BA\backslash wedge\; B$ auch wahr.

Was würde es bedeuten, wenn $A\wedge BA\backslash wedge\; B$ falsch wäre? Dann müsste entweder $11$ keine Lösung sein oder $22$ ist keine Lösung.

Also könnten $AA$ und $BB$ nicht gleichzeitig gelten - daher muss mindestens eine der Aussagen falsch sein. Nach den Regeln der Negation heißt das, dass entweder $\mathrm{\neg }A\backslash neg\; A$ oder $\mathrm{\neg }B\backslash neg\; B$ wahr sein muss, also $\mathrm{\neg }A\vee \mathrm{\neg }B\backslash neg\; A\; \backslash vee\; \backslash neg\; B$.

Das ist eine der de Morganschen Regeln:

Dafür benutzt man auch das Zeichen $\iff \backslash Leftrightarrow$ (die genaue Bedeutung wird im Abschnitt über Äquivalenz erklärt):

Die andere de Morgansche Regel ist

Diese Regel kann man so erklären: wenn $A\vee BA\backslash vee\; B$ falsch ist, dann müssen $\mathrm{\neg }A\backslash neg\; A$ und $\mathrm{\neg }B\backslash neg\; B$ wahr sein.

Zu kompliziert gedacht? Dafür haben wir ja die Möglichkeit, die Äquivalenz der Ausdrücke mit Wahrheitswerttabellen nachzuprüfen:

Da die roten Spalten übereinstimmen, sind die beiden Ausdrücke äquivalent.

Ähnlich wie bei den Zahlen das Distributivgesetz $a\cdot (b+c)=(a\cdot b)+(a\cdot c)a\backslash cdot(b+c)=(a\backslash cdot\; b)+(a\backslash cdot\; c)$ gilt, gibt es auch für die Logik-Verknüpfungen "Und" und "Oder" je ein Distributivgesetz:

Sicher weißt du schon, wie du die Gültigkeit der Regeln nachprüfen kannst. Es geht natürlich mit einer Wahrheitswerttabelle! Da es drei Aussagen sind, musst du $2^3=82^3=8$ Fälle unterscheiden. Das kannst du in einer Aufgabe nachrechnen.

Diesmal kannst du aber auch anders überlegen und dir dabei die schon bewiesenen Regeln zunutze machen. Los geht es mit

$A\wedge (B\vee C)\iff (A\wedge B)\vee (A\wedge C)A\backslash wedge(B\backslash vee\; C)\backslash Leftrightarrow(A\backslash wedge\; B)\backslash vee(A\backslash wedge\; C)$

• Wenn $AA$ wahr ist, dann ist die linke Seite nach dem Absorptionsgesetz äquivalent zu $B\vee CB\backslash vee\; C$. Aber auch rechts kann man nach dem Absorptionsgesetz $A\vee BA\backslash vee\; B$ zu $BB$ und $A\vee CA\backslash vee\; C$ zu $CC$ zusammenziehen, also ist die rechte Seite auch zu $B\vee CB\backslash vee\; C$ äquivalent.

• Wenn $AA$ falsch ist, dann ist sicher die linke Seite falsch, und weil dann auch $A\wedge BA\backslash wedge\; B$ und $A\wedge CA\backslash wedge\; C$ falsch sind, ist es auch die rechte Seite.

Ganz ähnlich beweist du das zweite Distributivgesetz

$A\vee (B\wedge C)\iff (A\vee B)\wedge (A\vee C)A\backslash vee(B\backslash wedge\; C)\backslash Leftrightarrow\; (A\backslash vee\; B)\backslash wedge\; (A\backslash vee\; C)$

• Wenn $AA$ wahr ist, dann ist die linke Seite wahr, und weil dann auch $A\vee BA\backslash vee\; B$ und $A\vee CA\backslash vee\; C$ wahr sind, ist es auch die rechte Seite.

• Wenn $AA$ falsch ist, ist nach dem Absorptionsgesetz die linke Seite äquivalent zu $B\wedge CB\backslash wedge\; C$. Aus dem gleichen Grund ist $A\vee BA\backslash vee\; B$ zu $BB$ und $A\vee CA\backslash vee\; C$ zu $CC$ äquivalent, also ist die rechte Seite genau wie die linke zu $B\wedge CB\backslash wedge\; C$ äquivalent.

Sind $AA$ und $BB$ Aussagen, so definiert man die Implikation $A\Rightarrow BA\backslash Rightarrow\; B$ durch $\mathrm{\neg }A\vee B\backslash neg\; A\; \backslash vee\; B$.

Die Idee dabei ist so: die Implikation soll bedeuten, dass aus der Aussage $AA$ die Aussage $BB$ folgt, d.h. wenn $AA$ wahr ist, soll auch $BB$ wahr sein. Ist $AA$ falsch, gibt es keine Bedingung an $BB$.

Das bedeutet, dass die Wahrheitswerttabelle von $A\Rightarrow BA\backslash Rightarrow\; B$ so aussieht:

Die ersten beiden Zeilen sagen "Wenn $AA$ wahr ist, ist auch $BB$ wahr und nicht etwa falsch". Die unteren beiden Zeilen sagen "Wenn $AA$ falsch ist, kann $BB$ wahr oder falsch sein, beides ist OK".

Was hat das denn nun mit $\mathrm{\neg }A\vee B\backslash neg\; A\; \backslash vee\; B$ zu tun?

Eine Möglichkeit ist es, eine Wahrheitswerttabelle dazu aufzustellen und zu sehen, dass die Aussageverknüpfungen wirklich äquivalent sind. Eine andere ist die Benutzung der de Morganschen Regeln und der Distributivgesetze.

Einfache Beispiele

$(A\Rightarrow w)\iff w(A\backslash Rightarrow\; w)\backslash Leftrightarrow\; w$

$(w\Rightarrow A)\iff A(w\backslash Rightarrow\; A)\backslash Leftrightarrow\; A$

$(A\Rightarrow f)\iff \mathrm{\neg }A(A\backslash Rightarrow\; f)\backslash Leftrightarrow\; \backslash neg\; A$

$(f\Rightarrow A)\iff w(f\backslash Rightarrow\; A)\backslash Leftrightarrow\; w$

Zusammenhang mit der Äquivalenz

Die Idee ist, dass zwei Aussageverknüpfungen äquivalent sind, wenn jeweils eine aus der anderen folgt:

$(A\iff B)\iff ((A\Rightarrow B)\wedge (B\Rightarrow A))(A\backslash Leftrightarrow\; B)\; \backslash Leftrightarrow\; \backslash Big(\; (A\backslash Rightarrow\; B)\; \backslash wedge\; (B\backslash Rightarrow\; A)\backslash Big)$