Title: CERES in Propositional Proof Schemata,
Abstract: 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. Ceres was extended to proof schemata, which
are templates for usual first-order proofs, with parameters for natural
numbers. 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 a cut-free proof? 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.