|
|
«Алгоритмические вопросы алгебры и логики» (семинар С.И.Адяна)
14 октября 2014 г. 18:30–20:05, г. Москва, Математический институт им.В.А.Стеклова РАН
|
|
|
|
|
|
Об одном достаточном условии финитной аппроксимируемости модальных логик
И. Б. Шапировский |
Количество просмотров: |
Эта страница: | 199 |
|
Аннотация:
Финитная аппроксимируемость модальной логики означает её полноту относительно некоторого класса конечных реляционных структур (шкал Крипке). В случае конечно аксиоматизируемой логики это свойство немедленно влечёт её алгоритмическую разрешимость.
Скажем, что шкала $(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$ и высота шкалы конечна.
Из этого следуют новые результаты о разрешимости и финитной аппроксимируемости ряда модальных логик.
|
|