Über die Erfüllbarkeit derjenigen Zählausdrücke, welche in der Normalform zwei benachbarte Allzeichen enthalten. (Q2624159)

In dieser Abhandlung wird ein Verfahren angegeben, mit dessen Hilfe man entscheiden kann, ob ein Zählausdruck, worin außer Semszeichen genau zwei benachbarte Allzeichen vorkommen, erfüllbar ist oder nicht. In \S {} 1 beweist Verf. drei Hilfssätze über Modelle und Tabellen. Dabei bedeutet ``Modell'' eine Folge von logischen Funktionen über einem Individuenbereich, und eine Tabelle \(p\)-ter Ordnung ist ein Modell über der Menge der Zahlen \(1, 2,\ldots, p\). Hilfssatz 1 drückt für Tabellen einen Übergang von einem Individuenbereich zu einem anderen aus. Hilfssatz 2 gibt die notwendige und hinreichende Bedingung dafür, daß eine gewisse Anzahl von Tabellen \(T_1,\ldots,T_k\) für gewisse Individuen mit einer einzigen Tabelle \(T\) übereinstimmen kann. Nach Hilfssatz 3 kann man aus einer unendlichen Folge von Tabellen wachsender Ordnung, wobei jede eine Fortsetzung der vorhergehenden ist, ein Modell über der Menge aller natürlichen Zahlen bilden. In \S {} 2 betrachtet Verf. die Zählausdrücke der Form \[ (x_1)(x_2)(Ex_3)\ldots (Ex_n)K. \] Wird angenommen, daß dieser Ausdruck durch das Modell \(M\) über der Menge \(M\) erfüllt ist, so ist der Kernausdruck \(K\) für die verschiedenen \(n\)-tupel der Individuen auf mindestens eine Art erfüllt, d. h. man bekommt eine nicht-leere Menge von Tabellen \(n\)-ter Ordnung, welche den Kernausdruck erfüllen. Verf. zeigt, daß diese Menge drei charakteristische Eigenschaften \(A, B, C\) hat. Danach beweist er, daß auch umgekehrt die Existenz einer nichtleeren Menge von Tabellen mit den Eigenschaften \(A, B, C\), welche \(K\) erfüllen, zur Erfüllbarkeit des gegebenen Zählausdrucks genügt. Dies gelingt dadurch, daß er alle geordneten Paare \((\alpha, \beta )\) mit \(\alpha, \beta = 1,2,3,\ldots \) in bestimmter Weise abzählt und mit Hilfe dieser Abzählung eine Folge von Tabellen \(Z_k\), wo \(Z_k\) die Ordnung \(1+ k (n-2)\) hat, rekurrierend definiert, und zwar so, daß er nachweisen kann, daß \(Z_{k+1}\) mit \(Z_k\) innerhalb des Individuenbereiches für \(Z_k\) übereinstimmt. Nach Hilfssatz 3 folgt daraus die Existenz eines Modells über der natürlichen Zahlenreihe, und der Zählausdruck ist dadurch erfüllt. Da es sich offenbar durch endliches Probieren entscheiden läßt, ob eine nicht leere Tabellenmenge der erwähnten Art existiert oder nicht, so ist hierdurch die Erfüllbarkeitsfrage gelöst. In \S {} 3 wird in einfacher Art bewiesen, daß man das Entscheidungsproblem für Zählausdrücke, die mit einer Reihe von Seinszeichen anfangen, auf dasselbe Problem für Zählausdrücke zurückführen kann, worin diese Seinszeichen entfernt sind, während die Zahl der Allzeichen nicht geändert wird und benachbarte Allzeichen benachbart bleiben. Zufolge \S {} 2 ist dadurch das Entscheidungsproblem gelöst für alle Zählausdrücke mit bloß zwei Allzeichen, die benachbart sind. In den Schlußbemerkungen gibt Verf. einige Gründe an, warum das benutzte Verfahren nicht genügt, um auch für Zählausdrücke mit mehr Allzeichen das Entscheidungsproblem zu lösen.