МПЗиО_8_17_ДескриптЛогики (1185827)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

ПРЕДСТАВЛЕНИЕЗНАНИЙ:ДЕСКРИПТИВНЫЕЛОГИКИСОДЕРЖАНИЕ1. Логическая модель и дескриптивные(дескрипционные) логики2. Дескриптивная логика ALCКонцепты: синтаксис и семантика База знаний: TBox и ABox Задачи логического вывода в БЗ3. Расширения логики ALC4. Сравнение вывода в БЗ и БД5. Заключение, Домашнее задание2ИСТОКИДЕСКРИПТИВНЫХ ЛОГИКРазвитие логической модели, с учетом средств ПЗ, разработанных в рамках других моделей потребностей формального ПЗ(необходимо для построения онтологий)Логика ALC (Attributive Language with Complements),1991 г. – первая и одна из базовых дескриптивных логик(ДЛ), на основе которой строятся многие другиеНыне на базе разных ДЛ построены онтологиив самых различных предметных областях:химия, биология, медицина, биоинформатика и др.Реализованы программные системы – механизмырассуждений, вывода знаний (reasoners)3ОСОБЕННОСТИДЕСКРИПТИВНЫХ ЛОГИКОсобенности логической модели ПЗ: знания представляются как совокупность формул операции над знаниями – на базе логического выводаКлючевые понятия ДЛ: конце́пт и роль соответствуют: Концепт (понятие) – это множество, класс (объектов),одноместный предикат:Студент, Автомобиль Роль – это свойство, бинарное отношение, предикат:Учиться (кто, где), Родитель (кто, кого)Выражения языка – составные концепты строятсяиз атомарных концептов и атомарных ролей,при помощи набора конструкторовДЛ позволяют формулировать утверждения не толькоо классах, но также о конкретных объектах – индивидах(экземплярах классов)4КОНСТРУКТОРЫ КОНЦЕПТОВКаждая ДЛ: определенный набор конструкторовдля построения составных концептовСтандартные конструкторы: Пересечение (конъюнкция) концептов:С⊓BОбъединение (дизъюнкция) концептов:Дополнение (отрицание) концепта:¬CОграничение на значения роликвантором всеобщности: R.CЭкзистенциальное ограничение(ограничение квантором существования):  R.Cгде C и В – концепты, а R – рольC⊔BКонкретная ДЛ характеризуется синтаксическимиправилами для построения составных концептов5ALC : СИНТАКСИС КОНЦЕПТОВЭлементы формул-концептов:– множество символов (имен) атомарных концептов– множество символов (имен) атомарных ролей(эти множества не пустые, конечные)– кванторы, служебные символы (точки, скобки)Синтаксические правила для концептов: Всякий атомарный концепт А является концептом Выражения ⊤ и ⊥ являются концептами (истина и ложь) Если C есть концепт, то его дополнение ¬ C – концепт Если C и В – концепты, то С ⊓ B иC⊔B(пересечение и объединение) являются концептами Если C – концепт, а R – атомарная роль, то выражения R.C и  R.C являются концептамиНикакие другие выражения не являются концептами6ALC : СЕМАНТИКА, ПРИМЕРЫИнтерпретация I состоит из непустой области Dи функции, интерпретирующей атомарныеконцепты и роли, а также составные концептыПримеры: Атомарные концепты Animal, Cat, Dog, Human,Male, Female, Student ; Роли has и hasChild(«естественная» интерпретация)Student ⊓ Female – множество студенток hasChild .

Male – все особи, чьи дети мужского полаHuman ⊓  hasChild . ¬ Student – люди, все детикоторых не являются студентамиMale ⊓  has . ((Cat ⊔ Dog) ⊓ ¬ Female) – мужчины …? Если пара (x, z) объектов-индивидов принадлежитотношению-роли R , т.е. верно x R z , то говорят, чтоиндивид z является R-последователем индивида x7ALC : СЕМАНТИКА КОНЦЕПТОВИнтерпретация I на области D(формальная семантика) Каждому атомарному концепту С ставитсяв соответствие подмножество из области DКаждой атомарной роли – бинарное отношение в DВыражение ⊤ интерпретируется как вся область DВыражение ⊥ – как пустое множество Далее индукция по построению концепта (рекурсивно):Дополнение ¬ C интерпретируется как D CПересечение С ⊓ В и объединение С ⊔ В концептов –как пересечение и объединение соответствующихмножеств, т.е.

C  В и C  В8СЕМАНТИКА КВАНТОРНЫХОГРАНИЧЕНИЙВыражение  R.C интерпретируется какмножество тех объектов-индивидов, у которых всеR-последователи принадлежат интерпретацииконцепта C.Формально:(R.C )  {e  D | d  D : (e, d )  R  d  C}Выражение  R.C интерпретируется как множествотех объектов индивидов, у которых имеетсяR-последователь, принадлежащий интерпретацииконцепта C.Формально:(R.C )  {e  D | d  D : (e, d )  R  d  C} В частности: R.⊤ ≡ ⊤и R.⊥ ≡ ⊥9ALC И ЛОГИКА ПРЕДИКАТОВЛогику ALC (и многие ДЛ) можно рассматривать какфрагменты логики предикатов при естественномпереводе концептов в предикатные формулы Для атомарных концептов C и атомарных ролей Rвводятся соответственно одноместные C(x) идвухместные R(x, y) предикатные символы Дополнение, пересечение и объединение концептовпереходит в булевы связки: ¬ , ∧ , ∨Выражение  R.C переходит в  y (R (x,y) → C(y) )Выражение  R.C переходит в  y (R(x,y) ∧ C(y) )(переменная y – новая, а C – перевод соответств.

концепта) Составной концепт – формула с одной своб. переменной,например, дляHuman ⊓  hasChild . ¬ Studentформула Human(x) ∧ ( y (hasChild(x,y)  ¬ Student (y) )10СВЯЗЬ ALC с ЛОГИКОЙ L2Перевод в предикаты согласуется семантикой ДЛ,т.е. при любой I , если атомарные концепты и ролиинтерпретированы так же, как и соответствующие импредикаты, то и любой составной концепт интерпретируетсятем же самым множеством, что и соответствующая емупредикатная формулаНе всякая формула логики предикатов является переводомкакого-либо концепта; например, формула  x Р(x)При переводе могут получиться лишь формулы, в которыхквантор навешивается на второй аргумент предикатаALC погружена в логику L2 предикатов с двумяпеременными, которая является разрешимойВажно: перевод позволяет переносить результаты оразрешимости, вычислительной сложности и т.

п. изобласти логики предикатов в область ДЛ11КОМПОНЕНТЫ ALC и БЗЗнания записываются в виде аксиом,все множество аксиом разбивается на: TBox (terminological box) — набор утвержденийобщего вида — терминология, общие знания опонятиях (концептах) и их взаимосвязях (ролях),интенсиональные знания ABox (assertional box) — набор утвержденийчастного вида, знания об объектах-индивидах, ихсвойствах и связях с другими объектами,экстенсиональные знанияПервые более стабильны и постоянны, тогда каквторые более подвержены модификациямБаза знаний= TВox + ABox12КОМПОНЕНТА TBoxТерминологические аксиомы: Вложенность концептов: выражение вида С ⊑ B Эквивалентность концептов: выражение С  Bгде С и B – произвольные концепты,а ⊑ – символ вложенности (subsumption), на основевложенности строится иерархия концептовВозможны также аксиомы (в расширениях ALC): Вложенность ролей: R ⊑ SЭквивалентность ролей: R  Sгде R и S – произвольные роли. Терминология – конечный набор терминологическихаксиом перечисленных видов Семантика терминологии определяется естественнымобразом13СЕМАНТИКА ТЕРМИНОЛОГИИПусть дана интерпретация I Аксиома C ⊑ B истинна в интерпретации I , еслиС  B , при этом I называется моделью этой аксиомы Аксиома С  B истинна в I , если С = B (множества равны) Концепт С выполним, если существует интерпретация I,в которой множество С ≠  (I называется моделью С)Для заданной терминологии T : Терминология является выполнимой в интерпретации I ,если I является моделью всех входящих в нее аксиом(I является моделью терминологии) Концепт С выполним в терминологии T, если существуетмодель этой терминологии, в которой множество С ≠ Важно: рассмотрение терминологий не выводит нас за рамкилогики предикатов и логики L214БЗ: ТЕРМИНОЛОГИЧЕСКИЕ ЗАДАЧИЗадачи логического анализа и вывода новыхзнаний для терминологической компоненты БЗ: Выполнимость атомарных концептов относительнотерминологии (если этого нет, то ошибка ПЗ) Проверка (аксиом) вложенности концептов Совместимость аксиом терминологии: проверка того, чтотерминология вообще имеет хотя бы одну модель Вывод новых вложений для составных концептов Классификация терминологии, т.е.

построение иерархии(таксономии) концептов – частично упорядоч. множествавсех атомарных концептов относительно вложения Обнаружение эквивалентных концептов Проверка ацикличности терминологии В логиках, содержащих ALC, проблема вложенностиконцептов сводится к выполнимости концепта15АЦИКЛИЧЕСКИЕ ТЕРМИНОЛОГИИАксиомы вида С  B можно считать определениями:Woman  Human ⊓ FemaleMother  Woman ⊓ hasChild.⊤Ацикличность – разумное требование:смысл новых, производных концептов, стоящих в левыхчастях равенств-определений, однозначным образомопределяется через смысл базовых концептов, входящихв правую часть и не встречающихся в левых частяхПример нарушения ацикличности: Mother  Parent ⊓ WomanParent  Mother ⊔ FatherВследствие нарушения возможны несколькоинтерпретаций этих концептов: Mother – множество матерей, Parent – множество родителей Mother – множество всех женщин, Parent – объединениемножеств отцов и женщин Mother – пустое множество, Parent – множество отцов16КОМПОНЕНТА ABoxСодержит утверждения-факты.Вводится множество имён индивидов: a, b, c, …Два вида утверждений об индивидах: утверждение о принадлежности индивида aконцепту C записывается как C(a) или a: C утверждение о связи двух индивидов a и bролью R записывается какR(a,b) или (a,b): R или a R bСистема фактов Abox – конечный набор такихутвержденийПримеры:Ann: Female ⊓ StudentAnn has RexRex: Dog ⊓ ∀hasChild.⊥17СЕМАНТИКА ABoxРасширение интерпретации I : каждому имени aиндивида сопоставлен некоторый элемент из области D Утверждение-факт C(a) или R(a,b) выполняется винтерпретации I , если имеет место соответственноaC или (a, b)  R,при этом I называется моделью этого факта ABox является выполнимым в интерпретации I , если в нейвыполняются все факты набора (т.е.

I - модель ABox) ABox называется выполнимым в терминологии T, еслисуществует модель ABox, являющаяся одновременномоделью терминологии (т.е. общая модель БЗ) Индивид a является экземпляром концепта C в БЗ, еслив любой модели БЗ имеет место aCОбычно рассматриваются интерпретации, удовлетворяющиесоглашению об уникальности имён (unique name assumption):разным именам индивидов сопоставленыразличные элементы D (инъективное отображение)18ЗАДАЧИ по БЗ с ABoxЛогические и алгоритмические задачи: Выполнимость базы знаний: имеет ли заданнаяпара (TBox, ABox) хотя бы одну модель? Принадлежность объекта-индивида заданному концепту БЗ Извлечение экземпляров: найти все экземпляры заданногоконцепта относительно заданной БЗ Классификация индивида: поиск для него наиболее узкого,т.е.

наименьшего (по вложению) атомарного концепта Ответ на запрос к БЗ: выдать все наборы индивидов,удовлетворяющие заданным ограничениям на факты В настоящее время изучены т.н. конъюнктивные запросык БЗ ДЛ (а также их дизъюнкции), которые похожи нааналогичные запросы из области БД Для запросов более общего вида задача быстро приобретаетвысокую вычислительную сложностьили даже становится неразрешимой19ЛОГИКА ALC : ХАРАКТЕРИСТИКАСтрого говоря, ALC – это не одна логика,а семейство дескриптивных логик, где каждаялогика задается конкретным набором атомарныхконцептов и ролей, а также индивидов (сигнатурой)Сигнатура логики – конечные непустые множества– атомарных концептовCN = {C1, C2,… Cn }– атомарных ролейRN = {R1, R2,… Rm }– индивидных объектовIN = {I1, I2,… Ik }Свойства логики ALC : Разрешимость: наличие алгоритма установлениявыполнимости концепта, совместимости БЗ(следует из вложимости в логику L2) Вычислительная сложность: полиномиальнаяВ дескрипт.

Характеристики

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций