RUS  ENG
Полная версия
СЕМИНАРЫ

«Алгоритмические вопросы алгебры и логики» (семинар С.И.Адяна)
14 октября 2014 г. 18:30, г. Москва, Математический институт им.В.А.Стеклова РАН


Об одном достаточном условии финитной аппроксимируемости модальных логик

И. Б. Шапировский

Аннотация: Финитная аппроксимируемость модальной логики означает её полноту относительно некоторого класса конечных реляционных структур (шкал Крипке). В случае конечно аксиоматизируемой логики это свойство немедленно влечёт её алгоритмическую разрешимость.
Скажем, что шкала $(W,R)$ допускает фильтрацию Францена, если для любого её конечного разбиения найдётся его конечное измельчение такое, что для любых элементов нового разбиения $U, V$ выполняется импликация:
$$ \exists x\in U ~\exists y\in V~ xRy \Longrightarrow \forall x\in U~ \exists y\in V~ xRy $$

В начале 1970-х аспирантом Сегерберга Франценом был замечен следующий несложный, но любопытный факт: модальная логика любого класса шкал, допускающих описанную фильтрацию, финитно аппроксимируема. В частности, с помощью этого факта он получил упрощенное доказательство теоремы Булла о финитной аппроксимируемости всех расширений логики $S4.3$ (это доказательство было опубликовано в 1973 году Сегербергом, которому и принадлежит термин "фильтрация Францена"). В дальнейшем эта техника почти не использовалась.
Недавно нам с Андреем Кудиновым удалось построить фильтрации Францена для всех шкал таких, что $R^n\subseteq R^m$, $n>m$ и высота шкалы конечна. Из этого следуют новые результаты о разрешимости и финитной аппроксимируемости ряда модальных логик.


© МИАН, 2024