Aussagenlogik

Die Aussagenlogik (englisch: propositional logic od. pr. calculus), auch (veraltet) Urteilslogik, ist ein Bereich der Logik, der sich mit der logischen Bewertung von Aussagen befasst.

Umgangssprachliche Einleitung

Einfache Aussage

Eine Aussage A ist eine Behauptung, die entweder wahr (w,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.

Beispiele für einfache Ausagen:

• A1: München ist 781 km von Hamburg entfernt.
• A2: 9 ist durch 3 teilbar
• A3: Kaiserslautern wird in dieser Saison deutscher Fussballmeister.
• A4: Alle Autos sind grün.

A2 ist offensichtlich wahr, A4 dagegen ist falsch. A1 muss man zunächst prüfen bevor man entscheiden kann, ob A1 wahr oder falsch ist. Ob A3 wahr ist kann man derzeit nicht entscheiden. Das wird sich erst am Ende der Fussballsaison herausstellen.

D.h. eine Aussage ist 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.

Mit nicht-verknüpfte 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.

Wir verneinen die obigen Beispiele:

• ¬A1: München ist nicht 781 km von Hamburg entfernt.
• ¬A2: 9 ist nicht durch 3 teilbar
• ¬A3: Kaiserslautern wird in der dieser Saison nicht deutscher Fussballmeister.
• ¬A4: Nicht alle Autos sind grün. Es kann durchaus grüne Autos geben, aber es gibt auch Autos die nicht grün sind.
  Näheres dazu im Abschnitt "Für alle ...".

Allgemein gilt für die Verneinung:

• Wenn eine Aussage A wahr ist, dann ist die Verneinung ¬A falsch.
• Wenn eine Aussage A falsch ist, dann ist die Verneinung ¬A wahr.
• Eine Aussage A kann nicht gleichzeitig wahr und falsch sein.

und-verknüpfte Aussage - Konjunktion

Man kann 2 Aussagen A und B miteinander verknüpfen durch das Wort und. Dadurch erhält man eine neue Aussage C.
Sprechweise: A und B
Schreibweise: $A\land 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 A oder B oder beide Ausagen falsch sind.

Beispiel für eine und-Verknüpfung:

• C1: 9 ist durch 3 teilbar und gleichzeitig eine Quadratzahl.
• C2: 9 ist nicht durch 3 teilbar und gleichzeitig eine Quadratzahl.
• C3: 9 ist durch 3 teilbar und keine Quadratzahl.
• C4: 9 ist nicht durch 3 teilbar und keine Quadratzahl.

In diesem Beispiel sind die Teilaussagen A = "9 ist durch 3 teilbar" und B = "9 ist eine Quadratzahl" bzw. deren Verneinung miteinander verknüpft.
Nur C1 = "A und B" ist wahr, weil A wahr ist und auch B wahr ist.
C2 = "¬A und B" ist falsch, weil ¬A falsch ist.
C3 = "A und ¬B" ist falsch, weil ¬B falsch ist.
C4 = "¬A und ¬B" ist falsch, weil sowohl ¬A als auch ¬B falsch ist.

oder-verknüpfte Aussage - Disjunktion

Man kann 2 Aussagen A und B miteinander verknüpfen durch das Wort oder und erhält so eine neue Aussage C.
Sprechweise: A oder B
Schreibweise:$A\vee 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.

Beispiel für eine oder-Verknüpfung:

• C5: 9 ist durch 3 teilbar oder 9 ist eine Quadratzahl.
• C6: 9 ist nicht durch 3 teilbar oder 9 ist eine Quadratzahl.
• C7: 9 ist durch 3 teilbar oder 9 ist keine Quadratzahl.
• C8: 9 ist nicht durch 3 teilbar oder 9 ist keine Quadratzahl.

In diesem Beispiel sind die Teilaussagen A = "9 ist durch 3 teilbar" und B = "9 ist eine Quadratzahl" bzw. deren Verneinung miteinander verknüpft.
Nur C8 = "¬A oder ¬B" ist falsch, weil ¬A falsch ist und auch ¬B falsch ist.
C5 = "A oder B" ist wahr, weil sowohl A als auch B wahr sind.
C6 = "¬A oder B" ist wahr, weil B wahr ist.
C7 = "A oder ¬B" ist wahr, weil A wahr ist.

Folgerungen - Implikation

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 => B

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:

• Es regnet => die unüberdachte Straße ist nass.
• Person x hat einen Wagen der Marke BMW => x hat ein Auto
• n ist teilbar durch 6 => n ist teilbar durch 3

Aus einer wahren Folgerung A => B kann man eine weitere wahre Folgerung ableiten, nämlich ¬B => ¬A. Für die Beispiele bedeutet dies:

• Die unüberdachte Straße ist nicht nass => es regnet nicht
• x hat kein Auto => x hat keinen Wagen der Marke BMW
• n ist nicht durch 3 teilbar => n ist nicht durch 6 teilbar.

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

• Es regnet nicht => Die Straße ist nicht nass.
  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 => x hat kein Auto
  falsch, denn er könnte ja einen Mercedes haben
• n ist nicht durch 6 teilbar => n ist nicht durch 3 teilbar.
  Auch diese Folgerung ist falsch. Die Zahl 15 ist nicht durch 6 teilbar, wohl aber durch 3.

Das bedeutet: Wenn die Folgerung A => B wahr ist, dann erhält man aus der Aussage ¬A keine Aussage über B; B kann wahr oder falsch sein.

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

Verneinung einer und-verknüpften Aussage

Die Verneinung zu der Aussage "A und B" lautet:

¬(A und B) <=> (¬A) oder (¬B)

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 teilbar durch 2 und n ist teilbar durch 3

Verneinung: ¬(n ist teilbar durch 2 und n ist teilbar durch 3) <=> (n ist nicht teilbar durch 2) oder (n ist nicht teilbar durch 3)

Verneinung einer oder-verknüpften Aussage

Die Verneinung zu der Aussage "A oder B" lautet:

¬(A oder B) <=> (¬A) und (¬B)

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 n ist teilbar durch 3

Verneinung: ¬(n ist teilbar durch 2 oder n ist teilbar durch 3) <=> (n ist nicht teilbar durch 2) und (n ist nicht teilbar durch 3)

Gleichwertige Aussagen - Äquivalenz

Zwei Aussagen A und B sind äquivalent, wenn gilt: A => B und umgekehrt B => A.

Schreibweise: A <=> B

Sprechweisen:

• Aussage A ist zu Aussage B äquivalent
• A ist genau 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 durch 6 teilbar <=> n ist durch 2 und durch 3 teilbar.
  Wenn n durch 6 teilbar ist, dann folgt daraus, dass n durch 2 und durch 3 teilbar ist. Umgekehrt gilt: Wenn n durch 2 und durch 3 teilbar ist, dann ist n durch 6 teilbar.
• Heute ist Dienstag <=> Morgen ist Mittwoch

Auch die Verneinung einer Äquivalenz ist richtig:

A <=> B kann man auch verneinen ¬A <=> ¬B

Angewandt auf die Beispiele:

• Die ganze Zahl n ist nicht durch 6 teilbar <=> ¬(n ist durch 2 und durch 3

teilbar) <=> (n ist nicht durch 2 teilbar) oder (n ist nicht durch 3 teilbar)

• Heute ist nicht Dienstag <=> Morgen ist nicht Mittwoch

Die Begriffe "notwendig" und "hinreichend"

Betrachten wir die Implikation A => 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: n ist durch 6 teilbar => n ist 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, aber nicht hinreichend für die Teilbarkeit durch 6. 9 ist durch 3 teilbar (notwendige Bedingung erfüllt), aber 9 ist nicht teilbar durch 6.

Beispiel 2: x hat einen BMW => x hat 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 eine Auto.

Beispiel 3: n ist durch 6 teilbar <=> n ist durch 3 teilbar und n ist gerade Sie Aussage "n ist durch 3 teilbar und n ist gerade" ist notwendig und hinreichend für die Teilbarkeit durch 6.

Formaler Zugang

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

Aussagen können mit zweistelligen Operatoren verknüpft werden:

• Konjunktion und
• Disjunktion oder
• Implikation wenn ... dann...
• Äquivalenz ...genau dann wenn ...

Sie können auch negiert werden:

• Negation nicht

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 v ~p), heißen Tautologien, Aussagen, die für alle Belegungen falsch sind (z.B. p & ~p), heißen Kontradiktionen.

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

Siehe auch: Prädikatenlogik, Wahrheitstabelle