2022; Physical and Mathematical Sciences, 56(2 (258): 58–65
Shared with The Gufo

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

Anahit Chubaryan*

Received: 2025-01-22 · Published: 2022-07-13

© 2022 The Author(s) and the original publisher.

CC BY-NC 4.0 This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
Shared article.
Original title
PROOF COMPLEXITIES ON A CLASS OF BALANCED FORMULAS IN SOME PROPOSITIONAL SYSTEMS
Author
Anahit Chubaryan
Published
2022-07-13
Licence
Creative Commons Attribution-NonCommercial 4.0 International
Original
https://doi.org/10.46991/PYSU:A/2022.56.2.058

Abstract

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.
1 / ? 100% Open in new tab Download Cite

Loading the full text…

Download Follow Updates