Aussagenlogik

Was ist Aussagenlogik?

Die Aussagenlogik ist ein Teilgebiet der Logik, das sich mit Aussagen und deren Verknüpfung durch Junktoren befasst. Sie geht von strukturlosen Elementaraussagen (Atomen) aus, denen ein Wahrheitswert zugeordnet wird. In der klassischen Aussagenlogik erhält jede Aussage einen Wahrheitswert aus einer Booleschen Algebra, meist wahr oder falsch. Der Wahrheitswert einer zusammengesetzten Aussage lässt sich dann allein aus den Wahrheitswerten ihrer Teilaussagen bestimmen.

Die klassische Logik ist durch zwei Prinzipien gekennzeichnet:

• Prinzip der Zweiwertigkeit (Bivalenzprinzip): Jede Aussage hat genau einen von zwei Wahrheitswerten, falsch oder wahr.
• Prinzip der Extensionalität (Kompositionalität): Der Wahrheitswert einer zusammengesetzten Aussage ist eindeutig durch die Wahrheitswerte ihrer Teilaussagen bestimmt.

Die Aussagenlogik untersucht nur, aus welchen Teilsätzen ein Satz zusammengesetzt ist. Die innere Struktur nicht weiter zerlegbarer (atomarer) Aussagen wird nicht betrachtet; das übernimmt zum Beispiel die Prädikatenlogik.

Werden diese Prinzipien aufgehoben, entstehen nichtklassische Logiken: Hebt man die Zweiwertigkeit auf, erhält man mehrwertige Logiken (z. B. dreiwertige Logik oder Fuzzy-Logik). Hebt man die Extensionalität auf, entstehen nichtextensionale Logiken wie die Modallogik mit den Operatoren „es ist notwendig, dass“ und „es ist möglich, dass“.

Logische Systeme stehen nicht in einem Konkurrenzverhältnis um Wahrheit oder Richtigkeit. Welches System man verwendet, ist eine pragmatische Frage. Die metaphysische Frage, welches System die Wirklichkeit „richtig“ beschreibt, gehört in andere Gebiete wie Philosophie und Wissenschaftstheorie.

Historisch diskutierte Aristoteles erstmals aussagenlogische Grundsätze (Satz vom Widerspruch, Satz vom ausgeschlossenen Dritten, indirekter Beweis). Die zweiwertige Semantik entwickelten Diodoros Kronos und Philon, den ersten Kalkül Chrysippos von Soli. George Boole schuf 1847 eine erste vollständige und entscheidbare Formalisierung der Tautologien, Gottlob Frege 1879 den ersten Kalkül mit Schlussregeln (Begriffsschrift), und Bertrand Russell formulierte 1908 den später durchgesetzten Aussagenkalkül.

Junktoren: Negation, Konjunktion, Disjunktion

Eine Aussage ist ein Satz, der entweder wahr (w, true, 1, ⊤) oder falsch (f, false, 0, ⊥) ist – „Halbwahrheiten“ gibt es nicht. Eine Elementaraussage enthält keine aussagenlogischen Verknüpfungen (nicht, und, oder, wenn … dann, genau dann wenn). Auch wenn man den Wahrheitswert nicht kennt (z. B. bei ungelösten mathematischen Problemen), ist die Aussage wahr oder falsch.

Negation (¬A): Die Verneinung einer Aussage A kehrt ihren Wahrheitswert um. ¬A ist genau dann wahr, wenn A falsch ist. Man erhält sie stets durch die Formulierung „Es ist nicht der Fall, dass …“. A und ¬A können nicht gleichzeitig wahr sein.

Konjunktion (A ∧ B): Die Und-Verknüpfung behauptet die Wahrheit aller Teilaussagen. A ∧ B ist wahr genau dann, wenn sowohl A als auch B wahr sind; sonst ist sie falsch.

Disjunktion (A ∨ B): Das nichtausschließende Oder behauptet, dass mindestens eine Teilaussage wahr ist. A ∨ B ist wahr, wenn mindestens eine der Aussagen wahr ist oder beide wahr sind; falsch nur, wenn beide falsch sind. Achtung: Die Bezeichnung „Disjunktion“ wird auch für das ausschließende Oder verwendet; einige Autoren nennen das nichtausschließende Oder daher Adjunktion.

Beispiel mit A: „9 ist durch 3 teilbar“ (wahr) und B: „9 ist eine Quadratzahl“ (wahr):

• A ∧ B („9 ist durch 3 teilbar und 9 ist eine Quadratzahl“) ist wahr.
• ¬A ∧ B wäre falsch, weil ¬A falsch ist.
• A ∨ B ist wahr, weil beide Teilaussagen wahr sind.
• ¬A ∨ ¬B wäre falsch, weil beide verneinten Teilaussagen falsch sind.

Implikation, Bikonditional und ausschließendes Oder

Die materiale Implikation (Konditional, Subjunktion) A → B (auch A ⇒ B oder A ⊃ B) drückt eine hinreichende Bedingung aus: Schon wenn A der Fall ist, ist auch B der Fall. Weitere Lesarten: „Aus A folgt B“, „A impliziert B“, „B ist eine notwendige Bedingung für A“, „Nur wenn B, dann A“. A heißt Antezedens, B Konsequens (Sukzedens).

Wahrheitstabelle: A → B ist wahr, wenn A falsch ist (egal ob B wahr oder falsch), und wahr, wenn beide wahr sind; falsch nur, wenn A wahr und B falsch ist. Wichtig: Die materiale Implikation drückt keinen Kausalzusammenhang und keine zeitliche Nähe aus, sondern nur den formalen Zusammenhang.

Der Umkehrschluss von A → B auf ¬B → ¬A ist gültig (Beispiel: Wenn die Straße nicht nass ist, regnet es nicht). Dagegen ist der Schluss von A → B und ¬A auf ¬B falsch: Aus ¬A folgt keine Aussage über B („Ex falso sequitur quodlibet – Aus Falschem folgt Beliebiges“).

Warum ist B notwendig für A? Wenn A die Wahrheit von B nach sich zieht, kann A nicht eintreten, ohne dass B eintritt – B ist also „notwendig“ für A. Die oft als kontraintuitiv empfundene Wendung „Nur wenn die Straße nass ist, regnet es“ kommt daher, dass man das umgangssprachliche „wenn … dann“ als Kausalität oder zeitliche Folge missversteht. Die materiale Implikation meint schlicht: wenn A wahr ist, ist B wahr – zeitlos und zusammenhanglos.

Das Bikonditional (objektsprachliche bzw. materiale Äquivalenz) A ↔ B (auch ⇔, =, ≡; „genau dann wenn“, englisch „if and only if“, iff) drückt eine hinreichende UND notwendige Bedingung aus. A ↔ B ist genau dann wahr, wenn A und B denselben Wahrheitswert haben. Es ist logisch äquivalent zu (A → B) ∧ (B → A). Beispiel: Die natürliche Zahl n ist genau dann durch 6 teilbar, wenn n durch 2 und durch 3 teilbar ist.

Achtung: Das Bikonditional (Objektsprache) darf nicht mit der logischen Äquivalenz verwechselt werden, einer metasprachlichen Eigenschaft zweier Aussagen. Zusammenhang: A ↔ B ist genau dann eine Tautologie, wenn A und B logisch äquivalent sind.

Das ausschließende Oder (Kontravalenz, Antivalenz; Schreibweise A ↮ B, A ⊻ B oder xor) sagt „entweder A oder B“ – genau eine der beiden Aussagen ist wahr. Es ist falsch, wenn beide falsch sind, aber auch, wenn beide wahr sind. In den meisten logischen Sprachen ist es kein eigener Junktor, sondern z. B. das verneinte Bikonditional ¬(A ↔ B). In der Schaltalgebra ist es als xor wichtig.

De Morgansche Gesetze

Verneinung einer Konjunktion: ¬(A ∧ B) ist logisch äquivalent zu ¬A ∨ ¬B. Die Verneinung von „A und B“ ist also „A ist nicht der Fall oder B ist nicht der Fall (oder beides)“. Beispiel: Die Verneinung von „Es regnet, und die Erde ist eine Scheibe“ lautet: „Es regnet nicht oder die Erde ist keine Scheibe (oder beides).“ In der Schaltalgebra entspricht dies dem Junktor nand.

Verneinung einer Disjunktion: ¬(A ∨ B) ist logisch äquivalent zu ¬A ∧ ¬B („weder A noch B“). Beispiel: Die Verneinung von „Die Erde ist eine Scheibe, oder die Erde ist ein Würfel“ lautet: „Die Erde ist weder eine Scheibe noch ein Würfel.“ In der Schaltalgebra entspricht dies dem Junktor nor.

Formaler Zugang: Syntax, Kalküle, Herleitung

Ziel der formalen Logik ist es, die Regeln des logischen Schließens streng zu fassen, damit scheinbar zwingende Schlüsse nicht zu absurden Ergebnissen führen. Dazu ist eine Trennung der Sprachebenen nötig: Die formale Aussage A ∧ B wird auf einer metasprachlichen Ebene erklärt, indem über A und B geredet wird. Die Aussagenlogik kann als Kalkül (formales System) definiert werden, in dem die Begriffe wahr und falsch zunächst nicht vorkommen; stattdessen gibt es Axiome (Zeichenketten) und Schlussregeln, mit denen weitere Zeichenketten hergeleitet werden.

Von einem formalen System fordert man Korrektheit (nur wahre, d. h. semantisch gültige Sätze sind herleitbar) und Vollständigkeit (alle wahr interpretierbaren Sätze sind herleitbar). Für die klassische Aussagenlogik existieren korrekte und vollständige Kalküle. Für komplexere Systeme wie die Mengenlehre ist das unmöglich – bewiesen durch Kurt Gödelschen Unvollständigkeitssatz 1931.

Bausteine der Sprache: Satzbuchstaben (atomare Formeln) P₀, P₁, P₂, …, die Junktoren ¬, ∧, ∨, →, ↔ und runde Klammern als Gliederungszeichen.

Formationsregeln definieren induktiv, welche Zeichenketten Formeln sind: Alle Satzbuchstaben sind Formeln; ist F eine Formel, so auch (¬F); sind F und G Formeln, so auch (F ∧ G), (F ∨ G), (F → G) und (F ↔ G). Nichts anderes ist eine Formel.

Schlussregeln sind rein formale Transformationsregeln, die so gewählt werden, dass die Ergebnisse semantisch folgen. Zwei Beispiele:

• Modus ponendo ponens: Aus F → G und F darf auf G geschlossen werden.
• Substitutionsregel: Alle Vorkommnisse eines Atoms dürfen durch denselben beliebig komplexen Satz ersetzt werden, z. B. aus P → (P ∨ Q) wird (P ∧ ¬Q) → ((P ∧ ¬Q) ∨ Q).

Axiome sind ausgezeichnete Formeln, die in einer Herleitung ohne weitere Rechtfertigung verwendet werden. Sie sind optional: Kalküle wie das Systeme natürlichen Schließens oder Baumkalküle kommen ohne Axiome aus. Beispiel ist Russells Aussagenkalkül (1908, 1910 in die Principia Mathematica übernommen) mit Axiomen wie (P ∨ P) → P, Q → (P ∨ Q), (P ∨ Q) → (Q ∨ P), (P ∨ (Q ∨ R)) → (Q ∨ (P ∨ R)) und (Q → R) → ((P ∨ Q) → (P ∨ R)); dabei wird (P → Q) definiert als (¬P ∨ Q) und (P ∧ Q) als ¬(¬P ∨ ¬Q). Alternativ kann man Axiomenschemata angeben, dann braucht man keine Substitutionsregel.

Herleitung und Beweis: Eine Herleitung ist eine nummerierte Liste von Sätzen, beginnend mit Prämissen oder Axiomen; jeder weitere Satz ist ein Axiom oder durch Schlussregeln aus Vorherigem gewonnen; der letzte Satz ist die Konklusion. Eine Herleitung ohne Prämissen heißt Beweis. Aus Prämissen Δ hergeleitete Konklusion P notiert man Δ ⊢ P; ein ohne Annahmen bewiesener Satz P heißt Theorem (⊢ P, Zeichen aus Freges Begriffsschrift).

Semantik, Metatheorie und philosophische Einordnung

Semantik: In der Logik geht es um die Bedeutung der formalen Sprache. Im Zentrum steht die Auswertungsfunktion (Bewertungsfunktion, Wahrheitswertefunktion) V, eine Abbildung von der Menge der Formeln in die Menge der Wahrheitswerte. Jedem Satzbuchstaben (Atom) wird durch eine Interpretation v (eine Abbildung von den Atomen in die Wahrheitswerte) ein Wahrheitswert zugeordnet. Für zusammengesetzte Formeln legen Wahrheitstabellen fest, wie jeder Junktor die Wahrheitswerte bestimmt: ¬ kehrt den Wert um; ∧ ist nur bei zwei wahren Argumenten wahr; ∨ nur bei zwei falschen Argumenten falsch; → nur bei wahr/falsch falsch; ↔ genau dann wahr, wenn beide Argumente gleich sind.

Es gibt insgesamt vier einstellige und sechzehn zweistellige Junktoren. Die gewählte Menge ¬, ∧, ∨, →, ↔ ist funktional vollständig, d. h., alle anderen Junktoren lassen sich damit ausdrücken.

Gültigkeit und Tautologien: Eine Formel heißt semantisch gültig (Tautologie, Notation ⊨ P), wenn sie unter allen Interpretationen wahr ist. Ein Argument heißt semantisch gültig, wenn unter allen Zuordnungen, unter denen alle Prämissen wahr sind, auch die Konklusion wahr ist – nach Leibniz: „Aus Wahrem folgt nur Wahres“ (Notation Δ ⊨ P). Beachte den Unterschied: Δ ⊢ P ist syntaktische Herleitbarkeit, Δ ⊨ P semantische Gültigkeit.

Weitere Eigenschaften: Eine Formel ist erfüllbar, wenn es mindestens eine Interpretation gibt, unter der sie wahr ist; widerlegbar, wenn es eine gibt, unter der sie falsch ist; unerfüllbar, wenn sie unter allen Interpretationen falsch ist. Eine Formel F ist genau dann eine Tautologie, wenn ¬F unerfüllbar ist. Die Frage, ob eine Formel erfüllbar ist (Erfüllbarkeitsproblem, SAT-Problem), ist für allgemeine Formeln NP-vollständig; das Wahrheitstafelverfahren ist ein Brute-Force-Verfahren mit 2^n Zeilen bei n Atomen. Für Horn-Formeln ist das Problem dagegen in polynomialer Laufzeit lösbar.

Algebraische Sicht: Aus Sicht der formalen Algebra ist die Semantik der klassischen Aussagenlogik eine zweiwertige Boolesche Algebra. So hat die Konjunktion das neutrale Element wahr (V(X ∧ W) = V(X), wenn V(W) = wahr) und die Disjunktion das neutrale Element falsch. Die Schaltalgebra und die elementare Mengenlehre bilden ebenfalls Boolesche Algebraen – aus algebraischer Sicht besteht zwischen ihnen kein Unterschied. Jede Formel lässt sich zudem in eine äquivalente Formel in konjunktiver und eine in disjunktiver Normalform umformen.

Metatheorie untersucht Eigenschaften logischer Systeme selbst:

• Konsistenz: Ein Kalkül ist konsistent, wenn sich kein Widerspruch (keine Formel P ∧ ¬P) herleiten lässt. Alternativ (bei parakonsistenten Logiken): konsistent, wenn nicht alle Formeln herleitbar sind. In der klassischen Logik fallen beide Begriffe zusammen, da dort Ex falso quodlibet gilt.
• Korrektheit: Nur semantisch gültige Formeln (Tautologien) und gültige Argumente sind herleitbar.
• Vollständigkeit: Alle semantisch gültigen Formeln sind herleitbar.
• Adäquatheit: Korrektheit und Vollständigkeit zusammen; ein adäquater Kalkül kann alle und nur die semantisch gültigen Sätze herleiten.

Metatheoretische Resultate: Alle korrekten Kalküle sind konsistent, aber ein konsistenter Kalkül muss nicht korrekt sein, und ein vollständiger Kalkül muss weder korrekt noch konsistent sein.

Philosophie: Logische Systeme sind formal gleichwertig nebeneinander stehende Systeme. Praktisch bewährt sich die klassische Aussagenlogik z. B. in der Schaltalgebra und Programmiersprachen, die Prädikatenlogik z. B. bei Prolog, während Fuzzy-, nonmonotone, mehrwertige und parakonsistente Logiken bei unsicherem oder widersprüchlichem Wissen nützlich sind. Die metaphysische Frage, ob ein Prinzip der Zweiwertigkeit gelte (ob alle Aussagen über die Wirklichkeit wahr oder falsch sind), ist ungelöst; Einwände betreffen Aussagen über Zukünftiges (bei Aristoteles) und prinzipiell nicht feststellbare Wahrheiten. Befürworter verweisen darauf, dass Metatheoretiker immer zweiwertig urteilen (ein Kalkül ist stets konsistent oder inkonsistent usw.). Zur Frage, was logische Gegenstände „sind“, gibt es u. a. den platonischen Standpunkt (Zeichen benamen real existierende abstrakte Gegenstände wie das Wahre und das Falsche), den Nominalismus (es gibt nur die Zeichen) und den Konstruktivismus (Gegenstände werden durch den Umgang mit Zeichen konstruiert).