Статья в сборнике "Математические вопросы кибернетики" №2, Москва, 1989
Авторы:Раца М.Ф.
Алгоритмическая неразрешимость проблемы выразимости в модальных логиках
Аннотация:
Статья посвящена изучению проблемы выразимости в модальных логиках. Автором доказано, что не существует алгоритма, решающего проблему выразимости в логике S4 или в логике D*, или в какой-нибудь промежуточной между ними модальной логике. Отсюда следует, что логика S4, логика D* и любая промежуточная между ними модальная логика неразрешимы по выразимости. А также, что любое расширение логики S4, не являющееся локально табличной логикой, неразрешимо по выразимости. Кроме этого, к основным результатам работы следует отнести доказательство того, что конечно аксиоматизируемое расширение логики S4 разрешимо по выразимости тогда и только тогда, когда оно является локально табличной логикой.
Ключевые слова:
математическая логика, модальные логики, проблема выразимости, логика S4, табличная логика