Дата публикации: 2018

Дата публикации в реестре: 2020-03-18T12:55:09Z

Аннотация:

Исследуется вопрос о взаимосвязи между вычислительной сложностью проблемы разрешения модальной пропозициональной логики и сложностью контрмоделей для формул, которые ей не принадлежат. Известно, что для многих нормальных мономодальных пропозициональных логик разные исследователи применяли сходные конструкции для доказательства PSPACE-трудности проблемы разрешения логики и для обоснования нижних экспоненциальных оценок минимального числа элементов в шкалах Крипке, опровергающих формулы, не принадлежащие ей. Аналогичная ситуация наблюдается и для суперинтуиционистских пропозициональных логик. При этом какие-либо точно сформулированные математические критерии, выражающие эту наблюдаемую связь, автору неизвестны. В работе показано, что если отказаться от условия нормальности в модальных логиках, то можно найти контрпример. Именно, в работе строятся квазинормальные модальные пропозициональные логики, являющиеся линейно аппроксимируемыми и имеющие как сколь угодно высокую сложность проблемы разрешения, так и сколь угодно высокую степень неразрешимости, причём в обоих случаях достаточно рассматривать лишь константные фрагменты

Тип: Статья