?
Финитная аппроксимируемость обобщенно транзитивных симметричных модальных логик.
С. 411–415.
Кудинов А. В., Шапировский И. Б.
В работе рассматриваются модальные логики бинарных отношений, удовлетворяющих условиям вида $R^m\subseteq R^n$. Несмотря на то, что эти логики легко описываются и имеют весьма простую аксиоматику, вопрос о финитной аппроксимируемости таких логик открыт. Эта задача возникла в 60х годах прошлого века (для случая m=3, n=2), и до сих пор остаётся нерешённой. В работе доказывается финитная аппроксимируемость для частного случая - при m=n+1} и симметричном отношении.
Язык:
русский
В книге
М.: ИППИ РАН, 2009.
Сперанский С. О., Вестник Новосибирского государственного университета. Серия: Математика, механика, информатика 2011 Т. 11 № 4 С. 78–93
В настоящей статье изучаются вычислительные аспекты формального требования максимальной специфичности, накладываемого на правила в языке пропозициональной классической логики, когда над этим языком задана вычислимая рационально-значная вероятностная мера. Доказана неразрешимость ряда общих проблем по обнаружению максимально специфичных правил и вероятностных мер, для которых совокупность всех специфичных правил вычислима; установлена разрешимость множества максимально специфичных правил при неких ...
Добавлено: 27 декабря 2025 г.
Сперанский С. О., Алгебра и логика 2011 Т. 50 № 4 С. 533–546
Язык для рассуждений о вероятности обобщается за счёт добавления в него кванторов по пропозициональным формулам. Далее рассматриваются соответствующие вопросы разрешимости. В частности, представленные результаты демонстрируют неразрешимость проблемы общезначимости для довольно слабого фрагмента нового языка. С другой стороны, устанавливается разрешимость ограниченной проблемы общезначимости для АЕ-предложений. ...
Добавлено: 27 декабря 2025 г.
Грефенштейн А. В., Сперанский С. О., Математический сборник 2024 Т. 215 № 3 С. 37–69
Разрабатывается кванторная версия пропозициональной модальной логики BK из статьи С. П. Одинцова и Х. Вансинга, в основе которой лежит (немодальная) система Белнапа–Данна; мы будем обозначать эту версию через QBK. Сначала с помощью метода канонических моделей будет доказано, что QBK — как и некоторые важные её расширения — сильно полна относительно подходящей семантики возможных миров. Затем мы ...
Добавлено: 26 декабря 2025 г.
Кудинов А. В., Мясников К. М., Математика и теоретические компьютерные науки 2025 Т. 3 № 2 С. 58–84
В работе доказывается, что для слабо транзитивных логик с универсальной модальностью, проверку выполнимости формулы для которых можно произвести в PSPACE}, добавление аксиомы связности не увеличивает сложность этой проверки, причем строится явный алгоритм, который решает эту задачу. ...
Добавлено: 14 октября 2025 г.
Рыбаков М. Н., Щербаков М. И., В кн.: Четырнадцатые Смирновские чтения по логике: материалы Междунар. науч. конф., Москва, 19-21 июня 2025 г.: М.: Издатель Александр Воробьев, 2025. С. 46–49.
Логики с аксиомой конвергентности: сложность при малом числе переменных в языке ...
Добавлено: 21 июня 2025 г.
Кудинов А. В., Рыбаков М. Н., В кн.: Четырнадцатые Смирновские чтения по логике: материалы Междунар. науч. конф., Москва, 19-21 июня 2025 г.: М.: Издатель Александр Воробьев, 2025. С. 36–39.
Показано, что каждая модальная логика, содержащая классическую логику высказываний и содержащаяся в слабой логике Гжегорчика, имеет NP-трудную проблему выполнимости для константного фрагмента. В частности, константные фрагменты ненормальных модальных логик E, EM, EN и EMN являются coNP-полными. ...
Добавлено: 21 июня 2025 г.
Дудаков С. М., Авхимович Н. В., Вестник Тверского государственного университета. Серия: Прикладная математика 2023 № 1 С. 24–35
В работе рассматриваются алгебраические системы, где в качестве носителя выступают конечные подмножества некоторой безатомной булевой алгебры. Для полученной системы мы вводим новое отношение для конечных подмножеств: считаем, что одно подмножество состоит в отношении с другим подмножеством в том и только том случае, когда все элементы одного подмножества меньше всех элементов другого. Мы демонстрируем, что теория ...
Добавлено: 12 ноября 2023 г.
Оноприенко А. А., Алгебра и логика 2022 Т. 61 № 6 С. 720–741
Рассматривается совместная логика задач и высказываний QHC, введённая С. А. Мелиховым, а также интуиционистская модальная логика QH4. Рассмотрено погружение этих логик в классическую логику предикатов первого порядка. Установлен аналог теоремы Лёвенгейма-Сколема о счётной элементарной подмодели для логик QHC и QH4. ...
Добавлено: 4 ноября 2023 г.
Семенов А. Л., Сопрунов С. Ф., Чебышевский сборник 2021 Т. 22 № 1(77) С. 304–327
В статье представлены результаты и открытые проблемы, относящиеся к пространствам определимости (редуктам), а также источникам этой области, начиная с XIX века. Исследуются условия конечности и ограничения, в том числе глубина чередования кванторов и число аргументов. Описаны результаты, относящиеся к описанию решеток пространств определимости для числовых и других естественных структур. Методы исследования включают изучение групп автоморфизмов ...
Добавлено: 11 марта 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 г.
Рыбаков М. Н., Александров К. И., Шкатов Д. П., / ArXiv. Серия arXiv:2112.03833 "arXiv:2112.03833". 2021.
В работе показано, что любое произведение нормальных модальных пропозициональных логик, содержащее логику T в качестве сомножителя, погружается в свой фрагмент от одной переменной. Приведённое доказательство является более простой версией аналогичного доказательства, которое готовится к публикации, для произведений и полупроизведений, содержащих в качестве сомножителя логику KTB рефлексивно-симметричных шкал Крипке. ...
Добавлено: 10 декабря 2021 г.
Шишов К. В., Логико-философские штудии 2018 Т. 16 № 1-2 С. 137–139
В работе [1] представляется алгебраическая структура QMV-алгебры, которая, опираясь на идеи и результаты [2], характеризуется в качестве обобщения для многозначных алгебр. В качестве множества-носителя этого класса структур выступает частично-упорядоченное множество всех эффектов, в действительном интервале [0,1], где под эффектом понима- ется ограниченный линейный оператор в гильбертовом пространстве. Используя метод, предложенный в [3], предполагается существование реляционной ...
Добавлено: 22 марта 2021 г.
Kikot S., Шапировский И., Золин Е. Е., , in: Advances in Modal LogicVol. 13.: College Publications, 2020. P. 369–388.
Добавлено: 2 декабря 2020 г.
Оноприенко А. А., Математический сборник 2020 Т. 211 № 5 С. 98–125
Рассматривается пропозициональный фрагмент HC объединенной логики задач и высказываний, введенной C. A. Мелиховым. Строятся модели типа Крипке для этой логики, доказывается полнота логики HC относительно таких моделей, а также свойство конечных моделей. Рассмотрены примеры применения моделей типа Крипке логики HC для решения некоторых вопросов (в частности, доказательство того, что HC является консервативным расширением логики H4). Также показано, что логика HC полна относительно шкал Крипке с проверяющими мирами, введенных С. Н. Артёмовым ...
Добавлено: 20 октября 2020 г.
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 г.
Цыгуров А. С., Философия. Журнал Высшей школы экономики 2017 Т. 1 № 3 С. 170–174
В рецензии рассматриваются как содержательные, так и методологические инновации в кантоведении, предложенные Н. Стэнгом в его книге "Kant's Modal Metaphysics". Анализируется актуальность и обоснованность применения аппарата современной логики к исследованию кантовского наследия. ...
Добавлено: 19 ноября 2019 г.
Захаров В. А., Винарский Е. М., В кн.: Материалы XIII Международного семинара "Дискретная математика и ее приложения" имени академика О.Б. Лупанова (Москва, МГУ, 17-22 июня 2019).: М.: Изд-во механико-математического факультета МГУ, 2019. С. 257–260.
Конечные автоматы Мили, представляющие собой простейшую математическую модель преобразования потоковых данных, широко используются во многих областях информатики. Но для некоторых приложений большое значение имеют не только значения обрабатываемых данных и порядок их следования, но также интервалы времени, которые отделяют события, присходящие по ходу вычисления автомата. Такие свойства уже не описывается явно средствами классической теории конечных ...
Добавлено: 17 октября 2019 г.