×

Zum Entscheidungsproblem der mathematischen Logik. (German) JFM 54.0056.05

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 Löwenheim und 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.

PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] In betreff dieses letzten Punktes der Argrumentation sei auf § 2, S. 353-354 hingewiesen, wo für einen ganz entsprechenden Fall die Überlegung ansführlicher an gegeben wird.
[2] Leopold Löwenheim, ?Über Möglichkeiten im Relativkalkul?, Math. Annalen76. Leipzig 1915. · JFM 44.0078.01
[3] Th. Skolem, ?Logisch-kombinatorische Untersuchungen über die Erfüllbarkeit oder Beweisbarkeit mathematischer Sätze nebst einem Theorem über dichte Mengeu?. Videnskapsselskapets Skrifter. I. Mat. Naturv. Kl., 1920, Nr. 4. Kristiania. · JFM 48.1121.01
[4] Dieser Satz wird im folgenden genauer formuliert.
[5] Heinrich Behmann, ?Beiträge zur Algebra der Logik. insbesondere zum Entscheidungsproblem?. Math. Annalen86, Heft 3/4 (1922); S. 163-229. · JFM 48.1119.02 · doi:10.1007/BF01457985
[6] Der Fall eines unendlichen, durch eine endliche Zahl nach unten abgegrenzten Anzahlintervalles kommt hiernach auch in Betracht.
[7] Über sein Ergebnis hat Herr Schönfinkel in der Göttinger mathematischen Gesellschaft im Wintersemester 1922/23 referiert.
[8] Hierin sollen die Fällen mit inbegriffen sein, wo die Formel nur aus einer einzigen Disjunktion besteht, aber auch, wo ein Konjunktionsglied nur aus einer Variablen bzw. einer negierten Variablen besteht. D. h. es sind ?eingliedrige? Konjunktionen und Disjunktionen zugelassen.
[9] Ganz entsprechendes gilt für die disjunktive Normalform.
[10] Man könnte denken, daß hierzu der in der Einleitung erwähnte Satz von Löwenheim anzuwenden wäre, wonach jedes Problem der Allgemeingültigkeit (bzw. der Erfüllbarkeit) sich auf ein solches zurückführen läßt, bei dem nur Relationen mitzwei Argumenten auftreten. Diese Reduktion können wir jedoch hier nicht verwerten, weil durch sie die Zahl der in der logischen Formel voranstehenden Zeichen vermehrt wird, ? während für unsern Zweck ein Verfahren erfordert wird, das den Typns der Formel ungeändert läßt.
[11] Die BedingungB r hängt offenbar nicht von der Wahl der Individuenb 1 , ...,b r ab.
[12] Im Falle, daß \(\mathfrak{A}\) (x, y) bereits als Aussagenverknüpfung allgemeingültig ist, wird die Normalform \(\operatorname{Re} \) (x, y) 0-gliedrig, und die BedingungB r ist dann in trivialer Weise erfüllt.
[13] Diese ist keine ausgezeichnete Normalform.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.