Кафедра математической логики и теории алгоритмов

Дескрипционная логика (спецкурс, Евгений Золин)

Интересные материалы:

Программы и задачи:

  • 2017–2018:

  • 2011–2012:
    • [ pdf ] Программа спецкурса (первый семестр)
    • [ pdf ] Программа спецкурса (второй семестр)
  • 2010–2011:
    • [ pdf ] Программа спецкурса (годовой экзамен)
    • [ pdf ] Список задач к экзамену (годовой экзамен)
  • 2009–2010:
    • [ pdf ] Программа спецкурса (первый семестр)
    • [ pdf ] Программа спецкурса (второй семестр)
    • [ pdf ] Список задач к экзамену (второй семестр)

Лекции:

В конспектах имеются неточности (например, с развёрткой, с экспоненциальными моделями),
в ближайшее время будут исправлены.

   0.  [ pdf ] Две семантики логики высказываний (вводная лекция)

  1. [ pdf ] Логика ALC:

    • синтаксис и семантика, выполнимые и эквивалентные концепты;
    • связь с логикой предикатов;
    • связь с модальной логикой.
  2. [ pdf ] Терминологии (TBox):

    • синтаксис и семантика;
    • выполнимость и эквивалентность концептов относительно терминологий (определение, сводимость друг к другу).
    • ациклические терминологии, их корректность и устранимость;
    • связь с глобальным отношением следования в модальной логике (недописано).
  3. [ pdf ] Системы фактов (ABox) и базы знаний:

    • синтаксис и семантика ABox, соглашение об уникальности имён, базы знаний;
    • основные алгоритмические проблемы в ДЛ, их сводимость друг к другу.
    • отличие баз знаний от баз данных: предположение об открытости мира в ДЛ.
  4. [ pdf ] Разрешимость логики ALC.

    • Табло-алгоритм для логики ALC без терминологий, его завершаемость, корректность, полнота;
    • разрешимость проблемы выполнимости концептов и ABox-ов в логике ALC;
    • табло-алгоритм для логики ALC с терминологиями, его завершаемость, корректность, полнота;
    • разрешимость проблемы выполнимости баз знаний в логике ALC.
  5. [ pdf ] Вычислительная сложность логики ALC:

    • проблема выполнимости концептов ALC лежит в классе PSpace;
    • лемма об экспоненциальных моделях;
    • булевы формулы с кванторами QBF, их PSpace-полнота;
    • логика ALC является PSpace-трудной;
    • лемма об экспоненциально глубоких моделях логики ALC с терминологиями;
    • логика ALC с терминологиями является ExpTime-трудной (недописано).
  6. [ pdf ] Расширения логики ALC численными ограничениями на роли, обратными ролями, номиналами:

    • синтаксис и семантика логики ALCOIQ ;
    • устранимость ABox в логике ALCO ;
    • устранимость TBox в логике ALCOI ;
    • понятие логики, полной относительно конечных / древовидных моделей;
    • логика ALCIF с терминологиями не является ПОКМ;
    • логика ALC с терминологиями является ПОКМ, ПОДМ, но не ПОДКМ.
  7. [ pdf ] Логики с аксиомами для ролей:

    • синтаксис и семантика RBox;
    • устранимость терминологий в логике SH.
    • понятие простой роли относительно RBox, определение логик SHQ и SHIQ.
    • неразрешимость логики SHN с неограниченным синтаксисом.
  8. [ pdf ] Запросы к базам знаний:

    • синтаксис и семантика запросов, ответ на запрос;
    • импликации между запросами (эквивалентные определения);
    • алгоритмические проблемы для запросов, их сводимость друг к другу;
    • неразрешимость проблемы ответа на запросы с неравенством.
  9. [ pdf ] Логики с операциями над ролями:

    • синтаксис и семантика операций над ролями;
    • выразимость операций друг через друга;
    • логика ALCIF(*) не является ПОКМ;
    • логика ALCF(o) не является ПОДМ;
    • в логике ALC(∪,*) устранимы терминологии;
    • логика ALC(∩) полна относительно деревьев с мультиребрами;
    • связь логики ALCreg с пропозициональной динамической логикой PDL (недописано).
    • неразрешимость некоторых логик с операциями над ролями.
  10. [ pdf ] Логика с равенством атрибутов:

    • синтаксис и семантика логики ALCf;
    • неразрешимость логики с равенством атрибутов и обратными ролями ALCIf.
  11. [ pdf ] Логика с многоместными отношениями:

    • синтаксис и семантика логики DLR ;
    • логика DLR является расширением логики ALCIQ ;
    • понятие реификации (способа выражения многоместных отношений через двуместные);
    • вложение терминологий DLR в терминологии ALCIQ , сохраняющее выполнимость:
      • перевод концептов и отношений логики DLR в концепты логики ALCIQ ;
      • аксиомы реификации и регулярные модели, лемма о регуляризации для терминологий;
      • теорема о реификации терминологий DLR ;
    • базы знаний в логике DLR  — синтаксис и семантика;
    • вложение баз знаний DLR в базы знаний ALCIQ , сохраняющее выполнимость:
      • перевод ABox-ов логики DLR  в ABox-ы логики ALCIQ ;
      • ABox реификации и регулярные модели, лемма о регуляризации для баз знаний;
      • теорема о реификации баз знаний DLR ;
    • расширение логики DLR  регулярными ролями — логика DLR reg (недописано);
    • вложение логики DLR reg в логику ALCIQ reg (недописано).
  12. [ pdf ] Логики с конкретными областями L(D):

    • понятие конкретной области;
    • синтаксис и семантика логики ALC(D);
    • понятие разрешимой конкретной области;
    • разрешимость логик с конкретными областями (обзор);
    • обобщенный конструктор концептов;
    • обобщенный конструктор ролей;
    • временная конкретная область Allen(Q) (недописано);
    • пространственная конкретная область RCC-8(R2) (недописано).
  13. [ pdf ] Свойство аддитивности логик.

  14. [ pdf ] Сведения из теории алгоритмов:

    • разрешимые проблемы, алгоритмическая сводимость проблем;
    • неразрешимая проблема домино;
    • классы сложности (детерминированные и недетерминированные);
    • понятие полиномиальной сводимости;
    • сложность важнейших логик.
  • [ pdf ] Список литературы.
Состав кафедры