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" $x<5\Rightarrow x<6$ gültig ist, musst du das Konzept der Aussageformen verwenden - du kannst ja nicht feststellen, ob $x<5$ eine wahre Aussage ist, weil darin die Variable $x$ 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)$

• $3+9<4(f)$

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

• $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}$ und ${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=2$

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

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

$\neg A$ nennt man Verneinung oder Negation von $A$.

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

Dabei gelten die Regeln:

• Ist $A$ wahr, so ist $\neg A$ falsch.

• Ist $A$ falsch, so ist $\neg A$ wahr.

• $\neg (\neg A)$ hat denselben Wahrheitswert wie $A$

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

Beispiele

• Ist A die wahre Aussage "$6$ ist durch $3$ teilbar", so ist $\neg A$ die falsche Aussage "Es ist nicht so, dass $6$ durch $3$ teilbar ist". Das lässt sich auch als "$6$ ist nicht durch $3$ teilbar" formulieren.

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

• Ist $A$ die (falsche) Aussage "Alle Zahlen sind gerade", so ist die Negation von $A$ 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 $A$, was man schon daran merken kann, dass diese Aussage genauso falsch wie $A$ ist.

Mehrere Aussagen lassen sich durch ein logisches "Und" (Symbol: $\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 B$ ist schon falsch, wenn auch nur eine der beiden Aussagen $A$ und $B$ falsch ist.

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

Für $A$: "$5<7$" und $B$: "$5$ ist ungerade" kann man $A\wedge B$ formulieren als "5 ist kleiner als $7$ und ungerade". Da $A$ und $B$ wahr sind, ist auch $A\wedge B$ wahr.

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

"Sie trank ihr Glas leer und ging".

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

Weitere Beispiele:

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

• Analog bedeutet $3<\pi <4$ genauer $(3<\pi )\wedge (\pi <4)$ - eine wahre Aussage, da beide Teile wahr sind.

• $(1<2)\wedge (4<3)$ ist falsch, da der zweite Teil falsch ist.

Rechenregeln

Es gilt das Assoziativ- und das Kommutativgesetz:

$A\wedge B$ und $B\wedge A$ haben denselben Wahrheitswert

$(A\wedge B)\wedge C$ und $A\wedge (B\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$ 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 B$ ist nur dann falsch, wenn $A$ und $B$ beide falsch sind.

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

$(2<3)\vee (4<3)$ 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.

$(3<2)\vee (2^2>5)$ ist falsch, weil beide Klammern falsch sind.

Rechenregeln

Es gilt das Assoziativ- und das Kommutativgesetz:

$A\vee B$ und $B\vee A$ haben denselben Wahrheitswert

$(A\vee B)\vee C$ und $A\vee (B\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)$ und $\left(f\right)$), bei zwei Aussagen vier, bei drei Aussagen acht und allgemein bei $n$ Aussagen $2^n$.

Das ist die einfachste Tabelle, die für $\neg A$:

In der linken Spalte stehen die beiden Möglichkeiten der Wahrheitswerte von $A$, in der rechten die entsprechenden von $\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 $A$ und $B$ aufgeschrieben, in der Spalten unter $A\wedge B$ und $A\vee B$ stehen die entsprechenden Wahrheitswerte der Verknüpfungen.

Man nennt zwei logische Ausdrücke $A$ und $B$ äquivalent (Schreibweise: $A\iff 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$ 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 \neg B)\vee (\neg A\wedge B))\iff (A\vee B)\wedge (\neg A\vee \neg B))$

Als Abkürzung kann man $C:\iff (A\wedge \neg B)\vee (\neg A\wedge B)$ und $D:\iff (A\vee B)\wedge (\neg A\vee \neg B)$ verwenden, du musst also $C\iff D$ nachweisen.

Also sind die Ausdrücke äquivalent.

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

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

Idempotenz

$A\wedge A\iff A$ und $A\vee A\iff A$

Absorbtion

$A\wedge w\iff A$ und $A\vee w\iff w$

$A\wedge f\iff f$ und $A\vee f\iff 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 A$ und $A\wedge B\iff B\wedge A$

Assoziativgesetze

$(A\wedge B)\wedge C\iff A\wedge (B\wedge C)$ und $(A\vee B)\vee C\iff A\vee (B\vee C)$

Weitere Regeln

$A\vee \neg A\iff w$

$A\wedge \neg A\iff 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$. Dann haben wir zwei Aussagen:

$A$: $1$ ist eine Lösung der Gleichung

$B$: $2$ ist eine Lösung der Gleichung

Dann ist - da $A$ und $B$ beide wahr sind, $A\wedge B$ auch wahr.

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

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

Das ist eine der de Morganschen Regeln:

Dafür benutzt man auch das Zeichen $\iff$ (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 B$ falsch ist, dann müssen $\neg A$ und $\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)$ 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=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)$

• Wenn $A$ wahr ist, dann ist die linke Seite nach dem Absorptionsgesetz äquivalent zu $B\vee C$. Aber auch rechts kann man nach dem Absorptionsgesetz $A\vee B$ zu $B$ und $A\vee C$ zu $C$ zusammenziehen, also ist die rechte Seite auch zu $B\vee C$ äquivalent.

• Wenn $A$ falsch ist, dann ist sicher die linke Seite falsch, und weil dann auch $A\wedge B$ und $A\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)$

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

• Wenn $A$ falsch ist, ist nach dem Absorptionsgesetz die linke Seite äquivalent zu $B\wedge C$. Aus dem gleichen Grund ist $A\vee B$ zu $B$ und $A\vee C$ zu $C$ äquivalent, also ist die rechte Seite genau wie die linke zu $B\wedge C$ äquivalent.

Sind $A$ und $B$ Aussagen, so definiert man die Implikation $A\Rightarrow B$ durch $\neg A\vee B$.

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

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

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

Was hat das denn nun mit $\neg A\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$

$(w\Rightarrow A)\iff A$

$(A\Rightarrow f)\iff \neg A$

$(f\Rightarrow A)\iff 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))$