Publication Details:
"ՀՀ ԳԱԱ Զեկույցներ" հանդեսը հիմնադրվել է 1944թ.: Լույս է տեսնում տարին 4 անգամ:
Journal or Publication Title:
ՀՀ ԳԱԱ Զեկույցներ = Доклады НАН РА = Reports NAS RA
Date of publication:
Volume:
Number:
ISSN:
Official URL:
Additional Information:
Չուբարյան Ա. Ա., Ազիզյան Հ. Ս., Chubaryan A. A., Azizyan H. S.
Title:
O сложностях выводов балансированных формул в двух пропозициональных системах выводов
Other title:
Ասույթային հաշվի երկու համակարգերում բալանսավորված բանաձևերի արտածումների բարդությունների վերաբերյալ ; On Proof Complexities of Balanced Formulas in Two Propositional Proof Systems
Creator:
Чубарян, А. А. ; Азизян, А. С.
Contributor(s):
Պատ․ խմբ.՝ Վ. Հ․ Համբարձումյան (1944-1959) ; Մ․ Մ․ Ջրբաշյան (1960-1965) ; Ա․ Գ․ Նազարով (1966-1983) ; Պատ․ խմբ․ տեղակալ՝ Վ․ Հ․ Ղազարյան (1983-1986) ; Պատ․ խմբ․՝ Դ․ Մ․ Սեդրակյան (1987-1999) ; Գլխավոր խմբ․՝ Ս․ Ա․ Համբարձումյան (2000-2004) ; Վ․ Ս․ Զաքարյան (2005-2018) ; Ռ․ Մ․ Մարտիրոսյան (2018-)
Subject:
Uncontrolled Keywords:
балансированные формулы ; дерево расщеплений ; определяющий конъюнкт ; сложности выводов
Coverage:
Abstract:
Для одного класса балансированных формул исследованы минимальные значения количества шагов и длины выводов в двух пропозициональных системах: системе ОР, основанной на обобщённом методе расщепления, и системе Е, основанной на определяющей дизъюнктивной нормальной форме. Для всех четырех исследуемых величин получены одинаковые по порядку (по логарифмической шкале) верхние и нижние оценки. Ասույթային հաշվի երկու՝ ընդհանրացված տրոհման մեթոդի վրա հիմնված ОР և որոշիչ դիզյունկտիվ ձևի վրա հիմնված Е համակարգերում ուսումնասիրվել են բալանսավորված բանաձևերի մի դասի համար արտածումների քայլերի քանակի և երկարության նվազագույն արժեքները: Բոլոր չորս ուսումնասիրված մեծությունների համար ստացվել են լոգարիթմական սանդղակով միևնույն կարգի վերին և ստորին գնահատականներ:
In this paper the minimal number of proof steps and proof sizes for some class of balanced formulas are investigated in two propositional proof systems: system OP, based on the generalization of splitting method, and system E, based on the determinative disjunctive normal form. The same by order (according logarithmic scale) the upper and lower bounds are obtained for all four investigated quantities.
Place of publishing:
Երևան
Publisher:
Type:
Format:
Identifier:
Call number:
Digitization:
ՀՀ ԳԱԱ Հիմնարար գիտական գրադարան