Модальная и алгебраическая логика (научный семинар) - YouTube

На онлайн-заседании объединенного семинара кафедры математической логики и теории алгоритмов МГУ

"Модальная и алгебраическая логика" и "Логические методы в информатике"

в ближайший четверг 25 апреля, начало в 18:45, состоится доклад

М.Н. Рыбаков (ИППИ РАН, ВШЭ, ТвГУ)

Неразрешимость логики QLC в языке с двумя предметными переменными

Логика QLC — предикатная суперинтуиционистская логика, определяемая семантически классом линейных шкал Крипке. Предполагается рассказать об алгоритмических свойствах фрагментов этой логики. Известно, что фрагмент с одной предметной переменной логики QLC алгоритмически разрешим, а с тремя — нет (последнее следует из неразрешимости классической логики предикатов в языке с тремя переменными). Интересен вопрос о разрешимости её фрагмента с двумя переменных, ему в основном и будет посвящён доклад.

Логика QLC находится между логикой слабого закона исключённого третьего QKC и классической логикой предикатов QCL, при этом QCL в языке с двумя переменным разрешима, а QKC — нет (и даже при одной одноместной предикатной букве). Мы покажем, что QLС в языке с двумя переменными алгоритмически неразрешима (при этом для доказательства достаточно позитивных формул в языке с одной бинарной предикатной буквой и бесконечным множеством унарных). Если останется время, то обсудим также алгоритмические свойства расширений QLC (многие из них неразрешимы и даже сильно неразрешимы в языке с двумя переменными).

Доказательство идейно очень простое, и предварительные знания не требуются. Желательно иметь представление о семантике Крипке для интуиционистского предикатного языка, но все необходимые определения будут даны.

Видеозаписи предыдущих докладов:

https://www.youtube.com/playlist?list=PLEBNQnjHceeVxr2o766qqr993dyaKWRCX

Веб-страница с аннотациями и слайдами:

http://logic.math.msu.ru/sem/ml/

Для получения ссылки ZOOM пишите в личные сообщения группы.

Источник: vk.com

Комментарии: