?
Современная модальная логика: между математикой и информатикой
С. 265-305.
Шехтман В. Б., Шапировский И. Б.
Модальная логика возникла в древности для формализации понятий возможного и необходимого.
Современная модальная логика стала одним из инструментов решения задач информатики ---
как теоретических, так и вполне прикладных.
Произошёл достаточно неожиданный переход из области абстрактных философских
категорий в актуальную и практически значимую современную дисциплину. Он был обусловлен тем, что модальная логика (как и логика в целом) приобрела развитый математический аппарат --- алгебраический, топологический, теоретико-модельный. В настоящей заметке мы хотим, избегая сложных технических деталей, познакомить читателя с некоторыми базовыми математическими понятиями
модальной логики.
Kikot S., Shapirovsky I., Золин Е. Е., , in : Advances in Modal Logic. Volume 10. : College Publications, 2014. P. 333-352.
Фильтрация является стандартным средством для установления финитной аппроксимируемости модальных логик. В работе изучаются логики и классы шкал, допускающие фильтрацию (фильтруемые), и указываются операции на них, сохраняющие фильтруемость. В частности, показано, что операции добавления обратного отношения и транзитивного замыкания отношения сохраняет фильтруемость. Используя данные результаты, установлено, что всякая регулярная грамматическая модальная логика (возможно с обратными модальностями) ...
Добавлено: 14 июня 2018 г.
Кудинов А. В., Шапировский И. Б., В кн. : Сборник статей конференции Информационные технологии и системы (ИТиС'09). : М. : ИППИ РАН, 2009. С. 411-415.
В работе рассматриваются модальные логики бинарных отношений, удовлетворяющих условиям вида $R^m\subseteq R^n$. Несмотря на то, что эти логики легко описываются и имеют весьма простую аксиоматику, вопрос о финитной аппроксимируемости таких логик открыт. Эта задача возникла в 60х годах прошлого века (для случая m=3, n=2), и до сих пор остаётся нерешённой. В работе доказывается финитная ...
Добавлено: 27 февраля 2013 г.
Рыбаков М. Н., Вестник Тверского государственного университета. Серия: Прикладная математика 2018 № 3 С. 81-94
Рассматривается вопрос о возможности эффективного описания ненормальных и квазинормальных предикатных модальных логик, определяемых семантически посредством классов шкал Крипке с выделенными мирами. Доказывается, что любая ненормальная или квазинормальная (в т. ч. нормальная) модальная предикатная логика, полная относительно некоторого первопорядково определимого класса шкал Крипке с выделенными мирами, погружается в классическую логику предикатов. Показано, как построить соответствующее погружение, ...
Добавлено: 6 октября 2019 г.
Кудинов А. В., В кн. : Сборник статей конференции Информационные технологии и системы (ИТиС'11). : М. : ИППИ РАН, 2011. С. 335-339.
Мы изучаем модальную логику с топологической модальностью и модальностью неравенства вещественной прямой и доказываем, что она финитно аппроксимируема и разрешима. ...
Добавлено: 27 февраля 2013 г.
Золин Е. Е., Logic Journal of the IGPL 2015 Vol. 23 No. 6 P. 861-880
Доказан локальный аналог теоремы Гольдблатта-Томасона о характеризации модально определимых классов шкал Крипке с выделенной точкой; результат также обобщен на случай шкал с несколькими выделенными точками. Дается сравнение результатов с подобными результатами для гибридной модальной логики; формулируются открытые вопросы. ...
Добавлено: 14 июня 2018 г.
Золин Е. Е., Journal of Logic and Computation 2017 Vol. 27 No. 5 P. 1399-1420
We extend the language of the modal logic K4 of transitive frames with two sorts of modalities. In addition to the usual possibility modality (which means that a formula holds in some successor of a given point), we consider graded modalities (a formula holds in at least n successors) and converse graded modalities (aformula holds ...
Добавлено: 14 июня 2018 г.
Шехтман В. Б., Успехи математических наук 2016 Т. 71 № 5 С. 185-186
Приводятся новые результаты о локальной табличности модальных и суперинтуиционистских логик высказываний. Кратко изложена техника бисимуляционных игр, применяемая для доказательства этих результатов. ...
Добавлено: 16 марта 2017 г.
Kikot S., Шапировский И., Золин Е. Е., , in : Advances in Modal Logic. Vol. 13.: College Publications, 2020. P. 369-388.
Добавлено: 2 декабря 2020 г.
Кудинов А. В., Шапировский И. Б., Известия РАН. Серия математическая 2017 Т. 81 № 3 С. 134-159
В работе доказана финитная аппроксимируемость и разрешимость семейства предтранзитивных модальных логик конечной высоты.
Построены специальные разбиения (фильтрации) предтранзитивных шкал конечной высоты, из чего следует финитная аппроксимируемость и разрешимость их модальных логик. ...
Добавлено: 4 сентября 2017 г.
Кудинов А. В., Шапировский И. Б., В кн. : Сборник статей конференции Информационные технологии и системы (ИТиС'11). : М. : ИППИ РАН, 2011. С. 353-356.
В работе рассматриваются нормальные одномодальные предтранзитивные логики, т.е. логики, в которых можно выразить транзитивную модальность. Вопрос финитной аппроксимируемости предтранзитивных логик остается нерешенным уже на протяжении продолжительного времени. Хорошо известно, что логика отношений эквивалентности S5 вкладывается в логику предпорядков S4. Мы обобщаем этот результат на случай произвольной предтранзитивной логики L: в L вкладывается логика Lsim -- ...
Добавлено: 27 февраля 2013 г.
Рыбаков М. Н., Вестник Тверского государственного университета. Серия: Прикладная математика 2018 № 4 С. 87-97
Исследуется вопрос о взаимосвязи между вычислительной сложностью проблемы разрешения модальной пропозициональной логики и сложностью контрмоделей для формул, которые ей не принадлежат. Известно, что для многих нормальных мономодальных пропозициональных логик разные исследователи применяли сходные конструкции для доказательства PSPACE-трудности проблемы разрешения логики и для обоснования нижних экспоненциальных оценок минимального числа элементов в шкалах Крипке, опровергающих формулы, не ...
Добавлено: 6 октября 2019 г.
Вялый М. Н., Рубцов А. А., Дискретный анализ и исследование операций 2012
Работа посвящена двум алгоритмическим задачам, связанным с анализом поведения конечного автомата при чтении сверхслова (бесконечной последовательности): достигает ли автомат принимающего состояния и достигает ли он принимающего состояния бесконечно часто. Первая задача возникает при анализе моделей обобщённого недетерминизма, а вторая – при анализе разрешимости монадических теорий второго порядка. Получены новые условия разрешимости для этих задач. Доказано, что всякая задача ...
Добавлено: 17 октября 2014 г.
Shkatov D., Рыбаков М. Н., , in : Conference of the South African Institute of Computer Scientists and Information Technologists 2020 (SAICSIT '20). : ACM, 2020. P. 58-65.
Доказаны аналоги теоремы Чёрча и теоремы Трахтенброта для логики квазиарных предикатов. ...
Добавлено: 20 июля 2020 г.
Хайтович Д. Г., / Cornell University. Series arXiv "math". 2021. No. 2110.
Добавлено: 7 декабря 2021 г.
Рыбаков М. Н., В кн. : Десятые Смирновские чтения: материалы Междунар. науч. конф., Москва, 15–17 июня 2017 г. : М. : Современные тетради, 2017. С. 41-43.
Рассматриваются предикатные модальные логики с одним одноместным предикатом. Показано, что соответствующие фрагменты подлогик таких логик как QS5, QGL или QGrz неразрешимы. ...
Добавлено: 7 октября 2019 г.
Хайтович Д. Г., В кн. : Двенадцатые Смирновские чтения: материалы Международной научной конференции, Москва, 24–26 июня 2021 г. : М. : Русское общество истории и философии науки, 2021. С. 145-148.
В литературе существует несколько эпистемических расширений stit-логики. Один из наиболее популярных вариантов -- kstit-логика Пэкета и Хорти -- предлагает ввести аппарат действий-токенов и действий-типов, а также установить ряд семантических ограничений на связь эпистемических и исторических отношений. В данной статье мы выведем несколько контринтуитивных теорем, доказуемых в kstit-логике, и предложим свой вариант эпистемического расширения, избегающего их. ...
Добавлено: 21 сентября 2021 г.
Беклемишев Л. Д., Успехи математических наук 2018 Т. 74 № 4 С. 3-52
Строго позитивные логики в последнее время привлекают внимание специалистов благодаря их сочетанию эффективности и приемлемой выразительности. Язык исчисления рефлексий RC состоит из импликаций между формулами, составленными из пропозициональных переменных и константы “истина” лишь с помощью связки конъюнкции и модальностей, интерпретируемых в арифметике Пеано как ограниченные равномерные схемы рефлексии. Мы расширяем язык RC дополнительным семейством модальностей, соответствующих операторам, которые сопоставляют данной арифметической теории T её ...
Добавлено: 2 октября 2018 г.
Славнов С. А., Moscow Mathematical Journal 2005 Vol. 5 No. 2 P. 477-492
Классический результат о топологической семантике модальных логик, принадлежащий МакКинси и Тарскому (и часто называемый теоремой Тарского), состоит в полноте логики S4 по отношению к интерпретациям в пространстве R^n
для любого n. В последнее время разные авторы рассматривали динамические топологические логики, которые интерпретируются в динамических пространствах (абстрактных динамических системах). Динамическое пространство – это топологическое пространство вместе с непрерывной функцией на нем. В работе Артёмова, Даворен и ...
Добавлено: 27 февраля 2013 г.
Захаров В. А., Винарский Е. М., В кн. : Материалы XIII Международного семинара "Дискретная математика и ее приложения" имени академика О.Б. Лупанова (Москва, МГУ, 17-22 июня 2019). : М. : Изд-во механико-математического факультета МГУ, 2019. С. 257-260.
Конечные автоматы Мили, представляющие собой простейшую математическую модель преобразования потоковых данных, широко используются во многих областях информатики. Но для некоторых приложений большое значение имеют не только значения обрабатываемых данных и порядок их следования, но также интервалы времени, которые отделяют события, присходящие по ходу вычисления автомата. Такие свойства уже не описывается явно средствами классической теории конечных ...
Добавлено: 17 октября 2019 г.
Дудаков С. М., Авхимович Н. В., Вестник Тверского государственного университета. Серия: Прикладная математика 2023 № 1 С. 24-35
В работе рассматриваются алгебраические системы, где в качестве носителя выступают конечные подмножества некоторой безатомной булевой алгебры. Для полученной системы мы вводим новое отношение для конечных подмножеств: считаем, что одно подмножество состоит в отношении с другим подмножеством в том и только том случае, когда все элементы одного подмножества меньше всех элементов другого. Мы демонстрируем, что теория ...
Добавлено: 12 ноября 2023 г.
Рыбаков М. Н., Агаджанян И. А., / arXiv. Серия 2211.14571 "Logic". 2022.
Доказывается PSPACE-трудность константных фрагментов всех логик, лежащих между K и wGrz ...
Добавлено: 5 декабря 2022 г.
Оноприенко А. А., Математический сборник 2022 Т. 213 № 7 С. 97-120
Рассматривается совместная логика задач и высказываний QHC, введенная С. А. Мелиховым. Строятся модели Крипке с отмеченными мирами этой логики, показывается корректность и полнота логики QHC относительно этого типа моделей. Показана консервативность логики QHC относительно интуиционистской модальной логики QH4, совпадающей с “lax logic” QLL+. Построены модели Крипке с отмеченными мирами логики QH4, доказана теорема о корректности и ...
Добавлено: 11 июля 2022 г.