Модальная логика случайных шкал Крипке тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Слюсарев Владислав Владимирович

• Слюсарев Владислав Владимирович
• кандидат наук
• 2026

Оглавление диссертации кандидат наук Слюсарев Владислав Владимирович

1.1 Модальная логика

1.2 Семантика Крипке

1.3 Хорновы замыкания

1.4 Леммы о сохранении общезначимости модальных формул

1.5 Теория вероятностей

1.6 Асимптотический анализ

1.7 Комбинаторные числа и их асимптотики

1.8 Почти достоверные логики

1.9 Случайные шкалы

2 Почти достоверные логики равномерно распределённых случайных шкал

2.1 Общие результаты

2.2 Теорема о переносе для связных шкал

2.3 Логика SLas

2.4 Логики GL.3as и Grz.3as

2.5 Логики евклидовых шкал

3 Почти достоверные логики хорновых замыканий случайной шкалы

3.1 Общие свойства почти достоверных логик хорновых замыканий

3.2 Логика MLr

3.3 Псевдотранзитивные логики

3.4 Псевдоевклидовы логики

3.5 Логики Та*, КБ**, ТВа*

Заключение

^исок литературы

Введение диссертации (часть автореферата) на тему «Модальная логика случайных шкал Крипке»

Введение

Данная работа посвящена характеризации случайных конечных структур с бинарным отношением в терминах модальной логики. Задачи, связанные с логическими свойствами случайных структур, активно изучались в математике, начиная с последней трети XX века, главным образом для языков классической логики, таких как язык первого порядка. Закон нуля и единицы для логики первого порядка — это один из наиболее значимых результатов в данной области. Он утверждает, что любое свойство случайных п-арных отношений на структуре конечной мощности, определимое в языке первого порядка, имеет асимптотическую вероятность, равную нулю или единице, при мощности структуры, стремящейся к бесконечности. Примером являются свойства случайных графов. Закон нуля и единицы для логики первого порядка независимо доказали различными методами Ю. Глебский и соавторы [28] и Р. Фейгин [7].

Доказательство Фейгина использует связь между конечными случайными структурами и счётной случайной структурой. В частности, в случае графов, т.е. структур с одним бинарным отношением, рассматривается граф Радо — конструкция счётного случайного графа. Х. Гайфман [8] доказал, что граф Радо имеет и-категоричную теорию первого порядка, и построил её счётную аксиоматизацию. Он предложил систему аксиом экстенсиональности, которые соответствуют тому, что для любых п элементов структуры существует элемент, связанный отношением с каждым из этих элементов любым наперёд заданным способом. Доказано, что аксиомы экстенсиональности общезначимы в счётной случайной структуре с одним отношением почти наверное. Из и-категоричности следует, что существует счётная структура, которой граф Радо изоморфен с вероятностью, равной единице. Аналогичные утверждения верны и для произвольного конечного реляционного языка первого порядка.

Фейгин [7] показал, что все аксиомы экстенсиональности верны в конечных реляционных структурах асимптотически почти наверное. Таким образом,

для любого предложения s произвольного реляционного языка первого порядка L эквивалентны следующие утверждения:

• s общезначимо асимптотически почти наверное в случайных конечных L-структурах;

• s является теоремой теории первого порядка, заданной аксиомами экстенсиональности;

• s выводится из конечного числа аксиом экстенсиональности;

• s общезначимо почти наверное в случайной счётной L-структуре.

Следовательно, для любого предложения первого порядка s, либо s, либо его отрицание принадлежит первопорядковой теории графа Радо.

В литературе этот результат Фейгина, из которого, в частности, следует, что асимптотическая почти достоверность в конечных структурах эквивалентна почти достоверности в счётной структуре, называется теоремой о переносе (англ. transfer theorem). Он вызвал повышенный интерес к конечной теории моделей и последующие исследования законов нуля и единицы. Подобные результаты были доказаны для некоторых расширений логики первого порядка. А. Бласс, Ю. Гу-ревич и Д. Козен [3] доказали его для расширения языка первого порядка с операторами неподвижной точки. Затем Ф. Колайтис и М. Варди установили обобщение для инфинитарного языка с ограниченным числом переменных L^ ш [14] и некоторых фрагментов монадического языка второго порядка [15]. Многие подобные результаты доказываются с использованием вариантов и обобщений теоремы Фейгина о переносе.

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

Для логики второго порядка закон нуля и единицы, вообще говоря, не выполнен. В частности, определимо свойство «структура содержит нечётное количество элементов», которое не имеет асимптотической вероятности. Предложения, не имеющие асимптотической вероятности, также построены в монадическом экзистенциальном фрагменте логики второго порядка М£} [2]. Контрпримеры к закону нуля и единицы были также построены для более узких случаев этого языка, в частности, для логики неориентированных графов [16; 20].

Среди фрагментов логики второго порядка представляет интерес пропозициональная модальная логика с семантикой Крипке. В качестве случайных структур возможно рассмотрение как шкал Крипке, так и моделей Крипке. Более того, закон нуля и единицы уместно рассматривать как для общезначимости, так и для выполнимости модальных формул в шкалах Крипке. Таким образом модальная логика позволяет рассматривать различные фрагменты языка второго порядка: так, общезначимость в шкалах Крипке соответствует универсальному, а выполнимость — экзистенциальному монадическому языку.

Перечислим основные результаты, относящиеся к закону нуля и единицы для шкал и моделей Крипке. Дж. Халперн и Б. Капрон доказали закон нуля и единицы для класса всех случайных моделей, а также нескольких модально определимых классов случайных моделей [13]. Ж. Ле Барс [16] построил пример модальной формулы, общезначимость которой в случайных конечных шкалах Крипке не имеет асимптотической вероятности, тем самым опровергнув закон нуля и единицы для класса всех конечных шкал Крипке. Существуют классы конечных шкал, для которых закон нуля и единицы выполнен. Р. Вербрюгге [25] показала, что для логики GL закон нуля и единицы выполняется как для шкал, так и для моделей, и представила аксиоматические системы для формул, истинных асимптотически почти наверное.

Другая нетривиальная задача заключается в вычислении почти достоверной логики данной случайной структуры — множества всех предложений, которые выполнены в этой структуре с асимптотической вероятностью, равной едини-

це. Одним из первых результатов, относящихся к этой задаче, является аксиоматизация почти достоверной логики первого порядка в графе Радо — модели счётного случайного графа, представленная Х. Гайфманом [8]. Для модальной логики также известны некоторые аксиоматизации почти достоверных логик. Для класса всех конечных моделей Крипке эта логика совпадает с логикой Карнапа [13]. В. Горанко и Б. Капрон [10] представили счётную систему аксиом для почти достоверной логики случайной счётной шкалы Крипке. Затем Горанко [9] использовал этот результат для изучения почти достоверной логики случайной конечной шкалы Крипке. Р. Вербрюгге нашла счётные системы аксиом для почти достоверных логик конечных шкал и моделей логики GL [25], а также для конечных моделей логик Grz и wGrz [26].

Актуальность темы. В существующей литературе не описаны общие методы, которые позволили бы вычислять почти достоверные логики для различных классов шкал. Результаты Горанко [9] и Вербрюгге [25] во многом опираются на известные аксиоматики логики первого порядка рассматриваемых структур. Ранее не были представлены нетривиальные примеры классов шкал Крипке, для которых установлена конечная аксиоматизируемость почти достоверной логики. Представляет интерес не решённая в известных работах задача нахождения классов шкал, модальная логика которых совпадает с их почти достоверной логикой. Данная работа формулирует общий метод вычисления почти достоверных логик, основанный на оценке вероятностей с использованием перечислительной комбинаторики. С помощью этого метода мы получаем нетривиальные примеры классов шкал, почти достоверная логика которых конечно аксиоматизируема.

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

1. Почти достоверные логики случайной шкалы Крипке из классов, определяемых модальными логиками К05, К045, К5В, S5, Grz.3, GL.3, SL.

2. Почти достоверные логики хорновых замыканий случайной шкалы Крипке:

псевдотранзитивных, псевдоевклидовых.

Для достижения поставленной цели необходимо было решить следующие задачи:

1. Исследовать соотношение между почти достоверной логикой, соответствующей данной модальной логике, и почти достоверной логикой класса всех связных шкал этой логики.

2. Найти почти достоверные логики классов связных шкал, соответствующих логикам Х05, ^45, K5B, S5, Grz.3, GL.3, SL.

3. Исследовать распределение псевдотранзитивных и псевдоевклидовых замыканий случайной шкалы Крипке.

Научная новизна:

1. Было выполнено оригинальное исследование соотношений между почти достоверными логиками класса всех шкал и класса всех связных шкал данной модальной логики. Результаты исследования приведены в тексте в теореме 83.

2. Впервые для изучения почти достоверных модальных логик применён комбинаторно-вероятностный метод.

3. Впервые представлены нетривиальные примеры модальных логик, которые являются почти достоверными логиками своего класса шкал.

Теоретическая значимость работы заключается в предложенном новом методе исследования почти достоверных логик в различных классах шкал Крип-ке, а также в полученных аксиоматиках, которые могут лечь в основу дальнейших исследований почти достоверных модальных логик и законов нуля и единицы для модальных логик. Практическая значимость работы заключается в полученных результатах, описывающих распределения случайных шкал Крипке в рассмотренных классах, которые могут быть использованы для усовершенствования алгоритмов решения вычислительных задач модальной логики, таких как проверка общезначимости и выполнимости формулы в заданной шкале.

Основные положения, выносимые на публичное представление.

1. Справедливы следующие равенства для почти достоверных логик классов шкал, определяемых модальными логиками:

(a) KD5as = KD5;

(b) KD45as = KD45;

(c) K5Bas = K5B;

(d) S5as = S5;

(e) Grz 3as = Grz.3;

(f) GL.3as = GL.3;

(g) SLas = SL.

2. Почти достоверная логика хорнова замыкания случайной шкалы Крип-ке, соответствующего модальной логике K + Omp ^ Op, равна S5 для любого m ^ 2.

3. Почти достоверная логика хорнова замыкания случайной шкалы Крип-ке, соответствующего модальной логике K + Om^P ^ □mp, равна S5 для любого m ^ 1.

Публикации и апробация работы. Результаты работы были опубликованы в статьях:

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

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

3. V. Sliusarev. Modal logics of almost sure validities in some classes of euclidean and transitive frames. Combinatorics andNumber Theory. — 2025. — Т. 14, №1. — С. 49—64.

Автор представил результаты работы на конференциях и семинарах:

1. Слюсарев В. В. «Модальные логики хорновых замыканий случайной шкалы Крипке». НИС «Современные проблемы математической логики», НИУ ВШЭ, 2023.

2. V. Sliusarev. «Modal Logics of Horn Closures of the Random Kripke Frame».

The 29th Joint NMSU/UTEP Workshop on Mathematics, Computer Science, and Computational Sciences, New Mexico State University, 2023.

3. Слюсарев В. В. «Модальные логики случайных шкал в определимых классах». НИС «Современные проблемы математической логики», НИУ ВШЭ, 2023.

Методология и методы исследования. Во всей работе активно используются такие конструкции модальной логики, как р-морфизмы, несвязные суммы, порождённые подшкалы, и теоремы модальной логики о сохранении общезначимости модальных формул в шкалах Крипке, полученных с помощью этих конструкций, а также результаты о сохранении истинности модальных формул ограниченной модальной глубины. Полнота приводимых аксиоматизаций для почти достоверных логик доказывается с использованием перечисленных конструкций и известных утверждений о финитной аппроксимируемости ряда модальных логик. Для исследования распределений случайных шкал Крипке используются методы перечислительной комбинаторики. Применяются результаты комбинаторики, связанные с тождествами и асимптотическими равенствами для комбинаторных последовательностей, таких как числа Белла. Асимптотические вероятности возникновения различных свойств случайной шкалы Крипке вычисляются непосредственно по определению либо с использованием известных неравенств теории вероятности, таких как неравенство Чебышёва и неравенство Йенсена. При вычислении пределов вероятностей применяются методы асимптотического анализа.

1 Обзор используемых определений и результатов

1.1 Модальная логика

В этом разделе мы определим основные понятия: модальные формулы, нормальные модальные логики.

Определение 1. Множеством пропозициональных переменных будем называть некоторое счётное множество РУ.

Модальной формулой называется конечная последовательность символов из алфавита РУ и {(,), ^, □}, удовлетворяющая рекурсивному определению:

1. ± — модальная формула.

2. Если р <Е РУ, то р — модальная формула.

3. Если ф,ф — модальные формулы, то (ф ^ ф) — модальная формула.

4. Если ф — модальная формула, то □ф — модальная формула. МЬ — множество всех модальных формул.

Определение 2. Будем использовать следующие сокращения в модальных формулах:

1. Т := ± ^ ±;

2. —ф := ф ^ ±;

3. ф V ф := —ф ^ ф;

4. ф Л ф := —(—ф V —ф);

5. ф ^ ф := (ф ^ ф) Л (ф ^ ф);

6. Оф := —□—ф.

7. О0ф = ф и Ог+1ф = ООгф для г ^ 0.

Определение 3. Множество L модальных формул называется нормальной модальной логикой, если:

1. L содержит все тавтологии классической пропозициональной логики;

2. L содержит аксиому нормальности □(р ^ д) ^ (□р ^ □д);

3. L замкнуто относительно трёх правил вывода: (MP) Если ф е L и ф — ф е L, то ф е L; (Gen) Если ф е L, то □ф е L;

(Sub) Если ф е L, то ф[ф/р] е L, гдер е PV, ф[ф/р] — результат замены всех вхождений переменной р в формуле ф на формулу ф.

Определение 4. K — минимальная нормальная модальная логика.

Определение 5. Пусть L — нормальная модальная логика, Г С ML — множество модальных формул. Обозначим через L + Г минимальную нормальную модальную логику, которая содержит множество L U Г.

Введём обозначения для нормальных модальных логик, которые будут далее рассматриваться в тексте.

Определение 6. Определим модальные логики:

SL = K + Ор ^ □р; K5 = K + ООр — □р; KD5 = K5 + ОТ; KD45 = KD5 + ООр — Ор; K5B = K5 + ООр — р;

S5 = K5 + р — Ор; GL.3 = K + □(□р — р) — □р + □ (□р Л р — q) У □ (□q Л q — р); Grz.3 = K + □(□(р — □р) — р) — р + □(□р — q) У □(□q — р).

1.2 Семантика Крипке

В этом разделе мы определим шкалы и модели Крипке, сформулируем определения истинности модальной формулы в точке модели Крипке и общезначимости модальной формулы в шкале Крипке. Затем мы опишем классы шкал, которые характеризуют нормальные модальные логики из определения 6.

Определение 7. Шкалой Крипке будем называть пару Г = Я), где W — произвольное непустое множество, Я С W х W. Множество W назовём носителем шкалы Г и обозначим через dom Г.

Определение 8. Пусть W — непустое множество, Я С W х W — отношение. Будем использовать следующие обозначения.

1. V ) — множество всех подмножеств множества W;

2. Ы^ — диагональное отношение {(х,х) | х Е W};

3. Я-1 = {(у,х) I (х,у) Е Я} — отношение, обратное к Я;

4. Я о Я' = {(х,у) I хЯг и гЯ'у для некоторого г Е W} — композиция отношений Я и Я' для любого отношения Я' С W х W;

5. Я0 = Ы^; Яи+1 := Я о Яп для всех п > 0 — степени отношения Я;

6. Я+ = У^^^ Яг — транзитивное замыкание Я;

7. Я* = У ¿>0 Яг; — рефлексивно-транзитивное замыкание Я;

8. Я(х) = {у Е W I хЯу} — множество Я-потомков точки х Е W;

9. Я[и] ^ Ух&и Я(х) — множество Я-потомков множества и С W;

10. Я\и = ЯП(и х и) — сужение Я на и для любого подмножества и С W.

Определение 9. Оценкой в шкале Крипке Г = (^ Я) называется функция

V : РУ — V^),

сопоставляющая пропозициональным переменным подмножества W.

Определение 10. Моделью Крипке называется пара М = (Г, V), где Г — шкала Крипке, V — оценка в Г. Будем также писать М = (^ Я, V), если Г = (^ Я).

Определение 11. Пусть М = (^ Я, V) — модель Крипке, ф — модальная формула. Запись М, а = ф означает, что формула ф истинна в точке а Е W модели М. Запись М, а = ф означает, что формула ф не истинна в точке а модели М.

Истинность модальной формулы ф в точке V Е W модели М = Я, V) определяется рекурсивно:

1. М,а =

2. Если р Е РУ, то М, а = р тогда и только тогда, когда а Е V (р).

3. Если ф,ф — модальные формулы, то М,а = ф ^ ф тогда и только тогда, когда М, а = ф или М, а = ф.

4. Если ф — модальная формула, то М, а = □ф тогда и только тогда, когда для любого Ь Е W, такого что аЯЬ, выполнено М, Ь = ф.

Определение 12. Формула ф Е ML общезначима в шкале Крипке Г, если при любой оценке V : РУ ^ Т^) для любой точки w Е W выполнено Г, V^ = ф.

Определение 13. Логикой Log Т класса шкал Крипке Т называется множество всех модальных формул ф Е ML, таких что Г = ф для любой шкалы Г Е Т.

Если Т = {Г}, то будем опускать фигурные скобки: положим по определению Log Г = Log{F}.

Определение 14. Классом шкал Fr Г множества формул Г С ML называется класс всех шкал Крипке Г, таких что Г = ф для любой модальной формулы ф Е Г.

Многие модальные логики, включая те, которые мы перечислили в определении 6, имеют классы шкал, которые легко описываются через свойства отношения шкалы. Далее мы определим несколько важных свойств отношений и охарактеризуем с их помощью классы шкал рассматриваемых логик.

Определение 15. Пусть W — непустое множество, Я С W х W — отношение.

1. Я называется функцией, если для любого а Е W выполнено | Я(а) | = 1.

2. Я сериальное, если для любого а Е W выполнено Я(а) = 0.

3. Я евклидово, если для любых а, Ь, с Е W, таких что аЯЬ и аЯс, выполнено ЬЯс.

4. Я рефлексивное, если Ы^ С Я.

5. Я иррефлексивное, если Ы^ П Я = 0.

6. Я симметричное, если Я = Я-1.

7. Я транзитивное, если Я2 С Я.

8. Я нётерово, если не существует бесконечных простых Я-цепей, то есть последовательностей {ап}пЕ^ С W, таких что апЯап+1 и ап = ап+1 для любого п Е n.

9. Я неветвящееся, если для любых а, Ь, с Е W, таких что аЯЬ и аЯс, выполнено ЬЯс, или сЯЬ, или с = Ь.

10. Я называется отношением эквивалентности, если Я рефлексивно, симметрично и транзитивно.

Введённые здесь термины распространяются также на шкалы Крипке. Например, будем говорить, что шкала Я) евклидова, если Я евклидово.

Предложение 16. (см. [4, раздел 3.6]) Пусть Г = (W, Я) — шкала Крипке.

1. Г |= SL тогда и только тогда, когда Я является функцией.

2. Г |= Х5 тогда и только тогда, когда Я евклидово.

3. Г |= Х05 тогда и только тогда, когда Я евклидово и сериальное.

4. Г |= Х045 тогда и только тогда, когда Я евклидово, сериальное, транзитивное.

5. Г = K5B тогда и только тогда, когда Я евклидово и симметричное.

6. Г = S5 тогда и только тогда, когда Я является отношением эквивалентности.

7. Г = GL.3 тогда и только тогда, когда Я транзитивное, иррефлексив-ное, нётерово и неветвящееся.

8. Г = Grz.3 тогда и только тогда, когда Я транзитивное, рефлексивное, нётерово и неветвящееся.

Известно, что все модальные логики из определения 6 полны по Крипке (см. [4, разделы 4.3 и 10]), то есть совпадают с модальными логиками своих классов шкал. Так, например, ^ | Log(Fr(K5)), причём Fr(K5) — это класс всех шкал с евклидовым отношением согласно предложению 16. Это наблюдение можно усилить, что часто полезно в доказательствах: вместо класса всех шкал данной

логики оказывается достаточно рассматривать его подкласс, состоящий из всех конечных шкал, где общезначима данная логика.

Определение 17. Модальная логика L называется финитно аппроксимируемой, если существует класс F конечных шкал Крипке, такой что L = Log F.

Заметим, что в этом определении F Q G, где G — класс всех конечных шкал, в которых общезначима логика L. Следовательно, Log G Q Log F = L. При этом L Q Log G по построению класса G. Таким образом, справедливо следующее наблюдение.

Предложение 18. Пусть модальная логика L финитно аппроксимируема, F — класс всех конечных шкал логики L. Тогда L = Log F.

Финитная аппроксимируемость логик, введённых в определении 6, широко известна и может быть установлена с помощью стандартных техник, таких как фильтрации (см. [4, раздел 5.3]) и селективные фильтрации (см. [4, раздел 5.5]).

Предложение 19. Логики SL, K5, KD5, KD45, K5B, S5, GL.3, Grz.3 финитно аппроксимируемы.

1.3 Хорновы замыкания

Для построения конструкции случайной шкалы данной модальной логики интересна следующая задача: для заданной шкалы F = (W, R) и модальной логики L найти шкалу F1 = (W,R) с минимальным по включению отношением R D R, таким что F' = L. Эту шкалу можно неформально понимать как ближайшую к F шкалу из класса шкал логики L. В этом разделе мы опишем известное достаточное условие на логику L, при котором для любой шкалы F искомая шкала F' существует.

Определение 20. (см. [6, раздел 9.3]) Универсальным хорновым предложением называется предложение на языке первого порядка с одним двуместным преди-

катным символом Я вида

Ух1 ... Ухп (х^ Л ... Л х^ Ях^к ^ хтЯх1), (1)

где п > 0, к ^ 0 и ц, . . . , гк, ]]_, ..., ]к, т, I Е {1, ..., п}.

Определение 21. Класс шкал Крипке Т называется хорновым классом, если существует множество хорновых предложений Н, такое что Т является классом всех шкал, удовлетворяющих Н для любого Н Е Н.

Определение 22. Модальная логика L является хорновой, если Fr(L) — хорнов класс.

Определение 23. Пусть Т — хорнов класс шкал Крипке, Г | (W, Я) — шкала. Определим Т-замыкание шкалы Г как шкалу (^ Я'), где Я' С W х W — минимальное по включению отношение, удовлетворяющее условиям:

1. Я С Я';

2. (^ Я') Е Т.

Определение 24. Если L — хорнова модальная логика, то Fr(L)-замыкание шкалы Крипке называется её L-замыканием.

Предложение 25. Для любого хорнова класса Т и любой шкалы Г существует Т-замыкание шкалы Г.

Доказательство. Пусть Г | (W, Я). Обозначим через К множество всех отношений Я' С W х W, таких что Я С Я' и (^ Я') Е Т.

Заметим, что для любого хорнова предложения Н максимальное отношение W х W удовлетворяет Н, так как оно удовлетворяет правой части любой импликации вида (1). Тогда W х W Е К, так что К = 0.

Пусть Яо | П К. Тогда Я С Яо. Покажем, что (^ Яо) Е Т. Пусть Н — множество универсальных хорновых предложений, определяющее Т. Рассмот-

рим любое предложение Н Е Н вида

Ух Уу Ух1 ... Ухп (ф(х,у,х1,... ,г„) — хЯу).

Пусть оценка переменных х, у, г1, ..., гп элементами а, Ь, с1, ..., сп Е W обращает ф(х, у, г1,..., гп) в истину. Тогда аЯ'Ь для любого Я' Е К, поскольку (^ Я') удовлетворяет Н. Таким образом, (а,Ь) Е ПЯ' = Я0, что и требовалось.

По построению Я0 имеем Я0 С Я' для любого Я' Е К. Следовательно, шкала ^,Я0) является Т-замыканием Г. □

Обозначим Т-замыкание шкалы Г через (Г)Т; если Т = Fr(L) для некоторой логики L, то мы также будем обозначать его через (Г)ь.

1.4 Леммы о сохранении общезначимости модальных формул

В этом разделе мы опишем некоторые факты, с помощью которых мы будем изучать модальные логики шкал.

Определение 26.

1. Пусть Г1 = [, Я1) и = Я2) — шкалы Крипке. Изоморфизмом шкал Г1 и Г2 называется биекция / : W1 — W2, такая что для любых а, Ь Е W1 выполнено, что аЯ1Ь тогда и только тогда, когда ](а)Я2/(Ь).

2. Пусть М1 = V1) и М2 = (Ш2, Я2, V2) — модели Крипке. Тогда биекция / : W1 — W2 называется изоморфизмом моделей М1 и М2, если она является изоморфизмом шкал (W1, Я1) и (W2, Я2) и для любых а Е W1 и р Е РУ выполнено, что а Е V1(p) тогда и только тогда, когда ](а) Е V2(p).

Запись Г1 = Г2 означает, что шкалы Г1 и Г2 изоморфны, то есть существует изоморфизм шкал Г и Г2. То же относится к моделям.

Очевидно, что если / : W1 — W2 — изоморфизм моделей М1 и М2, то для любой модальной формулы ф верно, что М1 ,а = ф тогда и только тогда,

когда M2, f (a) = ф. Отсюда следует, что если между шкалами F1 и F2 существует изоморфизм, то Log Fi = Log F2.

Определение 27. Пусть F = (W, R) — шкала Крипке, U Q W — непустое множество. Сужением F\U называется шкала (U, R\U).

Определение 28. Пусть F = (W, R) — шкала Крипке, U Q W — непустое множество. Порождённой подшкалой FtU называется сужение F\(R*[U]).

Обозначение. Если U = {a}, то будем использовать сокращение Fta для FtU. Шкалы вида Fta называются конусами или точечно-порождёнными шкалами.

Лемма 29. (см. [11, раздел 2.2]) Пусть F = (W, R) — шкала Крипке. Тогда

LogF = р| Log(FtU) = р| Log(Fta).

UQW aEW

Определение 30. Пусть I — некоторое непустое множество, {Fi}iEl — семейство шкал Крипке и Fi = (W., Ri) для любого i Е I. Несвязной суммой семейства шкал Крипке {F.}.eI называется шкала УiGl Fi = (W, R), где:

W = {(i,w) \i E I, w E Wi}, (i, w)R(j, u) тогда и только тогда, когда i = j и wRiu.

Обозначение. Будем использовать сокращение F1 Ы F2 := уiE{1 2} Fi.

Лемма 31. (см. [11, раздел 2.2]) Пусть I — непустое множество, {Fi}iEl — семейство шкал Крипке, F = У ieI Fi. Тогда Log F Q Log Fi для всех i Е I.

Следствие 32. Пусть I — непустое множество, {Fi }iEl — семейство шкал Крипке, F = У iEl Fi. Тогда

Log F = p| Log Fi..

iEl

Доказательство. По предыдущей лемме Log F С Q^ Log Fi. Обратное включение верно по лемме 29, так как для любого i Е I шкала Fi изоморфна порождённой подшкале Ft{(i, w) | w Е dom Fi}. □

Определение 33. Пусть F = (W, R) и F' = (W', R') — шкалы Крипке. Отображение f : W ^ W' называется p-морфизмом из F в F', если выполнены три условия:

1. f — сюръекция;

2. (монотонность) для любой пары элементов x,y Е W, таких что xRy, выполнено f (x)R'f (y);

3. (поднятие) для любых x Е W и у' Е W', таких что f (x)R'y', существует у Е W, такой что xRy и f (y) = y'.

В этом случае будем писать f : F ^ F'.

Лемма 34. [22, главаI, теорема 3.11]Пусть F = (W, R) и F' = (W', R') — шкалы Крипке, и существуетp-морфизм f : F ^ F'. Тогда Log(F) С Log(F').

Определение 35. Рекурсивно определим функцию md : ML ^ n U {0} — модальную глубину формулы:

1. md(±) = 0;

2. md(p) = 0 для любой p Е PV;

3. md(^> ^ ф) = max{md(^>), md^)};

4. md(^) = md(p) + 1.

Определение 36. Пусть F = (W, R) — шкала Крипке, x Е W и m Е n. Определим усечённый конус F^m — шкалу Крипке:

m

Wim = U Rl(x);

i=0

R^m = R\W^m;

F^m _ /w^m

F x x 1 R x ) .

Если V — оценка в шкале Г, то определим оценку в усечённом конусе Г^т по правилу Vfm(p) = V(р) П W^т(х) для любого р е РУ.

Лемма 37. (см. [11, раздел 3.2]) Пусть Г = (^ Я) — шкала Крипке, V — оценка и х е W. Пусть т е n. Тогда для любой формулы ф, такой что md(ф) ^ т, верно

Г, V ,х = ф ^ Г^т, Vfm, х = ф.

Следствие 38. Если md(ф) = т, то Г = ф тогда и только тогда, когда существует точка х е dom Г, такая что Г^т = ф.

1.5 Теория вероятностей

Список литературы диссертационного исследования кандидат наук Слюсарев Владислав Владимирович, 2026 год

СПИСОК ЛИТЕРАТУРЫ

1. Aho A. V., Garey M. R., Ullman J. D. The Transitive Reduction of a Directed Graph // SIAM Journal on Computing. — 1972. — Vol. 1, no. 2. — P. 131-137.

2. Bars J.-M. L. Counterexamples of the 0-1 Law for Fragments of Existential Second-Order Logic: an Overview // Bulletin of Symbolic Logic. — 2000. — Vol. 6. — P. 67-82.

3. Blass A., Gurevich Y., Kozen D. A zero-one law for logic with a fixed-point operator // Information and Control. — 1985. — Vol. 67, no. 1. — P. 70-90.

4. Chagrov A. V., Zakharyaschev M. Modal Logic. Vol. 35. — Oxford University Press, 1997.

5. Chen B., Yeh X-^.Some Explanations of Dobinski's Formula // Studies in Applied Mathematics. — 1994. — Vol. 92. — P. 191-199.

6. Ebbinghaus H., Flum J. Finite Model Theory. — Springer Berlin Heidelberg, 1999.

7. Fagin R. Probabilities on finite models // Journal of Symbolic Logic. — 1976. — Vol. 41, no. 1. — P. 50-58.

8. Gaifman H. Concerning measures in first order calculi // Israel Journal of Mathematics. — 1964. — Vol. 2. — P. 1-18.

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

10. Goranko V., Kapron B. The Modal Logic of the Countable Random Frame // Archive for Mathematical Logic. — 2003. — Vol. 42, no. 3. — P. 221-243.

11. Goranko V., Otto M. Model theory of modal logic // Studies in Logic and Practical Reasoning. — 2007. — Dec. — Vol. 3. — P. 249-329.

12. Gut A. Probability: A Graduate Course. — Springer, 2013.

13. Halpern J. Y, Kapron B. Zero-One Laws for Modal Logic // Annals of Pure and Applied Logic. — 1994. — Vol. 69, no. 2/3. — P. 157-193.

14. Kolaitis P, Vardi M. Y. Infinitary logics and 0-1 laws // Information and Computation. — 1992. — Vol. 98, no. 2. — P. 258-294.

15. Kolaitis P. G., Vardi M. Y. 0-1 Laws for Fragments of Second-Order Logic: An Overview // Logic from Computer Science. — New York, NY : Springer New York, 1992. — P. 265-286.

16. 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.

17. Miksa F., Moser L., Wyman M. Restricted Partitions of Finite Sets // Canadian Mathematical Bulletin. — 1958. — Vol. 1, no. 2. — P. 87-96.

18. Nagle M. C., Thomason S. K. The Extensions of the Modal Logic K5 // The Journal of Symbolic Logic. — 1985. — Vol. 50, no. 1. —P. 102-109.

19. Odlyzko A. M. Asymptotic enumeration methods // Handbook of Combinatorics (Vol. 2). — Cambridge, MA, USA : MIT Press, 1996. — P. 1063-1229.

20. Popova S., Zhukovskii M. Existential monadic second order logic of undirected graphs: a disproof of the Le Bars conjecture // Annals of Pure and Applied Logic. —2019. — Vol. 170. — P. 505-514.

21. Renyi A., Szekeres G. On the height of trees // Journal of The Australian Mathematical Society. — 1967. — Vol. 7. — P. 497-507.

22. Segerberg K. An Essay in Classical Modal Logic. — Uppsala, Filosofiska Foreningen Och Filosofiska Institutionen Vid Uppsala Universitet, 1971.

23. Segerberg K. On the Logic of 'To-Morrow' // Theoria. — 1967. — Vol. 33, no. 1. — P. 45-52.

24. Spencer J. H., Florescu L. Asymptopia. Vol. 71. —American Mathematical Society, 2014.

25. 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.

26. Verbrugge R Zero-one laws with respect to models of provability logic and two Grzegorczyk logics // Advances in Modal Logic 2018: Accepted Short Papers. — 08/2018. —P. 115-120.

27. Wilf H. S. Generatingfunctionology. —Academic Press, 1990.

28. Область и степень реализуемости формул ограниченного исчисления предикатов / Ю. Глебский [и др.] // Кибернетика. — 1969. — Т. 5. — С. 142— 154.

29. Яковлев Г. Н. Лекции по математическому анализу. Ч. 1. — Москва : Физ-матлит, 2004.

Работы соискателя, результаты которых выносятся на защиту

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

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

3. Sliusarev V. Modal logics of almost-sure validities in some classes of Euclidean

and transitive frames // Combinatorics and number theory. — 2025. — T. 14, № 1. — C. 49—64.