?
Квантификация по пропозициональным формулам в вероятностной логике: вопросы разрешимости
Алгебра и логика. 2011. Т. 50. № 4. С. 533–546.
Язык для рассуждений о вероятности обобщается за счёт добавления в него кванторов по пропозициональным формулам. Далее рассматриваются соответствующие вопросы разрешимости. В частности, представленные результаты демонстрируют неразрешимость проблемы общезначимости для довольно слабого фрагмента нового языка. С другой стороны, устанавливается разрешимость ограниченной проблемы общезначимости для АЕ-предложений.
Язык:
русский
Сперанский С. О., Вестник Новосибирского государственного университета. Серия: Математика, механика, информатика 2011 Т. 11 № 4 С. 78–93
В настоящей статье изучаются вычислительные аспекты формального требования максимальной специфичности, накладываемого на правила в языке пропозициональной классической логики, когда над этим языком задана вычислимая рационально-значная вероятностная мера. Доказана неразрешимость ряда общих проблем по обнаружению максимально специфичных правил и вероятностных мер, для которых совокупность всех специфичных правил вычислима; установлена разрешимость множества максимально специфичных правил при неких ...
Добавлено: 27 декабря 2025 г.
Сперанский С. О., Алгебра и логика 2013 Т. 52 № 2 С. 236–254
Изучаются иерархии проблем общезначимости для префиксных фрагментов вероятностной логики с кванторами по пропозициональным формулам, обозначаемой QPL, и её вариантов. Доказывается: если подполе F вещественных чисел определимо в стандартной модели арифметики посредством формулы второго порядка, не содержащей кванторов по множествам, то проблема общезначимости над F-значными вероятностными структурами для $\Sigma_4$-QPL-предложений является $\Pi^1_1$-полной и, как следствие, соответствующая иерархия проблем общезначимости схлопывается. Более того, при ...
Добавлено: 27 декабря 2025 г.
Сперанский С. О., Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика) 2023 Т. 510 С. 8–12
Пусть $\mathsf{QPL}$ – предложенный в [Speranski 2017] двусортный вероятностный язык, который расширяет хорошо известный «полиномиальный» язык, описанный в [Fagin et al. 1990, раздел 6], посредством добавления кванторов по событиям. Мы показываем, что все безатомные пространства имеют одну и ту же $\mathsf{QPL}$-теорию и эта теория разрешима. Также мы вводим понятие элементарного инварианта для QPL и используем его для ...
Добавлено: 26 декабря 2025 г.
Дудаков С. М., Авхимович Н. В., Вестник Тверского государственного университета. Серия: Прикладная математика 2023 № 1 С. 24–35
В работе рассматриваются алгебраические системы, где в качестве носителя выступают конечные подмножества некоторой безатомной булевой алгебры. Для полученной системы мы вводим новое отношение для конечных подмножеств: считаем, что одно подмножество состоит в отношении с другим подмножеством в том и только том случае, когда все элементы одного подмножества меньше всех элементов другого. Мы демонстрируем, что теория ...
Добавлено: 12 ноября 2023 г.
Семенов А. Л., Сопрунов С. Ф., Чебышевский сборник 2021 Т. 22 № 1(77) С. 304–327
В статье представлены результаты и открытые проблемы, относящиеся к пространствам определимости (редуктам), а также источникам этой области, начиная с XIX века. Исследуются условия конечности и ограничения, в том числе глубина чередования кванторов и число аргументов. Описаны результаты, относящиеся к описанию решеток пространств определимости для числовых и других естественных структур. Методы исследования включают изучение групп автоморфизмов ...
Добавлено: 11 марта 2023 г.
Kikot S., Шапировский И., Золин Е. Е., , in: Advances in Modal LogicVol. 13.: College Publications, 2020. P. 369–388.
Добавлено: 2 декабря 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 г.
Рыбас А. Л., Kostogryzov A., Grigoriev L. и др., , in: Proceedings 2018 Global Smart Industry Conference (GloSIC).: Chelyabinsk: IEEE, 2018. P. 1–7.
Добавлено: 23 июня 2020 г.
Захаров В. А., Винарский Е. М., В кн.: Материалы XIII Международного семинара "Дискретная математика и ее приложения" имени академика О.Б. Лупанова (Москва, МГУ, 17-22 июня 2019).: М.: Изд-во механико-математического факультета МГУ, 2019. С. 257–260.
Конечные автоматы Мили, представляющие собой простейшую математическую модель преобразования потоковых данных, широко используются во многих областях информатики. Но для некоторых приложений большое значение имеют не только значения обрабатываемых данных и порядок их следования, но также интервалы времени, которые отделяют события, присходящие по ходу вычисления автомата. Такие свойства уже не описывается явно средствами классической теории конечных ...
Добавлено: 17 октября 2019 г.
Захаров В. А., Жайлауова Ш. Р., В кн.: Материалы XIII Международного семинара "Дискретная математика и ее приложения" имени академика О.Б. Лупанова (Москва, МГУ, 17-22 июня 2019).: М.: Изд-во механико-математического факультета МГУ, 2019. С. 272–274.
В данной статье мы продолжаем поиск и исследование новых классов недетерминированных автоматов-преобразователей с разрешимой проблемой эквивалентности. Цель исследования~--- провести как можно более точную и подробную демаркацию границы между разрешимыми и неразрешимыми случаями проблемы эквивалентности для рассматриваемой модели вычислений. Мы рассматриваем один класс недетерминированных автоматов, работающих над выходным алфавитом из одной буквы. Характерная особенность рассматриваемых автоматов-преобразователей ...
Добавлено: 17 октября 2019 г.
Рыбаков М. Н., В кн.: Десятые Смирновские чтения: материалы Междунар. науч. конф., Москва, 15–17 июня 2017 г.: М.: Современные тетради, 2017. С. 41–43.
Рассматриваются предикатные модальные логики с одним одноместным предикатом. Показано, что соответствующие фрагменты подлогик таких логик как QS5, QGL или QGrz неразрешимы. ...
Добавлено: 7 октября 2019 г.
Рыбаков М. Н., Логические исследования 2017 Т. 23 № 2 С. 60–75
Рассматриваются модальные предикатные логики в языке, содержащем только одноместные предикатные буквы. Показано, что любая логика, содержащаяся в QS5, QGLLin или QGrz.3 является алгоритмически неразрешимой в языке с одной одноместной предикатной буквой (как при наличии, так и при отсутствии в логике формулы Баркан). Также показано, что логики конечных шкал Крипке (как с расширяющимися, так и с ...
Добавлено: 7 октября 2019 г.
Рыбаков М. Н., Вестник Тверского государственного университета. Серия: Прикладная математика 2018 № 4 С. 87–97
Исследуется вопрос о взаимосвязи между вычислительной сложностью проблемы разрешения модальной пропозициональной логики и сложностью контрмоделей для формул, которые ей не принадлежат. Известно, что для многих нормальных мономодальных пропозициональных логик разные исследователи применяли сходные конструкции для доказательства PSPACE-трудности проблемы разрешения логики и для обоснования нижних экспоненциальных оценок минимального числа элементов в шкалах Крипке, опровергающих формулы, не ...
Добавлено: 6 октября 2019 г.
Шехтман В. Б., Шапировский И. Б., В кн.: Современная логика: основания, предмет и перспективы развития.: М.: ИД "Форум", 2018. С. 265–305.
Модальная логика возникла в древности для формализации понятий возможного и необходимого.
Современная модальная логика стала одним из инструментов решения задач информатики --как теоретических, так и вполне прикладных.
Произошёл достаточно неожиданный переход из области абстрактных философских
категорий в актуальную и практически значимую современную дисциплину. Он был обусловлен тем, что модальная логика (как и логика в целом) приобрела развитый математический аппарат --- алгебраический, топологический, ...
Добавлено: 21 сентября 2018 г.
Kikot S., Shapirovsky I., Золин Е. Е., , in: Advances in Modal Logic. Volume 10.: College Publications, 2014. P. 333–352.
Фильтрация является стандартным средством для установления финитной аппроксимируемости модальных логик. В работе изучаются логики и классы шкал, допускающие фильтрацию (фильтруемые), и указываются операции на них, сохраняющие фильтруемость. В частности, показано, что операции добавления обратного отношения и транзитивного замыкания отношения сохраняет фильтруемость. Используя данные результаты, установлено, что всякая регулярная грамматическая модальная логика (возможно с обратными модальностями) ...
Добавлено: 14 июня 2018 г.
Кудинов А. В., Шапировский И. Б., Известия РАН. Серия математическая 2017 Т. 81 № 3 С. 134–159
В работе доказана финитная аппроксимируемость и разрешимость семейства предтранзитивных модальных логик конечной высоты.
Построены специальные разбиения (фильтрации) предтранзитивных шкал конечной высоты, из чего следует финитная аппроксимируемость и разрешимость их модальных логик. ...
Добавлено: 4 сентября 2017 г.
Захаров В. А., Cybernetics and Systems Analysis 2010 № 4 С. 39–48
В статье показано, каким образом двухленточные автоматы можно применять для проверки эквивалентности последовательных программ. Семантика последовательных программ определяется на основе моделей динамической логики. В том случае, когда динамическая шкала ациклична (т.е. в программе нет взаимно обратимых операторов), она может быть описана двухленточным детерминированным автоматом. Тогда задача проверки эквивалентности программ, семантика операторов которых определяется динамическими ...
Добавлено: 30 сентября 2015 г.
Макеева Л. Б., В кн.: Проблемы викладання логiки та дисциплiн логичного циклу. V Мiжнародна науково-практична конференцiя. Материалы доповiдей и виступiв.: К.: Киевский национальный университет им. Тараса Шевченко, 2012. С. 107–109.
Дается описание курса по индуктивной и вероятностной логике, который читается студентам философского факультета НИУ ВШЭ. ...
Добавлено: 12 марта 2015 г.
Макеева Л. Б., M.: ., 2014.
The present manual is written on the basis of the course on inductive logic which is delivered in English to philosophy students of National Research University Higher School of Economics. The manual describes the main approaches to constructing inductive logic; it clarifies its key notions and rules, and it formulates its major problems. This introductory ...
Добавлено: 9 марта 2015 г.
Вялый М. Н., Рубцов А. А., Дискретный анализ и исследование операций 2012
Работа посвящена двум алгоритмическим задачам, связанным с анализом поведения конечного автомата при чтении сверхслова (бесконечной последовательности): достигает ли автомат принимающего состояния и достигает ли он принимающего состояния бесконечно часто. Первая задача возникает при анализе моделей обобщённого недетерминизма, а вторая – при анализе разрешимости монадических теорий второго порядка. Получены новые условия разрешимости для этих задач. Доказано, что всякая задача ...
Добавлено: 17 октября 2014 г.
Смольянина Е. А., Серебряков И. А., Вестник Нижегородского университета им. Н.И. Лобачевского. Серия: Филология (Российская Федерация) 2014
Статья посвящена проблемам изучения вероятностной логики в научном тексте ...
Добавлено: 20 апреля 2014 г.
Смольянина Е. А., Серебряков И. А., Вестник Нижегородского университета им. Н.И. Лобачевского. Серия: Филология 2015 № 1 С. 290–296
Статья посвящена новому взгляду на логические отношения, репрезентирующие научную мысль в научном тексте и его переводе. В работе обосновывается применение комплексного анализа логичности научного текста на основе формальной и вероятностной логики. ...
Добавлено: 18 апреля 2014 г.
Тулупьев А. Л., Сироткин А. В., Вестник Санкт-Петербургского университета. Серия 1. Математика. Механика. Астрономия 2012 № 3 С. 63–72
Обработка фрагментов знаний с вероятностной неопределенностью в интеллектуальных системах поддержки принятия решений основывается на трех видах локального логи- ко-вероятностного вывода: проверка и поддержание непротиворечивости, априорный и апостериорный вывод. В настоящей статье вычислительные формулы, на которые опираются перечисленные виды логико-вероятностного вывода, представлены на матрично-векторном языке, что сокращает, упрощает и делает более строгой последующую спецификацию алгоритмов вывода. ...
Добавлено: 25 марта 2014 г.