Aussagenlogik

aus Freepedia, der freien Wissensdatenbank

Dieser Artikel bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf bitte mit, ihn zu verbessern und entferne anschließend diese Markierung.

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.

Eine Erweiterung der Aussagenlogik ist die Prädikatenlogik, bei der auch die Eigenschaften von Objekten und ihre Geltungsbereiche betrachtet wird.

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:

<math>A_1</math>: München ist 781 km von Hamburg entfernt.
<math>A_2</math>: 9 ist durch 3 teilbar.
<math>A_3</math>: Kaiserslautern wird in dieser Saison deutscher Fußballmeister.
<math>A_4</math>: Alle Autos sind grün.

<math>A_2</math> ist offensichtlich wahr, <math>A_4</math> dagegen ist falsch. <math>A_1</math> muss man zunächst prüfen, bevor man entscheiden kann, ob <math>A_1</math> wahr oder falsch ist. Ob <math>A_3</math> 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: <math>A_4</math> 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".

<math>A</math>	<math>\neg A</math>
falsch	wahr
wahr	falsch

Wir verneinen die obigen Beispiele:

<math>\neg A_1</math>: München ist nicht 781 km von Hamburg entfernt.
<math>\neg A_2</math>: 9 ist nicht durch 3 teilbar
<math>\neg A_3</math>: Kaiserslautern wird in dieser Saison nicht deutscher Fußballmeister.
<math>\neg A_4</math>: 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 <math>A</math> wahr ist, dann ist die Verneinung <math>\neg A</math> falsch.
Wenn eine Aussage <math>A</math> falsch ist, dann ist die Verneinung <math>\neg A</math> wahr.
Eine Aussage <math>A</math> kann nicht gleichzeitig wahr und falsch sein.
Die Aussagen <math>A</math> und <math>\neg A</math> können nicht gleichzeitig wahr sein.

Und-verknüpfte Aussagen - Konjunktion

Man kann zwei Aussagen A und B durch das Wort und (Schreibweise: <math>\and</math>) Dadurch erhält man eine neue Aussage <math>C</math>.

Sprechweise: A und B
Schreibweise: <math>A \and B</math>
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.

<math>A</math>	<math>B</math>	<math>A \and B</math>
wahr	wahr	wahr
falsch	wahr	falsch
wahr	falsch	falsch
falsch	falsch	falsch

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 <math>\and</math> miteinander verknüpt:

<math>C_1</math>: 9 ist durch 3 teilbar und 9 ist eine Quadratzahl.
<math>C_2</math>: 9 ist nicht durch 3 teilbar und 9 ist eine Quadratzahl.
<math>C_3</math>: 9 ist durch 3 teilbar und 9 ist keine Quadratzahl.
<math>C_4</math>: 9 ist nicht durch 3 teilbar und 9 ist keine Quadratzahl.

Nur <math>C_1 = A \and B</math> ist wahr, weil <math>A</math> wahr ist und auch <math>B</math> wahr ist.
<math>C_2 = \neg A \and B</math> ist falsch, weil <math>\neg A</math> falsch ist.
<math>C_3 = A \and \neg B</math> ist falsch, weil <math>\neg B</math> falsch ist.
<math>C_4 = \neg A \and \neg B</math> ist falsch, weil sowohl <math>\neg A</math> als auch <math>\neg B</math> 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: <math>A \vee B</math>
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.

<math>A</math>	<math>B</math>	<math>A \vee B</math>
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 <math>\vee</math> miteinander verknüpt:

<math>C_5</math>: 9 ist durch 3 teilbar oder 9 ist eine Quadratzahl.
<math>C_6</math>: 9 ist nicht durch 3 teilbar oder 9 ist eine Quadratzahl.
<math>C_7</math>: 9 ist durch 3 teilbar oder 9 ist keine Quadratzahl.
<math>C_8</math>: 9 ist nicht durch 3 teilbar oder 9 ist keine Quadratzahl.

Nur <math>C_8 = \neg A \vee \neg B</math> ist falsch, weil <math>\neg A</math> falsch ist und auch <math>\neg B</math> falsch ist.
<math>C_5 = A \vee B</math> ist wahr, weil sowohl <math>A</math> als auch <math>B</math> wahr sind.
<math>C_6 = \neg A \vee B</math> ist wahr, weil <math>B</math> wahr ist.
<math>C_7 = A \vee \neg B</math> ist wahr, weil <math>A</math> 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: <math>A \Rightarrow B</math>

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

<math>A \rightarrow B</math>

<math>A</math>	<math>B</math>	<math>A \rightarrow B</math>
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 <math>A \Rightarrow B</math> kann man eine weitere wahre Folgerung ableiten, nämlich <math>\neg B \Rightarrow \neg A</math>.

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 <math>A \Rightarrow B</math> 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: <math>A \Rightarrow B</math> und umgekehrt <math>B \Rightarrow A</math>.

<math>A</math>	<math>B</math>	<math>A \Leftrightarrow B</math>
falsch	falsch	wahr
falsch	wahr	falsch
wahr	falsch	falsch
wahr	wahr	wahr

Schreibweise: <math>A \Leftrightarrow B</math>

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 verknüpften Aussage (De Morgansche Gesetze):

Verneinung einer Konjunktion

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

<math>A</math>	<math>B</math>	<math>\neg(A \and B)</math>
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 gleichermaßen 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 Disjunktion

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

<math>A</math>	<math>B</math>	<math>\neg(A \vee B)</math>
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

<math>A</math>	<math>B</math>	<math>\neg(A \Leftrightarrow B)</math>
falsch	falsch	falsch
falsch	wahr	wahr
wahr	falsch	wahr
wahr	wahr	falsch

Durch die Verneinung einer Äquivalenz-Aussage <math>A \Leftrightarrow B</math>
erhält man eine Antivalenz-Aussage <math>\neg(A \Leftrightarrow B) </math>.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 <math>A\Rightarrow B</math>.

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 ableitbare 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ählbar unendliche Menge mit der Eigenschaft:

<math>V \cap \{ \vee, \wedge, \neg, (, ) \} = \empty</math>

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

Alle atomaren Formeln <math>F \in V</math> sind Formeln.
Ist F eine Formel, so ist auch <math> \neg F</math> eine Formel.
Sind F und G zwei Formeln, so sind auch <math>(F \wedge G) </math> und <math>(F \vee G)</math> Formeln.
Kein anderes Wort (das sich nicht über diese Definition herleiten lässt) ist eine aussagenlogische Formel.

<math> \neg F</math> heißt Negation von F
<math>(F \wedge G) </math> heißt Konjunktion (und) von F und G
<math>(F \vee G)</math> heißt Disjunktion (oder) von F und G

Abkürzungen

<math>(F_1 \Rightarrow F_2) = ( \neg F_1 \vee F_2 )</math> (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)
<math>(F_1 \Leftrightarrow F_2) = ( F_1 \wedge F_2 ) \vee ( \neg F_1 \wedge \neg F_2 ) </math> (Äquivalenz oder Bijunktion ... 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).

Bei der Wahl einer aussagenlogischen Sprache sind wir frei. Jede Auswahl unter den 16 verschiedenen Operatoren, die es gibt, können zu einer Definition einer aussagenlogischen Sprache herangezogen werden. Darunter sind zwei, die bereits jeweils einzeln semantisch vollständig sind: NAND (Nicht-Und, die negierte Konjunktion) und NOR (Nicht-Oder, die negierte Disjunktion).

Generell kann man mit Hilfe des Postschen Vollständikeitskriteriums herausfinden, ob die Auswahl an Operatoren vollständig für die Aussagenlogik sind. Wenn eine solche Auswahl minimal ist, heißt sie auch Basis für die Aussagenlogik.

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ächst 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 <math>2^n</math> 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

Literatur

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

Von "http://de.freepedia.org/Aussagenlogik.html"

Seitenkategorien: Wikipedia Überarbeiten | Logik