Моделирование логических систем средствами их фрагментовModelling of logical systemsby means of their fragments

В диссертации исследуются вопросы алгоритмической выразительности фрагментов неклассических логик, получающихся ограничениями на используемые средства языка; в пропозициональных языках это прежде всего число пропозициональных переменных, а в предикатных — число и арность предикатных букв, а также число предметных переменных. Описаны общие методы, позволяющие полиномиально погружать логические системы в полном языке в их фрагменты, удовлетворяющие довольно сильным ограничениям указанного вида. В качестве следствий получены результаты об алгоритмической сложности таких фрагментов. Описаны достаточные условия, при которых эти методы работают. Приведены примеры систем, в отношении которых описанные методы не работают и при этом соответствующие их фрагменты алгоритмически проще, чем система в полном языке. Основные результаты диссертации можно коротко сформулировать следующим образом: многие модальные пропозициональные логики моделируются в их фрагментах с одной пропозициональной переменной или даже без переменных, суперинтуиционистские — в их фрагментах от двух пропозициональных переменных, модальные и суперинтуиционистские предикатные — в их фрагментах с одной унарной предикатной буквой и двумя предметными переменными. Уделено внимание исключениям: например, описаны бесконечные классы модальных предикатных логик, монадические фрагменты которых, даже будучи обогащёнными равенством, являются разрешимыми.