Investigation of the Proof Complexity Measures of Strongly Equal K-Tautologies in Some Proof Systems
DOI:
https://doi.org/10.14738/tmlai.71.6187Keywords:
many-valued logic, determinative conjunct, strongly equal tautologies, proof complexity characteristicsAbstract
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.
