PROOF COMPLEXITIES ON A CLASS OF BALANCED FORMULAS IN SOME PROPOSITIONAL SYSTEMS

Author(s)

PROOF COMPLEXITIES ON A CLASS OF BALANCED FORMULAS IN SOME PROPOSITIONAL SYSTEMS Anahit Chubaryan

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.

DOI: 10.46991/PYSU:A/2022.56.2.058 Physical and Mathematical Sciences, 56(2 (258) 58-65

Download PDF

Keywords

balanced tautologies, elimination system, generalized splitting system, proof complexity characteristics

Check for updates

Share

Contact admin with any questions, comments or concerns

[email protected]