Lecture Notes in Computer Science, 2008, Volume 4978/2008, 318-329, DOI: 10.1007/978-3-540-79228-4_28

Logical Closure Properties of Propositional Proof Systems
(Extended Abstract)

Olaf Beyersdorff

View Related Documents

Abstract

In this paper we define and investigate basic logical closure properties of propositional proof systems such as closure of arbitrary proof systems under modus ponens or substitutions. As our main result we obtain a purely logical characterization of the degrees of schematic extensions of EF{\mathit{EF}} in terms of a simple combination of these properties. This result underlines the empirical evidence that EF{\mathit{EF}} and its extensions admit a robust definition which rests on only a few central concepts from propositional logic.

Fulltext Preview

Image of the first page of the fulltext document