1.6.4. Фразы Хорна

В прямом методе вывод проводился исходя из свойств связок и из того, что предметная область описывалась через импликацию, конъюнкцию, дизъюнкцию и отрицание. Этот способ удобен для представления человеком – специалистом, потому что ему проще выражать свои знания через высказывания ЕСЛИ ТО . ("ЕСЛИ температура >39, слабость и покраснение, ТО необходимо принять лекарство, лечь в постель и пить большое количество воды." Робинсон предложил более удобную форму описания предметной области, позволяющий строить вывод с помощью ЭВМ.

Представим функцию импликации в виде минимальной ДНФ с помощью формулы;

A C  A v C

(A1&A2& &AM)B v C, Ей будет соответствовать формула (с учё-том правила де Моргана) A1 vA2 v vAM v B v C. Перенесём положительные литералы вперед и получим B v C v A1 vA2 v vAM. Такую формулу называют фразой Хорна, положительные литералы (B,C) называют альтернативными следствиями, негативные (A1,A2, ,AM )– необходимыми посылками.

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

Точный дизъюнкт выражает некоторое правило: негативные литеры соответствуют гипотезам (которые представлены высказываниями), а позитивные заключения.

Унитарный позитивный хорновский дизъюнкт представляет собой некоторый факт, т.е. заключение не зависящее от каких-либо гипотез.

Задача состоит в том, что надо проверить некоторую цель логически выведенную из множества фактов и правил.

Алгоритм построения резолюций для множества фраз Хорна упрощается.

Рассмотрим множество S фраз Хорна. Алгоритма построения резолюций:

При условии Ложь  S,

выбираем P и с, такие что:

P – унитарный позитивный дизъюнкт из S, C – дизъюнкт из S, содержащий P, вычисляем резольвенту r; заменяем множество S на (S/{C]{r}).

Таким образом, на каждом этапе одна фраза Хорна заменяется другой, и некоторый атом удаляется из одного дизъюнкта. Отсюда следует, что выполнение алгоритма всегда завершается, какая бы стратегия ни была принята при выборе P и с. Если N – число атомов, первоначально присутствующих в S (C учётом повторений), то процедура вычисления резольвенты будет выполняться N раз.

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

Показано, что любую предметную область можно представить в виде фраз Хорна. Для этого любую формулу в описании предметной области необходимо преобразовать в КНФ (конъюнктивную нормальную форму – конъюнкцию элементарных дизъюнкций) и далее каждую элементарную дизъюнкцию представить в виде фразы Хорна.

Пример. Пусть предметная область описана в виде {A v (B & D), B C, A v D }. Представим её в виде фраз Хорна.

A v (B & D)  (A v B) & (A v D). Этому высказыванию соответствует две фразы Хорна (A v B) и (A v D).

BC B v C .

A v D – является фразой Хорна.

Итак, имеем предметную область, описанную фразами Хорна: {A v B, A v D, B v C, A v D}