Beiträge zur Algebra der Logik, insbesondere zum Entscheidungsproblem. (Q1463926)

In dieser Abhandlung wird ein Spezialfall von dem Hauptproblem der mathematischen Logik, dem sogenannten \textit{Entscheidungsproblem}, zur vollständigen Erledigung gebracht. Bei dem Entscheidungsproblem hat man eine engere und eine weitere Fragestellung zu unterscheiden. Das \textit{engere} Problem betrifft logische Formeln der ``ersten Stufe'', d. h. solche, in denen sich die Zeichen für Allheit und Existenz (Allzeichen und Seinszeichen) nur auf die Individuen (des zugrunde gelegten Individuenbereichs) beziehen; die auftretenden logischen Funktionen sind hier \textit{variabel}, mit Ausnahme der Beziehung der Identität (``\(x\) ist identisch mit \(y\)''), welche als einzige individuelle Relation zugelassen wird. Die Aufgabe besteht darin, ein allgemeines Verfahren zu finden, durch das für eine vorgelegte Formel entschieden werden kann, ob sie allgemeingültig ist, d. h. bei beliebigen Einsetzungen bestimmter logischer Funktionen für die auftretenden Funktionsvariablen stets eine richtige Aussage ergibt. Zu dem \textit{erweiterten} Problem gelangt man dadurch, daß man die Allzeichen und Seinszeichen auch in Verbindung mit Funktionsvariablen anwendet. Man betrachtet dann Formern der ``zweiten Stufe'', in denen sämtliche Variablen durch Allzeichen oder Seinszeichen gebunden sind, in deren Bedeutung also nichts weiter unbestimmt bleibt als der Bereich der Individuen, welcher zugrunde gelegt wird. Von einer beliebigen vorgelegten Formel dieser Art gilt es nun zu entscheiden, ob sie richtig ist oder nicht bzw. für welche Individuenbereiche sie richtig ist. (Aus dieser Fragestellung gewinnt man das engere Problem zurück, indem man sich auf diejenigen Formeln der zweiten Stufe beschränkt, in denen jede Funktionsvariable mit einem [auf die gesamte Formel sich erstreckenden] Allzeichen verbunden ist.) Die Bedingung für den Individuenbereich, von der die Richtigkeit einer vorgelegten Formel eventuell abhängt, kann nur eine Anzahl- oder Mächtigkeits-Bedingung sein. Der von \textit{Behmann} behandelte Spezialfall des Entscheidungsproblems ist dadurch gekennzeichnet, daß als variable logische Funktionen nur solche mit einem einzigen Argument, also Prädikate auftreten. Für diesen Fall wird von Behmann das engere und auch das weitere Entscheidungsproblem zur völligen Erledigung gebracht. Die Methode der Entscheidung besteht darin, daß nach der Herstellung einer gewissen Normalform die Prädikaten-Variablen samt den zugehörigen Allzeichen bzw. Seinszeichen der Reihe nach eliminiert werden, so daß man zu einer mit der vorgelegten Formel inhaltlich äquivalenten Formel gelangt, welche kein variables Prädikat, vielmehr als einzige logische Funktion die Identitäts-Relation enthält und die sich dann -- falls sie nicht für jeden Individuenbereich richtig oder für jeden falsch ist -- in eine Anzahlbedingung für den Individuenbereich umformen läßt. Und zwar hat diese Bedingung den Inhalt, daß die Anzahl der Individuen einem von gewissen endlich vielen getrennten Zahl-Intervallen angehören muß (von denen eines ein unendliches, nach oben offenes Intervall sein kann). Aus dieser Form des Ergebnisses folgt insbesondere, daß eine Formel der betrachteten Art für jeden beliebigen Individuenbereich richtig ist, falls sie für jeden \textit{endlichen} Bereich richtig ist. Das von Behmann angegebene Entscheidungsverfahren ist nicht nur grundsätzlich durchführbar, sondern auch zur praktischen Verwendung geeignet. Historisch sei bemerkt, daß L. Löwenheim in seiner Abhandlung ``Über Möglichkeiten im Relativkalkül'' (Math. Ann. 76, 1915) im \S~3 bereits das von Behmann behandelte Entscheidungsproblem für die erste Stufe auf einem andern Wege -- in engerem Anschluß an die Ansätze von Schröder - gelöst und auch für die zweite Stufe das entsprechende Verfahren zur Lösung angedeutet hat. Verf. hat übrigens seine Resultate ohne die Kenntnis dieser Abhandlung gefunden.