Journal of Advances in Applied Mathematics

Download PDF (353.7 KB) PP. 164 - 172 Pub. Date: July 31, 2017

DOI: 10.22606/jaam.2017.23006

• Arman Tshitoyan^*
  PhD Student, Department of Informatics and Applied Mathematics, Yerevan State University, Yerevan, Armenia

In this paper the main proof complexity characteristics in two types of proof systems for a version of many valued propositional logic are investigated for some class of k-valued ( k ≥ 3 ) tautologies. We consider a Hilbert style cut free system and a system, which is dual to resolution system, for many valued logic with implication, defined by Gödel, and negation, defined by permuting the truth values cyclically. For considered class of tautologies we obtain simultaneously optimal bounds for different proof complexity measures (asymptotically the same upper and lower bounds for each measures).

Many-valued logics, Hilbert style proof systems, sequent proof systems, elimination systems, proof complexity.

[1] J. Lukasiewicz, O Logice Trojwartosciowej (On three-valued logic), Ruch Filozoficzny (Lwow), Vol.5, 1920, 169- 171.

[2] An.Chubaryan, Relative efficiency of some proof systems for classical propositional logic, Proceedings of NASA RA, Vol.37,N5,2002, and Journal of CMA (AAS), Vol.37, N5, 2002, 71-84.

[3] A.A.Chubaryan, A.S.Tshitoyan, A.A.Khamisyan, On some proof systems for many-valued logics and on proof complexities in it, (in Russian) Reports of NASA RA, Vol.116, N2, 2016, 18-24.

[4] Chubaryan Anahit, Khamisyan Artur, Generalization of Kalmar’s proof of deducibility in two valued propositional logic into many valued logic, Pure and Applied Mathematics Journal, Vol 6, No. 2, 2017, doi: 10.116448/j.pamj. 20170602.12.,71-75.

[5] Y. Filmus, M. Lauria, J. Nordstrom, N. Thapen, N. Ron-Zewi: Space Complexity in Polynomial Calculus, 2012 IEEE Conference on Computational Complexity (CCC), 2012, 334-344.