logische Signatur

07.12.2009
In der Aussagenlogik können Junktoren wie $\wedge, \vee, \neg$ eine (logische) Signatur bilden. Eine Signatur gilt als (funktional) vollständig, wenn jede boolsche Funktion dadurch abgebildet werden kann; andernfalls ist sie (Überraschung!) unvollständig. Jetzt stellt sich die Frage, wie man zeigen kann, dass eine Signatur vollständig oder unvollständig ist.

Möglichkeit 1: Gegenbeispiel

Das ist nicht besonders elegant, aber meist einen Versuch wert. Gegeben sei eine Signatur wie z.B. $\{\rightarrow\}$ und man sucht eine Boolsche Funktion, die sich nicht dadurch abbilden lässt. Bei dem Beispiel, der Implikation fällt das nicht schwer: sie kann dem Eingabewert 1 nie eine 0 zuordnen. Also ist $\{\rightarrow\}$ nicht funktional vollständig. Offensichtlich sollte man nicht allzuviel Zeit investieren, um ein Gegenbeispiel zu finden, weil ja noch das Risiko besteht, dass die Signatur vollständig sein könnte. Wenn also die Klassiker wie $0 \longrightarrow 1$ , $0 \longrightarrow 0$ , $1 \longrightarrow 1$ , $1 \longrightarrow 0$ , die Negation $\neg$ o.ä. darstellbar ist, wird es Zeit für Möglichkeit 2.

Möglichkeit 2: Bekanntes Nutzen

Diese Methode ist etwas komfortabler, stellt aber mehr Gehirnakrobatik als die erste dar. Ist eine Signatur bekannt vollständig oder unvollständig, kann man daraus Schlüsse für neue Signaturen ziehen. Ist eine Signatur $M$ gegeben und ist sie funktional vollständig, so ist eine Signatur $N$ genau dann funktional vollständig, wenn alle Junktoren aus $M$ durch (meist längere) Junktorketten aus $N$ darstellbar sind. Umgekehrt gilt für eine funktional unvollständige Signatur $O$ : sind alle Junktoren aus der neuen Signatur $P$ durch Junktorketten aus $O$ darstellbar, bringt $P$ "nichts Neues" und ist somit auch unvollständig. Um dieses Verfahren anwenden zu können, sollte man eine kleine Sammlung an vollständigen und unvollständigen Signaturen parat haben:

vollständig:

$\{\neg, \wedge, \vee\}$ (Negation, Konjunktion, Disjunktion) Beweis: Diese Junktoren sind für die konjunktive oder disjunktive kanonische Normalform notwendig, mit der per definitionem alle Belegungen darstellbar sind.
$\{\neg, \wedge\}$ (Negation, Konjunktion) Beweis: nach der de Morganschen Regel gilt: $x_1 \vee x_2 \equiv \neg(\neg x_1 \wedge \neg x_2)$
$\{\neg, \vee\}$ (Negation, Disjunktion) Beweis: nach der de Morganschen Regel gilt: $x_1 \wedge x_2 \equiv \neg(\neg x_1 \vee \neg x_2)$
$\{|\}$ (NAND) Beweis: $\neg x_1 \equiv x_1|x_1$ und $x_1 \wedge x_2 \equiv (x_1|x_2)|(x_1|x_2))$

nicht vollständig:

$\{\rightarrow\}$ (Implikation) Beweis: s.o.
$\{\otimes\}$ (XOR) Beweis: Gegenbeispiel $x_1 \wedge x_2$ ist nicht darstellbar