Publication Details:
"ՀՀ ԳԱԱ Զեկույցներ" հանդեսը հիմնադրվել է 1944թ.: Լույս է տեսնում տարին 4 անգամ:
Journal or Publication Title:
ՀՀ ԳԱԱ Զեկույցներ = Доклады НАН РА = Reports NAS RA
Date of publication:
Volume:
Number:
ISSN:
Official URL:
Additional Information:
Ափինյան Լ. Ա., Չուբարյան Ա. Ա., Apinyan L. A., Chubaryan A. A.
Title:
Other title:
Ասույթային հաշվի մի շարք համակարգերում բանաձևերի որոշ ընտանիքների գծային և ծառատիպ արտածումների երկարությունների համեմատություն ; Linear and Tree-Like Proofs Sizes Comparison for Any Formulae Families in Some Systems of Propositional Calculus
Creator:
Апинян, Л. A. ; Чубарян, А. A.
Contributor(s):
Պատ․ խմբ.՝ Վ. Հ․ Համբարձումյան (1944-1959) ; Մ․ Մ․ Ջրբաշյան (1960-1965) ; Ա․ Գ․ Նազարով (1966-1983) ; Պատ․ խմբ․ տեղակալ՝ Վ․ Հ․ Ղազարյան (1983-1986) ; Պատ․ խմբ․՝ Դ․ Մ․ Սեդրակյան (1987-1999) ; Գլխավոր խմբ․՝ Ս․ Ա․ Համբարձումյան (2000-2004) ; Վ․ Ս․ Զաքարյան (2005-2018) ; Ռ․ Մ․ Մարտիրոսյան (2018-)
Subject:
Uncontrolled Keywords:
разновидности секвенциальных систем исчисления высказываний ; система обобщенных расщеплений ; количество шагов и длина вывода ; экспоненциальное ускорение
Coverage:
Abstract:
Для некоторых семейств формул исследованы длины как линейных, так и древовидных выводов в ряде систем исчисления высказываний: в разновидностях секвенциальных систем (с кванторами, с правилом подстановки, с правилом сечения, без правила сечения, монотонных), а также в системе обобщенных расщеплений. Сравнение полученных результатов с ранее полученными оценками для шагов тех же разновидностей выводов тех же формул и в тех же системах указывает на определенную значимость именно длины вывода как основной сложностной характеристики выводов.
Բանաձևերի որոշ ընտանիքների համար ուսումնասիրված են գծային և ծառատիպ արտածումների երկարությունները ասույթային հաշվի մի քանի համակարգերում՝ սեկվենցիալ համակարգերի տարատեսակներում (ծավալիչներով, տեղադրման կանոնով, հատույթի կանոնով, առանց հատույթի կանոնի, մոնոտոն), ինչպես նաև ընհանրացված տրոհումների համակարգում: Աշխատանքում ստացված արդյունքների համեմատությունը նախկինում ստացված նույն բանաձևերի նշված համակարգերում արտածումների քայլերի համար ստացված արդյունքների հետ փաստում է արտածումների երկարության՝ որպես բարդության բնութագրիչի արժևորումը:
The sizes of linear and tree-like proofs for any formulae families are investigated in some systems of propositional calculus: in different sequent systems (with quantifier rules, with substitution rule, with cut rule, without cut rule, monotone) and in the generalization splitting system. The comparison of obtained here results with the bounds, wich are obtained for the steps of proofs for the same formulas in the mentioned systems former, shows the importance of the size of proof as complexities characteristic
Place of publishing:
Երևան
Publisher:
Type:
Format:
Identifier:
Call number:
Digitization:
ՀՀ ԳԱԱ Հիմնարար գիտական գրադարան