Aussagenlogik

Die Aussagenlogik untersucht, wie sich aus einfachen Aussagen durch Wörter wie „und“, „oder“, „nicht“ und „wenn … dann“ neue Aussagen bilden lassen und wann diese neuen Aussagen wahr oder falsch sind. Sie fragt nicht, was eine Aussage inhaltlich bedeutet, sondern nur, ob sie wahr oder falsch ist. Das klingt trocken, ist aber das Fundament jedes mathematischen Beweises und jeder Computerschaltung.

Auf dieser Seite gehst du Schritt für Schritt vor: Was ist überhaupt eine Aussage? Welche Verknüpfungen (Junktoren) gibt es? Wie baust du eine Wahrheitstafel? Dann folgen Tautologien, die Regeln von De Morgan, die Kontraposition und der Unterschied zwischen „notwendig“ und „hinreichend“. Zum Schluss stehen ein Ausblick auf Quantoren, Anwendungen in der Technik, Übungen mit Lösungen und die Geschichte der Logik von Aristoteles bis Boole.

Was ist eine Aussage?

Eine Aussage ist ein Satz, von dem man sinnvoll sagen kann, dass er wahr oder falsch ist. Es muss nicht bekannt sein, welches von beiden zutrifft. Entscheidend ist, dass es genau eines von beiden ist.

• „7 ist eine Primzahl.“ Das ist eine wahre Aussage.
• „Berlin liegt in Frankreich.“ Das ist eine falsche Aussage. Auch falsche Sätze sind Aussagen.
• „2 + 2 = 5.“ Das ist eine falsche Aussage.
• „Jede gerade Zahl größer als 2 ist Summe zweier Primzahlen.“ Das ist die Goldbachsche Vermutung. Bis heute weiß niemand, ob sie stimmt. Es ist trotzdem eine Aussage, denn sie ist entweder wahr oder falsch.

Keine Aussagen sind dagegen:

• Fragen: „Wie spät ist es?“
• Befehle und Ausrufe: „Mach die Tür zu!“, „Hurra!“
• Aussageformen mit einer Variablen: „x + 3 = 7“. Erst wenn du für x eine Zahl einsetzt (oder sagst „für alle x“), entsteht eine Aussage. Für x = 4 ist sie wahr, für x = 5 falsch.
• Selbstbezügliche Sätze wie „Dieser Satz ist falsch.“ Wäre er wahr, wäre er falsch, und umgekehrt. Er hat keinen eindeutigen Wahrheitswert.

Die Junktoren: Aussagen verknüpfen

Mit Junktoren (Verknüpfungszeichen) baust du aus Aussagen neue Aussagen. Der Wahrheitswert der neuen Aussage hängt nur von den Wahrheitswerten der alten ab.

• Negation ¬A („nicht A“): Sie dreht den Wahrheitswert um. Ist A wahr, ist ¬A falsch.
• Konjunktion A ∧ B („A und B“): Sie ist nur wahr, wenn beide wahr sind.
• Disjunktion A ∨ B („A oder B“): Sie ist wahr, wenn mindestens eine der beiden wahr ist.
• Implikation A → B („wenn A, dann B“): Sie ist nur falsch, wenn A wahr und B falsch ist.
• Äquivalenz A ↔ B („A genau dann, wenn B“): Sie ist wahr, wenn beide denselben Wahrheitswert haben.

Das Oder: einschließend, nicht „entweder … oder“

Im Alltag meint „oder“ oft „entweder … oder“: „Du bekommst Eis oder Kuchen.“ Gemeint ist: eins von beiden, nicht beides. In der Logik ist das Oder dagegen einschließend. A ∨ B ist auch dann wahr, wenn beide Aussagen wahr sind. Die Aussage „5 ist ungerade oder 5 ist eine Primzahl“ ist wahr, obwohl beides zutrifft. Das ausschließende „entweder … oder“ gibt es als eigenen Junktor (XOR). Es lässt sich ausdrücken als (A ∨ B) ∧ ¬(A ∧ B).

Die Implikation: Warum aus Falschem alles folgt

Die Implikation A → B verwirrt am meisten, denn sie ist auch dann wahr, wenn A falsch ist. Ein Alltagsbeispiel hilft. Dein Freund verspricht: „Wenn du die Prüfung bestehst, gehen wir ein Eis essen.“ Wann hat er sein Versprechen gebrochen?

• Du bestehst und ihr geht Eis essen: Versprechen gehalten (w).
• Du bestehst, aber es gibt kein Eis: Versprechen gebrochen (f).
• Du bestehst nicht, ihr geht trotzdem Eis essen: Versprechen nicht gebrochen (w). Er hat ja nur gesagt, was bei bestandener Prüfung passiert.
• Du bestehst nicht, es gibt kein Eis: Versprechen nicht gebrochen (w).

Auch ein mathematisches Beispiel zeigt es. Die Aussage „Für alle Zahlen x gilt: Wenn x > 5 ist, dann ist x² > 25“ ist wahr. Trotzdem gibt es Zahlen, bei denen die Voraussetzung falsch ist: Für x = 3 ist x > 5 falsch, und die Folgerung x² = 9 > 25 ist auch falsch. Für x = −10 ist die Voraussetzung falsch, die Folgerung 100 > 25 aber wahr. In beiden Fällen darf die Implikation nicht falsch werden, sonst wäre die allgemeine Aussage falsch. Darum gilt: Aus einer falschen Voraussetzung folgt jede Aussage (lateinisch ex falso quodlibet).

Wahrheitstafeln Schritt für Schritt

Mit einer Wahrheitstafel prüfst du, wann eine zusammengesetzte Aussage wahr ist. Du rechnest sie wie eine Gleichung von innen nach außen. Zuerst werden die Teilaussagen ausgewertet, dann die Verknüpfungen darüber.

Tautologie, Widerspruch und logische Äquivalenz

Manche zusammengesetzte Aussagen haben in jeder Zeile denselben Wahrheitswert:

• Eine Tautologie ist immer wahr, unabhängig von den Wahrheitswerten der Teilaussagen. Beispiel: A ∨ ¬A („Es regnet oder es regnet nicht“).
• Ein Widerspruch ist immer falsch. Beispiel: A ∧ ¬A („Es regnet und es regnet nicht“).

Zwei Aussagen heißen logisch äquivalent (Zeichen ≡), wenn sie in jeder Zeile der Wahrheitstafel denselben Wahrheitswert haben. Dann darfst du eine durch die andere ersetzen. Das ist das wichtigste Werkzeug zum Umformen.

Die Regeln von De Morgan

Wie verneinst du eine „und“- oder „oder“-Aussage? Die Regeln des englischen Mathematikers Augustus De Morgan (1806–1871) sagen es:

• ¬(A ∧ B) ≡ ¬A ∨ ¬B
• ¬(A ∨ B) ≡ ¬A ∧ ¬B

Beim Verneinen wird also aus „und“ ein „oder“ und umgekehrt, und die Teilaussagen werden verneint. Ein Beispiel: „Es regnet und es ist kalt“ ist falsch genau dann, wenn „es regnet nicht oder es ist nicht kalt“ wahr ist. Es genügt, dass eine der beiden Bedingungen fehlt.

Prüfe die erste Regel mit einer Wahrheitstafel. Die Spalten für ¬(A ∧ B) und ¬A ∨ ¬B stimmen in jeder Zeile überein:

Die Verbindung zur Mengenlehre: Aussagen und Mengen folgen denselben Regeln. Dem „und“ entspricht der Schnitt ∩, dem „oder“ die Vereinigung ∪, dem „nicht“ das Komplement. De Morgan gilt daher auch für Mengen: Das Komplement des Schnitts ist die Vereinigung der Komplemente. Die Operationen stehen auf der Seite Mengenlehre, die Diagramme gehen auf John Venn zurück.

Kontraposition und Umkehrung

Aus einer Implikation A → B kannst du zwei verwandte Aussagen bilden:

• die Kontraposition ¬B → ¬A (man dreht die Richtung um und verneint beide Teile),
• die Umkehrung B → A (man dreht nur die Richtung um).

Die Kontraposition ist immer gleichwertig zur ursprünglichen Aussage, die Umkehrung dagegen nicht. Das zeigt die Wahrheitstafel:

Die dritte und die sechste Spalte stimmen in jeder Zeile überein, die siebte (Umkehrung) nicht. Ein Beispiel: „Wenn eine Zahl durch 9 teilbar ist, ist sie durch 3 teilbar“ ist wahr. Die Kontraposition „Wenn eine Zahl nicht durch 3 teilbar ist, ist sie nicht durch 9 teilbar“ ist ebenfalls wahr. Die Umkehrung „Wenn eine Zahl durch 3 teilbar ist, ist sie durch 9 teilbar“ ist dagegen falsch: 6 ist durch 3, aber nicht durch 9 teilbar. Die Teilbarkeitsregeln findest du auf der Seite Ganze Zahlen.

Die Kontraposition ist nicht nur ein Umformungstrick. Sie ist auch ein wichtiger Beweisweg: Manchmal ist es leichter, ¬B → ¬A zu beweisen als A → B. Die Beweisverfahren werden auf der Seite Beweisverfahren erklärt.

Notwendig und hinreichend

Zwei Wörter, die in Mathebüchern ständig vorkommen: Gilt A → B, dann ist

• A hinreichend für B: Es genügt, dass A gilt, damit auch B gilt.
• B notwendig für A: Ohne B kann A nicht gelten.

Gelten beide Richtungen, also A → B und B → A, dann ist A ↔ B wahr: Die Bedingung ist notwendig und hinreichend. Beispiel: n ist durch 6 teilbar genau dann, wenn n durch 2 und durch 3 teilbar ist. Wenn du „genau dann, wenn“ liest, ist die Äquivalenz gemeint, geschrieben auch „gdw.“ oder „⇔“.

Ausblick: Quantoren

Die Aussagenlogik kann den Satz „Alle Primzahlen außer 2 sind ungerade“ nicht ausdrücken, denn sie kennt keine Variablen. Dafür gibt es die Quantoren der Prädikatenlogik:

• ∀ („für alle“): ∀x ∈ ℕ: x² ≥ x. Das ist wahr.
• ∃ („es gibt“): ∃x ∈ ℕ: x + 3 = 7. Das ist wahr (x = 4).

Beim Verneinen vertauschen sich die Quantoren, ähnlich wie bei De Morgan „und“ und „oder“ vertauscht werden:

• ¬(∀x: P(x)) ≡ ∃x: ¬P(x)
• ¬(∃x: P(x)) ≡ ∀x: ¬P(x)

Das Gegenteil von „Alle Schwäne sind weiß“ ist also nicht „Alle Schwäne sind schwarz“, sondern „Es gibt einen Schwan, der nicht weiß ist“. Ein einziges Gegenbeispiel widerlegt eine Allaussage: „Alle Primzahlen sind ungerade“ ist falsch wegen 2. Das Gegenteil von „Es gibt eine größte Zahl“ ist „Zu jeder Zahl gibt es eine größere“.

Anwendung: Schaltkreise und Programmieren

Die Junktoren stecken in jedem Computer. Eine Schaltung, die zwei Eingangssignale verarbeitet, kennt die Bausteine AND (Konjunktion), OR (Disjunktion) und NOT (Negation). Strom an steht für 1, Strom aus für 0, wie im Dualsystem auf der Seite Zahlensysteme. Ein Haustürschloss, das nur öffnet, wenn der Schlüssel passt und die Tür nicht verriegelt ist, ist ein AND-Gatter mit einem NOT.

Beim Programmieren helfen die Regeln von De Morgan: Die Bedingung „!(a && b)“ ist gleichwertig mit „!a || !b“. Eine Anmeldung, die nur klappt, wenn Passwort richtig und Konto aktiv ist, schlägt fehl, wenn das Passwort falsch ist oder das Konto nicht aktiv ist. Wie George Boole die Logik in eine Algebra mit 0 und 1 übersetzte und wie daraus Schaltungen wurden, steht auf der Seite George Boole.

Übungen

Mit dem Arbeitsblatt Aussagenlogik üben kannst du Wahrheitswerte mit immer neuen Aussagen trainieren.

Geschichte: Von Aristoteles bis Boole

Die Logik ist älter als die Mathematik, wie wir sie kennen. Aristoteles (384–322 v. Chr.) entwickelte in seinen Analytica priora die Lehre vom Syllogismus: Schlüsse wie „Alle Menschen sind sterblich, Sokrates ist ein Mensch, also ist Sokrates sterblich“. Seine Logik handelt von Begriffen und Gruppen („alle“, „einige“), noch nicht von Verknüpfungen ganzer Aussagen.

Die Aussagenlogik im engeren Sinn entwickelten die Stoiker im 3. Jahrhundert v. Chr., vor allem Chrysippos von Soloi. Sie untersuchten Verknüpfungen ganzer Sätze („wenn … dann“, „und“, „oder“) und formulierten Schlussregeln wie den modus ponens: Wenn A gilt und A → B gilt, dann gilt B. Ihre Schriften sind nur in Bruchstücken erhalten, wir kennen sie vor allem durch spätere Autoren.

Gottfried Wilhelm Leibniz träumte im 17. Jahrhundert von einem Kalkül, mit dem man Streitfragen durch Rechnen entscheiden könnte (er schrieb: „Calculemus!“, „Lasst uns rechnen!“). Seine Logikschriften wurden aber erst um 1900 veröffentlicht. Den Traum erfüllte im 19. Jahrhundert George Boole (1815–1864): In The Mathematical Analysis of Logic (1847) und An Investigation of the Laws of Thought (1854) behandelte er logische Aussagen wie algebraische Gleichungen. Auch De Morgan arbeitete zur selben Zeit an einer Algebra der Logik, und die nach ihm benannten Regeln stammen aus dieser Zeit. Eine Übersicht über diese Epoche bietet die Mathematik des 19. Jahrhunderts.

1879 veröffentlichte Gottlob Frege die Begriffsschrift, eine Formelsprache mit Quantoren, in der sich Schlüsse lückenlos aufschreiben lassen. Damit begann die moderne mathematische Logik. 1937 zeigte Claude Shannon in seiner Masterarbeit, dass sich Booles Algebra auf Relaisschaltungen anwenden lässt. Seitdem steckt die Aussagenlogik in der Digitaltechnik.

Häufige Fragen

Was ist der Unterschied zwischen Aussagenlogik und Prädikatenlogik?

Die Aussagenlogik verknüpft ganze Aussagen und kennt keine Variablen. Die Prädikatenlogik kann zusätzlich über Elemente sprechen und hat dafür Variablen und die Quantoren ∀ und ∃.

Warum ist „falsch → beliebig“ wahr?

Eine Implikation verspricht nur etwas für den Fall, dass die Voraussetzung wahr ist. Ist sie falsch, kann das Versprechen nicht gebrochen werden. Darum gilt die Implikation dann als wahr.

Was bedeutet ≡?

Das Zeichen ≡ steht für logische Äquivalenz: Beide Aussagen haben in jeder Zeile der Wahrheitstafel denselben Wahrheitswert.

Wie viele Zeilen hat eine Wahrheitstafel mit drei Aussagen?

2³ = 8 Zeilen, denn jede der drei Aussagen kann wahr oder falsch sein.

Quellen und weiterführende Literatur

• Wikipedia: Aussagenlogik
• Wikipedia: Chrysippos von Soloi
• MacTutor History of Mathematics: George Boole (englisch)
• MacTutor History of Mathematics: Augustus De Morgan (englisch)
• Albrecht Beutelspacher: Das ist o.B.d.A. trivial!, Springer Spektrum.