Einfache Aussage (Elementaraussage)

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:

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

${\displaystyle A_{2}}$ ist offensichtlich wahr (triviale mathematische Aussage), ${\displaystyle A_{4}}$ dagegen ist falsch (es gibt einfache Gegenbeispiele). ${\displaystyle A_{1}}$ stellt im mathematischen Sinne keine Aussage dar (ungenau genug in vielerlei Hinsicht, hat Interpretationsspielraum), gleiches gilt für ${\displaystyle 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: ${\displaystyle 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

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“.

${\displaystyle A}$	${\displaystyle \neg A}$
falsch	wahr
wahr	falsch

Wir verneinen die obigen Beispiele:

• ${\displaystyle \neg A_{1}}$: Es ist nicht der Fall, dass München 781 km von Hamburg entfernt ist.
• ${\displaystyle \neg A_{2}}$: Es ist nicht der Fall, dass 9 durch 3 teilbar ist.
• ${\displaystyle \neg A_{3}}$: Es ist nicht der Fall, dass Eintracht Frankfurt in der nächsten Saison deutscher Fußballmeister wird.
• ${\displaystyle \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 ${\displaystyle A}$ wahr ist, ist die Verneinung ${\displaystyle \neg A}$ falsch.
• Wenn eine Aussage ${\displaystyle A}$ falsch ist, ist die Verneinung ${\displaystyle \neg A}$ wahr.
• Eine Aussage ${\displaystyle A}$ kann nicht gleichzeitig wahr und falsch sein.
• Die Aussagen ${\displaystyle A}$ und ${\displaystyle \neg A}$ können nicht gleichzeitig wahr sein.

Und-verknüpfte Aussagen – Konjunktion

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 ${\displaystyle \land }$ (Schreibweise: ${\displaystyle A\land B}$), gelegentlich auch das kaufmännische Und, den Ampersand (&).

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

Die Aussage ${\displaystyle A\land B}$ ist immer dann wahr, wenn sowohl A als auch B jeweils wahr sind. Andernfalls ist ${\displaystyle 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

${\displaystyle A}$	${\displaystyle B}$	${\displaystyle A\land B}$
wahr	wahr	wahr
falsch	wahr	falsch
wahr	falsch	falsch
falsch	falsch	falsch

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

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

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

Nichtausschließendes Oder – 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 „${\displaystyle \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: ${\displaystyle A\vee B}$
• auf Englisch und in der Schaltalgebra auch A OR B

Die Aussage ${\displaystyle 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 ${\displaystyle 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

${\displaystyle A}$	${\displaystyle B}$	${\displaystyle A\vee B}$
wahr	wahr	wahr
falsch	wahr	wahr
wahr	falsch	wahr
falsch	falsch	falsch

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

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

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

Materiale 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

${\displaystyle A\rightarrow B}$

oder auch

${\displaystyle 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.

${\displaystyle A}$	${\displaystyle B}$	${\displaystyle A\rightarrow B}$	${\displaystyle \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 ${\displaystyle A\rightarrow B}$ auf ${\displaystyle \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 ${\displaystyle 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.

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:

${\displaystyle 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 ${\displaystyle 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 ${\displaystyle (A\rightarrow B)\land (B\rightarrow A)}$. Tatsächlich sind diese beiden Aussagen logisch äquivalent.

${\displaystyle A}$	${\displaystyle B}$	${\displaystyle 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 ${\displaystyle A\leftrightarrow B}$ genau dann eine Tautologie ist, wenn die beiden Aussagen A und B logisch äquivalent sind.

Ausschließendes Oder

${\displaystyle A}$	${\displaystyle B}$	${\displaystyle \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 ${\displaystyle \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)

Verneinung einer Konjunktion

Die Verneinung der Konjunktion „A und B“ (in der logischen Schreibweise: ${\displaystyle A\land B}$) lautet „Es ist nicht der Fall, dass A und B zutreffen“ (in der logischen Schreibweise: ${\displaystyle \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: ${\displaystyle (\neg A\lor \neg B)}$).

${\displaystyle A}$	${\displaystyle B}$	${\displaystyle \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 ${\displaystyle \neg (A\land B)}$.

Verneinung einer Disjunktion

Die Verneinung der Disjunktion „A oder B (oder beides)“ (in der logischen Schreibweise: ${\displaystyle A\lor B}$) lautet „Es ist nicht der Fall, dass A oder B zutrifft“ (in logischer Schreibweise: ${\displaystyle \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: ${\displaystyle \neg A\land \neg B}$).

${\displaystyle A}$	${\displaystyle B}$	${\displaystyle \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 ${\displaystyle \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 ${\displaystyle 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 Konsequens 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.

Einleitung

Spätestens beim lauten Lesen von Sätzen wie

„Die Aussage ${\displaystyle 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.

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:

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

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.

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.