The proof system, based on resolution method, has become quite popular in automatic theorem proving, because this method is simple to implement. At present many kinds of extensions for resolution method are known： Re...The proof system, based on resolution method, has become quite popular in automatic theorem proving, because this method is simple to implement. At present many kinds of extensions for resolution method are known： Resolution with restricted number of variables in disjuncts, resolution over Linear Equations, Cutting planes, etc. For Classical, Intuitionistic and Minimal （Johansson＇s） propositional logics, the authors introduce the family of resolution systems with full substitution rule （SRC, SRI and SRM） and with e-restricted substitution rule （SeRC, SeRf and SeRM）, where the number of substituted formula connectives is bounded by . The authors show that for each of mentioned logic the SR-type system （in tree form） is polynomially equivalent to Frege systems by size, but for every ~＇ 〉 0, Se＋lR-type has exponential speed-up over the SeR-type （in tree form）.展开更多
文摘The proof system, based on resolution method, has become quite popular in automatic theorem proving, because this method is simple to implement. At present many kinds of extensions for resolution method are known： Resolution with restricted number of variables in disjuncts, resolution over Linear Equations, Cutting planes, etc. For Classical, Intuitionistic and Minimal （Johansson＇s） propositional logics, the authors introduce the family of resolution systems with full substitution rule （SRC, SRI and SRM） and with e-restricted substitution rule （SeRC, SeRf and SeRM）, where the number of substituted formula connectives is bounded by . The authors show that for each of mentioned logic the SR-type system （in tree form） is polynomially equivalent to Frege systems by size, but for every ~＇ 〉 0, Se＋lR-type has exponential speed-up over the SeR-type （in tree form）.
