Beweisprogramme für die Prädikatenlogik und der Vollständigkeitssatz von Beth

Die vorliegende Schrift ist eine - teilweise verbesserte und umgearbeitete - Fassung einer Arbeit, die aus einem Seminar tiber die Anwendungsmoglichkeiten der Programrniersprache COMIT bei Herrn Professor UNGER hervorging. Herrn Professor UNGER und Herrn Professor HASENJAEGER, der mich in den Problem kreis der maschinellen Beweisverfahren eingefuhrt und speziell auf die Moglich keit hingewiesen hat, den Bethschen Vollstandigkeitsbeweis fur ein solches Ver fahren nutzbar zu machen, gilt mein besonderer Dank. Herrn Professor HASEN JAEGER verdanke ich auch den Hinweis auf die (in 3.5 behandelte) Version des Bethschen Satzes fur praenexe N ormalform. In dieser Arbeit stellen wir ein neues Beweisprogramm fur die Praedikatenlogik dar, das "im Prinzip" in der Lage ist, jeden wahren Satz der Praedikatenlogik auch zu beweisen. Grundlage dieses Programmes ist der Vollstandigkeitsbeweis von BETH [1], den wir auch fiir zahlreiche Beweise heranziehen werden. Grundsatzlich solI diese Arbeit ohne Vorkenntnisse aus der Logik verstandlich sein; im ersten Teil stellen wir daher die Aussagen- und Praedikatenlogik von Grund auf dar. Urn uns langwierige syntaktische Herleitungen soweit als moglich zu ersparen, folgen wir hierbei den im wesentlichen von H. RASIOWA und R.

Inhalt

1. Boolesche Algebren.- 1.1 Definitionen.- 1.2 Erzeugendensysteme.- 1.3 Ideale in Booleschen Algebren.- 1.4 Unendliche Vereinigungen und Durchschnitte.- 2. Aussagenlogik.- 2.1 Definition der Aussagenlogik.- 2.2 Der Satz von Lindenbaum.- 2.3 Der Vollständigkeitssatz.- 2.4 Normalformen.- 3. Praedikatenlogik.- 3.1 Definition der Praedikatenlogik.- 3.2 Die Q-Algebra des PK.- 3.3 Belegungen.- 3.4 Der Bethsche Vollständigkeitsbeweis.- 3.5 Der Satz von Beth für praenexe Normalform.- 4. Der Satz von Herbrand und einige Beweisprogramme.- 4.1 Der Satz von Herbrand.- 4.2 Programme, die auf dem Satz von Herbrand beruhen.- 4.3 Das Verfahren von D. Prawitz, H. Prawitz und N. Voghera.- 5. Unser Beweisprogramm.- 5.1 Grundriß des Verfahrens.- 5.2 Begründung unseres Verfahrens.- 5.3 Das COMIT-Beweisprogramm.