Two systems for proving tautologies, based on the split method

Autor:	E. Ya. Dantsin
Rok vydání:	1983
Předmět:	Statistics and Probability Discrete mathematics Applied Mathematics General Mathematics Structure (category theory) Sequent calculus Automorphism Tautology (logic) Simple (abstract algebra) Computer Science::Logic in Computer Science Rule of inference Time complexity Axiom Mathematics
Zdroj:	Journal of Soviet Mathematics. 22:1293-1305
ISSN:	1573-8795 0090-4104
Popis:	We consider two calculi in which all propositional tautologies, and only these, are provable. Despite their simple structure (each calculus has one axiom and one rule of inference), we may obtain linear estimates for the length of deduction in them for various frequently occurring classes of formulas, whose tautology is recognized in polynomial time. We study the characteristics of formulas which influence the length of deduction in these systems. In particular, one of these characteristics is the degree of symmetry defined by automorphisms of the formulas.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::160282c47969c3db6ec686609b42fc61 https://doi.org/10.1007/bf01084392 Zobrazit plný text záznamu Full text from SpringerLink