Исследование логических проблем информатикиНИР

Источник финансирования НИР

Этапы НИР

# Сроки Название
1 1 января 2014 г.-31 декабря 2014 г. Исследование логических проблем информатики
Результаты этапа: Получен критерий С-представимости конъюнктивных запросов над дескрипционной логикой ALC. Данный критерий позволяет за полиномиальное время распознать, можно ли данный запрос к базе знаний представить в виде дизъюнкции простейших, и если да, то построить это так называемое С-представление запроса. С-представление запроса, будучи построенным один раз, позволяет гораздо быстрее получать ответы на данный запрос над любой базой знаний (проблема ответа на запросы в общем случае экспоненциально сложнее, чем на запрос, для которого найдено С-представление). Установлено, что расширение любой модальной логики, обладающей свойством фильтруемости, модальностями, соответствующими обратному отношению, объединению, композиции отношений, транзитивному замыканию отношений, приводит к логике, также обладающей свойством фильтруемости. Как следствие, получены новые результаты о фильтруемости, а следовательно, и финитной аппроксимости и разрешимости, различных модальных логик. В частности, получено значительно более простое доказательство фильтруемости, а следовательно, и разрешимости любой регулярной грамматической модальной логики, а также пропозициональной динамической логики. Разработаны явные конструкции фильтрации для важнейших грамматических модальных логик - правосторонних, левосторонних, двусторонних с совпадающим нетерминалом, циклических, и их аналогов в языке с обратными модальностями. Описана топологическая семантика для интуиционистской эпистемической логики, формализующей модальность знания средствами интуиционистской логики высказываний.
2 1 января 2015 г.-31 декабря 2015 г. Исследование логических проблем информатики
Результаты этапа: Интуиционистская эпистемическая логика IEL (С. Артемов, Т. Протопопеску, 2014) описывает модальность знания в контексте интуиционистской логики. В отличие от классической логики знаний здесь справедлив принцип ко-рефлексии, утверждающий, что из интуиционистской верности факта можно извлечь справедливость утверждения об его известности. Обратное не имеет места, т.е утверждение о знании факта оказывается менее информативным, чем утверждение о его истинности. Ранее в процессе исполнения проекта была предложена топологическая семантика для логики IEL, доказаны соответствующие теоремы о корректности и полноте, установлена разрешимость логики IEL. В 2015 г. получены аналогичные результаты для расширения IEL+ логики IEL принципом идемпотентности знания. Исходная формулировка логики IEL представляет собой исчисление гильбертовского типа. Найдены эквивалентные секвенциальные формулировки. Они задают ту же логику, но различаются поведением процедуры поиска вывода снизу-вверх. Описана семантика некоторых логик доказательств для двух взаимодействующих дедуктивных систем разной дедуктивной силы. Доказаны теоремы о полноте.

Прикрепленные к НИР результаты

Для прикрепления результата сначала выберете тип результата (статьи, книги, ...). После чего введите несколько символов в поле поиска прикрепляемого результата, затем выберете один из предложенных и нажмите кнопку "Добавить".