Предикаты хорошо согласуются аппаратом правил. Пусть имеется правило если X отец y и y отец z, то X дед z. В предикатном представлении это правило имеет вид
Отец (X, Y) отец (Y, Z) дед(X, Z),
т.е. фактически записана операция импликации. Используя ее свойства из табл. 2.2, получим
.
В силу этого свойства очень часто четвертым методом описания знаний называют [12] логический метод, подразумевая метод предикатов первого порядка. Обобщим и получим:
n
Ai G (3.2),
i = 1
где Ai - предпосылка (аксиома, данные, факты), G – цель, а выражение (3.2) – формула, предложение, теорема.
Таким образом, логика предикатов первого порядка хорошо согласовывается с методом продукций. Возможность интеграции методов описания знаний и логики вывода показана на рис. 3.1.
Система предикатов, основанная на предложениях, называется пропозициональной.
Выражение (3.2) может быть представлено в ином виде
n __
Ai G, (3.3)
i = 1
называемом фразой Хорна.
Процесс рассуждения для формул (3.2) – доказательство теоремы. В процессе доказательства возникает две ранее названные проблемы.
1. Проблема выводимости.
2. Проблема извлечения результата.
Для больших наборов правил (тысяча и более) необходимо иметь математический («компьютерный») путь решения этих проблем. Для его изложения уточним и введем ряд дополнительных понятий и определений.
Предикат
реализуется на конечном множестве U
наборов входных аргументов. Множество
U
называют универсумом,
любой из этих наборов – интерпретацией.
Поскольку результатом действия предиката
является 0 или 1, то интерпретации можно
разделить на два класса: W,
в котором
предикат W
истинен, и
- где предикат W
ложен.
Замечание:
вместо W
часто используется название самого
предиката. Пусть предикат имеет имя P.
Множество истинности обозначается как
P,
а вместо
используем
.
Предикат или его отрицание называют литералом.
В решении проблемы выводимости используются следующие понятия:
1. Если формула (3.2) справедлива на всех интерпретациях U, то A является общезначимой (тавтология)
2. Если формула (3.2) ложна на всех интерпретациях, то она невыполнима (противоречива).
3. Формула (3.2) необщезначима, если она не является общезначимой.
4. Формула (3.2) непротиворечива, если она не является противоречивой
Два предиката F и G эквивалентны (F G), если они совпадают на множестве истинности (ложности). Для выводимости формула (3.2) должна быть общезначима.
Доказательство этого положения простое. Если Ai – истинны, то используется формула (3.2), если Ai – ложны, то формула (3.3).
В решении проблемы выводимости первоначально использовали формулу (3.2). Однако в прикладных математических операциях выяснилось, что проще доказать ложность отрицания цели.
В этом случае вместо выражения (3.3) следует используют выражение вида:
n __
Ai G. (3.4)
i = 1
Оно
получается заменой в выражении (3.3)
G
на
и взятием отрицания от получившегося
выражения. В дальнейшем будем использовать
(3.4).
До сих пор не использовалось понятие «квантор». Квантор выступает как одна из разновидностей предиката.
Заметим, что квантор общности не накладывает ограничений на свойства предикатов, в то время как квантор существования имеет серьезные ограничения по области действия: логическая зависимость справедлива только на множестве. В связи с этим с кванторами надо обращаться аккуратно. Например, справедливо выражение
(X)(F(X)G(X)) = (X)F(X)(X)G(X). (3.5)
Если в (3.5) заменить конъюнкцию на дизъюнкцию , то справедливость теряется.
Аналогично справедливо
(X)(F(X)G(X)) = (X)F(X)(X)G(X) (3.6)
При замене в (3.6) дизъюнкции на конъюнкцию на справедливость теряется.
Для кванторов справедливы законы де Моргана:
,
(3.7)
.(3.8)
Легко показать, что множества интерпретаций, где предикат истинен, для обеих частей выражения (3.7) совпадают.
Выражение
(3.8) доказывается на основе (3.7) заменой
F
на
и взятием отрицаний от левой и правой
частей
.
Для того чтобы оперировать квантором существования, используют процедуру перехода от квантора существования к квантору общности. Это процедура называется сколемизацией. Иллюстрируем его на примере.
(x)(y) P(x, y),
x={1, 2}элементы множества x,
y={1, 2}элементы множества y,
отсюда множество интерпретаций U={1,1; 1,2; 2,1; 2,2}. Пусть предикат имеет значения P(1, 1) = 1; P(1, 2) = 0; P(2, 1) = 0 P(2, 2) = 1. Введем функцию
и получим
(x)(y)P(x, f(x)),
где f(x) – функция Сколема, в рамках которой квантор существования ведет себя как квантор общности. Очень часто квантор общности опускают при написании предикатов. Приведем более общий пример сколемизации.
(x)(y)(z)(u)(w) P(x, y, z, u, w) = (x)(y)(z)(u)(w) P(x, f(x), z, u, g(x, z, u)).
Заметим, что в предикатах используется предваренная (префиксная) нормальная форма: кванторы находятся слева от системы предикатов, которая называется матрицей.
Все дальнейшие теоретические выкладки проводятся для так называемой фразовой формы, представляющей собой конъюнктивную нормальную форму, где знаки конъюнкций связывают дизъюнкты. Такая форма носит название стандартной предикатной формы. Иногда в ней знаки конъюнкции опускаются и выписываются только дизъюнкты.
Переход от исходной предикатной формы к стандартной предикатной форме осуществляется поэтапно:
1) исключение импликаций по формуле эквивалентности;
2) замена отрицаний с помощью формул де Моргана;
3) замена квантора существования на квантор общности с использованием сколемизации;
4) перенесение дизъюнкций внутрь скобок дизъюнктов и приведение формулы к клаузальной (от clause - предложение) форме;
5) вынесение кванторов общности перед предикатами и их опусканием.
Рассмотрим пример.
___________________
__
(x){P(x) {(y)[P(y) P[f(x,y)]]{(y)[Q(x, y) P(y)]}}}.
1. Заменим импликации
___________________
__ __ __
(x){P(x) {(y)[P(y) P[f(x,y)]]{(y)[Q(x, y) P(y)]}}}.
2. Заменим отрицание и y на w
__ __ __
(x){P(x) {(y)[P(y) P[f(x,y)]]{(w)[Q(x, w) P(w)]}}}.
3. Введем функцию Сколема w = g(x) и получим
__ __ __
(x){P(x) {(y)[P(y) P[f(x,y)]]{[Q(x, g(x)) P(g(x))]}}}.
4. Построим префиксную форму и опустим значки кванторов общности
__ __ __
{P(x) {[P(y) P[f(x,y)]]{[Q(x, g(x)) P(g(x))]}}}.