PROOF COMPLEXITIES ON A CLASS OF BALANCED FORMULAS IN SOME PROPOSITIONAL SYSTEMS - Chubaryan, Anahit A. (Proceedings of the YSU A: Physical and Mathematical Sciences, 2022)
In this paper four proof complexity characteristics for some class of balanced tautologies are investigated in two proof systems of propositional logic. One of the considered systems is based on determinative disjunctive normal form, the other on the generalization of splitting method. The optimal upper and lower bounds by logarithmic scale for all main proof complexity characteristics of considered tautologies are obtained in both systems.
Keywords: balanced tautologies; elimination system; generalized splitting system; proof complexity characteristics