Funktionale Vollständigkeit

Wahrheitsfunktionen

Die Lektion über die Semantik der Aussagenlogik hat jeder Formel unter jeder Belegung einen Wahrheitswert zugeordnet und gezeigt, dass dieser Wert nur von den Werten der in ihr vorkommenden Variablen abhängt; daher hat jede Formel mit $n$ Variablen eine Wahrheitstafel mit $2^{n}$ Zeilen. Die Frage dieser Lektion ist die umgekehrte. Gegeben sei eine beliebige Tafel, das heißt eine willkürlich neben die $2^{n}$ Zeilen geschriebene Spalte aus Einsen und Nullen: Gibt es eine Formel, die sie als Tafel hat? Wenn das für jede Tafel gilt, hat die Sprache keine Ausdruckslücken: Alles, was sich über den Wahrheitswert von $n$ Aussagen in Abhängigkeit von ihren Werten sagen lässt, wird mit einer Formel gesagt. Und da in diesem Kurs jede zusammengesetzte Formel mit dem Peirce-Pfeil gebildet ist, wird die Antwort auch sagen, ob ein einziger Junktor genügt, um alles zu sagen.

Was aus den vorigen Lektionen verwendet wird

Eine Belegung ist eine Funktion $v$ von der Menge der Variablen $\{v_1, v_2, \ldots\}$ in $\{0, 1\}$, wobei $1$ das Wahre und $0$ das Falsche ist; ihre Fortsetzung auf alle Formeln, die ebenfalls $v$ geschrieben wird, ist rekursiv definiert: $v((\varphi \downarrow \psi)) = 1$ genau dann, wenn $v(\varphi) = 0$ und $v(\psi) = 0$. Aus den offiziellen Abkürzungen hat dieselbe Lektion im Satz über die Werte der abgeleiteten Junktoren den Wert jedes Junktors berechnet; mit Summen und Produkten geschrieben, sind es die folgenden, für jede Belegung $v$ und alle Formeln $\varphi$ und $\psi$:

Außerdem gilt $v((\varphi \leftrightarrow \psi)) = v(\varphi)\,v(\psi) + (1 - v(\varphi))\,(1 - v(\psi))$, was genau dann $1$ ist, wenn $v(\varphi) = v(\psi)$, und $v((\varphi \veebar \psi)) = v(\varphi) + v(\psi) - 2\,v(\varphi)\,v(\psi)$, was genau dann $1$ ist, wenn $v(\varphi) \neq v(\psi)$. Da die Werte $0$ oder $1$ sind, ist das Quadrat eines Wertes der Wert selbst, $v(\varphi)\,v(\varphi) = v(\varphi)$, und ein Produkt von Werten ist genau dann $1$, wenn jeder Faktor $1$ ist; beide Beobachtungen werden ohne Wiederholung verwendet. Verwendet wird auch das Koinzidenzlemma: Wenn zwei Belegungen auf den Variablen von $\varphi$ übereinstimmen, das heißt auf den Variablen, die Teilformeln von $\varphi$ sind, geben sie $\varphi$ denselben Wert. Aus der Lektion über semantische Folgerung und Äquivalenz wird die semantische Äquivalenz übernommen: $\varphi \eqsem \psi$, wenn $v(\varphi) = v(\psi)$ für jede Belegung $v$. Schließlich gilt die Buchstabenkonvention der Lektion über die Formalisierung: $p$, $q$ und $r$ bezeichnen die Variablen $v_1$, $v_2$ und $v_3$.

Wahrheitsfunktionen und ihre Anzahl

Sei $n$ eine natürliche Zahl. Eine Zeile aus $n$ Werten ist eine Folge $a = (a_1, \ldots, a_n)$, in der jedes $a_i$ gleich $0$ oder $1$ ist; die Menge aller solchen Zeilen wird $\{0, 1\}^{n}$ bezeichnet. Eine Wahrheitsfunktion mit $n$ Argumenten ist eine Funktion

die jeder Zeile einen Wahrheitswert zuordnet. Sie wird als Tafel dargestellt: Die Zeilen werden in der Reihenfolge der Tafel geschrieben, beginnend mit derjenigen, in der alle Werte $1$ sind (für zwei Argumente $1\,1$, $1\,0$, $0\,1$, $0\,0$), und neben jede Zeile wird ihr Wert geschrieben. Eine Wahrheitsfunktion ist also eine Wahrheitstafel ohne Formel: die rechte Spalte, ohne etwas in ihrem Kopf.

Formeln, die Funktionen darstellen

Eine Formel und eine Wahrheitsfunktion hängen folgendermaßen zusammen. Ist $\varphi$ eine Formel, deren Variablen unter $v_1, \ldots, v_n$ liegen, so sagt man, $\varphi$ stellt die Wahrheitsfunktion $f$ mit $n$ Argumenten dar, wenn für jede Belegung $v$ gilt:

das heißt, wenn die Tafel von $\varphi$, geschrieben mit den Variablen $v_1, \ldots, v_n$, die Tafel von $f$ ist. Die Bedingung an die Variablen ist keine Nebensache: Die Formel $(p \wedge q)$ stellt keine Funktion mit einem Argument dar, weil ihr Wert nicht nur von dem von $p$ abhängt.

Es gibt unendlich viele Formeln mit Variablen unter $v_1, \ldots, v_n$ und nur $2^{2^{n}}$ Funktionen; also stellen viele Formeln dieselbe Funktion dar, und die Proposition besagt, dass es genau die untereinander äquivalenten sind. Zu klären bleibt, ob jede Funktion von einer Formel dargestellt wird oder ob manche Tafeln ohne eine Formel bleiben, die sie hat.