Publication Details:

"ՀՀ ԳԱԱ Զեկույցներ" հանդեսը հիմնադրվել է 1944թ.: Լույս է տեսնում տարին 4 անգամ:

Journal or Publication Title:

ՀՀ ԳԱԱ Զեկույցներ = Доклады НАН РА = Reports NAS RA

Date of publication:

2022

Volume:

122

Number:

2

ISSN:

0321-1339

Official URL:

Additional Information:

Չուբարյան Ա. Ա., Ազիզյան Հ. Ս., Chubaryan A. A., Azizyan H. S.

Other title:

Ասույթային հաշվի երկու համակարգերում բալանսավորված բանաձևերի արտածումների բարդությունների վերաբերյալ ; On Proof Complexities of Balanced Formulas in Two Propositional Proof Systems

Contributor(s):

Պատ․ խմբ.՝ Վ. Հ․ Համբարձումյան (1944-1959) ; Մ․ Մ․ Ջրբաշյան (1960-1965) ; Ա․ Գ․ Նազարով (1966-1983) ; Պատ․ խմբ․ տեղակալ՝ Վ․ Հ․ Ղազարյան (1983-1986) ; Պատ․ խմբ․՝ Դ․ Մ․ Սեդրակյան (1987-1999) ; Գլխավոր խմբ․՝ Ս․ Ա․ Համբարձումյան (2000-2004) ; Վ․ Ս․ Զաքարյան (2005-2018) ; Ռ․ Մ․ Մարտիրոսյան (2018-)

Coverage:

118-124

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:

ՀՀ ԳԱԱ «Գիտություն» հրատ.

Format:

pdf

Identifier:

սեղմիր այստեղ կապին հետևելու համար ; oai:arar.sci.am:321228

Call number:

АЖ 144

Digitization:

ՀՀ ԳԱԱ Հիմնարար գիտական գրադարան

Location of original object:

ՀՀ ԳԱԱ Հիմնարար գիտական գրադարան