Հայաստանի ատենախոսությունների բաց մատչելիության պահոց = Open Access Repository of the Armenian Electronic Theses and Dissertations (Armenian ETD-OA) = Репозиторий диссертаций Армении открытого доступа

Տեղադրության կանոնի տարատեսակների էֆեկտիվությունը դասական և ոչ դասական տրամաբանական համակարգերի համար

Նալբանդյան, Հակոբ Սիմոնի (2011) Տեղադրության կանոնի տարատեսակների էֆեկտիվությունը դասական և ոչ դասական տրամաբանական համակարգերի համար. PhD thesis, ԵՊՀ.

[img]
Preview
PDF (Abstract)
Available under License Creative Commons Attribution.

Download (305Kb) | Preview

    Abstract

    В диссертационной работе для классического, интуиционистского и минимального исчисления высказываний исследована эффективность различных модификаций правила подстановки с точки зрения двух основных критериев сложностных характеристик выводов: количества различных формул вывода и общей длины вывода. В работе введено понятие глубинно-ограниченного правила подстановки и сравнены по обеим указанным критериям выводы в системах Фреге с правилом подстановки без ограничений, в системах Фреге с глубинно-ограниченным правилом подстановки и в системах Фреге без правила подстановки. Используя полученные результаты , а также результаты для ранее исследованного правила подстановки с ограничением на количество переменных, вместо которых допустима одновременная подстановка, для классического исчисления высказываний доказана одинаковая эффективность (с полиномиальной точностью) по длине выводов систем Фреге и систем Фреге с правилом подстановки (в то время как еще в 1969г. было доказано, что правило подстановки может существенно ускорить количество шагов, во всех обзорах теории сложностей выводов соответствующая задача для длины выводов указывалась в числе нерешенных). В качестве «моста» между двумя сравниваемыми системами послужила система Фреге, дополненная правилом единичного переименования, т.е. подстановки с ограничением как на глубину (0) подставляемой формулы, так и на количество (1) переменных, вместо которых допустима одновременная подстановка. Աշխատանքում համեմատված են դասական, ինտուիցիոնիստական և մինիմալ ասույթային հաշվի տարբեր համակարգեր ըստ նրանցում ապացուցվող բանաձևերի արտածման բարդության տարբեր բնութագրիչների՝ արտածման քայլերի քանակի և արտածման երկարության: Ներմուծվել է խորությամբ սահմանափակված տեղադրման կանոնի գաղափարը, համաձայն որի թույլատրվում է կատարել միայն այնպիսի բանաձևերի տեղադրություն, որոնց խորությունը չի գերազանցում նախապես տրված m թվից: Դիտարկվում է նաև այնպիսի տեղադրության կանոն, երբ սահմանափակում է դրվում այն փոփոխականների քանակի վրա որոնց փոխարեն թույլատրվում է կատարել տեղադրություն:Ինտուիցիոնիստական և մինիմալ տրամաբանության համար համեմատվում են բոլոր վերոհիշյալ տիպի համակարգերը ըստ արտածումների բարդության երկու բնութագրիչների: In this thesis some proof systems of classical, intuitionistic and minimal propositional logics are compared by different characteristics of proof complexity (by the number of steps and by sizes) for the formulas, proved in these systems. The depth-restricted substitution rule is introduced such that the substitutions are allowed only for no more than m-depth formulas (for some fixed m). The constant-bounded substitution rule, when the substitution instead only no more than some fixed number of variables is allowed at a time, are considered also.

    Item Type: Thesis (PhD)
    Additional Information: Տեղադրության կանոնի տարատեսակների էֆեկտիվությունը դասական և ոչ դասական տրամաբանական համակարգերի համար: Efficiency of substitution rule modifications for classical and non-classical logical systems.
    Uncontrolled Keywords: Նալբանդյան Հակոբ Սիմոնի, Nalbandyan Hakob
    Subjects: Mathematics and Cybernetics
    Divisions: UNSPECIFIED
    Depositing User: NLA Circ. Dpt.
    Date Deposited: 16 Mar 2017 10:48
    Last Modified: 16 Mar 2017 10:48
    URI: http://etd.asj-oa.am/id/eprint/4295

    Actions (login required)

    View Item