Zum Entscheidungsproblem der mathematischen Logik. (Q5907239)

Die vorliegenden Untersuchungen befassen sich mit dem Entscheidungsproblem der ersten Stufe. Es wird der Bereich derjenigen logischen Formeln zugrunde gelegt, die sich aus Prädikaten- und Individuenvariablen, den Aussageverknüpfungen und dem ``alle'' und ``es gibt'' für Individuen aufbauen. Innerhalb dieses Bereichs war das Entscheidungsproblem bisher nur bei Beschränkung auf Prädikate mit einem Argument durch die Arbeiten von \textit{Löwenheim} und \textit{Behmann} gelöst. Die Verf. behandeln besondere Fälle des Vorkommens von zwei - und mehrgliedrigen Prädikaten. Da nach einen bekannten Satz der mathematischen Logik sich jede Formel durch eine äquivalente ersetzen läßt, in der die vorkommenden All- und Existentialzeichen unverneint zu Beginn der Formel stehen, so kann man die Formeln nach der Art des Vorkommens der All- und Existentialzeichen klassifizieren. Die Verf. untersuchen zunächst die Allgemeingültigkeit der Formeln, die nur Allzeichen oder nur Existentialzeichen haben, oder in denen die vorkommenden Existentialzeichen sämtlich hinter den Allzeichen stehen. Diese Fälle finden eine sehr einfache Erledigung. Als unvergleichlich schwieriger erweist sich das (im allgemeinen vollkommen ungelöste) Problem der Allgemeingültigkeit der Formeln, bei denen Existentialzeichen Allzeichen vorangehen. Hier wird ein Entscheidungsverfahren für Formeln von dem Typ \((Ex) (y) A(x,y)\) angegeben.