ScholarLens Back to search
2019•Transactions on Machine Learning and Artificial IntelligenceOpen access

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

Anahit Artashes Chubaryan ., Artur Khamisyan, Garik Petrosyan .

Open full text 0 citations

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.

Open-access reader

About this research paper

What this paper is about

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.

Why it matters

A significance statement is not available in the OpenAlex record.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available 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.

Key concepts: Proof complexity, Direct proof, Structural proof theory, Proof of concept, Proof theory, Mathematics, Combinatorial proof, Computer-assisted proof

Related papers

Related paper 1Related paper 2
Back to paper searchBrowse research topicsOriginal source
Investigation of the Proof Complexity Measures of Strongly Equal K-Tautologies in Some Proof Systems — Research Paper | ScholarLens