Aussagenlogik

Dieser Artikel bedarf einer Überarbeitung. Eine Begründung befindet sich in der Regel auf der Diskussionsseite. Wenn du Lust hast, verbessere den Artikel und entferne anschließend diesen Baustein.

Die Aussagenlogik, auch (veraltet) Urteilslogik, ist ein Bereich der Logik, der sich mit der logischen Bewertung von Aussagen befasst. Dabei werden Elementaraussagen durch Junktoren verknüpft. Die Struktur der Elementaraussagen wird nicht untersucht. Dies leistet die Prädikatenlogik.

Dieser Artikel befasst sich mit der klassischen Aussagenlogik, in der der Satz vom ausgeschlossenen Dritten (also das "Tertium non datur") gilt: Jede Aussage ist entweder wahr oder falsch. Von einem konstruktivischen Standpunkt gesehen, der den Begriff "wahr" etwa im Sinne von "beweisbar" versteht, ist das nicht zwingend der Fall. Dieser Standpunkt findet seinen Ausdruck in Systemen der intuitionistischen Aussagenlogik. Siehe hierzu auch den Artikel Dialogische Logik.

Inhaltsverzeichnis

1 Umgangssprachliche Einleitung

1.1 Einfache Aussage (Elementaraussage)
1.2 Verneinte Aussage - Negation
1.3 und-verknüpfte Aussagen - Konjunktion
1.4 oder-verknüpfte Aussagen - Disjunktion
1.5 Folgerungen - Implikation bzw. Subjunktion
1.6 Gleichwertige Aussagen - Äquivalenz
1.7 Verneinung einer und-verknüpften Aussage
1.8 Verneinung einer oder-verknüpften Aussage
1.9 Die Verneinung der Äquivalenz - die Antivalenz oder Kontravalenz
1.10 Die Begriffe "notwendig" und "hinreichend"

2 Formaler Zugang

2.1 Einleitung
2.2 Syntax

2.2.1 Abkürzungen

2.3 Semantik/Aussagen

3 Erfüllbarkeit

4 Siehe auch

5 Literatur

Umgangssprachliche Einleitung

Einfache Aussage (Elementaraussage)

Eine Aussage A ist ein Satz, der entweder wahr (w, wahr, true) oder nicht wahr (f, falsch, false) ist. Dies 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.

Beispiele für einfache Aussagen:

$A 1$ : München ist 781 km von Hamburg entfernt.
$A 2$ : 9 ist durch 3 teilbar.
$A 3$ : Kaiserslautern wird in dieser Saison deutscher Fußballmeister.
$A 4$ : Alle Autos sind grün.

$A 2$ ist offensichtlich wahr, $A 4$ dagegen ist falsch. $A 1$ muss man zunächst prüfen, bevor man entscheiden kann, ob $A 1$ wahr oder falsch ist. Ob $A 3$ wahr ist, kann man derzeit nicht entscheiden. Das wird sich erst am Ende der Fußballsaison herausstellen.

In der klassischen Aussagenlogik ist eine Aussage entweder wahr oder nicht wahr, auch wenn man (noch) nicht in der Lage ist, den Wahrheitsgehalt zu beurteilen. Dies 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

Das Gegenteil bzw. die Verneinung einer Aussage A erhält man immer dadurch, dass man der Aussage A das Wort nicht geeignet einfügt. Formal schreibt man für "nicht A" ¬A, auf Englisch und in der Schaltalgebra auch "NOT A".

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

Wir verneinen die obigen Beispiele:

$\neg A_1$ : München ist nicht 781 km von Hamburg entfernt.
$\neg A_2$ : 9 ist nicht durch 3 teilbar
$\neg A_3$ : Kaiserslautern wird in dieser Saison nicht deutscher Fußballmeister.
$\neg A_4$ : Nicht alle Autos sind grün. Es kann durchaus grüne Autos geben und es gibt auch Autos, die nicht grün sind.

Allgemein gilt für die Verneinung:

Wenn eine Aussage $A$ wahr ist, dann ist die Verneinung $\neg A$ falsch.
Wenn eine Aussage $A$ falsch ist, dann 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

Man kann zwei Aussagen A und B durch das Wort und (Schreibweise: $\and$ ) miteinander verknüpfen. Dadurch erhält man eine neue Aussage $C$ .

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

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

$A$	$B$	$A \and B$
falsch	falsch	falsch
falsch	wahr	falsch
wahr	falsch	falsch
wahr	wahr	wahr

Beispiele für eine und-Verknüpfung:

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

Diese Teilaussagen und ihre Negationen werden nun durch $\and$ miteinander verknüpt:

$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 \and B$ ist wahr, weil $A$ wahr ist und auch $B$ wahr ist.
$C_2 = \neg A \and B$ ist falsch, weil $\neg A$ falsch ist.
$C_3 = A \and \neg B$ ist falsch, weil $\neg B$ falsch ist.
$C_4 = \neg A \and \neg B$ ist falsch, weil sowohl $\neg A$ als auch $\neg B$ falsch ist.

oder-verknüpfte Aussagen - Disjunktion

Man kann 2 Aussagen A und B durch das Wort oder miteinander verknüpfen und erhält so eine neue Aussage C. Achtung! Das logische oder hat eine andere Bedeutung als das umgangssprachliche "oder", das meist im Sinne von "entweder ... oder" benutzt wird.

Sprechweise: "A oder B"; genauer: "A oder auch B"
Schreibweise: $A \vee B$
auf Englisch und in der Schaltalgebra auch A OR B

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

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

Beispiel für eine oder-Verknüpfung:

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

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

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

Nur $C_8 = \neg A \vee \neg B$ ist falsch, weil $\neg A$ falsch ist und auch $\neg B$ falsch ist.
$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.

Folgerungen - Implikation bzw. Subjunktion

Wenn man aus einer wahren Aussage A schließen kann, dass dann auch die Aussage B wahr ist, spricht man von einer Implikation. Schreibweise: $A \Rightarrow B$

Ist man noch während des Dialogs in der Aussagenlogik, so spricht man von einer Subjunktion.

$A \rightarrow B$

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

Sprechweisen:

Aus A folgt B
Unter der Voraussetzung A gilt B
A impliziert B
Wenn A gilt, dann gilt auch B
Aussage B ist notwendig für Aussage A (siehe Abschnitt "notwendig und hinreichend")
Aussage A ist hinreichend für Aussage B (siehe Abschnitt "notwendig und hinreichend")

Beispiele:

Wenn es regnet, wird die unüberdachte Straße nass.
Wenn Person x einen Wagen der Marke BMW hat, dann hat x ein Auto.
n ist teilbar durch 6, also ist n teilbar durch 3.

Aus einer wahren Folgerung $A \Rightarrow B$ kann man eine weitere wahre Folgerung ableiten, nämlich $\neg B \Rightarrow \neg A$ .

Für die Beispiele bedeutet dies:

Wenn die unüberdachte Straße nicht nass ist, kann es nicht geregnet haben.
Wenn x kein Auto hat, kann x keinen Wagen der Marke BMW haben.
Wenn n nicht durch 3 teilbar ist, kann n nicht durch 6 teilbar sein.

Umgangssprachlich lässt man sich gelegentlich zu weiteren - falschen - Aussagen verleiten:

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 BMW, also hat x kein Auto.
falsch, denn er könnte ja einen Mercedes 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 quolibet" - "Aus Falschem - was du willst")

Die Implikation ist ein wichtiges Mittel in der Mathematik. Die meisten mathematischen Sätze sind eine Implikation.

Gleichwertige Aussagen - Äquivalenz

Zwei Aussagen A und B sind äquivalent, wenn gilt: $A \Rightarrow B$ und umgekehrt $B \Rightarrow A$ .

$A$	$B$	$A \Leftrightarrow B$
falsch	falsch	wahr
falsch	wahr	falsch
wahr	falsch	falsch
wahr	wahr	wahr

Schreibweise: $A \Leftrightarrow B$

Sprechweisen:

Aussage A ist äquivalent zu Aussage B.
A ist genau dann (dann und nur dann) wahr, wenn auch B wahr ist.
A ist notwendig und hinreichend für B. (siehe Abschnitt "notwendig und hinreichend")

Beispiel:

Die ganze 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.

Verneinung einer und-verknüpften Aussage

Die Verneinung zu der Aussage "A und B", also $\neg(A \and B)$
ist gleichwertig mit der oder-verknüpften Aussage $(\neg A) \vee (\neg B)$
Auf Englisch und in der Schaltalgebra schreibt man dafür A NAND B (not-and).

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

Beispiel:
Aussage A: Die ganze Zahl n ist durch 2 teilbar.
Aussage B: Die ganze Zahl n ist durch 3 teilbar.

Aussage "A und B": n ist durch 2 und durch 3 teilbar .

Verneinung: n ist nicht durch 2 und durch 3 teilbar.
Dies besagt dasselbe wie: n ist nicht durch 2 teilbar, oder n ist nicht durch 3 teilbar

Verneinung einer oder-verknüpften Aussage

Die Verneinung zu der Aussage "A oder B", also $\neg(A \vee B)$
ist gleichwertig mit der und-verknüpften Aussage $(\neg A) \and (\neg B)$
Auf Englisch und in der Schaltalgebra schreibt man dafür A NOR B (not-or).

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

Beispiel:
Aussage A: Die ganze Zahl n ist durch 2 teilbar.
Aussage B: Die ganze Zahl n ist durch 3 teilbar.

Aussage "A oder B": n ist teilbar durch 2 oder auch teilbar durch 3.

Verneinung: n weder durch 2 noch durch 3 teilbar.
Dies besagt dasselbe wie: n ist nicht durch 2 und auch nicht durch 3 teilbar

Die Verneinung der Äquivalenz - die Antivalenz oder Kontravalenz

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

Durch die Verneinung einer Äquivalenz-Aussage $A \Leftrightarrow B$
erhält man eine Antivalenz-Aussage $\neg(A \Leftrightarrow B)$ .
In Englisch und in der Schaltalgebra schreibt man dafür A XOR B (eXclusiv-or).

Sprechweisen:

Aussage A ist antivalent zu Aussage B.
Aussage A ist kontravalent zu Aussage B.
Entweder es gilt Aussage A oder es gilt Aussage B.

Antivalenz ist dann gegeben, wenn entweder nur A oder nur B wahr ist.

Angewandt auf die Beispiele:

Die ganze Zahl n ist entweder durch 2 und durch 3 teilbar, oder n ist nicht durch 6 teilbar.
Heute ist entweder Dienstag oder Mittwoch.

Die Begriffe "notwendig" und "hinreichend"

Betrachten wir die Implikation $A\Rightarrow B$

Man sagt: B ist notwendig für A. Ohne B kann A nicht erfüllt sein.

Ferner ist A hinreichend für B. Es reicht aus, dass A wahr ist. Dann ist auch B wahr.

Beispiel 1: Ist n durch 6 teilbar, dann ist n auch durch 3 teilbar. Teilbarkeit durch 3 ist notwendig für die Teilbarkeit von 6. Wenn n nicht durch 3 teilbar ist, dann kann n auch nicht durch 6 teilbar sein. Teilbarkeit durch 6 ist hinreichend für die Teilbarkeit durch 3. Wenn man weiß, dass n durch 6 teilbar ist, dann reicht dies aus, um zu wissen, dass n auch durch 3 teilbar ist. Teilbarkeit durch 3 ist zwar notwendig, dennoch nicht hinreichend für die Teilbarkeit durch 6. 9 ist durch 3 teilbar (notwendige Bedingung erfüllt) und 9 ist nicht teilbar durch 6.

Beispiel 2: Wenn x einen BMW hat, hat x ein Auto. Man muss Besitzer eines Autos sein, d.h. es ist notwendig, um überhaupt einen BMW besitzen zu können. Hat man kein Auto, kann man nicht gleichzeitig einen BMW haben, da man ja andernfalls ein Auto hätte. Es ist allerdings hinreichend, der Besitzer eines BMW zu sein, um mit Wahrheit sagen zu können, man habe ein Auto.

Beispiel 3: n ist genau dann durch 6 teilbar, wenn n durch 3 teilbar und gerade ist. Die Aussage "n ist durch 3 teilbar und n ist gerade" ist notwendig und hinreichend für die Teilbarkeit durch 6.

Mehr über "notwendig" und "hinreichend"

Formaler Zugang

Einleitung

Spätestens beim lauten Lesen von Sätzen wie:

"Die Aussage A∧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 Ergebnisse 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 hierzu eine Trennung der Sprachebenen unerlässlich ist: Die formale Aussage A∧B soll dadurch erklärt werden, dass auf einer metasprachlichen Ebene über die Aussage A wie auch über die Aussage B geredet wird.

Ein Versuch dies durchzuführen, besteht darin, die Aussagenlogik als formales System zu definieren. Die Begriffe "wahr" und "falsch" kommen in diesem System zunächst überhaupt nicht vor. Statt dessen werden Axiome gesetzt, die einfach als Zeichenketten angesehen werden, aus denen weitere "herleitbare" Zeichenketten aufgrund von bestimmten Schlussregeln hergeleitet werden.

Natürlich ist das Ziel dabei, 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 Konsistenz, das zweite die nach Vollständigkeit des formalen Systems.

Bei der klassischen Aussagenlogik, mit der wir es hier zu tun haben, ist dieses Problem gelöst. Das hängt damit zusammen, dass sich auf dieser Ebene der Logik auch keine Paradoxien formulieren lassen.

Syntax

Formale Definition aussagenlogischer Formeln

Sei V eine abzählbare unendliche Menge mit der Eigenschaft:

$V \cap \{ \vee, \wedge, \neg, (, ) \} = \empty$

Nenne V die Menge der atomaren Formeln. Eine aussagenlogische Formel wird definiert als Wort über dem Alphabet $V \cup \{ \vee, \wedge, \neg, (, ) \}$ und induktiv definiert:

alle atomaren Formeln $F \in V$ sind Formeln
ist F eine Formel, so ist auch $\neg F$ eine Formel
sind F und G zwei Formeln, so sind auch $(F \wedge G)$ und $(F \vee G)$ Formeln
keine anderen Wörter (die sich nicht über diese Definition herleiten lassen) sind aussagenlogische Formeln

$\neg F$ heißt Negation von F
$(F \wedge G)$ heißt Konjunktion (und) von F und G
$(F \vee G)$ heißt Disjunktion (oder) von F und G

Abkürzungen

$(F_1 \rightarrow F_2) = ( \neg F_1 \vee F_2 )$ (Implikation oder Subjunktion wenn ... dann..., wobei zu berücksichtigen ist, dass diese Äquivalenz bei der intuitionistischen Interpretation der Subjunktion nicht gilt! Siehe auch Dialogische Logik)
$(F_1 \leftrightarrow F_2) = ( F_1 \wedge F_2 ) \vee ( \neg F_1 \wedge \neg F_2 )$ (Äquivalenz oder Bisubjunktion ... genau dann wenn ...)

Semantik/Aussagen

Als Aussagen gelten Sätze, die als wahr oder falsch bestimmt werden können. Diese werden als logische Aussagen bezeichnet. Die Aussagenlogik beschäftigt sich mit dem korrekten Folgern, d.h. dem Schließen von Voraussetzungen (Prämissen) auf eine Schlussfolgerung (Konklusion). In der klassischen Aussagenlogik muss der Aussage dabei entweder wahr oder falsch zugeordnet werden, d.h. es gibt nur zwei Werte (Zweiwertigkeitsprinzip, tertium non datur).

Es können auch aussagenlogische Sprachen definiert werden, die mit weniger Operatoren arbeiten. Eine solche Sprache muss funktional vollständig sein, d.h. die vorhandenen Operatoren müssen mächtig genug sein, um alle booleschen Funktionen nachbilden zu können. Es gibt zwei Operatoren, mit denen alleine schon eine Aussagenlogik definiert werden kann: NAND (Nicht-Und, die negierte Konjunktion) und NOR (Nicht-Oder, die negierte Disjunktion).

Aussagen, die immer, d.h. für alle Belegungen ihrer Variablen, wahr sind (z.B. p oder ¬p), heißen Tautologien, Aussagen, die für alle Belegungen falsch sind (z.B. p und ¬p), heißen Kontradiktionen.

Die Aussagenlogik ist eine Ausprägung der Booleschen Algebra. Der nächste komplexere Logikformalismus ist die Prädikatenlogik.

Erfüllbarkeit

Die Feststellung, ob eine Aussage/Formel erfüllbar - oder eine Tautologie ist, ist für allgemeine Formeln nicht effizient lösbar. Bei einer Formel mit n atomaren Formeln sind $2 n$ Belegungen zu überprüfen (mittels Brute Force und Wahrheitstabellen). Das Erfüllbarkeitsproblem ist NP-vollständig.

Es gibt allerdings optimierte Algorithmen, die dieses Problem relativ schnell für Horn-Formeln oder für Formeln in KNF (Konjunktive Normalform) lösen können.

Eine ausführliche Beschreibung findet sich im Artikel Erfüllbarkeitsproblem der Aussagenlogik.

Siehe auch

Kategorie:Logik

Literatur

Rüdiger Inhetveen: Logik. Eine dialog-orientierte Einführung. Leipzig 2003 ISBN 3-937219-02-1