Ամսագրի կամ հրապարակման վերնագիր:
Հրապարակման ամսաթիւ:
Հատոր:
ISSN:
Պաշտոնական URL:
Լրացուցիչ տեղեկութիւն:
Ափինյան Լևոն Ա․, Չուբարյան Անահիտ Ա., Апинян Левон A., Чубарян Анаит А.
Վերնագիր:
Այլ վերնագիր:
Ասույթային հաշվի մի շարք համակարգերում բանաձևերի որոշ ընտանիքների գծային և ծառատիպ արտածումների երկարությունների մասին ; О длинах линейных и древовидных выводов некоторых семейств формул в ряде систем исчисления высказываний
Ստեղծողը:
Apinyan, Levon A. ; Chubaryan, Anahit A.
Խորագիր:
Mathematical cybernetics ; Computer science
Չվերահսկուող բանալի բառեր:
The varietiesof propositional sequent systems ; The generalization splitting system ; The proof size and number of proof steps ; Exponential speed-up
Ամփոփում:
The sizes of linear and tree-likeproofs for any formulae families are investigated in some systems of propositional calculus: in different sequent systems (with quantifier rules, with the substitution rule, with the cut rule, without the cut rule, monotone) and in the generalization splitting system. The comparison of results obtained here with the boundsobtained formerly for the steps of proofs for the same formulas in the mentioned systems shows the importance of the sizeof proof among the other characteristics of proofcomplexities.