RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. LOMI, 1981 Volume 105, Pages 24–44 (Mi znsl3397)

This article is cited in 14 papers

Two tautologihood proof systems based on the split method

E. Ya. Dantsin


Abstract: Two systems for generating of all propositional tautologies and only them are considered. In every of these calculuses there are one axiom and one rule of inference. Proofs for tautologies of many well-known classes with polinomial time recognition algorithm have linear length in these systems. Various formulae's characteristics that influence on length of proofs are studied (one of them is a symmetry of formulae).

UDC: 510.66


 English version:
Journal of Soviet Mathematics, 1983, 22:3, 1293–1305

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024