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

Thomas Schwentick Der Vollständigkeitssatz der Prädikatenlogik • Der Satz gilt auch für die Prädikatenlogik mit Gleichheit, der Beweis ist aber komplizierter Logik für Inf. / Schwentick / WiSe 07/08 B: Prädikatenlogik - 6.Eigenschaften Folie 2. Der Endlichkeitssatz der Prädikatenlogik Satz 6.2 [Endlichkeitssatz] Eine unendliche Menge F von PL-Formeln ist genau dann erfüllbar, wenn jede endliche