#матлог #учёба #семинар #не_мехмат #ВШЭ

Уважаемые коллеги, приглашаем вас принять участие в заседании научного семинара "Современные проблемы математической логики" в ВШЭ.

Дата и время: 14.02.2025 в 16:20

Семинар пройдет в формате ZOOM, для получения ссылки пишите на почту kudinov.andrey@gmail.com.

Видео докладов выкладываются на канале:
https://www.youtube.com/channel/UC_Aq6N03uRgVkEcvS6lJLog

Докладчик: Кирилл Александров

Название: Сложность линейно аппроксимируемых расширений базисной пропозициональной логики

Аннотация:
Изучение алгоритмических свойств логик исторически было связано с оцениванием размера наименьших шкал Крипке, отделяющих формулы от логик. Для логики L, полной относительно некоторого класса конечных шкал Крипке, оценка размера наименьших шкал Крипке логики L, опровергающих формулы определенной длины, проводится с помощью функции сложности, которая по длине формулы говорит, какого размера шкалы Крипке логики L достаточно использовать , чтобы опровергнуть формулы не из L данной длины.
Интерес к функции сложности логики связан с долгим убеждением, что ее характер (полиномиальный, экспоненциальный и др.) напрямую связан со сложностью логики, однако Хемаспаандра установила существование нормальных модальных логик с линейной функцией сложности и неразрешимым унарным фрагментом. М.Н. Рыбаков и Д.П. Шкатов расширили её результаты, а именно показали, что для любой степени неразрешимости существуют нормальные расширения модальных логик KTB, K4, GL, Grz с линейными функциями сложности и константными или унарными фрагментами с данной степенью неразрешимости, а также доказали существование суперинтуиционистских пропозициональных логик с похожими свойствами. Мы расширим данный результат на случай базисной пропозициональной логики BPL, которая представляет собой логику класса шкал Крипке с транзитивным и антисимметричным отношением достижимости, а именно покажем, что для любой степени неразрешимости существует линейно аппроксимируемая логика, расширяющая BPL, константный фрагмент которой имеет данную степень неразрешимости.

🔗 Логика в Москве


➰ ВК