Правила вывода, используемые в логических моделях

В различных логических системах используются разнообразные правила вывода. Приведем два наиболее распространенных из них.

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

2. Правило заключения (латинское название Modus Ponens – положительный модус) состоит в следующем:

Если a и a ® b являются истинными высказываниями-посылками, тогда и высказывание-заключение b также истинно. Записывается правило в виде дроби: .

Пример. Пусть имеются следующие истинные высказывания:

1. Если самолет проверен и заправлен, то он готов к вылету.

2. Если самолет готов к вылету и дано разрешение на взлет, то он либо взлетел, либо находится на взлетной полосе.

3. Если самолет взлетел, то он выполняет рейс.

4. Самолет ЯК-42 проверен и заправлен.

5. Самолет ТУ-134 проверен.

6. Самолет ИЛ-62 заправлен.

7. Самолету ЯК-42 дано разрешение на взлет.

8. Самолет ЯК-42 не находится на взлетной полосе.

Требуется определить, какой из самолетов в данный момент времени выполняет рейс.

Проанализируем данные высказывания. Высказывания 1, 2, 3 являются сложными и построены с использованием логических связок ® (импликация), Ù (И), Ø (НЕ). Во всех элементарных высказываниях, из которых построены предложения 1, 2, 3, субъектом является понятие «самолет», предикатами выступают сказуемые, описывающие свойства всех объектов, принадлежащих классу «самолет». Высказывания 4-8 являются фактами, истинными на момент времени T. Они являются элементарными высказываниями, описывающими свойства конкретных объектов предметной области.

Для формального описания задачи введем следующие одноместные предикаты:

ПРОВЕРЕН (X) – самолет X проверен;

ЗАПРАВЛЕН (X) – самолет X заправлен;

ГОТОВ (X) – самолет X готов к вылету;

ДАНО_РАЗР (X) – самолету X дано разрешение на взлет;

ВЗЛЕТЕЛ (X) – самолет X взлетел;

НАХ_ВЗП (X) – самолет X находится на взлетной полосе;

ВЫП_РЕЙС (X) – самолет X выполняет рейс.

Тогда исходное описание на языке логики предикатов будет иметь вид:

1. " C (ПРОВЕРЕН (C) Ù ЗАПРАВЛЕН (C) ® ГОТОВ (C))

2. " C (ГОТОВ (C) Ù ДАНО_РАЗР (C) ÙØ НАХ_ВЗП (C) ® ВЗЛЕТЕЛ(C))

3. " C (ГОТОВ (C) Ù ДАНО_РАЗР (C) ÙØ ВЗЛЕТЕЛ(Х)® НАХ_ВЗП (X))

4. " C (ВЗЛЕТЕЛ (X) ® ВЫП_РЕЙС (X))

5. ПРОВЕРЕН (ЯК-42)

6. ЗАПРАВЛЕН (ЯК-42)

7. ПРОВЕРЕН (ТУ-134)

8. ЗАПРАВЛЕН (ИЛ-62)

9. ДАНО_РАЗР (ЯК-42)

10. Ø НАХ_ВЗП (ЯК-42)

Предложения 1–4 является высказываниями. Переменная X связана квантором общности ". В дальнейшем квантор писать не будем, т.к. он присутствует во всех предложениях.

Чтобы определить, какой из самолетов в момент времени T выполняет рейс, подготовим запрос вида: M => ВЫП_РЕЙС (Z),

где M – множество предложений 1–10.

Вывод запроса можно представить следующей последовательностью шагов:

1 шаг. Применив к предложению 1 подстановку X =ЯК-42, получим заключение

ПРОВЕРЕН (ЯК- 42) Ù ЗАПРАВЛЕН (ЯК- 42) ® ГОТОВ (ЯК- 42).

2 шаг. Первая посылка: объединив предложения 5 и 6, получим

ПРОВЕРЕН (ЯК- 42) Ù ЗАПРАВЛЕН (ЯК- 42).

Вторая посылка - заключение шага 1:

ПРОВЕРЕН (ЯК- 42) Ù ЗАПРАВЛЕН (ЯК- 42) ® ГОТОВ (ЯК- 42).

Применив правило Modus Ponens

для =ПРОВЕРЕН (ЯК- 42) Ù ЗАПРАВЛЕН (ЯК- 42) и =ГОТОВ(ЯК- 42), получим заключение ГОТОВ (ЯК- 42).

3 шаг. Первая посылка: объединив заключение шага 2 и предложения 9,10, получим:

ГОТОВ (ЯК-42) Ù ДАНО_РАЗР (ЯК- 42) Ù Ø НАХ_ВЗП (ЯК- 42).

Вторая посылка: применив к правилу2 подстановку X =ЯК- 42, получим:

ГОТОВ (ЯК- 42) Ù ДАНО_РАЗР (ЯК- 42) Ù ØНАХ_ВЗП (ЯК- 42) ® ВЗЛЕТЕЛ (ЯК- 42)

Применив правило Modus Ponens, получим заключение ВЗЛЕТЕЛ (ЯК- 42).

4 шаг. Первая посылка: заключение шага 3 – ВЗЛЕТЕЛ (ЯК- 42).

Вторая посылка: применив к правилу 4 подстановку X =ЯК- 42, получим:

ВЗЛЕТЕЛ (ЯК- 42) ® ВЫП_РЕЙС (ЯК- 42).

Применив правило Modus Ponens, получим заключение ВЫП_РЕЙС (ЯК- 42).

Таким образом, в момент времени T рейс выполняет самолет ЯК-42. Остальные подстановки, например X =ИЛ-62, приводят к тупиковым ситуациям. Логический вывод выполнялся в прямом направлении, при этом в процессе вывода трижды использовалось правило заключения

Лекция 4. Принцип резолюций

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

В основе принципа резолюций лежит тавтология, получившая название «правило резолюций»:

(X Ú A) Ù (Y Ú ØA) ® (X Ú Y)

Докажем эту тавтологию с помощью тождеств булевой алгебры:

Ø ((X Ú A) Ù (Y Ú ØA)) Ú X Ú Y = (Ø X Ù Ø A) Ú (Ø Y Ù A) Ú X Ú Y =

= (X Ú (Ø X Ù Ø A)) Ú (Y Ú (Ø Y Ù A)) = ((X Ú Ø X) Ù (X Ú Ø A)) Ú ((Y Ú Ø Y) Ù

Ú (Y Ú A)) = (X Ú Ø A) Ú (Y Ú A) = X Ú Y Ú A Ú ØA = X Ú Y Ú 1 = 1 (True)

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

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

Пусть имеются 2 предложения: P ₁ Ú P ₂ Ú _… Ú P_n и Ø P ₁ Ú Q ₂ Ú _… Ú Q_m.

Здесь литерал Ø P ₁ – отрицание литерала P ₁. Из этих двух предложений можно вывести новое предложение – резольвенту. Резольвентой является дизъюнкция этих предложений с исключенной парой P ₁ и Ø P ₁:

P ₂ Ú _… Ú P_n Ú Q ₂ Ú _… Ú Q_m.

Принцип резолюций применяется к конъюнкции дизъюнктов. Следовательно, доказываемую теорему надо представить в виде конъюнкции дизъюнктов.

Теорема G ® H равносильна Ø G Ú H. Доказать истинность Ø G Ú H означает доказать ложность её отрицания Ø(Ø G Ú H) = G Ù Ø H. Таким образом, исходная теорема (вернее, ее отрицание) представлена в виде конъюнкции дизъюнктов и требуется доказать ложность этой конъюнкции. Первый дизъюнкт в этой конъюнкции – это посылка теоремы (G); второй дизъюнкт – отрицание заключения теоремы (H).

Следовательно, для доказательства теоремы с помощью принципа резолю-

ций надо посылки теоремы представить в виде дизъюнктов и построить отрицание выводимого заключения.

Рассмотрим доказательство теоремы с помощью принципа резолюций.

Пусть надо доказать, что если истинны формулы P ® R, P Ú Q, Q ® S, то истинна также формула R Ú S. Для этого выполним следующие шаги.

1. Приведем посылки к дизъюнктивной форме: Ø P Ú R, P Ú Q, Ø Q Ú S.

2. Построим отрицание выводимого заключения: Ø(R Ú S) = Ø R Ù Ø S.

Таким образом, отрицание исходной теоремы представляется в виде следующей конъюнкции: Ø(P Ú R) Ù (P Ú Q) Ù (Ø Q Ú S) Ù Ø R Ù Ø S. Надо доказать ложность этой формулы.

3. Применим правило резолюций:

(Ø P Ú R) Ù Ø R ® Ø P;

(P Ú Q) Ù Ø R ® Q;

(Ø Q Ú S) Ù Ø S. ® Ø Q;

Q ÚØ Q = False (противоречие или “пустой дизъюнкт»).

Резольвенту, получаемую на основании двух дополняющих друг друга литералов, например Q иØ Q, называют пустым предложением или пустой резольвентой и обозначают символом.

Итак, предположив ложность выводимого заключения, получено противоречие, следовательно, выводимое заключение является истинным, т.е. R Ú S выводимо из исходных посылок.

Доказательство с использованием принципа резолюций является доказательством путем опровержения.

Рассмотрено применение правила резолюций для случая конкретных предложений, которые являются дизъюнкцией конкретных литералов. Литерал является конкретным, если он не содержит никакой переменной.

Чтобы обобщить это правило на случай предложений, содержащих переменные, рассмотрим процесс унификации предложений. Унификация – это подстановка, которая делает термы одинаковыми.

Пусть имеем 2 предложения Ø F (X) Ú G (X) и F (f (Y)). Если первое предложение заменить на Ø F (f (Y)) Ú G (f (Y)), то принцип резолюций для этих предло-

жений реализуется таким образом: после исключения литералов Ø F (f (Y)) и

F (f (Y)) получаем резольвенту G (f (Y)).

Общий алгоритм опровержения с помощью резолюций имеет следующий вид:

Чтобы доказать G ® H

1. Построить С – множество предложений, полученных путем преобразования формул множества G.

2. Добавить к множеству С предложения, полученные из Ø H.

3. Пока пустое предложение не появится в С, выполнить:

3.1) начало: выбрать 2 различных предложения в С.

3.2) если они имеют резольвенты, то найти одну резольвенту и добавить ее к множеству С.

конец.

Покажем применение метода резолюций к рассмотренному выше примеру.

Запишем исходные утверждения в виде дизъюнктов:

1. Ø ПРОВЕРЕН (C ₁) Ú ØЗАПРАВЛЕН (C ₁) Ú ГОТОВ (C ₁)

2. ØГОТОВ (C ₂) Ú ØДАНО_РАЗР (C ₂) Ú НАХ_ВЗП (C ₂) Ú ВЗЛЕТЕЛ(C ₂)

3. ØГОТОВ (C ₃) Ú ØДАНО_РАЗР (C ₃) Ú ВЗЛЕТЕЛ(Х ₃) Ú НАХ_ВЗП (X ₃)

4. ØВЗЛЕТЕЛ (X ₄) Ú ВЫП_РЕЙС (X ₄)

5. ПРОВЕРЕН (ЯК-42)

6. ЗАПРАВЛЕН (ЯК-42)

7. ПРОВЕРЕН (ТУ-134)

8. ЗАПРАВЛЕН (ИЛ-62)

9. ДАНО_РАЗР (ЯК-42)

10. Ø НАХ_ВЗП (ЯК-42)

Запрос, ложность которого надо доказать: Ø ВЫП_РЕЙС (Z).

Доказательство запроса методом резолюций приведено в таблице 3.1.

В результате доказательства получен пустой дизъюнкт, следовательно, цель допускается. Композиция подстановок Z = X ₄ = X ₂ = X ₁ = ЯК-42 на наш запрос дает ответ Z = ЯК-42. Любая другая подстановка, например, X ₁=ТУ– 134, приводит в тупик.

Таблица 3.1.

Запрос	Правило	Подстановка
Ø ВЫП_РЕЙС (Z)		Z = X 4
ØВЗЛЕТЕЛ (X 4)		X 4 = X 2
ØГОТОВ (C 2) Ú ØДАНО_РАЗР (C 2) Ú НАХ_ВЗП (C 2)		X 2 = X 1
Ø ПРОВЕРЕН (C 1) Ú ØЗАПРАВЛЕН (C 1) Ú ØДАНО_РАЗР (C 1) Ú НАХ_ВЗП (C 1)		X1 = ЯК-42
Ø ЗАПРАВЛЕН (ЯК-42) Ú ØДАНО_РАЗР (ЯК-42) Ú НАХ_ВЗП (ЯК-42)
ØДАНО_РАЗР (ЯК-42) Ú НАХ_ВЗП (ЯК-42)
НАХ_ВЗП (ЯК-42)

Лекция 5. Семантические сети

Сетевые модели представления знаний в отличие от логических предоставляют более широкие возможности для описания сложных структур, которыми характеризуются знания. Это достигается выделением и включением в модель в явной форме всех отношений, образующих информационную структуру, с описанием их семантики. Основой этих моделей является сеть, вершины которой отождествляются с некоторыми понятиями, а дуги – с отношениями между понятиями. При этом вершины могут иметь собственную внутреннюю структуру. Широко используются сетевые модели двух типов: семантические сети и фреймы.

Семантическая сеть – это ориентированный граф с помеченными вершинами и дугами. Вершинам ставятся в соответствие конкретные объекты, а дугам

– семантически отношения между ними. Метки вершин представляют собой некоторые имена, в качестве которых могут выступать слова естественного языка. Метки дуг обозначают элементы множества отношений.

Рассмотрим более строгое определение семантической сети.

Пусть заданы конечные множества символов А ={ А ₁, А ₂, …, А_r }, называемых атрибутами, и конечное множество R ={ R ₁, R ₂, …, R_m } отношений.

Схемой или интенсионалом отношения R_i называют набор пар

INT (R_i) = {…,[ A_j, DOM (A_j)], …}, (4.1)

где R_i – имя отношения, DOM (A_j) – домен A_j, т. е. множество значений атрибута A_j отношения R_i.

Объединение всех доменов называется базовым множеством модели или множеством объектов, на которых задаются отношения R_i.

Экстенсионалом отношения R_i называют множество фактов

EXT (R_i)={ F ₁,…, F_p },

где F_k (k = 1, …, p) – факт отношения R_i.

Факт задается совокупностью пар «атрибут – значение», называемых атрибутными парами. Под фактом понимают конкретизацию определенного отношения между указанными объектами. В графической интерпретации факт – это подграф семантической сети, имеющий звездообразную структуру. Корень подграфа – вершина предикатного типа, помеченная уникальной меткой, включающей имя соответствующего отношения. Из вершины факта выходят ребра, помеченные именами атрибутов данного факта, ведущие в вершины базового множества, которые являются значениями этих атрибутов.

Рассмотрим пример, иллюстрирующий введенные определения. Пусть заданы базовое множество модели (множество объектов) – совокупность целых чисел {0, 1, 2}; множество отношений R, включающее 2 отношения: «меньше» и «сумма» (обозначим их соответственно «<» и «+»).

Интенсионал этих отношений в соответсвии с (4.1) запишется следующим образом:

INT (+) = { [1-е слагаемое, (0, 1, 2)], [2-е слагаемое, (0, 1, 2)], [сумма, (0, 1, 2)]};

INT (<) = {[меньше, (0, 1)],[больше, (1, 2)]}.

Экстенсионалы этих отношений записываются в виде фактов, которые сведем в таблицы:

Метка факта	Отношение «меньше»
меньше	больше
F7
F8
F9

Метка факта	Отношение «сумма»
1-е слагаемое	2-е слагаемое	сумма
F1
F2
F3
F4
F5
F6

Экстенсиональная семантическая сеть описывает конкретные объекты и отношения предметной области, т.е. её текущее состояние. Интенсиональная семантическая сеть описывает общую структуру предметной области на основе абстрактных объектов и отношений, т.е. обобщенных представителей некоторых классов объектов и отношений.

В семантической сети используют 3 основных типа объектов: концепты (понятия), события и свойства.

Концепты (понятия) представляют собой сведения об абстрактных или физических объектах предметной области.

События – это действия, которые могут внести изменения в предметную область. Результатом события является некоторое новое состояние предметной области.

Свойства используются для уточнения понятий, событий или других свойств. Применительно к понятиям свойства описывают их особенности или характеристики – цвет, размеры, качество; применительно к событиям свойства определяют продолжительность, место, время и т.д.

Многообразие семантических отношений условно делят на 4 класса: лингвистические, теоретико-множественные, логические, квантифицированные.

Лингвистические отношения. Наиболее употребительными лингвистическими отношениями являются падежные, к которым относятся следующие: агент – отношение между событием и тем, кто или что его вызывает; объект – отношение между событием и тем, над чем производится действие; условие – отношение, указывающее логическую зависимость между событиями; инструмент – объект, с помощью которого совершается событие; место – место совершения события.

Рассмотрим семантическую сеть с падежными отношениями, представляющую знания, содержащиеся в предложении «Если станок закончил обработку, робот грузит кассету с деталями на робокар, который перевозит их на склад, где штабелер помещает кассету в ячейку». Выделим 5 фактов: станок закончил обработку, робот грузит, робокар перевозит, кассета содержит, штабелер размещает. Факты обозначим овалом, а связанные с ними понятия - прямоугольником. Дуги пометим наименованиями отношений, которые они выражают. Схема семантической сети показана на рис 4.1.

Рис. 4.1 Представление падежных отношений в семантической сети.

Другой тип лингвистических отношений – характеризация глаголов и атрибутивные отношения. К характеризации глаголов относится наклонение, время, род, число, залог. Атрибутивные отношения – это цвет, размер, форма, модификация и т.д. Например, фраза «Большие красные шары» с использованием атрибутивных отношений может быть представлена структурой, изображенной на рис. 4.2.

Теоретико-множественные отношения – это отношения «множество –подмножество» (isa), элемент множества (е, de), отношение «целое – часть»

Мужской

род

цвет число

Красный Шар Множественное

размер

Большой

Рис. 4.2 Схема, иллюстрирующая атрибутивные отношения.

(part of). Этот класс отношений используется для построения иерархических структур для представления обобщенной информации. В таких структурах все свойства классов автоматически присваиваются подклассам. Такое наследование свойств позволяет избежать дублирования информации в сети.

Рассмотрим предложение, представляющее факт "все собаки – животные". Это предложение можно представить в форме, показанной на рис. 4.3, а, использовав для этого две вершины "собака" и "животное" и дугу, показывающую отношение между ними. Если присвоить собаке некоторое имя, то сеть можно расширить (см. рис. 4.3, б). В этом случае, кроме двух представленных в сети фактов "Шарик – собака", "собака – животное", из нее, используя отношение isa, можно вывести факт "Шарик – животное", т.е. получить вывод, благодаря иерархии наследования. В сети можно представить и знания, касающиеся атрибутов объекта. Например, факт "все собаки имеют хвост" показан в сети на рис 4.3, в.

Рис. 4.3 Представление теоретико-множественных отношений в сети.

Логические отношения – операции, используемые в исчислении высказываний: конъюнкция, дизъюнкция, отрицание, импликация.

Пример сети, в которой закодирована дизъюнкция D = "или OLD. BLACK была построена компанией Форд или OLD. BLACK принадлежит Джону", представлена на рис. 4.4. Здесь метка e обозначает элемент класса. Соответственно,

метка de обозначает, что данный элемент отличен от всех других элементов, обозначения которых указаны другими e (или de) – дугами для данного класса.

Рис. 4.4 Представление дизъюнкции в семантической сети.

Квантифицированные отношения – это логические кванторы общности и существования. Логические кванторы применяются для представления знаний декларативного типа, например, при записи таких утверждений, как «Каждый станок требует профилактического ремонта» или «Существует робот А, который может обслуживать все станки группы В».

При функционировании системы представления знаний основным является информационно-поисковый режим. Запрос представляет собой набор фактов (ситуацию), при описании которых допускается использование переменных в позициях значений атрибутов, атрибутов и имен отношений. Запрос представляется графом, в котором вершины, соответствующие переменным, не определены. Поиск ответа заключается в решении задачи вложения графа запроса (или его подграфа) в семантическую сеть. Выделяют два типа запросов – на существование и на перечисление. Запрос на существование не содержит переменных и предусматривает ответ типа ДА, если вложение графа запроса в семантическую сеть удалось, и НЕТ – в противном случае. При обработке перечисляющего запроса происходит поиск (перечисление) всех соответствующих графу запроса подграфов в семантической сети, а также конкретизация переменных.

Пусть, например, имеется запрос «Оператор сообщил, что робокар что-то перевозит. Определить, что и куда перевозит робокар». Поиск ответа осуществляется в семантической сети, изображенной на рис. 4.1. Запрос представляется графом (рис. 4.5), в котором вершины X и Y требуют конкретизации. Очевидно, звездообразный подграф факта «перевозит» в графе запроса (на рис. выделен штриховой линией) может быть вложен в семантическую сеть при совмещении с вершиной «перевозит» на рис. 4.1. При этом будут конкретизированы вершины X и Y: X – кассета, Y – склад. Ответ будет выглядеть так: робокар перевозит кассету на склад. Этот пример иллюстрирует поиск ответа в семантической сети в упрощенной форме, т. к. здесь не рассматривается процесс интерпретации запроса, который первоначально выражается на специальном языке общения.

Семантические сети, как модель представления знаний, обладают большими выразительными возможностями. Недостатком является сложность организации процедуры логического вывода вследствие того, что база знаний в семантических сетях объединена с механизмом логического вывода.

Рис. 4.5 Граф запроса.

Лекция 6. Фреймы для представления знаний

Фреймы предложены в 1975 году Марвином Минским. Фрейм (рамка в переводе с англ.) - это единица представления знаний, запомненная в прошлом, детали которой могут быть изменены согласно текущей ситуации. Фрейм представляет собой структуру данных, с помощью которых можно, например, описать обстановку в комнате или место для проведения совещания. М.Минский предлагал эту модель для описания пространственных сцен. Однако с помощью фреймов можно описать ситуацию, сценарий, роль, структуру и т.д.

Итак, фрейм – это структура данных для представления стереотипных ситуаций. Фреймы соответствуют понятиям, отражающим объекты, явления, характеристики предметной области. Фрейм можно рассматривать как семантический блок или модуль модели представления знаний. Модель представления знаний строится в виде сети фреймов, т.е. системы определенным образом взаимосвязанных фреймов.

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

Таким образом, фреймы представляют собой декларативно-процедурные структуры, т.е. совокупность описаний и (в некоторых случаях) связанных с

ними процедур, доступ к которым выполняется прямо из фрейма.

Существует большое число определений и моделей фреймов. В наиболее общем виде фреймом называют структуру представления знаний следующего вида:

{ n, (v ₁, g ₁, p ₁), (v ₂, g ₂, p ₂), …, (v _k, g _k, p _k) },

где n – имя фрейма; v_i – имя слота; g_i – значение слота; p_i – процедура.

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

Дата добавления: 2014-01-04