О разрешимых фрагментах некоторых логических систем

Первая половина заседания будет посвящена разрешимым фрагментам расширений исчисления Ламбека с экспоненциальной или с релевантной модальностью. Под знаком первой разрешены все структурные правила, под знаком второй — правила перестановки и сокращения. Исчисление Ламбека с релевантной модальностью применяется в математической лингвистике. Оба эти расширения алгоритмически неразрешимы. Рассматриваются их фрагменты, в которых модальность может применяться только к формулам хорновой глубины не более $1$. Для этих фрагментов доказывается разрешимость и принадлежность классу $\mathsf{NP}$. При этом используется вспомогательное исчисление, в котором для проверки, является ли секвенция аксиомой, используется выводимость в контекстно-свободных грамматиках. Эта часть основана на совместной работе С.Л. Кузнецова с С.М. Дудаковым, Б.Н. Карловым и Е.М. Фофановой.

Вторая половина заседания начнётся с доказательства одного несложного факта в классической логике первого порядка: если сигнатура не содержит функциональных символов, то проблема общезначимости для $\Pi_2$-предложений является алгоритмически разрешимой и соответствующий префиксный фрагмент обладает «свойством конечных моделей». Далее, будет рассказано, как доказывается разрешимость $\Pi_2$-фрагмента односортной — точнее, с кванторами по событиям — элементарной теории класса всех вероятностных пространств и сопутствующее «свойство конечных моделей». При этом $\Sigma_2$-фрагмент данной теории оказывается неразрешимым; более того, легко построить $\Sigma_2$-предложение, выражающее конечность пространств по модулю событий меры ноль.