#матлог #учёба #спецсеминар

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

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

в четверг 14.05, начало в 18:30, состоится доклад

Слюсарев Владислав Владимирович (МФТИ)

Две конструкции случайной шкалы Крипке

Мы изучаем вероятности общезначимости модальных формул в случайных шкалах Крипке на фиксированном n-элементном множестве. Распределение случайной n-элементной шкалы для каждого n может быть выбрано разными способами и приводит к разным результатам. Фиксируя распределение для каждого n, мы получаем семейство случайных шкал. Если для данной формулы вероятность того, что она общезначима в случайной n-элементной шкале, стремится к единице при n→∞, то мы говорим, что эта формула общезначима асимптотически почти наверное в данном семействе случайных шкал. Множество формул, общезначимых асимптотически почти наверное, называется почти достоверной логикой семейства случайных шкал. Мы говорим, что семейство случайных шкал удовлетворяет закону нуля и единицы, если вероятность общезначимости любой модальной формулы стремится либо к 0, либо к 1 при n→∞.

Наиболее естественным будет рассмотреть равномерное распределение на множестве всех шкал Крипке на n точках. Ж.-М. Ле Барс опроверг закон нуля и единицы для этого семейства [1]. В. Горанко описал частичную счётную аксиоматизацию для его почти достоверной логики [2]. Неизвестно, является ли эта логика разрешимо аксиоматизируемой. Позитивные результаты были получены для семейства случайных шкал с равномерным распределением на всех n-элементных шкалах логики GL: Р. Вербрюгге доказала закон нуля и единицы и описала счётную аксиоматизацию почти достоверной логики [3].

В этом докладе мы рассмотрим две общих конструкции случайных шкал Крипке. В первой конструкции рассматривается равномерное распределение на множестве всех n-элементных шкал заданной модальной логики L. Мы показываем, что для довольно широкого семейства логик вероятность общезначимости формулы можно оценить, рассматривая связные шкалы логики L, которые имеют более простую комбинаторную структуру. С помощью этого результата мы получаем конечные аксиоматизации почти достоверных логик, соответствующих логикам SL, GL.3, Grz.3, KD5, KD45, K5B и S5, и доказываем закон нуля и единицы для KD5, KD45, K5B и S5 [4,5].

Во второй конструкции мы рассматриваем Хорнову модальную логику L и строим L-замыкание случайной шкалы с равномерным распределением среди всех n-элементных шкал. Мы доказываем, что почти достоверные логики таких семейств случайных шкал являются нормальными расширениями логики, заданной аксиомами Горанко. Далее мы рассматриваем хорновы логики вида K + ♢^m p → ♢p и K + ♢^m □p → □^m p и доказываем, что для них выполнен закон нуля и единицы, а почти достоверная логика равна S5 [6].

[1] Le Bars J.-M. The 0-1 law fails for frame satisfiability of propositional modal logic // Proceedings 17th Annual IEEE Symposium on Logic in Computer Science. — 02/2002. — P. 225–234.

[2] Goranko V. The Modal Logic of Almost Sure Frame Validities in the Finite // Advances in Modal Logic. — 2020.

[3] Verbrugge R. Zero-one laws for provability logic: Axiomatizing validity in almost all models and almost all frames // 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2021. — IEEE Xplore, 06/2021.

[4] Слюсарев В. В. Почти достоверная модальная логика шкал Крипке с функциональным отношением // Труды Московского физико-технического института (национального исследовательского университета). — 2024. — Т. 16,No 3 (63). — С. 57—71.

[5] Слюсарев В. В. Почти достоверные модальные логики и законы нуля и единицы в хорновых классах // Доклады РАН. Математика, информатика, процессы управления. — 2024. — Т. 519. — С. 57––64.

[6] Sliusarev V. Modal logics of almost-sure validities in some classes of Euclidean and transitive frames // Combinatorics and number theory. — 2025. — Т. 14, No 1. — С. 49––64.

Видеозаписи предыдущих