next up previous contents index
Nächste Seite: Exkurs: Funktionale Vollständigkeit Aufwärts: Semantik der Sprache der Vorherige Seite: Wahrheitstafeln   Inhalt   Index

Exkurs: Alle aussagenlogischen Konnektive

Die in diesem Skriptum behandelte Sprache umfasst die Konnektive $\neg$, $\wedge$, $\vee$ und $\rightarrow$. Unsere Semantik, die jedem Satzbuchstaben einen der Werte $W$ und $F$ zuordnet, erlaubt viel mehr Konnektive. Dieses Kapitel beschäftigt sich mit der Frage, welche und wieviele Konnektive es geben könnte, ob sie alle in irgendeiner Hinsicht sinnvoll sind oder nicht und ob es einen Grund gibt, warum sich unsere logische Sprache auf die genannten Konnektive beschränkt.

Beginnen wir mit den einstelligen Konnektiven, d.h. mit jenen Konnektiven, die mit einem einzigen Satz verbunden sind. Hier kennen wir nur die Negation, $\neg$. Sie hat die Wahrheitstafel

\(
\begin{array}{c\vert c}
\varphi & \neg\varphi \\ \cline{1-2}
W & F \\
F & W
\end{array}\)

Gibt es einstellige Konnektive, die eine andere Wahrheitstafel haben? Die Antwort lautet offensichtlich ja; wir können folgende Wahrheitstafeln bilden:

\(
\begin{array}{c\vert c\vert c\vert c\vert c}
\varphi & \neg\varphi & K_2 & K_3 & K_4
\\ \cline{1-5}
W & F & F & W & W \\
F & W & F & W & F
\end{array}\)

Das erste Konnektiv ist unsere Negation; es kehrt den Wahrheitswert des Satzes um, auf den es angewandt wird. Das zweite Konnektiv gibt es in unserer Sprache nicht; es liefert in jedem Fall den Wert $F$. Das dritte Konnektiv liefert stets $W$; auch ein solches Konnektiv fehlt in unserer logischen Sprache. Das letzte Konnektiv, $K_4$, lässt den Wahrheitswert des Satzes, auf den es angewandt wird, unverändert. Auch über dieses Konnektiv verfügen wir nicht.

Wie sehr fehlen uns die fehlenden Konnektive? Nun, man mag argumentieren, dass die Konnektive $K_2$ bis $K_4$ nutzlos seien. Da Nutzen keine philosophische Kategorie ist, sollten wir einen anderen Zugang suchen: Kann man mit Hilfe der Konnektive $K_2$ bis $K_4$ irgendetwas ausdrücken, was man ohne sie nicht ausdrücken kann? Erfreulicherweise ist das nicht der Fall. Möchte man einen Satz $\varphi$ so umformulieren, dass er stets falsch ist (das entspricht Konnektiv $K_2$), dann schreibt man ganz einfach $\varphi\wedge\neg\varphi$. Dieser Ausdruck ist zwar etwas lang, aber wenn die Leserin die Wahrheitstabelle für ihn aufstellt, wird sie sehen, dass er tatsächlich konstant falsch ist.

Möchte man aus $\varphi$ einen konstant wahren Satz formen ($K_3$), so schreibt man ganz einfach z.B. $\varphi\vee\neg\varphi$. Auch das ist länger als es ein eigenes Konnektiv wäre, erspart uns aber das Auswendiglernen überflüssig vieler logischer Zeichen.

Wie man vorgehen muss, um Konnektiv $K_4$, das den Wahrheitswert eines Satzes unverändert lässt, nachzuahmen, möge der Leser selbst herausfinden. Ein kleiner Tip: Man muss überhaupt nichts tun.

Bei den zweistelligen Konnektiven ist der Sachverhalt komplizierter. Die Leserin wird gebeten, an dieser Stelle innezuhalten und zu überlegen, wieviele zweistellige Konnektive es geben mag, pathologische Fälle mit eingeschlossen (also z.B. ein zweistelliges Konnektiv, das immer $W$ liefert).

Die aufwendigste Methode, die gesuchte Anzahl herauszufinden, besteht darin, alle Möglichkeiten aufzuschreiben und anschließend zu zählen:

\(
\begin{array}{cc\vert c\vert c\vert c\vert c\vert c\vert c\vert c\vert c}
\va...
...&F&F&F&W&W&F&F&W&W \\
F&W&F&F&F&F&W&W&W&W \\
F&F&F&F&F&F&F&F&F&F
\end{array}\)

\(
\begin{array}{cc\vert c\vert c\vert c\vert c\vert c\vert c\vert c\vert c}
\va...
...&F&F&F&W&W&F&F&W&W \\
F&W&F&F&F&F&W&W&W&W \\
F&F&W&W&W&W&W&W&W&W
\end{array}\)

Wie man sieht, gibt es sechzehn zweistellige Konnektive. Wirklich überraschend ist das nicht: Eine Wahrheitstafel für ein zweistelliges Konnektiv hat vier Zeilen. In der ersten Zeile muss das Konnektiv entweder $W$ oder $F$ liefern; für die erste Zeile gibt es also zwei Möglichkeiten. Auch in der zweiten Zeile muss einer der beiden Wahrheitswerte stehen; die Zahl der Möglichkeiten in der ersten Zeile wird daher verdoppelt ($2\times 2$). Dadurch, dass auch in der dritten Zeile einer der zwei Werte $W$ und $F$ steht, wird das Zwischenergebnis erneut verdoppelt - wir stehen bei $2\times 2\times 2$. Da auch in der letzten Zeile einer der zwei Fälle auftreten muss, verdoppelt sich die Zahl der Möglichkeiten ein letztes Mal, und wir landen bei $2\times 2\times 2\times 2$, das ist $2^4$ bzw. sechzehn.

Da diese Liste vollständig ist, müssen auch die drei zweistelligen Konnektive unserer logischen Sprache darin auftreten: $K_1$ ist die Konjunktion, ,,$\wedge$``, $K_7$ ist die Disjunktion, ,,$\vee$``, und $K_{13}$ ist das Konditional, ,,$\rightarrow$``. dass es die übrigen Konnektive in unserer logischen Sprache nicht gibt, sagt nichts über ihre Sinnhaftigkeit aus. Einige der sechzehn Konnektive erfreuen sich großer Bedeutung und haben auch eigene Namen. Besonders wichtig sind Konnektiv $K_8$, das NOR oder Nichtoder, und Konnektiv $K_{14}$, NAND oder Nichtund.4.4 Konnektiv $K_6$, das ausschließende Oder (,,entweder ...oder``, lateinisch aut), hat in der Kryptologie (Verschlüsselung) eine hervorragende Stellung inne; es ist dort als Vernam-Chiffrierschritt (unvollständige Addition) bekannt.4.5 Die Leserin möge darüber nachdenken, welche der übrigen Konnektive in welcher Weise bedeutsam sein könnten.

Unabhängig von der Frage, ob alle sechzehn Konnektive in irgendeiner Hinsicht sinnvoll sind, lässt sich wie bei den einstelligen Konnektiven die Frage stellen, welche von ihnen nötig sind. Dazu ist folgende Definition hilfreich: Eine Menge von Konnektiven heißt funktional vollständig, wenn sich mit Hilfe dieser Konnektive jedes andere Konnektiv ausdrücken lässt. Die Menge unserer Konnektive, $\{\neg, \wedge, \vee, \rightarrow\}$ ist funktional vollständig. Es wäre eine gute Übung, an dieser Stelle innezuhalten und zu versuchen, einige der sechzehn möglichen Konnektive mit den Konnektiven unserer logischen Sprache auszudrücken.

Ist man des Denkens überdrüssig, kann man sich folgendes Verfahrens bedienen: Man bildet für jede Wahrheitswertzuordnung, bei der das zur Diskussion stehende Konnektiv den Wert $W$ liefert, eine Konjunktion. Das linke Konjunkt ist der Satz $\varphi$, wenn die Zuordnung dem Satz $\varphi$ den Wert $W$ zuordnet, und der Satz $\neg \varphi$, wenn sie ihm den Wert $F$ zuordnet. Das rechte Konjunkt lautet $\psi$, wenn die Zuordnung dem Satz $\psi$ den Wert $W$ zuordnet, und $\neg\psi$, wenn sie ihm $F$ zuordnet. Zuletzt werden alle so entstandenen Konjunktionen zu einer Disjunktion verbunden.

Zur Klärung wollen wir das Konnektiv $K_{11}$ betrachten. Es liefert für drei Zuordnungen den Wert $W$, nämlich für ${\varphi\over W}{\psi\over W}$, für ${\varphi\over W}{\psi\over F}$ und für ${\varphi\over F}{\psi\over F}$. Für jede dieser Zuordnungen müssen wir in der geschilderten Weise eine Konjunktion bilden. Die erste Konjunktion lautet $(\varphi \wedge \psi)$, weil die erste Zuordnung beiden Sätzen den Wert $W$ zuordnet. Die zweite Konjunktion ist $(\varphi\wedge\neg\psi)$, weil die zweite Zuordnung dem ersten Satz $W$ und dem zweiten Satz $F$ zuordnet. Die dritte und letzte Konjunktion hat die Gestalt $(\neg\varphi\wedge
\neg\psi)$, weil die dritte Zuordnung beiden Sätzen den Wert $F$ zuordnet. Wenn man die drei Konjunktionen zu einer Disjunktion verbindet, gelangt man zu $((\varphi\wedge\psi) \vee (\varphi\wedge\neg\psi)) \vee (\neg\varphi
\wedge\neg\psi)$4.6. Zur Kontrolle kann man für diesen Satz eine Wahrheitstafel aufstellen; sie hat denselben Verlauf wie das Konnektiv $K_{11}$.

Ein Sonderfall ist das Konnektiv $K_0$; da es in keiner Zeile den Wert $W$ liefert, ist das Verfahren nicht anwendbar. Es ist dennoch sehr einfach, $K_0$ mit den bekannten Konnektiven nachzuahmen, indem man z.B. $\varphi\wedge\neg\varphi$ oder - weil man beide Sätze unterbringen möchte - $(\varphi\wedge\neg\varphi) \wedge \psi$ schreibt.


next up previous contents index
Nächste Seite: Exkurs: Funktionale Vollständigkeit Aufwärts: Semantik der Sprache der Vorherige Seite: Wahrheitstafeln   Inhalt   Index
Christian Gottschall 2003-03-19