A Propositional Proof System with Permutation Quantifiers

Abstract

<p> Propositional proof complexity is a field of theoretical computer science which concerns itself with the lengths of formal proofs in various propositional proof systems. Frege systems are an important class of propositional proof systems. Extended Frege augments them by allowing the introduction of new variables to abbreviate formulas. Perhaps the largest open question in propositional proof complexity is whether or not Extended Frege is significantly more powerful that Frege. Several proof systems, each introducing new rules or syntax to Frege, have been developed in an attempt to shed some light on this problem.</p> <p> We introduce one such system, which we call H, which allows for the quantification of transpositions of propositional variables. We show that H is sound and complete, and that H's transposition quantifiers efficiently represent any permutation.</p> <p> The most important contribution is showing that a fragment of this proof system, H*1, is equivalent in power to Extended Frege. This is a complicated and rather technical result, and is achieved by showing that H*1 can efficiently prove translations of the first-order logical theory ∀PLA, a logical theory well suited for reasoning about linear algebra and properties of graphs.</p>