Mathematics

Proof complexities on a class of balanced formulas in some propositional systems

A. A. Chubaryan

Yerevan State University

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.

Keywords: balanced tautologies, elimination system, generalized splitting system, proof complexity characteristics.

MSC: Primary 03F20; Secondary 03F07

Received: 25.04.2022
Revised: 23.06.2022
Accepted: 01.07.2022

Language: English

DOI: 10.46991/PYSU:A/2022.56.2.058