CERES in aussagenlogischen Beweisschemata

Abstract

Die Schnittelimination, eines der bekanntesten Probleme in der Beweistheorie, wurde für Sequenzenkalüle erster Ordnung von Gentzen in seinem gefeierten Hauptsatz definiert und gelöst. Ceres bezeichnet einen anderen Algorithmus zur Schnittelimination erster und höherer Ordnung in der klassischen Logik. Er beruht auf der Idee einer charakteristischen Klauselmenge, die aus einem Beweis des Sequenzenkalküls extrahiert wurde und stets widerlegbar bleibt. Eine Resolutionswiderlegung dieser Klauselmenge dient als Gerüst für einen Beweis, der lediglich atomare Schnitte enthält. Das wird erreicht, indem die Klauseln der Resolutionswiderlegung durch die entsprechenden Beweisprojektionen des Originalbeweises ersetzt werden. Ceres wurde auf Beweisschemata ausgedehnt, die als Schablonen für gewöhnliche Beweise erster Ordnung dienen, die natürliche Zahlen als Parameter haben. Jede Instantiierung der Parameter durch konkrete Zahlen ergibt einen neuen Beweis erster Ordnung. Das Anwenden existierender Algorithmen der Schnittelimination auf jeden Beweis dieser unendlichen Sequenz würde zu einer ebenfalls unendlichen Folge von schnittfrei Beweisen führen. Das Ziel in der Logik erster Ordnung von Ceres ist es nun, stattdessen eine einheitliche, schematische Beschreibung dieser Sequenz schnittfrei Beweise zu liefern. Um dieses Ziel zu erreichen, wurde jedes Konzept in Ceres schematisch entworfen: es enthält Schemata der charakteristischen Klauselmenge, Schemata der Resolutionswiderlegung, Projektionsschemata etc. Während Ceres ein vollständiger Algorithmus zur Schnittelimination in der Logik erster Ordnung gilt, ist nicht klar, ob dies auch für die Schemata erster Ordnung zutrifft: liefert Ceres stets ein Schema schnittfreier Beweise, wenn ein Beweisschema mit Schnitten eingegeben wird? Die Schwierigkeit besteht darin, ein passendes Widerlegungsschema für das charakteristische Termschema eines Beweisschemas zu finden und darzustellen. In der vorliegenden Arbeit beschäftigen wir uns mit der Lösung dieses Problems, indem wir Ceres auf aussagenlogische Schemata einschränken, welche als Schablonen für aussagenlogische Beweise dienen. Durch die adäquate Beschränkung der Aussagekraft der aussagenlogischen Schemata und Beweisschemata wollen wir eine Version schematischen Ceres vorlegen, welche einen vollständigen Algorithmus der Schnittelimination für aussagenlogische Schemata liefert. Wir konzentrieren uns dabei auf einen bestimmten Schritt von Ceres: Schemata der Resolutionswiderlegung. Zuerst beweisen wir, dass durch das einfache Adaptieren von Ceres für Schemata erster Ordnung für unseren Fall der Algorithmus unvolständig ist. Danach modifizieren wir das Konzept des Schemas der Resolutionswiderlegung: um eine Klauselmenge zu widerlegen, bringen wir sie zuerst in eine allgemeine Form, um im Anschluss eine festgelegte Widerlegung dieser allgemeinen Klauselmenge zu benutzen. Unsere Variation von schematischem Ceres stellt den ersten Schritt in Richtung einer Vollständigkeit aussagenlogischer Schemata dar.

Cut-elimination is one of the most famous problems in proof theory, and it was defined and solved for first-order sequent calculus by Gentzen in his celebrated Hauptsatz. Ceres is a different cut-elimination algorithm for first- and higher-order classical logic. It is based on the notion of a characteristic set of clauses which is extracted from a proof in sequent calculus and is always unsatisfiable. A resolution refutation of this clause set is used as a skeleton for a proof with only atomic cuts. This is obtained by replacing clauses from the resolution refutation with the corresponding proof projection derived from the original proof. Ceres was extended to proof schemata, which are templates for usual first-order proofs, with parameters for natural numbers. Every instantiation of the parameters to concrete numbers yields a new first-order proof. We could apply existing algorithms for cut-elimination to each proof in this infinite sequence, obtaining an infinite sequence of cut-free proofs. The goal of Ceres for first-order schemata is instead to give a uniform, schematic description of this sequence of cut-free proofs. To this aim, every concept in Ceres was made schematic: there are characteristic clause set schemata, resolution refutation schemata, projection schemata, etc. However, while Ceres is known to be a complete cut-elimination algorithm for first-order logic, it is not clear whether this holds for first-order schemata too: given in input a proof schema with cuts, does Ceres always produce a schema for cut-free proofs? The difficult step is finding and representing an appropriate refutation schema for the characteristic term schema of a proof schema. In this thesis, we progress in solving this problem by restricting Ceres to propositional schemata, which are templates for propositional proofs. By limiting adequately the expressivity of propositional schemata and proof schemata, we aim at providing a version of schematic Ceres which is a complete cut-elimination algorithm for propositional schemata. We focus on one particular step of Ceres: resolution refutation schemata. First, we prove that by naively adapting Ceres for first-order schemata to our case, we end up with an incomplete algorithm. Then, we modify slightly the concept of resolution refutation schema: to refute a clause set, first we bring it to a generic form, and then we use a fixed refutation of that generic clause set. Our variation of schematic Ceres is the first step towards completeness with respect to propositional schemata.