On Quantified Splitting Proof System for Propositional Calculi
Keywords:
Quantified propositional proof systems, Generalized Splitting system, Proof steps, Proof size, Exponential speed-upAbstract
In this paper, some new quantified propositional proof system is introduced and compared by proof complexities with other quantified and not quantified propositional proof systems. It is proved that the introduced system 1) is polynomially equivalent to its quantifier-free variant and 2) has exponential speed-up by sizes over some variants of the quantified resolution system. As the introduced system has a very simple proof construction strategy, it can be very useful not only in Logic, and therefore in Artificial Intelligence, but also in areas such as Computational Biology and Medical Diagnosis.
References
S.A. Cook and A. R. Reckhow, “The relative efficiency of propositional proof systems”, Journal of Symbolic Logic, vol. 44, pp. 36-50, 1979.
O. Beyersdorff, Proof Complexity of Quantified Boolean Logic — A Survey, World Scientific Publishing Company, Chapter 15, 2023.
A. Chubaryan and Arm.Chubaryan, “Bounds of some proof complexity characteristics in the system of splitting generalization”, (in Russian), Otechestv. Nauka w epokhu izmenenij, vol.10, no. 2(7), pp. 11-14, 2015.
A. Chubaryan, S. Hovhanisyan and G. Gasparyan, “On some properties of the generalized splitting system”, (in Russian), Vestnik RAU, vol. 2, pp. 34-42, 2019.
A. Chubaryan, “Universal system for many-valued logic, based on splitting method, and some of its properties”, IJISSET, vol. 5, no. 5, pp. 52-55, 2019. www.ijisset.org/articles/2019-2/volume-5-issue-5/
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2024 Anahit A. Chubaryan
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
