Евгений Золин выступил с докладом на семинаре в МГУ
31 октября на объединённом семинаре «Логические проблемы информатики» и «Модальная и алгебраическая логика» состоялся доклад Евгения Золина.
Тема доклада: "Градуированная модальная логика: аксиоматика, разрешимость, определимость".
Аннотация:
В стандартном модальном языке имеется оператор возможности, означающий: формула верна в некотором последователе данного мира. Как с теоретической точки зрения, так и в некоторых приложениях естественно рассмотреть модальные логики с градуированными модальностями, означающими: формула верна в не менее (не более) n последователях данного мира. Первая аксиоматика градуированной модальной логики GrK класса всех шкал и соответствующая теорема о полноте появилась в работе К. Файна “In so many possible worlds” (1972). Далее последовала серия из 7 работ “Graded Modalities I, II, ..., VII” (1985–1999) итальянский исследователей (Fattorosi-Barnaba, de Caro, Cerrato и др.), причем первые 4 работы (то есть до 1994 года) они написали, не зная о существовании работы Файна; в частности, в 1988 году независимо от Файна нашли (другую) аксиоматику логики GrK .
В докладе дается обзор основных результатов в этой области: «конечная» (в некотором расширенном смысле) аксиоматизируемость градуированных аналогов «традиционных» модальных логик, таких как K, K4, S4, S5, в частности, необычные аксиомы для градуированной S4; разрешимость и сложность этих логик (Евгений Казаков, Ian Pratt-Hartmann, 2009); неразрешимость логики с градуированными прямыми и обратными модальностями (Золин, 2011), систематизация вычислительной сложности логик в языках, имеющих градуированные модальности и/или градуированные обратные модальности (Bednarczyk, Kieronski, Witkowski, 2018); характеризация градуированного модального языка (GrML) как фрагмента языка первого порядка, инвариантного относительно градуированных бисимуляций (van der Hoek 1992, de Rijke 2000); критерий GrML-определимости классов отмеченных моделей Крипке (de Rijke 2000); аналог теоремы Гольдблатта–Томасона, т.е. критерий GrML-определимости классов шкал Крипке (Katsuhiko Sano, Minghui Ma, AiML 2010). Упомянуты некоторые открытые вопросы в этой области.
Дополнение: Недавно получен аналог теоремы Розена о характеризации: над классом конечных моделей градуированный модальный язык является в точности фрагментом языка первого порядка, инвариантным относительно градуированных бисимуляций (Martin Otto “Graded modal logic and counting bisimulation”, 2019). Там же приводится описание градуированных бисимуляционных игр.
Многие из тем доклада освещены подробнее в лекциях докладчика «Модальная логика 2014-2015 года».
Сайт семинара.