-

8 12. Lösungen des Entscheidungsproblems für besondere Spezialfälle. 79

setzung der Funktionszeichen A, B,...K durch die Prädikate 4,,

Bo,... K, entsteht, wiederum in eine falsche Aussage übergeht, wenn
wir die Prädikate A, Bo,..., Ko durch 4,, B,,...K, ersetzen und
als Werte für die Variablen die Klassen &X,,&X,,... %n nehmen.

Demmnach brauchen wir die Entscheidung nur für den Fall auszu-
führen, daß es sich um höchstens 2*, also um endlich viele Gegenstände
handelt. Für diesen Fall läßt sich aber die Entscheidung durch ein end-
liches Verfahren erzwingen. Es seien a,,a,,...d4 (Is 2*) die Gegen-
stände, aus denen der Individuenbereich besteht. Ein Ausdruck (x) F(x)

ist dann gleichbedeutend mit der endlichen logischen Summe:

F(a,) & F(a) &... &F(a).
Ebenso ist (Ex)F(x) gleichwertig mit
F(a1) VF(“g) V VF(a;)_

Wir können also die All- und Seinszeichen in der betrachteten Formel
sämtlich entfernen und erhalten eine Formel, welche aus den Grund-
aussagen

Ala B(@) e K(@) e

lediglich mit den logischen Zeichen des Aussagenkalküls gebildet ist.

Setzen wir in der zuletzt gewonnenen Formel für jeden verschiedenen
Grundbestandteil A(a,), ... K(da,) eine besondere Aussagenvariable, so
entsteht eine bestimmte Formel des Aussagenkalküls. Dann und nur
dann, wenn diese letzte Aussagenformel immer richtig ist, ist auch die
logische Formel, von der wir ausgingen, richtig.

Mit der Entscheidung in dem angegebenen einfachen Bereich, in
dem die Prädikate mit mehr als einer Leerstelle fehlen, ist natürlich
noch nicht viel gewonnen. Gerade die Beziehungen, d::h.die.mehr-
gliedrigen Prädikate, spielen ja z. B. bei der axiomatischen Grund-
legung von mathematischen Disziplinen die Hauptrolle.

Stellt man nun ganz allgemein für den Funktionenkalkül die Frage
nach einem Entscheidungsverfahren, so muß man den folgenden Um-
stand besonders berücksichtigen:

Die Allgemeingültigkeit bzw. Erfüllbarkeit eines logischen Ausdrucks
kann davon abhängen, wie groß die Anzahl der Gegenstände im Individuen-
bereich ist. Z.B. ist

(Ex) (Ey) (F(x, x) & F(x, y)
dann und nur dann erfüllbar, wenn es mindestens zwei Individuen gibt.
Ebenso ist a
(x) (y)(F(%, %) v F(%, y))

allgemeingültig, falls es genau einen Gegenstand im Individuenbereich
gibt, sonst aber nicht. Diese Erscheinung tritt natürlich auch schon