1 Интеллектуальные системы Лекция 7. Логический вывод в логике первого порядка. Представление знаний Вахтин А. А.

2 Правила логического вывода для квантора Конкретизация высказывания с квантором всеобщности: Пример:

3 Правило логического вывода для квантора Для любых высказываний, переменной v и константного символа k, который не появляется где-либо в базе знаний, имеет место следующее: Пример:

4 1. Если некоторое высказывание следует из первоначальной базы знаний в логике первого порядка, то существует доказательство, которое включает лишь конечное подмножество этой пропозиционализированной базы знаний. 2. Вопрос о следствии для логики первого порядка является полу разрешимым; это означает, что существуют алгоритмы, которые позволяют найти доказательство для любого высказывания, которое следует из базы знаний, но нет таких алгоритмов, которые позволяли бы также определить, что не существует доказательства для каждого высказывания, которое не следует из базы знаний.

5 Обобщенное правило отделения Пусть имеются высказывания, если существует подстановка, такая, что то для всех i имеет место следующее: и q,

6 Унификация Пример:

7

8 Проблемы алгоритма прямого поиска 1. Поиск всех возможных унификаторов, таких, что предпосылка некоторого правила унифицируется с подходящим множеством фактов в базе знаний. 2. Повторная проверка каждого правила в каждой итерации для определения того, выполняются ли его предпосылки, даже если в базу знаний в каждой итерации вносится лишь очень немного дополнений. 3. Вырабатывается много фактов, которые не имеют отношения к текущей цели.

9 Согласование правил с известными фактами

10 Инкрементный прямой логический вывод каждый новый факт, выведенный в итерации t, должен быть получен по меньшей мере из одного нового факта, выведенного в итерации t-1.

11 Исключение нерелевантных фактов 1. Использование обратного логического вывода. 2. Ограничивается прямой логический вывод избранным подмножеством правил. 3. Перезаписывать множество правил с использованием информации из цели так, что в процессе прямого логического вывода рассматриваются только релевантные связывания переменных

12

13 Логическое программирование Логическое программирование – это технология, согласно которой системы должны конструироваться путем представления знаний на некотором формальном языке, а задачи решаться путем применения процессов логического вывода к этим знаниям. Уравнение Роберта Ковальского: Алгоритм = Логика + Управление

14 Усовершенствование логических программ 1. Вместо формирования списка всех возможных ответов для каждой подцели перед переходом к следующей подцели интерпретаторы Prolog вырабатывают один ответ и "дают обещание" выработать остальные после того, как будет полностью исследован текущий ответ.

15 Усовершенствование логических программ 2. После того как попытка продления пути поиска оканчивается неудачей, система Prolog возвращается к предыдущей точке выбора и только после этого получает возможность отменить связывания некоторых переменных.

16

17 Метод резолюции Теорема о полноте Любое высказывание, являющееся следствием заданных аксиом, имеет конечное доказательство. Теорема о неполноте Любая логическая система, которая включает принцип индукции, обязательно является неполной.

18 Коньюктивная нормальная форма 1. Устранение импликаций: 2. Перемещение связок внутрь выражений: 3. Стандартизация переменных: 4.Сколемизация:

19 Коньюктивная нормальная форма 5. Удаление кванторов всеобщности: 6. Распределение связки и :

20 Правило логического вывода с помощью резолюций где Пример: И

21

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

23 Категории и объекты Взаимодействие с миром происходит на уровне отдельных объектов, формирование рассуждений в основном происходит на уровне категорий

24 Категории и объекты Любой объект – элемент некоторой категории, например: Любая категория – подкласс другой категории, например: Все элементы категории имеют некоторые свойства, например: Элементы категории могут быть распознаны по некоторым свойствам, например: Вся категория в целом имеет некоторые свойства, например:

25 Физическая композиция 1. Часть целого (PartOf): PartOf(Bucharest, Romania) PartOf(Romania, EasternEurope) PartOf(EasternEurope, Europe) PartOf(Europe, Earth) Свойства PartOf: PartOf(х, х)

26 Физическая композиция 2. Свойства от собственных частей (PartPartition). 3. Совокупность (BunchOf): Свойство BunchOf: BunchOf ({x}) =x

27 Меры Length(L 1 ) = Inches(1.5) = Centimeters(3.81) Centimeters(2.54 х d) = Inches(d) Примеры: Diameter(Basketball12) = Inches(9.5) ListPrice(Basketball12) = $(19) d Days Duration(d) = Hours(24)

28 Объекты и вещество Объекты – исчисляемые существительные (муравьеды, ямы, теоремы) Вещество – неисчисляемые существительные (масло, вода, энергия)

29 События Happens(е, t) - событие е произошло во время t; Initiates(е, f, t) - возникновение события е во время t вызвало то, что флюентное высказывание f стало истинным; Terminates(w, f, t) - высказывание f перестало быть истинным; Clipped(f, t, t2) - высказывание f перестало быть истинным под влиянием некоторого события, происшедшего в какое-то время между t и t2;

30 Аксиома исчисления событий

31 Мыслимые объекты Belives – Убежден; Knows - Знает; Wants - Желает);

32

33