Exkurs: Funktionale Vollständigkeit

Wie im vorangehenden Kapitel bereits kurz angerissen, nennt man eine Menge von Konnektiven genau dann funktional vollständig, wenn sich mit Hilfe dieser Konnektive alle anderen Konnektive ausdrücken lassen. Die Menge unserer Konnektive, $\{\neg, \wedge, \vee, \rightarrow\}$, ist funktional vollständig. Wir wollen untersuchen, ob es auch andere funktional vollständige Konnektivmengen gibt und - wenn ja - ob darunter eine ist, die weniger Konnektive enthält als die vier bekannten.

Nun, eine erste Reduktion ist sehr einfach. Auf Seite  ist es uns gelungen, ein Verfahren anzugeben, mit dem alle Konnektive bloß mit $\neg$, $\wedge$ und $\vee$ ausgedrückt werden können. Daher ist es unmittelbar klar, dass die Menge $\{\neg, \wedge, \vee\}$ funktional vollständig ist. Das ist insoferne ein erfreuliches Ergebnis, als wir auf das mancherorts unbeliebte Konditional verzichten könnten.

Wenn es uns gelänge, eines der Konnektive der Menge $\{\neg, \wedge, \vee\}$ durch die beiden anderen auszudrücken, dann könnten wir eine noch kleinere funktional vollständige Konnektivmenge bilden. An dieser Stelle wäre wieder einmal eine gute Gelegenheit, innezuhalten und ein wenig nachzudenken: Ist es möglich, das Oder nur mit Hilfe des Nicht und des Und auszudrücken?

Ein Satz der Form $\varphi \vee \psi$ sagt aus, dass mindestens eines der beiden Disjunkte zutrifft. Wenn mindestens ein Disjunkt zutrifft, dann kann es nicht der Fall sein, dass beide Disjunkte nicht zutreffen. Das kann man aufschreiben: $\neg(\neg\varphi\wedge\neg\psi)$.^4.7 Diese Aussage aber enthält kein Oder mehr - wir haben unser Ziel erreicht und gezeigt, dass schon die Menge $\{\neg, \wedge\}$ funktional vollständig ist.

Übrigens sind auch die Mengen $\{\neg, \rightarrow\}$ sowie $\{\neg, \vee\}$ funktional vollständig - der Nachweis bleibt der Leserin zur Übung überlassen.

Die Suche nach funktional vollständigen Mengen ist keine sinnleere Spielerei; vielen Menschen fällt es schwer, sich logische Zeichen auswendig zu merken. Für sie ist es eine große Beruhigung zu wissen, dass man mit nur zwei Konnektiven eine logische Sprache aufbauen kann, die um nichts weniger ausdrucksstark ist als die hier vorgestellte mit ihren vier Konnektiven.

Wäre es denkbar, die Zahl der Konnektive noch weiter zu verringern, also eine funktional vollständige Menge zu finden, die nur ein einziges Konnektiv umfasst? - So überraschend das ist, die Antwort lautet ja.

Erinnern wir uns an Konnektiv $K_{14}$, für seine Freunde NAND. Mit seiner Hilfe lässt sich jedes andere Konnektiv ausdrücken. Die Verneinung $\neg \varphi$ wird formuliert als $\varphi$ NAND $\varphi$, und die Konjunktion $\varphi\wedge\psi$ als $(\varphi$ NAND $\psi)$ NAND $(\varphi$ NAND $\psi)$ - der Zweifler möge sich einmal mehr mit einer Wahrheitstabelle von der Wahrheit meiner Behauptung überzeugen. Da wir mittels des NAND sowohl das Nicht als auch das Und ausdrücken können, können wir mit seiner Hilfe in der Tat jedes Konnektiv ausdrücken, weil wir ja bereits gezeigt haben, dass die Menge $\{\neg, \wedge\}$ funktional vollständig ist. Somit ist auch die Menge $\{NAND\}$ funktional vollständig.

Ein Konnektiv, dessen Einermenge funktional vollständig ist, das alleine also ausreicht, alle anderen Konnektive auszudrücken, wird Sheffer-Funktion genannt. Eine andere Shefferfunktion ist das Nichtoder, NOR.