$ 8. Ergänzende Bemerkungen zum Problem der Allgemeingültigkeit. 17

Aussage der Summand X,v X,v...vV X nicht vorkommt. Hat man
nämlich eine Aussage, die sich aus X,, X,,...X„ ohne Negation auf-
baut, so ist diese Aussage immer richtig, falls für X,, X,,... X richtige
Aussagen eingesetzt werden. Eine Aussage, die X,vXz2vV...vVX„ als
Summand enthält, hat aber nicht diese Eigenschaft. Die genannte
Bedingung ist also notwendig. Andererseits ist sie auch hinreichend,
denn man kann jedes Glied der ausgezeichneten Normalform, das nicht
gleich X, v X2V...V Xn ist, ohne Negation ausdrücken. Z. B..schreibt
man
KKg n S X NC

K XX XXgr e SN NN N

Es sind demnach gerade die Hälfte der 2%” Aussagen, die aus
Xi, X,,... Xn gebildet werden können, ohne die Negation ausdrückbar.

$ 8. Ergänzende Bemerkungen zum Problem der
Allgemeingültigkeit und Erfüllbarkeit.

Die im vorigen angegebene ausgezeichnete Normalform für einen
Ausdruck, der sich aus den Grundaussagen X,, X,,... X zusammen-
setzt, wollen wir auch kurz als Entwicklung des Ausdrucks nach X,,
Xas: + An- Bezeichnen,

Es sei uns nun eine Aussagenverbindung gegeben, in der außer X,,
X2; .. .. Xp Noch'die Grundaussagen‘ Yı, Yo,... Yn vorkommen.. Auch
bei einem derartigen Ausdruck können wir in gewissem Sinne von
einer Entwicklung nach' X,, ... X sprechen. Es läßt sich nämlich der
Ausdruck darstellen als eine Summe, bei der jeder Summand aus dem
Produkt eines Ausdrucks, der nur von Yı, Ya,... Ym abhängt, mit einer
der Konstituenten von X,, X,,... Xx besteht.

Der Beweis ist sehr einfach. Wir brauchen den Ausdruck nur nach

sämtlichen vorkommenden Grundaussagen, also nach X,,...Xn,
Yı,... Ya zu entwickeln und die Glieder, “die die'gleichen Kon-
stituenten in bezug auf X,, X,,... X enthalten, zusammenfassen.

Diese Entwicklung‘ eines- Ausdrucks. nach X;, X2,.... X bietet
uns gewisse Vorteile. Wir hatten gesehen, daß die Entscheidung über
die Allgemeingültigkeit eines Ausdrucks, d.h. die Aufgabe, bei einem
vorgelegten logischen Ausdruck durch ein bestimmtes, endliches Ver-
fahren zu entscheiden, ob er immer richtig ist oder nicht, im Aussagen-
kalkül vollständig gelöst ist. Die Beantwortung dieser Frage geschieht
durch die Umformung auf die konjunktive Normalform. Dual zu dem
Problem der Allgemeingültigkeit ist das Problem der Erfüllbarkeit,
d. h. das Problem, zu entscheiden, ob ein vorgelegter logischer Ausdruck
immer falsch ist oder ob es Aussagen gibt, die ihn erfüllen, d. h. für
die er richtig ist. Die Lösung dieses Problems kann durch Umformen

Hilbert-Ackermann, Grundzüge. 2