Logik

Die (Aussagen-)Logik ist für sämtliche Teilbereiche der Mathematik von grundlegender Bedeutung.

Satz und Aussage

Lässt sich einem Satz A ein Wahrheitswert (w = \text{wahr} oder f = \text{falsch}) eindeutig zuordnen, so wird dieser Satz zu einer Aussage.

Als Darstellungsform für den Wahrheitswert von Aussagen wählt man häufig so genannte „Wahrheitstafeln“. Dabei werden spaltenweise die Wahrheitswerte der in der Kopfzeile angegebenen Aussage(n) aufgelistet.

{\color{white}f}A{\color{white}f}
{\color{white}f}w{\color{white}f}
{\color{white}f}f{\color{white}f}

Beispiele:

  • Der Satz „1 + 2 = 3“ ist eine wahre Aussage.
  • Der Satz „\text{9 ist eine Primzahl}“ ist eine falsche Aussage.
  • Der Satz „\text{Die Donau fließt ins schwarze Meer}“ ist eine wahre Aussage.
  • Der Satz „\text{Es ist spät}“ ist keine Aussage, da ihm kein Wahrheitswert zugeordnet werden kann.

Ein Satz ist auch dann eine Aussage, wenn sein Wahrheitswert zum gegebenen Zeitpunkt nicht feststellbar ist. Beispielsweise handelt es sich bei dem Satz „Am 3. April 1650 regnete es in Berlin.“ ebenfalls um eine Aussage, auch wenn sich ihr Wahrheitswert mit großer Wahrscheinlichkeit nicht mehr feststellen lässt.

Negation einer Aussage

Durch Verneinen einer Aussage A entsteht eine Aussage \neg A, die Negation der Aussage A genannt wird. Da der konkrete Wahrheitswert einer negierten Aussage \neg A stets vom Wahrheitswert der eigentlichen Aussage A abhängt, hat die entsprechende Wahrheitstafel zwei Spalten.

{\color{white}f}A{\color{white}f} {\color{white}f}\neg A{\color{white}f}
{\color{white}f}w{\color{white}f} {\color{white}ff}f{\color{white}f}
{\color{white}f}f{\color{white}f} {\color{white}ff}w{\color{white}f}

Die Negation einer wahren Aussage ist falsch, die einer falschen ist wahr; insbesondere entspricht die doppelte Negation einer Aussage \neg (\neg
A) der ursprünglichen Aussage A.

Beispiele:

  • A: „Die Geraden g und h schneiden sich.“
  • \neg A: „Die Geraden g und h schneiden sich nicht.“
  • \neg (\neg A): „Es ist nicht wahr, dass die Geraden g und h sich nicht schneiden.“

Verknüpfungen von Aussagen

Mit Hilfe von Bindewörtern wie „und“, „oder“, „genau dann, wenn“ usw. lassen sich mehrere (Teil-)Aussagen zu einer zusammengesetzten Aussage verknüpfen. In der Logik lassen sich mit Hilfe der folgenden Aussage-Funktionen zwei (oder mehrere) Aussagen zu einer neuen Aussage formen.

Die Konjunktion

Verknüpft man zwei Aussagen A_1 und A_2 durch das Wort „und“, so entsteht die Konjunktion der Aussagen A_1 und A_2, symbolisch mit A_1 \wedge A_2 bezeichnet.

Wahrheitstafel der Konjunktion
{\color{white}f}A_1{\color{white}f} {\color{white}f}A_2{\color{white}f} {\color{white}f}A_1 \wedge A_2{\color{white}f}
{\color{white}f}w{\color{white}f} {\color{white}f}w{\color{white}f} {\color{white}fff}w{\color{white}f}
{\color{white}f}w{\color{white}f} {\color{white}f}f{\color{white}f} {\color{white}fff}f{\color{white}f}
{\color{white}f}f{\color{white}f} {\color{white}f}w{\color{white}f} {\color{white}fff}f{\color{white}f}
{\color{white}f}f{\color{white}f} {\color{white}f}f{\color{white}f} {\color{white}fff}f{\color{white}f}

Eine Konjunktion zweier Aussagen ist somit nur wahr, wenn beide (Teil-)Aussagen wahr sind.

Beispiele:

  • Die Konjunktion der wahren Aussage A_18 ist eine gerade Zahl“ mit der falschen Aussage A_28 ist durch 3 teilbar“ ist die falsche Aussage A_1 \wedge A_2 : „8 ist eine gerade Zahl und durch 3 teilbar“.
  • Die falsche Aussage „Der Mars ist ein Gasplanet und hat eine größere Masse als die Erde“ ist eine Konjunktion der falschen Aussagen „Der Mars ist ein Gasplanet“ und „Der Mars hat eine größere Masse als die Erde“.

Die Adjunktion

Verknüpft man zwei Aussagen A_1 und A_2 durch das Wort „oder“, so entsteht die Adjunktion der Aussagen A_1 und A_2, symbolisch mit A_1 \vee A_2 bezeichnet.

Wahrheitstafel der Adjunktion
{\color{white}f}A_1{\color{white}f} {\color{white}f}A_2{\color{white}f} {\color{white}f}A_1 \vee A_2{\color{white}f}
{\color{white}f}w{\color{white}f} {\color{white}f}w{\color{white}f} {\color{white}fff}w{\color{white}f}
{\color{white}f}w{\color{white}f} {\color{white}f}f{\color{white}f} {\color{white}fff}w{\color{white}f}
{\color{white}f}f{\color{white}f} {\color{white}f}w{\color{white}f} {\color{white}fff}w{\color{white}f}
{\color{white}f}f{\color{white}f} {\color{white}f}f{\color{white}f} {\color{white}fff}f{\color{white}f}

Die Adjunktion ist somit wahr, wenn eine der beiden Aussagen wahr ist (oder beide wahr sind).

Beispiele:

  • Die Adjunktion der wahren Aussage 0 < 1 und der falschen Aussage 0 = 1 ist die wahre Aussage 0 \le 1.
  • Die wahre Aussage: „Entweder ist die Erde ein Würfel oder die Sonne ist ein Stern“ ist eine Adjunktion der falschen Aussage: „Die Erde ist ein Würfel“ und der wahren Aussage: „Die Sonne ist ein Stern“.

Die Implikation

Verknüpft man zwei Aussagen A_1 und A_2 durch das Wort „dann“, so entsteht die Implikation der Aussagen A_1 und A_2, symbolisch mit A_1 \Rightarrow A_2 bezeichnet.

Wahrheitstafel der Implikation
{\color{white}f}A_1{\color{white}f} {\color{white}f}A_2{\color{white}f} {\color{white}f}A_1 \Rightarrow A_2{\color{white}f}
{\color{white}f}w{\color{white}f} {\color{white}f}w{\color{white}f} {\color{white}fff}w{\color{white}f}
{\color{white}f}w{\color{white}f} {\color{white}f}f{\color{white}f} {\color{white}fff}f{\color{white}f}
{\color{white}f}f{\color{white}f} {\color{white}f}w{\color{white}f} {\color{white}fff}w{\color{white}f}
{\color{white}f}f{\color{white}f} {\color{white}f}f{\color{white}f} {\color{white}fff}w{\color{white}f}

Die Implikation ist wahr, wenn beide Aussagen A_1 und A2 wahr sind oder wenn die erste Aussage A_1 falsch ist.[1] Formal erhält man eine identische Wahrheitstafel, wenn man die Implikation (\neg A_2) \Rightarrow (\neg A_1) bildet.[2][3]

Beispiele:

  • Die Aussage „Wenn 2 < 1 ist, dann ist 3 < 2“ ist wahr, obwohl sie eine Implikation zweier falscher (Teil-)Aussagen ist.
  • Die Implikation der wahren Aussage „Die Lichtgeschwindigkeit beträgt annähernd \unit[300\,000]{km/s}“ und der falschen Aussage „Die Schallgeschwindigkeit ist größer als die Lichtgeschwindigkeit“ ist die falsche Aussage „Die Schallgeschwindigkeit beträgt mehr als \unit[300\,000]{km/s}„.

Äquivalenz zweier Aussagen

Verknüpft man zwei Aussagen A_1 und A_2 durch die Wortkombination „dann, und nur dann“, so entsteht die Äquivalenz der Aussagen A_1 und A_2, symbolisch mit A2 \Leftrightarrow A_2 bezeichnet.

Wahrheitstafel der Äquivalenz
{\color{white}f}A_1{\color{white}f} {\color{white}f}A_2{\color{white}f} {\color{white}f}A_1 \Leftrightarrow A_2{\color{white}f}
{\color{white}f}w{\color{white}f} {\color{white}f}w{\color{white}f} {\color{white}fff}w{\color{white}f}
{\color{white}f}w{\color{white}f} {\color{white}f}f{\color{white}f} {\color{white}fff}f{\color{white}f}
{\color{white}f}f{\color{white}f} {\color{white}f}w{\color{white}f} {\color{white}fff}f{\color{white}f}
{\color{white}f}f{\color{white}f} {\color{white}f}f{\color{white}f} {\color{white}fff}w{\color{white}f}

Die Äquivalenz zweier Teilaussagen ist nur wahr, wenn entweder beide Teilaussagen wahr oder beide falsch sind.[4]

Beispiele:

  • Die wahre Aussage „Im rechtwinkligen Dreieck gilt der Höhensatz“ äquivalent verknüpft mit der falschen Aussage „Im rechtwinkligen Dreieck sind alle Seiten gleich lang“ ergibt die falsche Aussage „Im rechtwinkligen Dreieck sind dann und nur dann alle Seiten gleich lang, wenn der Höhensatz gilt“.
  • Die Äquivalenzverknüpfung der falschen Aussage „Das Kilogramm ist eine Längeneinheit“ mit der wahren Aussage „Tausend Meter ergeben einen Kilometer“ ist die falsche Aussage „Das Kilogramm ist dann und nur dann eine Längeneinheit, wenn tausend Meter einen Kilometer ergeben“.

Kontravalenz zweier Aussagen

Verknüpft man zwei Aussagen A_1 und A_2 durch das Wort „entweder oder“ im ausschließenden Sinn, so entsteht die Kontravalenz der Aussagen A_1 und A_2, mit mit A_1 \dot{\vee} A_2 bezeichnet.

Wahrheitstafel der Kontravalenz
{\color{white}f}A_1{\color{white}f} {\color{white}f}A_2{\color{white}f} {\color{white}f}A_1 \, \dot{\vee} \, A_2{\color{white}f}
{\color{white}f}w{\color{white}f} {\color{white}f}w{\color{white}f} {\color{white}fff}f{\color{white}f}
{\color{white}f}w{\color{white}f} {\color{white}f}f{\color{white}f} {\color{white}fff}w{\color{white}f}
{\color{white}f}f{\color{white}f} {\color{white}f}w{\color{white}f} {\color{white}fff}w{\color{white}f}
{\color{white}f}f{\color{white}f} {\color{white}f}f{\color{white}f} {\color{white}fff}f{\color{white}f}

Die Kontravalenz zweier Teilaussagen ist nur dann wahr, wenn genau eine der beiden (Teil-)Aussagen wahr ist. Damit ist sie formal, wie ihr Name bereits andeutet, mit der Negation der Äquivalenz identisch.

Beispiel:

  • Verknüpft man die wahre Aussage „Der Zug fährt nach München“ kontravalent mit der falschen Aussage „Der Zug fährt nach Frankfurt“, so ergibt sich die wahre Aussage „Der Zug fährt entweder nach München oder nach Frankfurt“.

Regeln zu den Aussagenverknüpfungen

Zwischen den Aussagen beziehungsweise ihren Verknüpfungen sind folgende Äquivalenzen definiert, von denen einige eine formale Ähnlichkeit mit den Regeln für das Rechnen mit Zahlen haben:

  • Kommutativgesetz:

A_1 \wedge A_2 \Leftrightarrow A_2 \wedge A_1 \\
A_1 \vee A_2 \Leftrightarrow A_2 \vee A_1

  • Assoziativgesetz:

(A_1 \wedge A_2) \wedge  A_3 \Leftrightarrow A_1 \wedge  (A_2 \wedge A_3) \\
(A_1 \vee A_2) \vee  A_3 \Leftrightarrow A_1 \vee  (A_2 \vee A_3)

  • Distributivgesetz:

A_1 \wedge (A_2 \vee A_3) \Leftrightarrow (A_1 \wedge A_2) \vee (A_2 \wedge
A_3) \\
A_1 \vee (A_2 \wedge A_3) \Leftrightarrow (A_1 \vee A_2) \wedge (A_2 \vee
A_3)

Hinzu kommen folgende Regeln, die bisweilen für Beweisverfahren sowie in der Informatik nützlich sind:

  • Regeln von de Morgan:

\neg (A_1 \wedge A_2) \Leftrightarrow (\neg A_1) \vee (\neg A_2) \\
\neg (A_1 \vee A_2)   \Leftrightarrow (\neg A_1) \wedge (\neg A_2)

  • Absorptionsgesetz:

A_1 \wedge (A_1 \vee A_2) \Leftrightarrow A_1 \\
A_1 \vee (A_1 \wedge A_2) \Leftrightarrow A_1

  • Idempotenzgesetz:

A \wedge  A \Leftrightarrow  A\\
A \vee    A \Leftrightarrow  A\\

  • Komplementgesetz:

A_1 \vee (\neg A_2 \wedge A_2 ) \Leftrightarrow A \\
A_1  \wedge (\neg A_2  \vee A_2 ) \Leftrightarrow A

Dabei wird die Verknüpfung (\neg A) \vee A auch „Tautologie“ genannt; sie ist stets wahr.[5]

Variablen, Terme und Aussageformen

Eine Variable ist ein Symbol für ein beliebiges Element aus einer vorgegebenen Grundmenge. Darüber hinaus gelten für das Rechnen mit Variablen keine besonderen Regeln oder Gesetze.

Ein Term ist eine Bezeichnung zum einen für ein einzelnes mathematisches Objekt (beispielsweise \pm \frac{1}{2} ,\, \pi ,\, \sqrt{3}), zum anderen auch für eine Aneinanderreihung mehrerer Konstanten, Variablen, Klammern und Rechenoperatoren (beispielsweise 2 \cdot (x^2 - 1) ,\; x \in \mathbb{R}).[6] Terme enthalten allerdings kein Relationszeichen, sie sind somit weder wahr noch falsch.

Eine Aussageform enthält neben (mindestens) einer Variablen und (mindestens) einem Term stets ein Relationszeichen – beispielsweise x \ge 1 oder x_1 \cdot x_2 = 0. Um allerdings einer Aussageform auch einen Wahrheitswert zuordnen zu können, müssen zunächst alle auftretenden Variablen durch konkrete Elemente aus der Grundmenge ersetzt werden. Ebenso wie Aussagen lassen sich mehrere Aussageformen durch logische Verknüpfungen zu neuen Aussageformen kombinieren.

Die Abhängigkeit einer Aussageform von einer oder mehreren Variablen x_1
,\, x_2 ,\, \ldots wird in der Form A(x_1 ,\, x_2 ,\, \ldots ) ausgedrückt. Dabei lassen sich Aussageformen in drei Arten unterteilen:

  • Wird eine von einer Variablen x abhängige Aussageform A(x) für jedes beliebige x aus einer Grundmenge X erfüllt, so bezeichnet man die Aussageform A(x) als allgemeingültig bezüglich X.
  • Existiert mindestens ein x aus der Grundmenge X, das die Aussageform A(x) erfüllt, so bezeichnet man die Aussageform A(x) als erfüllbar bezüglich X.
  • Existiert kein x aus der Grundmenge X, das die Aussageform A(x) erfüllt, so bezeichnet man die Aussageform A(x) als unerfüllbar bezüglich X.

Aussageformen werden insbesondere in der Algebra als Gleichungen und Ungleichungen behandelt.

‚Für alle‘ und ‚Es gibt‘

Aussageformen können – neben dem Einsetzen von konkreten Objekten für die auftretenden Variablen – auch auf eine zweite Art und Weise zu Aussagen gemacht werden: Der Quantifizierung.

  • Eine allgemeine Aussageform A(x) wird zu einer „Existenz-Aussage“, wenn folgende Forderung erfüllt ist:

    „Es existiert (mindestens) ein Element x aus der Grundmenge X„, für das die Aussageform A(x) wahr ist.“

    Verkürzend kann eine Existenz-Aussage mit Hilfe des so genannten „Existenz-Quantors“ \exists formuliert werden: Anstelle von „Es existiert (mindestens) ein x“ kann auch kurz \exists x geschrieben werden.

  • Eine allgemeine Aussageform A(x) wird zu einer „Universal-Aussage“, wenn folgende Forderung erfüllt ist:

    „Für jedes Element x aus der Grundmenge X“ ist die Aussageform A(x) wahr.“

    Verkürzend kann eine Universal-Aussage mit Hilfe des so genannten „All-Quantors“ \forall formuliert werden: Anstelle von „Für alle x“ kann auch kurz \forall x geschrieben werden.

Während eine Existenz-Aussage \exists x \!: A(x) wahr ist, wenn die zugrunde liegende Aussageform A(x) auch nur für ein konkretes x erfüllt wird, so kann im umgekehrten Fall eine Universal-Aussage \forall
x \!: A(x) bereits durch den Existenz-Nachweis eines einzigen „Gegenbeispiels“ \exists x \!: \neg A(x) als falsch widerlegt werden.[7][8]

Direkte und indirekte Beweise

Die formalen Regeln der Logik können auch genutzt werden, um mittels bereits als wahr nachgewiesener Aussageformen Schlussfolgerungen auf neue Gesetzmäßigkeiten ziehen zu können. Auf diese Art gewonnene Lehrsätze (auch „Theoreme“ oder kurz „Sätze“ genannt) stellen das Grundgerüst der mathematischen Theorie dar.

Neben bereits bekannten Lehrsätzen werden auch so genannte Definitionen genutzt, um neue Sätze beweisen zu können. Beim Definieren wird ein Begriff durch die Festlegung wesentlicher, gemeinsamer Merkmale eindeutig bestimmt und von anderen Begriffen unterschieden. Definitionen sind weder wahr noch falsch, sie dienen vielmehr als Abkürzungen für unhandliche Formulierungen. Als Definitionszeichen für mathematische Terme verwendet man das Zeichen :=, eine Kurzschreibweise für „ist nach Definition gleich“.

Für die eigentlichen „Beweise“ sind u.a. folgende aussagenlogische Schlussregeln möglich:

  • Schlussfolgerung aus einer Implikation:
    Gilt eine Aussage A_1 und ist die Implikation A_1 \Rightarrow
A_2 wahr, so ist auch A_2 eine wahre Aussage. Kurz formuliert ist somit der aussagenlogische Ausdruck [ A_1 \wedge (A_1 \Rightarrow
A_2)] \Rightarrow A_2 allgemeingültig.
  • Schlussfolgerung aus einer Negation:
    Der aussagenlogische Ausdruck \neg (\neg A) \Rightarrow A ist allgemeingültig. Eine Aussage kann somit bewiesen werden, indem man die Negation der Aussage widerlegt.

Bei direkten Beweisen wird, ausgehend von gültigen Voraussetzungen und unter Verwendung von zulässigen Schlussregeln, nach endlich vielen Schritten direkt auf die Behauptung gefolgert. Bei indirekten Beweisen hingegen wird die Negation der Behauptung zu den Voraussetzungen hinzugenommen.

Die vollständige Induktion

Die vollständige Induktion ist ein häufig genutztes Verfahren zum direkten Beweisen einer Aussage. Die logische Schlussfolgerung beruht dabei auf drei Schritten:

  1. Mit dem „Induktionsanfang“ wird gezeigt, dass eine Aussageform A(x) für ein (beliebig wählbaren) Wert x = n gültig ist.
  2. Die „Induktionsannahme“ besteht darin, dass die Aussageform A(x) für ein bestimmtes n gültig ist.
  3. Mit dem „Induktionsschluss“, einem „Beweis im Beweis“, wird gezeigt, dass aus der Gültigkeit der Aussage A(n) auch die Gültigkeit der Aussage A(n + 1 ) folgt, in Kurzschreibweise A(n) \Rightarrow A(n+1).

Beispiel:

  • Mit Hilfe der vollständigen Induktion soll bewiesen werden, dass für alle natürlichen Zahlen n gilt:

    1 + 2 + \ldots + n = \frac{n \cdot (n + 1)}{2}

    1. Induktionsanfang: Für n_0 =1 gilt:

    1 = \frac{1 \cdot 2}{2} = 1 \quad \checkmark

    1. Induktionsannahme: Für eine beliebige Zahl n_0 gilt die Aussageform

    1 + 2 + \ldots n_0 = \frac{n_0
\cdot (n_0 + 1)}{2}

    1. Induktionsschluss: n_0 \Rightarrow n_0  + 1

    1 + 2 + \ldots + n_0 + (n_0 + 1)
 &= \frac{n_0
 \cdot (n_0 + 1)}{2} + (n_0 + 1) \\[4pt]
 &=  \frac{1}{2} \cdot n_0  \cdot (n_0  + 1) + (n_0
 + 1) = (n_0 + 1) \cdot \left( \frac{1}{2} \cdot n_0 + 1 \right) \\[6pt]
 &= (n_0 + 1) \cdot \frac{1}{2} \cdot (n_0 + 2) = \frac{(n
_0 + 1) \cdot (n_0 + 2)}{2} \\[6pt]
 &= \frac{(n_0 + 1) \cdot ((n_0 + 1) + 1)}{2} \quad
 \checkmark

    Aus der Richtigkeit der Aussageform für n_0 folgt somit auch die Richtigkeit der Annahme für n_0 + 1. Somit ist die Aussageform für alle n \ge 1 wahr.


Anmerkungen:

[1]Der letztere Fall wird bisweilen auch als „Ex falso quodlibet“ bezeichnet – aus einer falschen Annahme folgt Beliebiges.
[2]

Die vorschnelle Annahme, dass aus A_1 \Rightarrow A_2 auch (\neg A_1) \Rightarrow (\neg A_2) folge, ist hingegen falsch.

Ein anschauliches Beispiel hierfür ist die Aussage A_1 \Rightarrow
A_2 „Wenn es regnet, dann ist es bewölkt.“ Die Aussage (\neg A_1 )
\Rightarrow (\neg A_2) würde lauten „Wenn es nicht regnet, dann ist es nicht bewölkt“, was offensichtlich falsch ist. Die Aussage (\neg B)
\Rightarrow (\neg A) „Wenn es nicht bewölkt ist, dann regnet es nicht“ ist hingegen richtig.

Man sagt daher auch, dass A_1 notwendig für A_2 sei und dass A_2 hinreichend für A_1 sei.

[3]Es existiert sogar eine dritte Darstellungsweise der Implikation, und zwar (\neg A_1) \vee A_2. Dies lässt anhand der Wahrheitstabelle der Adjunktion überprüfen, indem man für A_1 die jeweils entgegengesetzten Wahrheitswerte annimmt und das Ergebnis der so gebildeten Adjunktion mit der Wahrheitstabelle der Implikation vergleicht.
[4]

Formal erhält man eine identische Wahrheitstafel, wenn man die beiden Implikationen (A_1) \Rightarrow (A_2) und (A_2) \Rightarrow
(A_1) bildet und durch eine Konjunktion miteinander verknüpft. Es gilt also:

(A_1 \Leftrightarrow A_2 ) \Leftrightarrow ( (A_1 \Rightarrow A_2 )
\wedge (A_2 \Rightarrow A_1 ))

[5]Das Gegenteil der Tautologie, die Aussage A \wedge (\neg A), heißt Kontradiktion; sie ist für jede beliebige Aussagen A stets falsch.
[6]Setzt man für die in Termen auftretenden Variablen konkrete mathematische Objekte des Grundbereichs ein, so ergibt sich ein neuer mathematischer Ausdruck; beispielsweise ergibt der Term 8 \cdot x - 10 für x
= 1 den Wert -2.
[7]In Zusammenhang mit den Quantoren \exists und \forall stellt der folgende Doppelpunkt : eine Kurzschreibweise für „so dass gilt:“ beziehungsweise „gilt:“ dar.
[8]Auch kombinierte Quantifizierungs-Aussagen sind möglich, beispielsweise „Für jeden Menschen m existiert ein Tag t, so dass die Aussageform A(m,t) erfüllt ist: m hat am Tag t Geburtstag“. Als Kurzform kann für diese (wahre) Aussage \forall m \;
\exists t \! : A(m,t) geschrieben werden.

Hinweis

Zu diesem Abschnitt gibt es Übungsaufgaben.