Einführung in die Logik/ Aussagenlogik

Aussagenlogik

Was heißt Aussagenlogik?

Die "Aussagenlogik" geht vor allem auf Frege zurück. Frege arbeitete sie in seiner berühmten Begriffsschrift aus. Die Aussagenlogik wurde später von Russel weiterentwickelnt, noch später von Wittgenstein im Tractatus logico-philosophicus. Mit diesem neuen Teilgebiet der Logik beginnt die moderne Logik, die auch mathematische oder Symbollogik genannt wird. Bei der Aussagenlogik geht es um Verknüpfungen von Elementarsätzen (Wittgenstein), die durch symbolische Variablen ersetzt werden, mittels so genannter "Junktoren", den Aussageverknüpfungen. Auf diese Weise kann man die Wahrheitswerte komplexer Aussagen immer genau bestimmten, wenn die Wahrheitswerte der Elementaraussagen bekannt sind. Die Wahrheitswerte bestimmt man mit Hilfe so genannter Wahrheitstafeln.

Elementaraussagen

Der Begriff "Elementarsatz" geht unmittelbar auf Wittgensteins für die Entwicklung der Aussagnelogik wichtigen Tractatus logico-philosophicus zurück. Unter einem Elementarsatz oder einer Elementaraussage versteht man die kleinste sprachliche Einheit, die noch einen Wahrheitswert annehmen und somit wahr oder falsch sein kann.

Variablen

Eine Variable ist in der formalen Logik ein "sprachliches Zeichen, für das beliebige Ausdrücke einer bestimmten Art eingesetzt werden können". Im Gegensatz zu logischen Konstanten haben Variablen keine selbständige Bedeutung". und sind "bedeutungsleere Zeichen, die nur dazu dienen, die Stellen anzuzeigen, an denen die bedeutungsvollen Konstanten ... einzusetzen sind.

Welche Ausdrücke für eine Variable eingesetzt werden dürfen, wird durch eine vorgegebene Menge von Elementen bestimmt. Diese wird Grund-, Objekt-, Definitions- oder Variabilitätsbereich oder Extension einer Variable genannt.

Die Ausdrücke, die für bestimmte Variable eingesetzt werden dürfen, heißen auch Werte dieser Variablen. Variablen repräsentieren ihre Werte. Man sagt auch, dass die Variablen die Menge der Gegenstände, die durch die Konstanten (ihre Werte) bezeichnet werden, durchlaufen.

In der Aussagenlogik verwendet man Variablen für die einzelnen Elementaraussagen. So sind entweder kleine Buchstaben gebräuchlich ( p, q, r usw.) oder auch große Buchstaben ( A, B, C usw.)

Wahrheitstabellen

Eine Wahrheitswertetabelle oder kurz Wahrheitstabelle sieht meist ungefähr so aus:

p	q	p ∧ q
w w f f	w f w f	w f f w

Links stehen die möglichen Wahrheitswerte der Elementaraussagen und rechts, welchen Wahrheitswert die Gesamtaussage dann hat. Man kann daraus auch ablesen, welchen Wert ein Atom hat, wenn der Wahrheitswert der anderen Atome und der Gesamtaussage gegeben sind. Die Junktoren

In der formalen Sprache, die wir in diesem Buch hauptsächlich verwenden, gibt es sechs Junktoren. Insgesamt gibt es sogar siebzehn Junktoren, einen zweistelligen und 16 Dreistellige, für jede denkbare Wahrheitstabelle einen, aber nur die folgenden sechs sind allgemein gebräuchlich:

Die Negation bzw. das "Nicht"

Dieser Junktor wird ¬ geschrieben. In der natürlichen Sprache entspricht ¬ p "nicht p". Er kehrt den Wahrheitswert der Aussage hinter ihm um. Die Negation ist der einzige in diesem Buch verwendete Junktor, zu dem nicht zwei Aussagen gehören. Daher nennt man ihn auch einen "zweistelligen Junktor".

Wahrheitstabelle:

p	¬ p
w f	f w

Die Konjunktion bzw. das "Und"

Diesen Junktor schreiben wir ∧. Die sprachliche Entsprechung von p ∧ q ist "p und q". Eine Konjunktion ist also nur wahr, wenn sowohl die Aussage davor als auch die danach wahr ist.

Wahrheitstabelle:

p	q	p ∧ q
w w f f	w f w f	w f f w

Die Disjunktion bzw. das "Oder"

Dieser Junktor wird ∨ geschrieben. Zu vergleichen ist p ∨ q mit "p oder q", allerdings nicht mit dem im Sinne von "entweder p oder q (nicht beides)" sondern mit der gewöhnlichen Bedeutung, in der auch beide zugehörigen Aussagen wahr sein dürfen. Das "entweder p oder q" wird auch "Exklusion"genannt.

Wahrheitstabelle:

p	q	p ∨ q
w w f f	w f w f	w w w f

Die Disjunktion ist unwahr, wenn die Aussage davor und die danach Unwahr ist und ansonsten wahr.

Die Implikation bzw. das "Immer-Wenn-Dann"

In diesem Buch schreiben wir die Implikation mit →. Man kann p → q mit „wenn p, dann q“ übersetzen.

Wahrheitstabelle:

p	q	p → q
w w f f	w f w f	w f w w

Zur Erklärung gucken wir uns am besten einen Beispielsatz an: „Wenn morgen die Sonne scheint, ist es morgen heiß“. Angenommen die Sonne scheint und es ist heiß, ist die Aussage offensichtlich war. Wenn die Sonne scheint und es nicht heiß ist, ist die Aussage offenbar unwahr. Wenn die Sonne nicht scheint, ist die Bedingung dafür, dass das zweite Atom nach dieser Aussage unbedingt wahr ist, überhaupt nicht gegeben. Daher ist es in dem Fall irrelevant, ob die Sonne scheint oder nicht, die Aussage ist wahr. Wenn man die Aussage „Immer wenn die Sonne scheint, ist es heiß.“ nimmt, widerspricht es ihr ja nicht, wenn es einmal heiß ist, und die Sonne nicht scheint, solange es immer noch bzw. wieder heiß ist, wenn die Sonne scheint.

Die Replikation bzw. das "Nur-Wenn-Denn"

In diesem Buch schreiben wir die Implikation mit ←. Man kann p ← q mit "nur wenn p, dann q" übersetzen.

Wahrheitstabelle:

p	q	p ← q
w w f f	w f w f	w w f w

Zur Erklärung gucken wir uns am besten einen Beispielsatz an: „Nur wenn morgen die Sonne scheint, wasche ich morgen das Auto“. Angenommen die Sonne scheint und ich wasche das Auto, ist die Aussage offensichtlich wahr. Wenn die Sonne scheint und ich wasche das Auto nicht, ist die Aussage ebenfalls wahr. Nur wenn die Sonne nicht scheint, und ich wasche das Auto trotzdem, ist die Aussage falsch.

Die Äquivalenz bzw. das "Genau-Dann-Wenn"

Die Äquivalenz wird formal ↔ geschrieben. Die natursprachliche Entsprechung zu p ↔ q st „q genau dann, wenn p“. Sie ist dann wahr, wenn sowohl die Aussage davor, als auch die danach wahr ist oder beide falsch sind. Ansonsten ist sie falsch.

Wahrheitstabelle:

p	q	p ↔ q
w w f f	w f w f	w f f w

Die (logische) Äquivalenz ist nur dann wahr, wenn "entweder" p "oder" q wahr sind. Ansonsten ist sie falsch. Man sollte verstanden haben, warum diese Wahrheitstabellen genau so aussehen und was die Junktoren dann bedeuten, dann muss man sie auch nicht auswendig lernen. Auf jeden Fall sollte man sie aber rekonstruieren können.

Notwendige und hinreichende Bedingung

Seien p und q Sachverhalte;

(1) Wenn gilt (d.h., wenn wahr ist): "immer" wenn p, dann q (Implikation); dann heißt p hinreichende Bedingung für q .

(2) Wenn gilt (d.h., wenn wahr ist): "nur" wenn p, dann q (Replikation); dann heißt p notwendige Bedingung für q.

Im Falle begrifflicher Abhängigkeitsverhältnisse erlaubt die Kenntnis, dass p hinreichend für q den Schluss, dass q notwendig für p ist, und umgekehrt.

Klammern und Klammerregeln

Die Klammern haben eigentlich die gleiche Bedeutung wie in der Mathematik. Die Ausdrücke in den Klammern werden zuerst ausgewertet. Ausdrückliche Klammerregeln sind wohl wenig sinnvoll, denn grundsätzlich muss es möglich sein, die Klammen frei zu setzen, und wenn ich eine Veränderung der Klammersetzung vornehme, ergibt sich auch eine komplett andere Aussage. Wir wollen es in dieser Einführung so handhaben, dass "immer" Klammern gesetzt werden, wo es sinnvoll ist. Eine Wertigkeit der Junktoren, wie bei der Regel "Punktrechnung geht vor Strichrechnung" in der Mathematik, erübrigt sich hier also.

Die aussagenlogische Form

Die einfachste aussagenlogische Form einer Aussage erhält man durch Einsetzung von Aussagenvariablen für alle elementaren Teilaussagen der Aussage, durch Einsetzung von Junktoren für die grammatischen Konjunktionen der Aussage sowie durch Klammerung zur sinngemäßen Gliederung komplexer Aussagen.

Übersetzung in die aussagenlogische Form

Will man eine komplexe aussage in die aussagenlogische Form übersetzen, muss man zuerst Anpassungen an der Sprache vornehmen, wie das Benutzen von Junktoren der formalen Sprache.

Beispiel:

Wenn gilt, dass ich nicht nach Hause fahre sondern gehe, dann friere ich und werde nass.

⇔ Wenn gilt, dass ich nicht nach Hause fahre und ich nach Hause gehe, dann gilt, dass ich friere und nass werde.

⇔ Ich fahre nicht nach Hause und ich gehe nach Hause ⇒ ich friere und ich werde nass.

⇔ Ich fahre nicht nach Hause ∧ ich gehe nach Hause ⇒ ich friere ∧ ich werde nass.

⇔ ¬ ich fahre nach Hause ∧ ich gehe nach Hause ⇒ ich friere ∧ ich werde nass.

Und jetzt endlich die eigentliche aussagenlogische Form:

⇔ ¬ p ∧ q ⇒ r ∧ s

Und ganz noch die richtige Klammersetzung:

⇔ ( ¬ p ∧ q ) → ( r ∧ s )

Rückübersetzung in die sprachliche Form

Wenn man die formale Sprache in die natürliche Sprache übersetzen will, kann es hilfreich sein, schrittweise vorzugehen. Als erstes übersetzt man den Junktor, der von keiner Klammer umgeben ist (oder von den wenigsten, für den unwahrscheinliche Fall, dass die ganze Aussage in Klammern steht), anschließend die mit den zweitwenigsten und so weiter. Anschließend ersetzt man die Satzsymbole eventuell durch Wörter, die auch für ein reales Objekt stehen. Dann kann man vielleicht noch verschiedene andere Verbesserungen vornehmen, die man dann intuitiv machen kann.

Beispiel:

( p ∧ ( q ∨ r ) ) → ( ( s ∨ t ) ∧ ¬ ( s ∧ d ) )

⇔ Wenn ( p ∧ ( q ∨ r ) ) gilt, dann gilt ( ( s ∨ t ) ∧ ¬ ( s ∧ d ) )

⇔ Wenn p gilt und q ∨ r gilt, dann gilt s ∨ t und es gilt ¬ ( s ∧ t )

⇔ Wenn p gilt und q oder r gilt, dann gilt s oder t und es gilt nicht s ∧ t

⇔ Wenn p gilt und q oder r gilt, dann gilt s oder t und es gilt nicht s und t

Jetzt müssen nur noch die Variablen ersetzt werden. Für p = "Ich gehe in die Stadt", q = "Ich habe Geld dabei", r = "Ich habe eine Kreditkarte dabei", s = "Ich kaufe ein Hemd", t = "Ich kaufe ein T-Shirt" ergibt sich die folgende sprachliche Form:

⇔ Wenn gilt, dass ich in die Stadt gehe und es gilt, dass ich Geld dabeihabe oder eine Kreditkarte dabeihabe, dann gilt, dass ich ein Hemd kaufe oder ein T-Shirt kaufe und es gilt nicht, dass ich ein Hemd kaufe und ein T-Shirt kaufe.

Oder etwas eleganter:

⇔ Wenn ich in die Stadt gehe, und Geld oder eine Kreditkarte dabeihabe, dann kaufe ich entweder ein Hemd oder ein T-Shirt. Das seltsame "gilt", das in den Sätzen vorkam ist ein Trick, um klarzumachen, wie die Junktoren der natürlichen Sprache geklammert werden müssen. In der gesprochenen Sprache gibt es dafür Betonungen, an denen man das feststellen kann, in der geschriebenen wäre zum Beispiel der vorletzte Schritt mehrdeutig.

Im Satz "Ich gehe in die Stadt und habe Geld oder eine Kreditkarte dabei" wurde das Verb "habe dabei" beim Teil mit dem Geld dabeihaben weggelassen. Dadurch ist klar, dass "habe" Geld oder eine Kreditkarte "dabei" eine Elementare Einheit ist, und die Klammern direkt darum gemacht werden müssen.

Erstellen von Wahrheitstabellen

Thomas Zoglauer schreibt in seiner "Einführung in die Logik für Philosophien":

"Jede komplexe Aussageform lässt sich in einer Wahrheitstafel in ihre Wahrheitswerte entwickeln. Hierzu gibt man den Wahrheitswert der ganzen Aussage in Abhängigkeit der Wahrheitswerte der Aussagenvariablen an. Enthält die Aussage 2 Wahrheitswerte, so sind 4 Fälle möglich, bei 3 Variablen muss man 8 Fallunterscheidungen machen usw."

Beispiel:

Wir wollen die Wahrheitstafel von ¬ p ∧ ( q → p ) aufstellen.

p	q	¬ p	q → p	¬ p ∧ ( q → p )
w w f f	w f w f	f f w w	w w f f	f f f w

Ergebnis: Die Aussageform ¬ p ∧ ( q → p ist genau dann wahr, wenn p und q wahr sind. Ansonsten ist sie falsch. Und weiter schreibt Zoglauer:

"Eine Aussageform heißt Tautologie, wenn sie für jede Belegung der Variablen mit Wahrheitswerten einen wahren Ausdruck liefert. Man sagt auch: Der Ausdruck ist allgemeingültig (oder tautologisch)."

Beispiel:

Wir wollen zeigen, dass ( ( p → q ) ∧ p ) → q eine Tautologie ist.

p	q	p → q	( p → q ) ∧ p	¬ p ∧ ( q → p )
w w f f	w f w f	w f w w	w f f f	w w w w

Ergebnis: Die Aussageform ( ( p → q ) ∧ p ) → q liefert "immer" einen wahren Ausdruck. Damit handelt es sich bei ihr um eine Tautologie. Die Aussageform ist tautologisch.

Und am Ende schreibt Zoglauer:

"In der Wahrheitswertentwicklung des Ausdrucks (d.h. in der letzten Spalte der Wahrheitstafel) tauchen nur die Werte w auf. Solche tautologischen Gesetze kennzeichnet man dadurch, dass man das Zeichen ⊢ davor setzt."

Tautologien in der Aussagenlogik

Eine Tautologie ist in der Logik eine allgemein gültige Aussage, das heißt eine Aussage, die aus logischen Gründen immer wahr ist. Weiter heißt es bei Wikipedia:

"Beispiele für Tautologien sind Aussagen wie "Wenn es regnet, dann regnet es" oder die tautologische sowie zirkuläre Aussage des Intelligenzforschers Edwin Boring aus dem Jahr 1924: "Intelligenz ist das, was der Intelligenztest misst." Teilweise wird der Begriff Tautologie für alle Arten von allgemeingültigen Aussagen verwendet, teilweise wird er auf solche Aussagen eingeschränkt, die in der zweiwertigen, klassischen Aussagenlogik allgemein gültig sind. Im letzteren, aussagenlogischen Sinn ist eine zusammengesetzte Aussage genau dann eine Tautologie, wenn sie wahr ist unabhängig davon, ob die Teilaussagen, aus denen sie zusammengesetzt ist, ihrerseits wahr oder falsch sind."

Beispiele für Tautologien sind:

• ⊢ ( p ∨ q ) ↔ ( p ∨ q )

• ⊢ p ∨ ¬ p

Tabelle der wichtigsten Tautologien der Aussagenlogik

Die folgende Tabelle gibt einen Überblick über die wichtigsten Tautologien der Aussagenlogik:

• ⊢ p ∨ ¬ p Gesetz vom ausgeschlossenen Dritten

• ⊢ ¬ ( p ∧ ¬ p ) Gesetz vom ausgeschlossenen Widerspruch

• ⊢ p → p Einfache Tautologie

• ⊢ p ← p Einfache Tautologie

• ⊢ ( p ∧ q ) → p Konjunktionsbeseitigung

• ⊢ p → ( p ∨ q )

• ⊢ p → ( q → p ) Paradoxie der Implikation

• ⊢ ¬ p → ( p → q ) Paradoxie der Implikation

• ⊢ p ← ( ¬ q ∧ q ) Paradoxie der Replikation

• ⊢ ( q ← p ) ← q Paradoxie der Replikation

• ⊢ ( ( p → q ) ∧ p ) → q Gesetz des Modus ponens

• ⊢ ( ( p → q ) ∧ ¬ q ) → p Gesetz des Modus tollens

Man kann durch eine Wahrheitswertentwicklung zeigen, dass die obigen Aussagen allgemeingültig (d.h. tautologisch) sind.

Paradoxien der Implikation

Die "Paradoxien der Implikation" sind eine Gruppe von Formeln der Aussagenlogik, die zwar Tautologien, aber intuitiv problematisch sind. Die Ursache der Paradoxien liegt darin, dass die Interpretation der Wahrheit einer Implikation in der natürlichen Sprache nicht ihrer formalen Interpretation in der klassischen Logik durch Wahrheitstabellen entspricht.

Tabelle der wichtigsten Paradoxien der Implikation

Die folgende Tabelle gibt einen Überblick über die wichtigsten Paradoxien der Implikation:

• ( ¬ p ∧ p ) → q

• p → ( q → p )

• ¬ p → ( p → q )

• p → ( q ∨ ¬ q )

• ( p → ¬ p ) ∨ ( ¬ p → p )

• ( p → q ) ∨ ( q → p )

Dass alle diese Formeln Tautologien sind, kann man mit der Methode der Wahrheitstabelle überprüfen. Es geht aber auch noch etwas einfacher und Schneller: Im Falle der 6. Formel oben z.B. ist der erste Teil der Disjunktion nur dann nicht wahr, wenn p wahr, aber q falsch ist. In diesem Fall ist aber der zweite Teil der Disjunktion wahr.

Paradoxien der Replikation

Die "Paradoxien der Replikation" sind eine Gruppe von Formeln der Aussagenlogik, die zwar Tautologien, aber intuitiv problematisch sind. Die Ursache der Paradoxien liegt darin, dass die Interpretation der Wahrheit einer Replikation in der natürlichen Sprache nicht ihrer formalen Interpretation in der klassischen Logik durch Wahrheitstabellen entspricht.

Tabelle der wichtigsten Paradoxien der Replikation

Die folgende Tabelle gibt einen Überblick über die wichtigsten Paradoxien der Replikation:

• p ← ( ¬ q ∧ q )

• ( q ← p ) ← q

• ( p ← q ] ← ¬ q )

• ( p ∨ ¬ p ) ← q

• ( p ← ¬ p ) ∨ ( ¬ p ← p )

• ( p ← q ) ∨ ( q ← p )

Dass alle diese Formeln Tautologien sind, kann man mit der Methode der Wahrheitstabelle überprüfen. Es geht aber auch noch etwas einfacher und schneller: Im Falle der 6. Formel oben z.B. ist der erste Teil der Disjunktion nur dann nicht wahr, wenn q wahr, aber p falsch ist. In diesem Fall ist aber der zweite Teil der Disjunktion wahr.

Äquivalenzen in der Aussagenlogik

Zwei logische Ausdrücke α und β heißen logisch äquivalent (in Zeichen: α ⇔ β ), wenn sie die gleiche Wahrheitswertentwicklung besitzen, oder anders gesagt, wenn der Ausdruck α ⇔ β eine Tautologie ist.

Tabelle der wichtigsten Äquivalenzen der Aussagenlogik

Die folgende Tabelle gibt einige wichtige logisch äquivalente Ausdrücke der Aussagenlogik wieder:

• p → q ⇔ ¬ p ∨ q Subjunktion der Implikation

• p ← q ⇔ ¬ q ∨ p Subjunktion der Replikation

• p → q ⇔ ¬ q → ¬ p Kontraposition der Implikation

• p ← q ⇔ ¬ p ← ¬ q Kontraposition der Replikation

• p ↔ q ⇔ ( p → q ) ∧ ( q → p ) Bisubjunktion

• p ↔ q ⇔ ( p ← q ) ∧ ( q ← p ) Bisubjunktion

• p ↔ q ⇔ ( p ∧ q ) ∨ ( ¬ p ∨ ¬ q ) Bisubjunktion

• p ∨ q ⇔ q ∨ p Kommutativgesetz der Distribution

• p ∧ q ⇔ q ∧ p Kommutativgesetz der Konjunktion

• p → q ⇔ ¬ p ∨ q Morgansche Regel

• p ∧ ( p ∨ q ) ⇔ p Verschmelzungsgesetz (Absorption)

• p ∨ ( p ∧ q ) ⇔ p Verschmelzungsgesetz (Absorption)

• ( p ∨ q ) ∨ r ⇔ p ∨ ( q ∨ r ) Assoziativgesetz

• ( p ∧ q ) ∧ r ⇔ p ∧ ( q ∧ r ) Assoziativgesetz

• p → q ⇔ ¬ p ∨ q Assoziativgesetz

• p ∧ ( q ∨ r ) ⇔ ( p ∧ q ) ∨ ( p ∧ r ) Distributivgesetz

• p ∨ ( q ∧ r ) ⇔ ( p ∨ q ) ∧ ( p ∨ r ) Distributivgesetz

• ( p ∧ q ) → r ⇔ p → ( q → r ) Exportation

Man kann durch eine Wahrheitswertentwicklung zeigen, dass die obigen Äquivalenten gültig sind.

Anwendungen

Eigentlich würde jetzt das weite Feld der Anwendungen folgen. Das würde aber den Rahmen dieser elementaren Einführung sprengen. Es sei lediglich auf die weiterführende Literatur verwiesen.