Investigation of the Proof Complexity Measures of Strongly Equal K-Tautologies in Some Proof Systems

  • Anahit Artashes Chubaryan Full Professor of Department of Informatics and Applied Mathematics, Yerevan State University
  • Artur Khamisyan Department of Informatics and Applied Mathematics Yerevan State University
  • Garik Petrosyan Department of Informatics and Applied Mathematics Yerevan State University
Keywords: many-valued logic, determinative conjunct, strongly equal tautologies, proof complexity characteristics

Abstract

Here we generalize the notions of determinative conjunct and strongly equal tautologies formany-valued logic (MVL) and  compare the proof complexity measures of strongly equal many-valued tautologies in some proof systems of MVL. It is proved  that in some “weak”   proof system the strongly equal many-valued tautologies have the same proof complexities, while in the “strong” proof systems the measures of proof complexities for strongly equal tautologies can essentially differ from each other.

References

(1) An. Chubaryan, Arm. Chubaryan, "A new conception of Equality of Tautologies", L&PS, Vol.V, No,1, 3-8,Triest, Italy, 2007.

(2) A.Chubaryan, G.Petrosyan, The relations between the proof complexities of strongly equal classical tautologies in Frege systems, Pоссийско-китайский научный журнал «Содружество» № I (1), 2016 / ФИЗ-МАТ НАУКИ,78-80.

(3) An. Chubaryan, A.Mnatsakanyan, On the bounds of the main proof measures in some propositional roof systems, Scholar Journal of Phis. Math. And Stat.,2014, Vol.1,Issue-2, pp.111-117.

(4) Chubaryan Anahit, Khamisyan Artur, Arman Tshitoyan, On some systems for Łukasiewicz’s many-valued logic and its properties, Fundamentalis Scientiam, Vol.8(8), Spain, 2017, 74-79.

(5) Anahit Chubaryan, Artur Khamisyan, Two types of universal proof systems for all variants of many-valued logics and some properties of them, Iran Journal of Computer Science, https://doi.org/10.1007/s42044-018-0015-4.

(6) J. Lukasiewicz, O Logice Trojwartosciowej, Ruch filoseficzny (Lwow), Vol. 5, 1920, 169-171.

(7) K.Godel, Zum intuitionistishen Aussagenkalkul, Akademie der Wissenshaften in Wien, Mathematische-naturwissenschaftliche Klasse, Auzeiger, Vol. 69, 1932, 65-66.

(8) A.A.Chubaryan: Comparison of proof sizes in systems and substitution systems of Frege, Izvestiya NAN Armenii, Matematika, vol. 35, No. 5, 2002, 71-84.

(9) 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.

Published
2019-03-08
How to Cite
Chubaryan, A. A., Khamisyan, A., & Petrosyan, G. (2019). Investigation of the Proof Complexity Measures of Strongly Equal K-Tautologies in Some Proof Systems. Transactions on Machine Learning and Artificial Intelligence, 7(1), 56. https://doi.org/10.14738/tmlai.71.6187