Ամսագրի կամ հրապարակման վերնագիր:

Математические вопросы кибернетики и вычислительной техники=Կիբեռնետիկայի և հաշվողական տեխնիկայի մաթեմատիկական հարցեր=Mathematical problems of computer science

Հրապարակման ամսաթիվ:

2019

Հատոր:

52

ISSN:

2579-2784

Լրացուցիչ տեղեկություն:

Համբարձումյան Արսեն. Ա., Գասպարյան Հայկ Ա., Հովհաննիսյան Սարգիս Ա., Չուբարյան Անահիտ Ա., Hambardzumyan Arsen A., Gasparyan Hayk A., Hovhannisyan Sarkis A., Chubaryan Anahit A.

Այլ վերնագիր:

Դասական և ոչ դասական տրամաբանությունների մինիմալ նույնաբանությունների քանակի և դրանց արտածումների հատկությունների մասին; On the Numbers of Minimal Tautologies and Properties of Their Proofs in Classical and Nonclassical Logic

Ծածկույթ:

66-73

Ամփոփում:

В настоящей работе для тавтологий заданной логики длины п доказано, что максимально возможное количество различных их минимальных тавтологий той же логики имеет экспоненциальную оценку от п, и доказано, что для каждой заданной в данной логике тавтологии существует такая минимальная тавтология, количество шагов вывода секвенциальной формы которой совпадает с наименьшим количеством шагов вывода секвенциальной формы заданной формулы в секвенциальных системах без правила сечения классической, интуиционистской, монотонной логик и логики Иогансона. Սույն աշխատանքում ապացուցված է, որ տվյալ տրամաբանության п երկարությամբ նույնաբանությունների մինիմալ նույնաբանությունների մաքսիմալ հնարավոր քանակը կարող է լինել ցուցչային ֆունկցիա п-ից, ինչպես նաև ապացուցված է, որ դասական, ինտուիցիոնիստական, մինիմալ և մոնոտոն տրամաբանությունների յուրաքանչյուր նույնաբանության համար գոյություն ունի այնպիսի մինիմալ նույնաբանություն, որի սեքվենցիալ ձևի արտածման բարդությունը համընկնում է տրված բանաձևի սեքվենցիալ ձևի արտածման նվազագույն քայլերի հետ թվարկված տրամաբանությունների առանց հատույթի կանոնի սեքվենցիալ համակարգերում: It is proved in this paper that the number of minimal tautologies for any given logic tautology of size п can be an exponential function in п, and it is also proved that for every tautology of the given logic there is some minimal tautology such that the number of its sequential form proof steps is equal to minimal steps in the proof of sequential form for the given tautology in cut-free sequent systems for classical, intuitionistic, Joganssons and monotone logics.

Հրատարակիչ:

Изд-во НАН РА

Ձևաչափ:

pdf

Նույնացուցիչ:

oai:arar.sci.am:261506

Բնօրինակի գտնվելու վայրը:

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