Ամսագրի կամ հրապարակման վերնագիր:
Հրապարակման ամսաթիվ:
Հատոր:
ISSN:
Լրացուցիչ տեղեկություն:
Վերնագիր:
Այլ վերնագիր:
Ստեղծողը:
Амбарцумян, Aрсен A. ; Гаспарян, Гайк А. ; Ованнисян, Саркис А. ; Чубарян, Анаит А.
Խորագիր:
Mathematical cybernetics ; Computer science
Չվերահսկվող բանալի բառեր:
минимальная тавтология ; строгая монотонность системы ; монотонность системы ; количество шагов выводов ; секвенциальные системы без правила сечения пропозициональных логик
Ծածկույթ:
Ամփոփում:
В настоящей работе для тавтологий заданной логики длины п доказано, что максимально возможное количество различных их минимальных тавтологий той же логики имеет экспоненциальную оценку от п, и доказано, что для каждой заданной в данной логике тавтологии существует такая минимальная тавтология, количество шагов вывода секвенциальной формы которой совпадает с наименьшим количеством шагов вывода секвенциальной формы заданной формулы в секвенциальных системах без правила сечения классической, интуиционистской, монотонной логик и логики Иогансона. Սույն աշխատանքում ապացուցված է, որ տվյալ տրամաբանության п երկարությամբ նույնաբանությունների մինիմալ նույնաբանությունների մաքսիմալ հնարավոր քանակը կարող է լինել ցուցչային ֆունկցիա п-ից, ինչպես նաև ապացուցված է, որ դասական, ինտուիցիոնիստական, մինիմալ և մոնոտոն տրամաբանությունների յուրաքանչյուր նույնաբանության համար գոյություն ունի այնպիսի մինիմալ նույնաբանություն, որի սեքվենցիալ ձևի արտածման բարդությունը համընկնում է տրված բանաձևի սեքվենցիալ ձևի արտածման նվազագույն քայլերի հետ թվարկված տրամաբանությունների առանց հատույթի կանոնի սեքվենցիալ համակարգերում: 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.