Aussagenlogik

Die Aussagenlogik (mathematische Logik) ist ein Ausdrucksmittel der Mathematik, dem wir in unterschiedlicher Terminologie und in allen möglichen mathematischen Sätzen begegnen können.

Wozu Logik

Die Logik ist eine Wissenschaft, die sich mit dem Schlussfolgern, der Wahrheit, der Beweisbarkeit und der Widerlegbarkeit beschäftigt. Dabei geht es in der Logik nur um die Form einer Mitteilung. Es interessiert uns nicht, was konkret mitgeteilt wird, genauso wenig wie verschiedene psychologische Interpretationen und ähnliche Dinge.

Wenn wir zum Beispiel den Satz „die Zahl 2 ist gerade und gleichzeitig ungerade“ haben, können wir folgern, dass der ganze Satz nicht wahr ist, weil die Zahl 2 nicht ungerade ist. Das sind Dinge, die allgemein die Logik behandelt.

Aussage

Grundlage der Aussagenlogik ist natürlich die Aussage. Eine Aussage ist jeder Aussagesatz, dessen Wahrheitswert wir bestimmen können. Beispiele für einfache Aussagen:

• Der Mount Everest ist der höchste Berg der Erde.
• Die natürliche Zahl fünf ist eine ungerade Zahl.
• HTML ist eine Programmiersprache.
• Zwei plus drei ist sechs.

Das alles sind Aussagen. Egal, ob sie wahr sind (die ersten beiden) oder falsch (die letzten beiden). Keine Aussage ist zum Beispiel ein Fragesatz oder ein Satz, bei dem wir den Wahrheitswert nicht eindeutig bestimmen können. Wieder ein Beispiel:

• Wird der Mount Everest auch nächstes Jahr der höchste Berg der Erde sein?
• Grün ist die schönste Farbe.

Der erste Satz kann keine Aussage sein, weil er ein Fragesatz ist. Beim zweiten Satz können wir wiederum nicht entscheiden, ob es eine wahre oder eine falsche Aussage ist. Ein solcher Satz heißt dann Hypothese (Vermutung).

Die klassische mathematische Logik kommt mit vagen Sätzen wie „Max ist groß“ oder „Anna ist eine gute Sängerin“ nicht besonders gut zurecht. Solche Aussagen lassen sich besser zum Beispiel in der Fuzzy-Logik behandeln, die auf Vagheit zugeschnitten ist.

Atomare Aussage

Im ersten Kapitel hatten wir das Beispiel der Aussage „die Zahl 2 ist gerade und gleichzeitig ungerade“. Eine solche Aussage können wir zusammengesetzt nennen, weil sie in Wirklichkeit zwei kürzere Aussagen verbindet: „die Zahl 2 ist gerade“ und „die Zahl 2 ist ungerade“. Diese beiden Aussagen sind dann durch den Junktor „und“ oder auch „und gleichzeitig“ verbunden.

Eine atomare Aussage ist also eine Aussage, die wir nicht weiter zerlegen können; in gewissem Sinn ist es die einfachste Feststellung. Die vorherigen Beispiele für Aussagen waren in Wirklichkeit atomare Aussagen:

• Der Mount Everest ist der höchste Berg der Erde.
• Die natürliche Zahl fünf ist eine ungerade Zahl.
• HTML ist eine Programmiersprache.
• Zwei plus drei ist sechs.

Atomare Aussagen bezeichnen wir im Folgenden mit kleinen Buchstaben des Alphabets, klassisch p, q, r, …, und nennen sie Aussagenvariablen.

Junktoren

Die mathematische Logik arbeitet üblicherweise mit einer bestimmten Menge von Junktoren. Zu den grundlegenden gehören vier zweistellige Junktoren:

• p ∧ q ist die Konjunktion der Aussagen, wir lesen „Aussage p und (gleichzeitig) Aussage q“
• p ∨ q ist die Disjunktion der Aussagen, wir lesen „Aussage p oder Aussage q“
• p ⇒ q ist die Implikation, wir lesen „wenn Aussage p, dann Aussage q“
• p ⇔ q ist die Äquivalenz, wir lesen „Aussage p genau dann, wenn Aussage q“

Konkrete Beispiele für Junktoren:

• Im Zentrum von Leipzig regnet es und gleichzeitig scheint die Sonne. (Konjunktion)
• Im Zentrum von Leipzig regnet es oder die Sonne scheint. (Disjunktion)
• Apple ist die coolste Firma und Max ist der coolste Typ. (Konjunktion)
• Wenn du ein Abführmittel nimmst, dann musst du bald sch… (Implikation)
• Wenn die Zahl x durch vier teilbar ist, dann ist sie auch durch zwei teilbar. (Implikation)
• Anna ist hübsch und gleichzeitig klug. (Konjunktion)
• Sängerinnen sind erfolgreich genau dann, wenn sie hübsch sind. (Äquivalenz)
• Wenn es nicht regnet, werden wir nicht nass. (Implikation)
• Wenn Max singen kann, dann bin ich der chinesische Gott des Spaßes. (Implikation)

Wir kennen noch einen weiteren gängigen Junktor: die Negation. Die Negation wird entweder mit einem Strich p′ oder mit dem Symbol ¬p bezeichnet.

Formel

Mithilfe von Aussagenvariablen (atomaren Aussagen) und Junktoren können wir eine kompliziertere Aussage zusammensetzen, die wir Formel nennen. Alle Beispiele in der vorherigen Liste von Sätzen waren in Wirklichkeit Formeln, denn wir hatten zwei atomare Formeln, zum Beispiel „Im Zentrum von Leipzig regnet es“ und „die Sonne scheint“, und haben sie mit Junktoren verbunden. Im ersten Fall haben wir sie mit dem Junktor „und gleichzeitig“ verbunden und die Formel „Im Zentrum von Leipzig regnet es und gleichzeitig scheint die Sonne“ erhalten, im zweiten Fall haben wir „oder“ verwendet und die Formel „Im Zentrum von Leipzig regnet es oder die Sonne scheint“ erhalten.

Formal definieren wir die Formel so:

• Jede Aussagenvariable (atomare Aussage) ist eine Formel (genauer können wir sagen, dass es sich um eine atomare Formel handelt).
• Wenn A und B Formeln sind, dann sind auch ¬A, (A ∧ B), (A ∨ B), (A ⇒ B), (A ⇔ B) Formeln.

Die Definition ergibt Sinn: Im ersten Punkt sagen wir, dass jede atomare Aussage zugleich eine Formel ist. Wenn wir also zwei atomare Aussagen haben, zum Beispiel „Im Zentrum von Leipzig regnet es“ und „die Sonne scheint“, dann haben wir zugleich auch zwei Formeln. Jetzt können wir den zweiten Punkt anwenden und eine kompliziertere Formel zum Beispiel so zusammensetzen:

• Im Zentrum von Leipzig regnet es und gleichzeitig scheint die Sonne.
• Im Zentrum von Leipzig regnet es oder die Sonne scheint.
• Wenn im Zentrum von Leipzig die Sonne scheint, dann regnet es.
• Die Sonne scheint im Zentrum von Leipzig genau dann, wenn es regnet.

Formeln müssen natürlich nicht unbedingt wahr sein. Jetzt haben wir eine weitere Menge von Formeln erhalten, sodass wir noch kompliziertere Formeln zusammensetzen können. Wenn wir A=„Im Zentrum von Leipzig scheint die Sonne oder es regnet.“ (wir wissen schon, dass das eine Formel ist) und B=„man sieht einen Regenbogen“ (nehmen wir wieder an, dass es im Zentrum von Leipzig ist, damit wir es nicht ständig wiederholen müssen) bezeichnen, können wir weitere Formeln bilden. Die Klammern in den Sätzen kennzeichnen nur, auf welche Teile sich der Junktor bezieht.

• A ∧ B: (Im Zentrum von Leipzig scheint die Sonne oder es regnet) und gleichzeitig (man sieht einen Regenbogen).
• A ∨ B: (Im Zentrum von Leipzig scheint die Sonne oder es regnet) oder (man sieht einen Regenbogen).
• A ⇒ B: (Wenn im Zentrum von Leipzig die Sonne scheint oder es regnet), dann (sieht man einen Regenbogen).
• A ⇔ B: (Im Zentrum von Leipzig scheint die Sonne oder es regnet) genau dann, wenn (man einen Regenbogen sieht).

Das sind alles Formeln. Wir können also wieder eine dieser Formeln nehmen und eine weitere Formel an sie anfügen. So können wir zum Beispiel das Ungetüm „Wenn im Zentrum von Leipzig die Sonne scheint oder es regnet oder man einen Regenbogen sieht, dann scheint die Sonne oder es regnet genau dann, wenn man einen Regenbogen sieht.“ bilden.

Im nächsten Teil werden wir uns mit dem Wahrheitswert von Formeln beschäftigen.