Aussagenlogik

Die Aussagenlogik ist ein Teilgebiet der Logik, das sich mit Aussagen und deren Verknüpfung durch Junktoren befasst, ausgehend von strukturlosen Elementaraussagen (Atomen), denen ein Wahrheitswert zugeordnet wird. In der klassischen Aussagenlogik wird jeder Aussage ein Element einer Booleschen Algebra als Wahrheitswert zugeordnet. Der Wahrheitswert einer zusammengesetzten Aussage lässt sich ohne zusätzliche Informationen mittels der Operationen der Booleschen Algebra aus den Wahrheitswerten ihrer Teilaussagen bestimmen.

Geschichte

Historisch geht die Aussagenlogik zurück bis zu Aristoteles, der erstmals aussagenlogische Grundsätze diskutierte, nämlich in seiner Metaphysik den Satz vom Widerspruch und den Satz vom ausgeschlossenen Dritten, und der in seiner ersten Analytik den indirekten Beweis thematisierte. Die zweiwertige aussagenlogische Semantik entwickelten etwas später die megarischen Philosophen Diodoros Kronos und Philon. Die Aussagensemantik und -axiomatik kombinierte der Stoiker Chrysippos von Soli, der den ersten aussagenlogischen Kalkül formulierte. Die Weiterentwicklung der Aussagenlogik der Stoa durch das Mittelalter wird oft übersehen. Eine erste vollständige und entscheidbare Formalisierung für aussagenlogische Tautologien – allerdings noch nicht für das aussagenlogische Schließen – schuf George Boole 1847 mit seinem algebraischen Logikkalkül. Den ersten aussagenlogischen Kalkül mit Schlussregeln formulierte Gottlob Frege im Rahmen seiner Begriffsschrift 1879. Er war die Vorlage für den Aussagenkalkül von Bertrand Russell 1908, der sich später durchsetzte (s. u.).

Abgrenzung zu anderen Logiken

Da in der heutigen Mathematik die klassische Aussagenlogik maßgeblich wurde, wird in diesem Artikel dieser moderne Haupttypus der Aussagenlogik behandelt. Allgemein ist die klassische Logik durch zwei Eigenschaften charakterisiert:

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

Das Prinzip der Zweiwertigkeit wird oft mit dem Satz vom ausgeschlossenen Dritten verwechselt.

Die klassische Aussagenlogik ist jenes Gebiet der klassischen Logik, das die innere Struktur von Sätzen (Aussagen) daraufhin untersucht, aus welchen anderen Sätzen (Teilsätzen) sie zusammengesetzt sind und wie diese Teilsätze miteinander verknüpft sind. Die innere Struktur von Sätzen, die ihrerseits nicht in weitere Teilsätze zerlegt werden können, wird von der Aussagenlogik nicht betrachtet. Ein Beispiel: Die Aussage „Alle Katzen sind Hunde, und die Erde ist eine Scheibe“ ist mit dem Bindewort „und“ aus den beiden kürzeren Aussagen „Alle Katzen sind Hunde“ und „Die Erde ist eine Scheibe“ zusammengesetzt. Diese beiden Aussagen lassen sich ihrerseits nicht mehr in weitere Aussagen zerlegen, sind aus aussagenlogischer Sicht also elementar oder atomar. Andere, auf die Aussagenlogik aufbauende logische Systeme betrachten die innere Struktur solcher atomaren Aussagen; ein wichtiges Beispiel ist die Prädikatenlogik.

In Abgrenzung zur klassischen Logik entstehen nichtklassische Logiksysteme, wenn man das Prinzip der Zweiwertigkeit, das Prinzip der Extensionalität oder sogar beide Prinzipien aufhebt. Nichtklassische Logiken, die durch die Aufhebung des Prinzips der Zweiwertigkeit entstehen, heißen mehrwertige Logik. Die Zahl der Wahrheitswerte (in diesem Falle üblicher: Pseudowahrheitswerte) kann dabei endlich sein (z. B. dreiwertige Logik), ist aber oft auch unendlich (z. B. Fuzzy-Logik). Hingegen verwenden Logiken, die durch die Aufhebung der Extensionalität entstehen, Junktoren (Konnektive), bei denen sich der Wahrheitswert des zusammengesetzten Satzes nicht mehr eindeutig aus dem Wahrheitswert seiner Teile bestimmen lässt. Ein Beispiel für nichtextensionale Logik ist die Modallogik, die die einstelligen nichtextensionalen Operatoren „es ist notwendig, dass“ und „es ist möglich, dass“ einführt.

Logische Systeme stehen innerhalb der Logik nicht in einem Konkurrenzverhältnis um Wahrheit oder Richtigkeit. Die Frage, welches logische System für einen bestimmten Zweck genutzt werden soll, ist eher eine pragmatische.

Oft werden logische Systeme und logische Fragestellungen mit außerlogischen Fragen verwechselt oder vermischt, z. B. mit der metaphysischen Frage, welches logische System „richtig“ sei, d. h. die Wirklichkeit beschreibe. Zu dieser Frage gibt es unterschiedliche Standpunkte einschließlich des positivistischen Standpunkts, dass diese Frage sinnlos sei. Diese Fragen fallen aber in andere Gebiete, z. B. Philosophie, Wissenschaftstheorie und Sprachwissenschaft.

Wenn in diesem Artikel die klassische Aussagenlogik behandelt wird, so ist das also nicht als metaphysische Festlegung zu verstehen oder gar als Behauptung, dass „alle Aussagen wahr oder falsch sind“. Es ist lediglich so, dass die klassische Aussagenlogik einfach nur solche Aussagen behandelt, die wahr oder falsch sind. Das ist eine große formale Vereinfachung, die dieses System relativ leicht erlernbar sein lässt. Braucht man aus metaphysischen oder pragmatischen Gründen mehr als zwei Wahrheitswerte, kann die klassische Aussagenlogik als Ausgangspunkt dienen, um ein geeignetes logisches System aufzustellen.

Umgangssprachliche Einleitung

Einfache Aussage (Elementaraussage)

→ Hauptartikel: Aussage (Logik)

Eine Aussage A ist ein Satz, der entweder wahr (w, wahr, true, 1) oder nicht wahr (f, falsch, false, 0) ist. Das gilt sowohl für einfache als auch für verknüpfte Aussagen. „Halbwahrheiten“ gibt es nicht. Eine Aussage kann sowohl der gewöhnlichen Sprache entstammen als auch der Sprache der Mathematik. Eine Elementaraussage ist eine Aussage, die keine aussagenlogischen Verknüpfungen (nicht, und, oder, wenn … dann, genau dann wenn) enthält.

Beispiele für Elementaraussagen:

• $A_{1}$: München ist 781 km von Hamburg entfernt.
• $A_{2}$: 9 ist durch 3 teilbar.
• $A_{3}$: Eintracht Frankfurt wird in der nächsten Saison deutscher Fußballmeister.
• $A_{4}$: Alle Autos sind grün.

$A_{2}$ ist offensichtlich wahr (triviale mathematische Aussage), $A_{4}$ dagegen ist falsch (es gibt einfache Gegenbeispiele). $A_{1}$ stellt im mathematischen Sinne keine Aussage dar (ungenau genug in vielerlei Hinsicht, hat Interpretationsspielraum), gleiches gilt für $A_{3}$.

In der klassischen Aussagenlogik ist eine Aussage entweder wahr oder nicht wahr, auch wenn man den Wahrheitsgehalt nicht kennt. Das ist zum Beispiel bei den ungelösten mathematischen Problemen der Fall.

Anmerkung: $A_{4}$ ist eine All-Aussage; die Struktur solcher Aussagen ist Gegenstand der Prädikatenlogik. Im Sinne der Aussagenlogik ist es eine Elementaraussage.

Verneinte Aussage – Negation

→ Hauptartikel: Negationszeichen

Die Verneinung bzw. Negation (auch: Satzverneinung, äußere Verneinung, kontradiktorisches Gegenteil) einer Aussage A ist diejenige Aussage ¬A, die genau dann wahr ist, wenn A falsch ist, und die genau dann falsch ist, wenn A wahr ist. Einfacher: Die Verneinung einer Aussage A dreht den Wahrheitswert von A in sein Gegenteil um.

Man erhält die Verneinung einer Aussage A immer dadurch, dass man ihr die Formulierung „Es ist nicht der Fall, dass“ voranstellt. Zwar lässt sich ein natürlichsprachlicher Satz auch verneinen, indem man das Wort „nicht“ oder eine andere negative Formulierung an geeigneter Stelle einfügt – es ist aber nicht immer ganz einfach, zu erkennen, welche Formulierung zu verwenden und an welcher Stelle einzufügen ist. Formal schreibt man für „nicht A“ in der gebräuchlichsten Notation (Schreibweise) ¬A, auf Englisch und in der Schaltalgebra auch „NOT A“, gelegentlich auch „~A“.

$A$	$\neg A$
falsch	wahr
wahr	falsch

Wir verneinen die obigen Beispiele:

• $\neg A_{1}$: Es ist nicht der Fall, dass München 781 km von Hamburg entfernt ist.
• $\neg A_{2}$: Es ist nicht der Fall, dass 9 durch 3 teilbar ist.
• $\neg A_{3}$: Es ist nicht der Fall, dass Eintracht Frankfurt in der nächsten Saison deutscher Fußballmeister wird.
• $\neg A_{4}$: Es ist nicht der Fall, dass alle Autos grün sind. (Es kann durchaus auch grüne Autos geben, aber es gibt mindestens ein Auto, das nicht grün ist.)

Allgemein gilt für die Verneinung:

• Wenn eine Aussage $A$ wahr ist, ist die Verneinung $\neg A$ falsch.
• Wenn eine Aussage $A$ falsch ist, ist die Verneinung $\neg A$ wahr.
• Eine Aussage $A$ kann nicht gleichzeitig wahr und falsch sein.
• Die Aussagen $A$ und $\neg A$ können nicht gleichzeitig wahr sein.

Und-verknüpfte Aussagen – Konjunktion

→ Hauptartikel: Konjunktion (Logik)

Eine Konjunktion ist eine aus zwei Aussagen zusammengesetzte Aussage, die die Wahrheit all ihrer Teilaussagen behauptet. Umgangssprachlich verbindet man zwei Aussagen A und B durch das Bindewort „und“ zu einer Konjunktion „A und B“, in der logischen Sprache verwendet man meist das Zeichen $\land$ (Schreibweise: $A\land B$), gelegentlich auch das kaufmännische Und, den Ampersand (&).

• Sprechweise: A und B
• Schreibweise: $A\land B$
• auf Englisch und in der Schaltalgebra auch A AND B

Die Aussage $A\land B$ ist immer dann wahr, wenn sowohl A als auch B jeweils wahr sind. Andernfalls ist $A\land B$ falsch, nämlich dann, wenn entweder A oder B oder beide Aussagen falsch sind.

Beispiele für eine Und-Verknüpfung:

• A: 9 ist durch 3 teilbar
• B: 9 ist eine Quadratzahl

$A$	$B$	$A\land B$
wahr	wahr	wahr
falsch	wahr	falsch
wahr	falsch	falsch
falsch	falsch	falsch

Diese Teilaussagen und ihre Negationen werden nun durch $\land$ miteinander verknüpft:

• $C_{1}$: 9 ist durch 3 teilbar und 9 ist eine Quadratzahl.
• $C_{2}$: 9 ist nicht durch 3 teilbar und 9 ist eine Quadratzahl.
• $C_{3}$: 9 ist durch 3 teilbar und 9 ist keine Quadratzahl.
• $C_{4}$: 9 ist nicht durch 3 teilbar und 9 ist keine Quadratzahl.

Nur $C_{1}=A\land B$ ist wahr, weil $A$ wahr ist und auch $B$ wahr ist.
$C_{2}=\neg A\land B$ ist falsch, weil $\neg A$ falsch ist.
$C_{3}=A\land \neg B$ ist falsch, weil $\neg B$ falsch ist.
$C_{4}=\neg A\land \neg B$ ist falsch, weil sowohl $\neg A$ als auch $\neg B$ falsch ist.

Nichtausschließendes Oder – Disjunktion

→ Hauptartikel: Disjunktion

Eine Disjunktion ist eine zusammengesetzte Aussage, die behauptet, dass mindestens eine ihrer Teilaussagen wahr ist. Die Disjunktion in diesem Sinn wird auch nichtausschließendes Oder genannt. (Aber Achtung: Die Bezeichnung „Disjunktion“ wurde und wird oft auch für das ausschließende Oder, „entweder … oder“, verwendet – man denke an das Konzept der disjunkten Mengen. Einige Autoren verwenden daher für das Nichtausschließende Oder den Begriff Adjunktion.) Das Formelzeichen „$\vee$“ stammt von dem lateinischen Wort „vel“; für ausschließendes Oder wurde im Lateinischen „aut ... aut“ verwandt.

• Sprechweise: „A oder B“; genauer: „A oder B oder beide“, häufig in juristischen oder medizinischen Texten: „A und/oder B“
• Schreibweise: $A\vee B$
• auf Englisch und in der Schaltalgebra auch A OR B

Die Aussage $A\vee B$ ist immer dann wahr, wenn mindestens eine der Teilaussagen A oder B wahr ist, bzw. wenn beide Teilaussagen wahr sind. Andernfalls ist $A\vee B$ falsch, nämlich dann, wenn sowohl A als auch B falsch sind.

Beispiel für eine Oder-Verknüpfung:

• A: 9 ist durch 3 teilbar
• B: 9 ist eine Quadratzahl

$A$	$B$	$A\vee B$
wahr	wahr	wahr
falsch	wahr	wahr
wahr	falsch	wahr
falsch	falsch	falsch

Diese Teilaussagen und ihre Negationen werden nun durch $\vee$ miteinander verknüpft:

• $C_{5}$: 9 ist durch 3 teilbar oder 9 ist eine Quadratzahl.
• $C_{6}$: 9 ist nicht durch 3 teilbar oder 9 ist eine Quadratzahl.
• $C_{7}$: 9 ist durch 3 teilbar oder 9 ist keine Quadratzahl.
• $C_{8}$: 9 ist nicht durch 3 teilbar oder 9 ist keine Quadratzahl.

$C_{5}=A\vee B$ ist wahr, weil sowohl $A$ als auch $B$ wahr sind.
$C_{6}=\neg A\vee B$ ist wahr, weil $B$ wahr ist.
$C_{7}=A\vee \neg B$ ist wahr, weil $A$ wahr ist.
Nur $C_{8}=\neg A\vee \neg B$ ist falsch, weil sowohl $\neg A$ als auch $\neg B$ falsch sind.

Materiale Implikation

→ Hauptartikel: Implikation

Die materiale Implikation, auch Konditional oder Subjunktion genannt, drückt die hinreichende Bedingung aus: Sie sagt, dass die Wahrheit des einen Satzes eine hinreichende Bedingung für die Wahrheit des anderen Satzes ist. Man schreibt

$A\rightarrow B$

oder auch

$A\supset B$ ^{(A 1)}

und liest

• A ist eine hinreichende Bedingung für B.
• Schon wenn A, dann B.
• A setzt voraus, dass B.
• B ist eine notwendige Bedingung für A.
  Dass B genau dann eine notwendige Bedingung für A ist, wenn A eine hinreichende Bedingung für B ist, ist eine auf den ersten Blick überraschende und vielleicht kontraintuitive, jedoch zutreffende Feststellung. Das Unterkapitel Hinreichende und notwendige Bedingung bemüht sich, diesen Zusammenhang sichtbarer zu machen.
• A impliziert B.
• Nur wenn B, dann A.

oder auch nur

• Wenn A, dann B.

In einem Konditional nennt man A das Antezedens, B das Konsequens oder Sukzedens.

Beispiele:

• Dass es regnet, ist eine hinreichende Bedingung dafür, dass die Straße nass ist.
• Schon wenn es regnet, ist die Straße nass.
• Wenn es regnet, ist die Straße nass.
• Nur wenn die Straße nass ist, kann es regnen.
• Wenn Person x einen Wagen der Marke y hat, hat x ein Auto.
• Wenn eine Zahl n durch 6 teilbar ist, dann ist die Zahl n durch 3 teilbar.

Die Lesart „wenn … dann“ ist insofern problematisch, als mit dem natürlichsprachlichen „wenn … dann“ vor allem inhaltliche Zusammenhänge wie Kausalität oder zeitliche Nähe ausgedrückt werden. All das macht die materiale Implikation nicht, sie nennt nur den formalen Zusammenhang: „Dass es regnet, ist eine hinreichende Bedingung dafür, dass die Straße nass ist“. Zur Frage, warum das eine hinreichende Bedingung ist – ob auf Grund eines kausalen Zusammenhangs oder auch nur rein zufällig –, nimmt die materiale Implikation nicht Stellung.

$A$	$B$	$A\rightarrow B$	$\neg B\rightarrow \neg A$
falsch	falsch	wahr	wahr
falsch	wahr	wahr	wahr
wahr	falsch	falsch	falsch
wahr	wahr	wahr	wahr

Als Umkehrschluss bezeichnet man den Schluss von $A\rightarrow B$ auf $\neg B\rightarrow \neg A$. Für die Beispiele bedeutet das:

• Wenn die Straße nicht nass ist, regnet es nicht.
• Wenn Person x kein Auto hat, dann hat x keinen Wagen der Marke y.
• Wenn die Zahl n nicht durch 3 teilbar ist, dann ist n nicht durch 6 teilbar.

Umgangssprachlich lässt man sich gelegentlich zu weiteren – falschen – Aussagen verleiten: ^{(A 2)}

• Weil es nicht regnete, kann die Straße nicht nass sein.
  Diese Folgerung ist falsch, da die Straße auch aus anderen Gründen nass werden kann (Rohrbruch, Übung der Feuerwehr …).
• x hat keinen Wagen der Marke y, also hat x kein Auto.
  Falsch, denn er könnte ja einen Wagen der Marke z haben.
• n ist nicht durch 6 teilbar, also ist n auch nicht durch 3 teilbar.
  Auch diese Folgerung ist falsch. Die Zahl 15 ist nicht durch 6 teilbar und sehr wohl durch 3.

Das bedeutet: Wenn die Folgerung $A\rightarrow B$ wahr ist, dann erhält man aus der Aussage ¬A keine Aussage über B; B kann wahr oder falsch sein. („Ex falso sequitur quodlibet“ – „Aus Falschem folgt Beliebiges“)

Die Implikation ist ein wichtiges Mittel in der Mathematik. Die meisten mathematischen Beweise verwenden das Konzept der Implikation.

 

Achtung Verwechslungsgefahr: Das ist kein Obermengenzeichen, sondern das Kurven-, Bogen- oder Hufeisenzeichen (Peano-Russellsche Schreibweise) – siehe Beitrag zur Implikation; das Teilmengenzeichen, welches gleich aussieht, müsste sich auf die andere Seite öffnen.

 

Im Englischen auch als modus morons („närrischer Modus, Modus des Trottels“) bekannt – ein pseudolateinisches Wortspiel in Anspielung auf diverse Modusbegriffe der Aussagenlogik wie Modus tollens, abgeleitet von englisch moron ‚Narr, Idiot, Trottel‘.

Bikonditional

→ Hauptartikel: Bikonditional

Das Bikonditional, oft auch objektsprachliche Äquivalenz oder materiale Äquivalenz genannt, drückt die hinreichende und notwendige Bedingung aus, sagt also, dass eine Aussage A genau dann zutrifft, wenn eine Aussage B zutrifft. Man schreibt:

$A\leftrightarrow B$

und liest

• A ist genau dann der Fall, wenn B der Fall ist.
• A genau dann wenn B.
• A ist äquivalent zu B.
• A ist dann und nur dann der Fall, wenn B der Fall ist.

Auch beim Bikonditional wird eine rein formale Aussage getroffen, die nichts über einen allfälligen inhaltlichen Zusammenhang von A und B aussagt.

Statt $A\leftrightarrow B$ zu sagen, kann man auch sagen, dass A eine hinreichende Bedingung für B und dass B eine hinreichende Bedingung für A ist, also $(A\rightarrow B)\land (B\rightarrow A)$. Tatsächlich sind diese beiden Aussagen logisch äquivalent.

$A$	$B$	$A\leftrightarrow B$
falsch	falsch	wahr
falsch	wahr	falsch
wahr	falsch	falsch
wahr	wahr	wahr

Beispiel:

• Die natürliche Zahl n ist genau dann durch 6 teilbar, wenn n durch 2 und durch 3 teilbar ist.
  Wenn n durch 6 teilbar ist, dann folgt daraus, dass n durch 2 und durch 3 teilbar ist. Umgekehrt gilt aber auch: Wenn n durch 2 und durch 3 teilbar ist, dann ist n durch 6 teilbar.
• Heute ist genau dann Dienstag, wenn morgen Mittwoch ist.

Das Bikonditional als zusammengesetzte Aussage innerhalb der logischen Sprache (siehe Objektsprache) wird oft mit dem Konzept der logischen Äquivalenz verwechselt oder vermischt. Die logische Äquivalenz ist eine metasprachliche, meist natürlichsprachlich formulierte Eigenschaft zweier Aussagen der logischen Sprache. Ein Zusammenhang zwischen logischer Äquivalenz und Bikonditional besteht nur insofern, als das Metatheorem gilt, dass ein Bikonditional $A\leftrightarrow B$ genau dann eine Tautologie ist, wenn die beiden Aussagen A und B logisch äquivalent sind.

Ausschließendes Oder

→ Hauptartikel: Kontravalenz

$A$	$B$	$\neg (A\leftrightarrow B)$
falsch	falsch	falsch
falsch	wahr	wahr
wahr	falsch	wahr
wahr	wahr	falsch

Das ausschließende Oder (Kontravalenz oder Antivalenz), „entweder A oder B“, besagt, dass genau eine der beiden von ihm verknüpften Aussagen wahr ist. Entsprechend ist ein ausschließendes Oder nicht nur dann falsch, wenn sowohl A als auch B falsch sind, sondern auch, wenn beide wahr sind. (Einige Autoren verwenden für das Ausschließende Oder den Begriff Alternative.)

Obwohl das ausschließende Oder ein Konzept ist, mit dem man in der natürlichen Sprache immer wieder zu tun hat, wird es in den meisten logischen Sprachen nicht als eigenständiger Junktor eingeführt. Stattdessen wird das ausschließende Oder zum Beispiel als verneintes Bikonditional ausgedrückt, also als $\neg (A\leftrightarrow B)$.

Große Bedeutung genießt das ausschließende Oder hingegen in der Schaltalgebra, wo es meist als XOR (eXclusive OR) aufgeschrieben wird.

Verneinung einer verknüpften Aussage (De Morgansche Gesetze)

→ Hauptartikel: De Morgansche Gesetze

Verneinung einer Konjunktion

Die Verneinung der Konjunktion „A und B“ (in der logischen Schreibweise: $A\land B$) lautet „Es ist nicht der Fall, dass A und B zutreffen“ (in der logischen Schreibweise: $\neg (A\land B)$). Diese ist logisch äquivalent mit der Aussage „A ist nicht der Fall, oder B ist nicht der Fall (oder beides)“ (in logischer Schreibweise: $(\neg A\lor \neg B)$).

$A$	$B$	$\neg (A\land B)$
falsch	falsch	wahr
falsch	wahr	wahr
wahr	falsch	wahr
wahr	wahr	falsch

Ein Beispiel:

Wenn man die Aussage

Es regnet, und die Erde ist eine Scheibe

verneinen möchte, dann kann man entweder sagen

Es ist nicht der Fall, dass es regnet und die Erde eine Scheibe ist.

oder man sagt

Es regnet nicht oder die Erde ist keine Scheibe (oder beides).

In der Schaltalgebra wird sehr oft der Junktor NAND verwendet, wobei „A NAND B“ denselben Wahrheitswertverlauf hat wie der Ausdruck $\neg (A\land B)$.

Verneinung einer Disjunktion

Die Verneinung der Disjunktion „A oder B (oder beides)“ (in der logischen Schreibweise: $A\lor B$) lautet „Es ist nicht der Fall, dass A oder B zutrifft“ (in logischer Schreibweise: $\neg (A\lor B)$).

Diese ist logisch äquivalent mit der Aussage „A ist nicht der Fall, und B ist nicht der Fall“ (in logischer Schreibweise:${\neg A\land \neg B}$ ).

$A$	$B$	$\neg (A\vee B)$
falsch	falsch	wahr
falsch	wahr	falsch
wahr	falsch	falsch
wahr	wahr	falsch

Ein Beispiel:

Wenn man die Aussage

Die Erde ist eine Scheibe, oder die Erde ist ein Würfel.

verneinen möchte, so sagt man

Es ist nicht der Fall, dass die Erde eine Scheibe ist oder dass die Erde ein Würfel ist.

Nach dem Gesetz von De Morgan kann man nun aber auch sagen:

Die Erde ist keine Scheibe, und die Erde ist kein Würfel

oder in schönerem Deutsch

Die Erde ist weder eine Scheibe noch ein Würfel.

In der Schaltalgebra wird das Konnektiv NOR verwendet, das denselben Wahrheitswertverlauf hat wie die Aussage $\neg (A\lor B)$.

Hinreichende und notwendige Bedingung

Dieser Abschnitt soll den zunächst oft als kontraintuitiv empfundenen Zusammenhang zwischen hinreichender und notwendiger Bedingung, wie er im Abschnitt über die materiale Implikation angesprochen wurde, wiederaufgreifen und näher ausführen.

Betrachten wir noch einmal die materiale Implikation $A\rightarrow B$.

Man sagt: A ist hinreichend für B: Schon wenn A der Fall ist, ist auch B der Fall.

Umgekehrt kann man aber auch sagen: B ist notwendig für A. Ohne B kann A nicht erfüllt sein.

Wie kommt dieser Zusammenhang zustande?

Wir wissen, dass die Wahrheit von A die Wahrheit von B nach sich zieht, denn A ist ja hinreichende Bedingung für B. Somit ist es einfach nicht möglich, dass A eintritt, ohne dass B damit ebenfalls eintreten würde: B ist also gezwungenermaßen der Fall, wenn A der Fall ist. B ist „notwendig“ für A.

Dieser Zusammenhang ist in Wahrheit also ziemlich einfach; Hauptgrund dafür, dass er anfangs oft als kontraintuitiv empfunden wird, ist wahrscheinlich die Schwierigkeit, zwischen den vielen Bedeutungen des umgangssprachlichen „wenn … dann“ einerseits und der rein formalen hinreichenden und notwendigen Bedingung andererseits strikt zu trennen.

Mit dem umgangssprachlichen „wenn … dann“ möchte man fast immer einen inhaltlichen (kausalen oder auch temporalen) Zusammenhang zwischen Antecedens und Konsequenz ausdrücken: „Regen verursacht Straßennässe“, „Zuerst fällt der Regen, erst nachher wird die Straße nass“. Wenn man die hinreichende Bedingung in diesem Sinn missversteht, dann ist es klar, dass die in umgekehrter Reihenfolge formulierte notwendige Bedingung „Nur wenn die Straße nass ist, regnet es“ seltsam aussieht: „Regen verursacht doch Straßennässe. Wie kann daraus je gefolgert werden, dass Straßennässe Regen verursacht?“

All dies sagt die materiale Implikation aber nicht aus. „A ist eine hinreichende Bedingung für B“ meint schlicht, dass wenn die Aussage A wahr ist, auch die Aussage B wahr ist – zeitlos und zusammenhanglos, nicht etwa „später“ oder „weil“.

Analog sagt die notwendige Bedingung, „B ist eine notwendige Bedingung für A“, lediglich das aus, dass B wahr ist, sofern A es ist. Genau das ist aber die Definition des Konditionals A → B.

Siehe auch: notwendige und hinreichende Bedingung

Formaler Zugang

Einleitung

Spätestens beim lauten Lesen von Sätzen wie

„Die Aussage $A\land B$ ist genau dann wahr, wenn die Aussagen A und B wahr sind“

wird der selbstbewusste Laie verlangen, dass ihm erklärt wird, was das soll.

Die Antwort des Logikers: Es soll versucht werden, Sicherheit in die Regeln des logischen Schließens zu bringen. Seit den Sophisten ist dem Abendland klar, dass scheinbar zwingende Schlüsse zu offensichtlich absurden Ergebnissen führen können. Immer wieder wurden Paradoxien formuliert und von großen Denkern als Herausforderung empfunden. Logiker versuchen deshalb, die Regeln des Argumentierens so streng wie möglich zu fassen.

Das einleitende Beispiel macht klar, dass dazu eine Trennung der Sprachebenen unerlässlich ist: Die formale Aussage A∧B soll dadurch erklärt werden, dass auf einer metasprachlichen Ebene sowohl über die Aussage A als auch über die Aussage B geredet wird.

Ein Versuch, dies durchzuführen, besteht darin, die Aussagenlogik als formales System, konkret als Kalkül (eine bestimmte Art eines formalen Systems) zu definieren. Die Begriffe „wahr“ und „falsch“ kommen in diesem System zunächst überhaupt nicht vor. Stattdessen werden Axiome gesetzt, die einfach als Zeichenketten angesehen werden, aus denen weitere ableitbare Zeichenketten aufgrund von bestimmten Schlussregeln hergeleitet werden.

Das Ziel dabei ist einerseits, dass in einem formalen System nur Zeichenketten (Sätze) hergeleitet werden können, die bei einer plausiblen Interpretation auch wahr sind. Andererseits sollen alle Sätze, die als „wahr“ interpretierbar sind, auch hergeleitet werden können. Das erste ist die Forderung nach Korrektheit, das zweite die nach Vollständigkeit des formalen Systems; beide Eigenschaften sind unter Kalkül: Der Begriff Kalkül in der Logik beschrieben.

Für die klassische Aussagenlogik, mit der wir es hier zu tun haben, gibt es Kalküle (formale Systeme), die sowohl korrekt als auch vollständig sind. Für gewisse komplexere logische Systeme (z. B. Mengenlehre) ist es aber unmöglich, einen vollständigen Kalkül aufzustellen, der auch korrekt ist; diese Erkenntnis wurde 1931 von Kurt Gödel bewiesen (Gödelscher Unvollständigkeitssatz).

Syntax

Es gibt viele verschiedene Möglichkeiten, die Syntax („Grammatik“) einer logischen Sprache formal zu definieren; meist geschieht das im Rahmen eines Kalküls. Die folgende Definition ist daher nur als Beispiel dafür zu verstehen, wie ein Kalkül für die klassische Aussagenlogik aussehen kann. Weitere Beispiele für konkrete Kalküle finden sich unter Baumkalkül, Begriffsschrift, Systeme natürlichen Schließens, Sequenzenkalkül oder Resolutionskalkül. Ein weiterer axiomatischer Kalkül ist als Beispiel im Artikel Hilbert-Kalkül angegeben, ein graphischer Kalkül im Artikel Existential Graphs.

Bausteine der aussagenlogischen Sprache

Als Bausteine der aussagenlogischen Sprache sollen Satzbuchstaben („atomare Formeln“, Satzkonstanten), Junktoren und Gliederungszeichen verwendet werden. Satzbuchstaben sollen die Zeichen P₀, P₁, P₂, … sein. Junktoren sollen die Zeichen ¬, ∧, ∨, → und ↔ sein. Als Gliederungszeichen sollen die runden Klammern dienen. ^{(A 1)}

Formal lässt sich das z. B. auf folgende Weise ausdrücken:

Sei V die (abzählbar unendliche) Menge der atomaren Formeln (Satzbuchstaben):

V = {P_n | n ∈ N₀} (N₀: Menge der natürlichen Zahlen inkl. 0), d. h. V = {P₀, P₁, P₂, P₃, …}

Sei J die Menge der Junktoren und Gliederungszeichen:

J = {¬, ∧, ∨, →, ↔, (, )}

Das Alphabet der logischen Sprache sei die Menge V ∪ J, also die Vereinigungsmenge von atomaren Formeln, Junktoren und Gliederungszeichen.

Formationsregeln

Die Formationsregeln legen fest, wie man aus den Bausteinen der aussagenlogischen Sprache Sätze (Formeln) bilden kann. Hier sollen aussagenlogische Formeln als Worte über dem Alphabet der logischen Sprache, also über V ∪ J wie folgt induktiv definiert werden: ^{(A 2)}

• Alle atomaren Formeln F ∈ V (d. h. alle Satzbuchstaben) sind Formeln.
• Ist F eine Formel, so ist auch (¬F) eine Formel.
  (Diese Formel heißt Negation von F.)
• Sind F und G zwei (nicht notwendigerweise unterschiedliche) Formeln, so ist auch (F ∧ G) eine Formel.
  (Diese Formel heißt Konjunktion von F und G.)
• Sind F und G zwei (nicht notwendigerweise unterschiedliche) Formeln, so ist auch (F ∨ G) eine Formel.
  (Diese Formel heißt Disjunktion von F und G.)
• Sind F und G zwei (nicht notwendigerweise unterschiedliche) Formeln, so ist auch (F → G) eine Formel.
  (Diese Formel heißt materiale Implikation oder Konditional von F und G.)
• Sind F und G zwei (nicht notwendigerweise unterschiedliche) Formeln, so ist auch (F ↔ G) eine Formel.
  (Diese Formel heißt Bikonditional von F und G.)
• Nichts anderes ist eine aussagenlogische Formel.

Schlussregeln

→ Hauptartikel: Schlussregel

Schlussregeln sind allgemein Transformationsregeln (Umformungsregeln), die auf bestehende Formeln angewandt werden und aus ihnen neue Formeln erzeugen. Wenn man einen Kalkül für ein logisches System aufstellt, dann wählt man die Transformationsregeln so, dass sie aus bestehenden Formeln solche Formeln erzeugen, die aus den Ausgangsformeln semantisch folgen – deshalb die Bezeichnung „Schlussregel“ (eine Schlussfolgerung ziehen).

Innerhalb der Syntax sind die Schlussregeln allerdings rein formale Transformationsregeln, denen für sich keinerlei inhaltliche Bedeutung zukommt.

An konkreten Schlussregeln sollen hier nur zwei angegeben werden: der Modus ponendo ponens und die Substitutionsregel.

Modus ponendo ponens

Aus einem Satz der Form $\varphi \rightarrow \psi$ und einem Satz der Form $\varphi$ darf man auf einen Satz der Form $\psi$ schließen; dabei sind $\varphi$ und $\psi$ Platzhalter für beliebige Formeln. Zum Beispiel darf man nach dieser Schlussregel aus „Wenn Regen die Straße benetzt, dann ist der Straßenbelag regennass“ und aus „Regen benetzt die Straße“ schließen auf „Der Straßenbelag ist regennass“.

Substitutionsregel (Ersetzungsregel)

In einem Satz dürfen alle Vorkommnisse eines beliebigen Atoms (z. B. „P“) durch einen beliebig komplexen Satz (z. B. $(P\land \neg Q)$) ersetzt werden. Es müssen dabei aber auch wirklich alle Vorkommnisse des gewählten Atoms ersetzt werden und sie müssen auch wirklich alle durch denselben Satz ersetzt werden.

Zum Beispiel darf mittels der Substitutionsregel aus $P\rightarrow (P\lor Q)$ auf $(P\land \neg Q)\rightarrow ((P\land \neg Q)\lor Q)$ geschlossen werden. Man sagt, P werde durch $(P\land \neg Q)$ ersetzt oder $(P\land \neg Q)$ werde für P substituiert (eingesetzt).

Siehe auch: Kalkül

 

Zur prädikatenlogischen Entsprechung siehe Prädikatenlogik erster Stufe – Symbole.

 

Zur prädikatenlogischen Entsprechung siehe Prädikatenlogik erster Stufe – Terme.

Axiome

→ Hauptartikel: Axiom

Axiome sind ausgezeichnete (im Sinn von: hervorgehobene) Formeln der aussagenlogischen Sprache. Die Auszeichnung besteht darin, dass sie innerhalb eines Beweises oder einer Herleitung (siehe unten) ohne weitere Rechtfertigung verwendet werden.

Pragmatisch wählt man solche Formeln als Axiome, die semantisch gesehen Tautologien sind, also immer zutreffen, und die dabei helfen, Beweise zu verkürzen. Innerhalb der Syntax sind die Axiome allerdings rein formale Objekte, denen keinerlei inhaltliche Bedeutung oder Rechtfertigung zukommt.

Axiome sind im Allgemeinen optional, d. h., ein Kalkül kann auch ganz ohne Axiome auskommen, wenn er ausreichend viele bzw. mächtige Schlussregeln hat. Axiomfreie Kalküle sind zum Beispiel die Systeme natürlichen Schließens oder Baumkalküle.

Hier soll exemplarisch ein axiomatischer Kalkül gezeigt werden, und zwar Russells Aussagenkalkül aus seiner Typentheorie 1908, den er 1910 in die Principia Mathematica übernahm. Dieser Kalkül umfasst die folgenden Axiome (von denen das vierte redundant, d. h. nicht unbedingt erforderlich ist, weil aus den anderen Axiomen herleitbar):

1. $(P\lor P)\rightarrow P$
2. $Q\rightarrow (P\lor Q)$
3. $(P\lor Q)\rightarrow (Q\lor P)$
4. $[P\lor (Q\lor R)]\rightarrow [Q\lor (P\lor R)]$
5. $(Q\rightarrow R)\rightarrow [(P\lor Q)\rightarrow (P\lor R)]$

Um aus diesen Axiomen auch solche gültigen Sätze herleiten zu können, die andere als die in den Axiomen vorkommende Junktoren enthalten, werden diese durch folgende Festlegung auf die vorhandenen Junktoren zurückgeführt:

1. $(P\rightarrow Q):=(\neg P\lor Q)$
2. $(P\land Q):=\neg (\neg P\lor \neg Q)$

Alternativ zu – wie hier – konkreten Axiomen kann man auch Axiomenschemata angeben, in welchem Fall man auch ohne Substitutionsregel auskommt. Interpretiert man die obigen Axiome als Axiomenschemata, dann stünde z. B. das erste Axiomenschema, $(P\lor P)\rightarrow P$, für unendlich viele Axiome, nämlich alle Ersetzungsinstanzen dieses Schemas.

Herleitung und Beweis

→ Hauptartikel: Ableitung (Logik)

Eine Herleitung ist eine Liste von aufsteigend nummerierten Sätzen, die mit einer oder mehreren Annahmen (den Prämissen der Herleitung) oder Axiomen beginnt. Alle auf diese folgenden Sätze sind entweder ebenfalls Axiome (bei manchen Kalkülen sind auch weitere Annahmen zulässig) oder sind aus einer oder mehreren der vorangehenden Zeilen durch Anwendung von Schlussregeln entstanden. Der letzte Satz in der Liste ist die Konklusion der Herleitung.

Eine Herleitung ohne Prämissen heißt Beweis. Oft werden aber die Wörter „Herleitung“ und „Beweis“ synonym gebraucht.

Wenn es gelingt, aus einer Menge von Annahmen (Prämissen) Δ eine Konklusion P herzuleiten, dann schreibt man auch $\Delta \vdash P$.

Gelingt es, einen Satz P ohne die Verwendung von Annahmen herzuleiten (zu beweisen), dann schreibt man auch: $\vdash P$. In diesem Fall wird P Theorem genannt.

Das Zeichen $\vdash$ geht auf die Begriffsschrift zurück, jenes Werk, in dem Gottlob Frege 1879 die erste Formalisierung der Prädikatenlogik angegeben hat.

In der klassischen Aussagenlogik wählt man die Schlussregeln so, dass sich mit ihrer Hilfe alle gültigen Argumente (und nur gültige Argumente) herleiten lassen; die Frage der Gültigkeit wird im folgenden Abschnitt, „Semantik“, behandelt.

Semantik

Außerhalb der Logik bezeichnet Semantik ein Forschungsgebiet, das sich mit der Bedeutung von Sprache und deren Teilen befasst. Oft wird auch das Wort Semantik gleichbedeutend mit dem Wort Bedeutung verwendet.

Auch innerhalb der Logik geht es bei Semantik um Bedeutung: Darum nämlich, den Ausdrücken einer formalen Sprache – zum Beispiel der hier behandelten Sprache der Aussagenlogik – eine Bedeutung zuzuordnen. In der Logik wird auch das meist sehr formal unternommen.

Im Zentrum der (formalen) Semantik steht eine Auswertungsfunktion (andere Bezeichnungen lauten Bewertungsfunktion, Denotationsfunktion, Wahrheitswertefunktion), die den Formeln der logischen Sprache eine Bedeutung zuordnet. Formal gesprochen ist die Auswertungsfunktion eine Abbildung von der Menge der Formeln der Sprache in die Menge der Wahrheitswerte. Oft wird die Auswertungsfunktion mit dem Großbuchstaben V bezeichnet.

In der klassischen Aussagenlogik ist die Auswertungsfunktion sehr einfach: Das Prinzip der Zweiwertigkeit fordert, dass sie für jede zu bewertende Formel genau einen von genau zwei Wahrheitswerten liefern muss; und das Prinzip der Extensionalität fordert, dass die Bewertungsfunktion beim Bewerten eines komplexen Satzes nur die Bewertung von dessen Teilsätzen berücksichtigen muss.

Jedem Atom, also jedem Satzbuchstaben (Atom) wird durch Festsetzung ein Wahrheitswert zugeordnet. Man sagt: Die Atome werden interpretiert. Es wird also z. B. festgelegt, dass P₀ wahr ist, dass P₁ falsch ist und dass P₂ ebenfalls falsch ist. Damit ist der Bewertung der Bausteine der logischen Sprache Genüge getan. Formal ist eine solche Bewertung – Interpretation genannt und oft mit dem Kleinbuchstaben v bezeichnet – eine Funktion im mathematischen Sinn, d. h. eine Abbildung von der Menge der Atome in die Menge der Wahrheitswerte.

Wenn die Auswertungsfunktion V auf ein Atom angewandt wird, d. h. wenn sie ein Atom bewerten soll, liefert sie die Interpretation dieses Atoms im Sinn des obigen Absatzes. Mit anderen Worten, sie liefert den Wert, den die Bewertung v dem Atom zuordnet.

Um die zusammengesetzten Formeln bewerten zu können, muss für jeden Junktor definiert werden, welchen Wahrheitswert die Bewertungsfunktion für die unterschiedlichen Wahrheitswertkombinationen liefert, den seine Argumente annehmen können. In der klassischen Aussagenlogik geschieht das meist mittels Wahrheitstabellen, weil es nur überschaubar wenige Möglichkeiten gibt.

Der einstellige Junktor ¬, die Negation, ist in der klassischen Aussagenlogik so definiert, dass er den Wahrheitswert seines Arguments ins Gegenteil umkehrt, also „verneint“: Ist die Bewertung einer Formel X wahr, dann liefert die Bewertungsfunktion für ¬X falsch; wird aber X falsch bewertet, dann liefert die Bewertungsfunktion für ¬X wahr. Die Wahrheitstabelle sieht folgendermaßen aus:

a	Negation ¬ a
f	w
w	f

Die Wahrheitswertverläufe der verwendeten zweistelligen Konnektive sind in der klassischen Aussagenlogik wie folgt definiert:

a	b	Konjunktion a ∧ b	Disjunktion a ∨ b	materiale Implikation Konditional a → b	Bikonditional a ↔ b
f	f	f	f	w	w
f	w	f	w	w	f
w	f	f	w	f	f
w	w	w	w	w	w

Allgemein gibt es für die klassische Aussagenlogik vier einstellige und sechzehn zweistellige Junktoren. Die hier behandelte logische Sprache beschränkt sich nur deshalb auf die Junktoren ¬, ∧, ∨, → und ↔, weil diese am gebräuchlichsten sind und weil sie auch inhaltlich noch am ehesten aus der Alltagssprache bekannt sind. Aus formaler Sicht ist die einzige Bedingung, die man bei der Wahl von Junktoren erfüllen möchte, die, dass sich mit den gewählten Junktoren auch alle anderen theoretisch möglichen Junktoren ausdrücken lassen; man sagt: Dass die Menge der gewählten Junktoren funktional vollständig ist. Diese Anforderung ist bei der hier getroffenen Wahl erfüllt.

Näheres zur Frage, wie viele und welche Junktoren es gibt und wie viele Junktoren man benötigt, um funktionale Vollständigkeit zu erreichen, ist im Kapitel Junktor beschrieben.

Semantische Gültigkeit, Tautologien

Semantische Gültigkeit ist eine Eigenschaft von Formeln oder von Argumenten. (Ein Argument ist die Behauptung, dass aus einigen Aussagen – den Prämissen – eine bestimmte Aussage – die Konklusion – folgt.)

Eine Formel der aussagenlogischen Sprache heißt genau dann semantisch gültig, wenn die Formel unter allen Interpretationen – d. h. unter allen Zuordnungen von Wahrheitswerten zu den in ihr vorkommenden Atomen – wahr ist; wenn sie sozusagen allgemeingültig ist; mit anderen Worten: Wenn die Wahrheitstabelle für diese Aussage in jeder Zeile das Ergebnis wahr zeigt. Man nennt semantisch gültige Formeln auch Tautologien und schreibt, wenn $P$ eine Tautologie ist, formal wie folgt:

$\models P$

Ein Argument heißt genau dann semantisch gültig, wenn unter der Voraussetzung, dass alle Prämissen wahr sind, auch die Konklusion wahr ist. In der Formulierung von Gottfried Wilhelm Leibniz: Aus Wahrem folgt nur Wahres. Diese Definition muss natürlich ebenfalls formal gefasst werden, und das geschieht wie folgt: Ein Argument ist genau dann semantisch gültig, wenn alle Zuordnungen von Wahrheitswerten zu den in Prämissen und Konklusion vorkommenden Atomen, unter denen die Bewertungsfunktion für alle Prämissen den Wert wahr liefert, auch für die Konklusion den Wert wahr liefert.

Um auszudrücken, dass aus einer Menge $\Delta$ von Formeln (der Prämissenmenge) eine Formel $P$ (die Konklusion) semantisch folgt, schreibt man formal wie folgt:

$\Delta \models P$

Beachte die graphische Ähnlichkeit und die inhaltliche Verschiedenheit zwischen $\Delta \vdash P$ (Kapitel „Herleitung und Beweis“) und $\Delta \models P$ (Siehe: Semantische Folgerung): Die erste Formulierung – $\Delta \vdash P$ – drückt die syntaktische Gültigkeit des Arguments aus, sagt also, dass aus den Formeln in $\Delta$ mit den Schlussregeln des gewählten Kalküls die Formel $P$ hergeleitet werden kann. $\Delta \models P$ hingegen behauptet die semantische Gültigkeit, die in der klassischen Aussagenlogik wie in den vorangegangenen Absätzen als das Leibniz’sche Aus Wahrem folgt nur Wahres definiert ist.

Siehe auch: Entscheidbar

Wichtige semantische Eigenschaften: Erfüllbarkeit, Widerlegbarkeit und Unerfüllbarkeit

Neben der Eigenschaft der Gültigkeit (Allgemeingültigkeit) gibt es einige andere wichtige Eigenschaften: Erfüllbarkeit, Widerlegbarkeit und Unerfüllbarkeit. Im Gegensatz zur Gültigkeit, die Eigenschaft von Formeln oder von Argumenten sein kann, sind Erfüllbarkeit, Widerlegbarkeit und Unerfüllbarkeit Eigenschaften von Sätzen oder von Satzmengen.

• Eine Formel heißt erfüllbar, wenn es mindestens eine Interpretation der in ihr vorkommenden Atome (Satzbuchstaben) gibt, unter der die Formel wahr ist.
• Eine Formel heißt widerlegbar, wenn es mindestens eine Interpretation der in ihr vorkommenden Atome gibt, unter der die Formel falsch ist.
• Eine Formel heißt unerfüllbar, wenn sie unter allen Interpretationen der in ihr vorkommenden Satzbuchstaben falsch ist.
• Eine Formelmenge heißt gültig, wenn alle in ihr enthaltenen Formeln erfüllbar sind.

Die Frage, ob eine Formel (oder eine Formelmenge) eine der genannten Eigenschaften hat, ist ebenso wie die Frage, ob eine Formel allgemeingültig, d. h. eine Tautologie ist, für allgemeine Formeln nicht effizient lösbar: Zwar ist die Wahrheitstafel ein Entscheidungsverfahren für jede dieser Fragen, doch umfasst eine Wahrheitstafel für eine Aussage bzw. eine Aussagemenge in n Atomen $2^{n}$ Zeilen; das Wahrheitstafelverfahren ist nichts anderes als ein Brute-Force-Verfahren.

Jede dieser Fragestellungen kann auf die Frage zurückgeführt werden, ob eine bestimmte Formel erfüllbar ist:

• Eine Formel $\varphi$ ist genau dann eine Tautologie, wenn $\neg \varphi$ unerfüllbar ist.
• Eine Formel $\varphi$ ist genau dann widerlegbar, wenn $\neg \varphi$ erfüllbar ist.

Die Frage, ob eine Aussage erfüllbar ist, wird Erfüllbarkeitsproblem oder SAT-Problem (nach dem englischen Wort für Erfüllbarkeit, satisfiability) genannt. Das SAT-Problem spielt eine wichtige Rolle in der theoretischen Informatik und Komplexitätstheorie. Das Erfüllbarkeitsproblem für allgemeine (beliebige) Formeln ist NP-vollständig, d. h. (unter der Voraussetzung, dass P ungleich NP) nicht in polynomialer Laufzeit lösbar.

Für bestimmte echte Teilmengen der Formeln der aussagenlogischen Sprache ist das SAT-Problem dennoch schneller, d. h. in polynomial beschränkter Rechenzeit lösbar. Eine solche Teilmenge sind die Horn-Formeln, das sind Konjunktionen von Disjunktionen, deren Disjunkte verneinte oder unverneinte Atome sind, wobei innerhalb einer solchen Disjunktion allerdings höchstens ein Atom unverneint sein darf.

Algebraische Sicht

Wenn man die Semantik betrachtet, die hier für die klassische Aussagenlogik aufgestellt wurde, dann erkennt man gewisse Gesetzmäßigkeiten. Wird z. B. die Auswertungsfunktion auf eine Aussage der Form X ∧ W angewendet, wobei W eine beliebige wahre Aussage sein soll, dann stellt man fest, dass die Auswertungsfunktion für X ∧ W immer den Wahrheitswert wahr liefert, wenn V(X)=wahr ist (das heißt V(X∧W)=V(X)). Von der Struktur her gleichwertige Gesetzmäßigkeiten gelten auch in anderen Semantiken, auch in solchen, die für ganz andere, nichtlogische Systeme aufgestellt werden. Für die Arithmetik gilt z. B., dass die dortige Bewertungsfunktion (hier V_Arithmetik genannt) für einen Ausdruck der Form X + Y immer den Wert von X liefert, sofern der Wert von Y null ist: V_Arithmetik(X+Y)=V_Arithmetik(X), wenn V_Arithmetik(Y) = null ist.

Eine formale Wissenschaft, die solche strukturellen Gesetzmäßigkeiten untersucht, ist die abstrakte Algebra (meist Teilgebiet der Mathematik, aber auch der Informatik). In der abstrakten Algebra wird zum Beispiel untersucht, für welche Verknüpfungen es ein neutrales Element gibt, d. h. ein Element N, das für eine Verknüpfung op dazu führt, dass (für beliebiges X) gilt: X op N = X. So würde man aus algebraischer Sicht sagen, dass es für die klassische aussagenlogische Konjunktion genau ein neutrales Element gibt, nämlich wahr, und dass es für die Addition in der Arithmetik ebenfalls genau ein neutrales Element gibt, nämlich die Zahl Null. Nur am Rande sei erwähnt, dass es auch für andere Junktoren neutrale Elemente gibt; das neutrale Element für die Disjunktion ist falsch: V(X ∨ F) = V(X), wenn V(F)=falsch ist.

Die formale Algebra betrachtet formale Semantiken rein nach ihren strukturellen Eigenschaften. Sind diese identisch, dann besteht zwischen ihnen aus algebraischer Sicht kein Unterschied. Aus algebraischer Sicht, genauer: Aus Sicht der formalen Algebra ist die Semantik für die klassische Aussagenlogik eine zweiwertige Boolesche Algebra. Andere formale Systeme, deren Semantiken jeweils eine Boolesche Algebra bilden, sind die Schaltalgebra und die elementare Mengenlehre. Aus algebraischer Sicht besteht daher zwischen diesen Disziplinen kein Unterschied.

Normalformen

Jede aussagenlogische Formel lässt sich in eine äquivalente Formel in konjunktiver Normalform und eine äquivalente Formel in disjunktiver Normalform umformen.

Metatheorie

In der Metatheorie werden die Eigenschaften von logischen Systemen untersucht: Das logische System ist in der Metatheorie der Untersuchungsgegenstand.

Eine metatheoretische Fragestellung ist zum Beispiel die, ob in einem Kalkül ein Widerspruch hergeleitet werden kann.

Der vorliegende Abschnitt soll einige wichtige metatheoretische Fragestellungen aus dem Blickwinkel der Aussagenlogik betrachten.

Konsistenz

Ein Kalkül wird genau dann konsistent genannt, wenn es unmöglich ist, mit Hilfe seiner Axiome und Regeln einen Widerspruch herzuleiten, d. h. eine Aussage der Form P ∧ ¬ P (z. B. „Hugo ist groß, und Hugo ist nicht groß“). Für einen Kalkül, der in der Aussagenlogik verwendet werden soll, ist das eine Mindestanforderung.

Ist es in einem Kalkül möglich, einen Widerspruch herzuleiten, dann wird der Kalkül inkonsistent genannt.

Es gibt formale Systeme, in denen solch ein Widerspruch hergeleitet werden kann, die aber durchaus sinnvoll sind. Für solche Systeme wird ein anderer Konsistenzbegriff verwendet: Ein Kalkül ist konsistent, wenn in ihm nicht alle Formeln herleitbar sind (siehe parakonsistente Logik).

Es lässt sich leicht zeigen, dass für die klassische Logik die beiden Konsistenzbegriffe zusammenfallen: In der klassischen Logik lässt sich aus einem Widerspruch jeder beliebige Satz herleiten (dieser Sachverhalt wird Ex falso quodlibet genannt), d. h. wenn ein klassischer Kalkül auch nur einen Widerspruch herleiten könnte, also im ersten Sinn inkonsistent wäre, dann könnte er jede Aussage herleiten, wäre also im zweiten Sinn inkonsistent. Wenn umgekehrt ein Kalkül inkonsistent im zweiten Sinn ist, also in ihm jede Aussage herleitbar ist, dann ist insbesondere auch jeder Widerspruch herleitbar und ist er auch inkonsistent im ersten Sinn.

Korrektheit

Ein Kalkül heißt genau dann korrekt (semantisch korrekt), wenn in ihm nur solche Formeln hergeleitet werden können, die auch semantisch gültig sind. Für die klassische Aussagenlogik bedeutet das einfacher: Ein Kalkül ist genau dann korrekt, wenn in ihm nur Tautologien bewiesen und nur gültige Argumente hergeleitet werden können.

Ist es in einem aussagenlogischen Kalkül möglich, mindestens ein ungültiges Argument herzuleiten oder mindestens eine Formel zu beweisen, die keine Tautologie ist, dann ist der Kalkül inkorrekt.

Vollständigkeit

Vollständig (semantisch vollständig) heißt ein Kalkül genau dann, wenn in ihm alle semantisch gültigen Formeln hergeleitet werden können; für die klassische Aussagenlogik: Wenn in ihm alle Tautologien hergeleitet werden können.

Adäquatheit

Ein Kalkül heißt genau dann im Hinblick auf eine spezielle Semantik adäquat, wenn er (semantisch) korrekt und (semantisch) vollständig ist.

Ein metatheoretisches Resultat ist zum Beispiel die Feststellung, dass alle korrekten Kalküle auch konsistent sind. Ein anderes metatheoretisches Resultat ist die Feststellung, dass ein konsistenter Kalkül nicht automatisch korrekt sein muss: Es ist ohne weiteres möglich, einen Kalkül aufzustellen, in dem zwar kein Widerspruch hergeleitet werden kann, in dem aber z. B. die nicht allgemeingültige Aussage der Form „A ∨ B“ hergeleitet werden kann. Ein solcher Kalkül wäre aus ersterem Grund konsistent, aus letzterem Grund aber nicht korrekt.

Ein weiteres, sehr einfaches Resultat ist die Feststellung, dass ein vollständiger Kalkül nicht automatisch auch korrekt oder nur konsistent sein muss. Das einfachste Beispiel wäre ein Kalkül, in dem jede Formel der aussagenlogischen Sprache herleitbar ist. Da jede Formel herleitbar ist, sind alle Tautologien herleitbar, die ja Formeln sind: Das macht den Kalkül vollständig. Da aber jede Formel herleitbar ist, ist insbesondere auch die Formel P₀ ∧ ¬ P₀ und die Formel A ∨ B herleitbar: Ersteres macht den Kalkül inkonsistent, letzteres inkorrekt.

Das Ideal, das ein Kalkül erfüllen sollte, ist Korrektheit und Vollständigkeit: Wenn das der Fall ist, dann ist er der ideale Kalkül für ein logisches System, weil er alle semantisch gültigen Sätze (und nur diese) herleiten kann. So sind die beiden Fragen, ob ein konkreter Kalkül korrekt und/oder vollständig ist und ob es für ein bestimmtes logisches System überhaupt möglich ist, einen korrekten und vollständigen Kalkül anzugeben, zwei besonders wichtige metatheoretische Fragestellungen.

Abgrenzung und Philosophie

Die klassische Aussagenlogik, wie sie hier ausgeführt wurde, ist ein formales logisches System. Als solches ist sie eines unter vielen, die aus formaler Sicht gleichwertig nebeneinander stehen und die ganz bestimmte Eigenschaften haben: Die meisten sind konsistent, die meisten sind korrekt, etliche sind vollständig, und einige sind sogar entscheidbar. Aus formaler Sicht stehen die logischen Systeme in keinem Konkurrenzverhalten hinsichtlich Wahrheit oder Richtigkeit.

Von formalen, innerlogischen Fragen klar unterschieden sind außerlogische Fragen: Solche nach der Nützlichkeit (Anwendbarkeit) einzelner Systeme für einen bestimmten Zweck und solche nach dem philosophischen, speziell metaphysischen Status einzelner Systeme.

Die Nützlichkeitserwägung ist die einfachere, bezüglich deren Meinungsunterschiede weniger tiefgehend bzw. weniger schwerwiegend sind. Klassische Aussagenlogik zum Beispiel bewährt sich in der Beschreibung elektronischer Schaltungen (Schaltalgebra) oder zur Formulierung und Vereinfachung logischer Ausdrücke in Programmiersprachen. Prädikatenlogik wird gerne angewandt, wenn es darum geht, Faktenwissen zu formalisieren und automatisiert Schlüsse daraus zu ziehen, wie das unter anderem im Rahmen der Programmiersprache Prolog geschieht. Fuzzy-Logiken, nonmonotone, mehrwertige und auch parakonsistente Logiken sind hochwillkommen, wenn es darum geht, mit Wissensbeständen umzugehen, in denen Aussagen mit unterschiedlich starkem Gewissheitsgrad oder gar einander widersprechende Aussagen abgelegt werden sollen und dennoch sinnvolle Schlüsse aus dem Gesamtbestand gezogen werden sollen. Auch wenn es je nach Anwendungsfall sehr große Meinungsunterschiede geben kann, welches logisches System besser geeignet ist, ist die Natur des Problems für alle Beteiligten unmittelbar und in gleicher Weise greifbar. Einzelwissenschaftliche Überlegungen und Fragestellungen spielen sich überwiegend in diesem Bereich ab.

(Noch) kontroverser als solche pragmatischen Überlegungen sind Fragestellungen philosophischer und metaphysischer Natur. Geradezu paradigmatisch ist die Frage, „welches logische System richtig ist“, wobei „richtig“ hier gemeint ist als: Welches logische System nicht nur einen Teilaspekt der Wirklichkeit modellhaft vereinfacht, sondern die Wirklichkeit, das Sein als Ganzes adäquat beschreibt. Zu dieser Fragestellung gibt es viele unterschiedliche Meinungen einschließlich der vom philosophischen Positivismus eingeführten Meinung, dass die Fragestellung als Ganzes sinnlos ist.

In den Bereich metaphysischer Fragestellungen fällt auch die Frage, ob es so etwas wie ein metaphysisches Prinzip der Zweiwertigkeit gebe, ob also Aussagen über die Wirklichkeit durchgehend ins Schema wahr/falsch passen oder nicht. Diese Frage ist unabhängig von der Frage, ob die Beschäftigung mit zwei- oder mehrwertigen Logiken praktisch sinnvoll ist: Selbst wenn ein metaphysisches Prinzip der Zweiwertigkeit herrscht, könnte man anwendungspraktisch mehrwertige Logiken nützen, etwa dazu, epistemische Sachverhalte zu fassen, zum Beispiel aus Aussagen zu schließen, die zwar metaphysisch wahr oder falsch sind, von denen aber nicht oder noch nicht bekannt ist, welches von beidem der Fall ist. Umgekehrt kann man auch dann, wenn ein solches metaphysisches Prinzip nicht gilt, zweiwertige Logik wegen ihrer Einfachheit für solche Anwendungen bevorzugen, bei denen nur mit solchen Sätzen umgegangen werden muss, die tatsächlich wahr oder falsch sind.

Die Frage nach einem metaphysischen Prinzip der Zweiwertigkeit ist wie die meisten metaphysischen Fragen nicht endgültig zufriedenstellend beantwortet. Ein früher Einwand gegen ein solches Prinzip, den Aristoteles zur Diskussion stellte, war das Thema der Aussagen über zukünftige Sachverhalte („Morgen wird es regnen“). Wenn Aussagen über Zukünftiges schon heute wahr oder falsch wären, so wird argumentiert, dann müsse die Zukunft bis ins letzte Detail vorbestimmt sein. Ein anderer Einwand, der vorgebracht wird, ist, dass es Aussagen gibt, deren Wahrheit praktisch oder theoretisch nicht festgestellt werden kann – zum Beispiel lässt sich die Wahrheit von „Der Rasen vor dem Weißen Haus bestand am 1. Februar 1870 aus genau 6.120.375,4 Grashalmen“ einfach nicht feststellen.

Befürworter eines metaphysischen Zweiwertigkeitsprinzips berufen sich oft auf das Verhalten von Metatheoretikern, also von Mathematikern oder Logikern, die Aussagen über formale Systeme treffen: Egal wie mehrwertig oder nichtklassisch das untersuchte System ist, die dabei getroffenen Metavermutungen, Metabehauptungen und Metafeststellungen sind immer zweiwertig: Ein Kalkül, auch ein parakonsistenter oder nonmonotoner, wird immer als entweder konsistent oder inkonsistent betrachtet, und ein logisches System ist immer entweder korrekt oder inkorrekt, vollständig oder nicht vollständig, entscheidbar oder unentscheidbar, niemals „ein bisschen“ von beidem. Befürworter deuten das als Hinweis darauf, dass es in der Wirklichkeit tatsächlich eine strenge Unterscheidung nach wahr und falsch gebe oder dass es zumindest sinnvoll ist, eine solche anzunehmen.

Eine andere philosophische Fragestellung ist die nach dem metaphysischen Status des Untersuchungsgegenstands der Logik, also danach, was logische Systeme, Kalküle, Wahrheitswerte eigentlich „sind“.

Der platonische Standpunkt besteht darin, dass die in der Logik verwendeten Zeichen und Konstrukte eine außerlogische Bedeutung haben, dass sie Namen für real existierende (wenn auch natürlich nicht-physikalische) Gegenstände sind. In diesem Sinn gäbe es so etwas wie das Wahre und das Falsche, abstrakte Gegenstände, die von den Zeichen „wahr“ und „falsch“ benannt werden.

Der Gegenpol zum Platonismus wäre der Nominalismus, der Existenz nur den Zeichen zuspricht, die in der Logik manipuliert werden. Gegenstand der Logik sind Zeichen, und die Tätigkeit der Logiker ist die Manipulation von Zeichen. Die Zeichen bezeichnen aber nichts, so etwas wie das Wahre oder das Falsche gibt es also nicht. Im Grundlagenstreit der Mathematik entspräche der nominalistischen Position die formalistische Richtung.

Eine Mittelstellung nähme der philosophische Konstruktivismus ein, demzufolge die Zeichen zwar keine unabhängig existierenden Gegenstände bezeichnen, durch den Umgang mit den Zeichen aber Gegenstände konstruiert werden.

Literatur

• Jon Barwise, John Etchemendy: The Language of First Order Logic (= CSLI Lecture Notes. Bd. 23). 2. Auflage, revised and expanded. Center for the Study of Language and Information, Stanford CA 1991, ISBN 0-937073-74-1.
• Ansgar Beckermann: Einführung in die Logik. 2., neu bearbeitete und erweiterte Auflage. de Gruyter, Berlin u. a. 2003, ISBN 3-11-017965-2.
• Karel Berka, Lothar Kreiser: Logik-Texte. Kommentierte Auswahl zur Geschichte der modernen Logik. 4., gegenüber der 3., erweiterte, durchgesehene Auflage. Akademie-Verlag, Berlin 1986.
• Wolfgang Detel: Grundkurs Philosophie. Band 1: Logik (= Universal-Bibliothek. Nr. 18468). Reclam, Stuttgart 2007, ISBN 978-3-15-018468-4.
• Wilfrid Hodges: Logic. Penguin Books, Harmondsworth 1977, ISBN 0-14-021985-4 (2. Auflage. ebenda 2001 ISBN 0-14-100314-6).
• Rüdiger Inhetveen: Logik. Eine dialog-orientierte Einführung (= Eagle. Bd. 2). Edition am Gutenbergplatz, Leipzig 2003, ISBN 3-937219-02-1.
• E. J. Lemmon: Beginning Logic. Nelson, London 1965 (2. Auflage. Chapman & Hall, London 1987, ISBN 0-412-38090-0).
• Wesley C. Salmon: Logik. (= Universal-Bibliothek. Nr. 7996). Reclam Stuttgart 1983, ISBN 3-15-007996-9.
• Erich Grädel: Mathematische Logik. Mathematische Grundlagen der Informatik, SS 2009. RWTH, Aachen 2009, S. 129 (uni-dortmund.de [PDF]). 

Weblinks

Wikibooks: Mathe für Nicht-Freaks: Aussagenlogik – Lern- und Lehrmaterialien

Wiktionary: Aussagenlogik – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen

• Kevin C. Klement: Propositional Logic. In: J. Fieser, B. Dowden (Hrsg.): Internet Encyclopedia of Philosophy.
• Christian Spannagel: Aussagen- und Prädikatenlogik. Vorlesungsreihe, 2012.