Portal de Periódicos da CAPES

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

2019; Volume: 7; Issue: 1 Linguagem: Inglês

10.14738/tmlai.71.6187

2054-7390

Anahit Artashes Chubaryan ., Artur Khamisyan, Garik Petrosyan .,

Logic, Reasoning, and Knowledge

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.