Отрицание как неуспех
"Мэри любит всех животных, кроме змей". Как выразить это на Прологе? Одну часть этого утверждения выразить легко: "Мэри любит всякого X, если Х - животное". На Прологе это записывается так:
любит( мэри, X) :- животное ( X).
Но нужно исключить змей. Это можно сделать, использовав другую формулировку:
Если Х - змея, то "Мэри любит X" - не есть
истина,
иначе, если Х - животное, то Мэри любит X.
Сказать на Прологе, что что-то не есть истина, можно при помощи специальной цели fail (неуспех), которая всегда терпит неудачу, заставляя потерпеть неудачу и ту цель, которая является ее родителем. Вышеуказанная формулировка, переведенная на Пролог с использованием fail, выглядит так:
любит( мэри, X) :-
змея( X), !, fail.
любит( Мэри, X) :-
животное ( X).
Здесь первое правило позаботится о змеях: если Х - змея, то отсечение предотвратит перебор (исключая таким образом второе правило из рассмотрения), а fail вызовет неуспех. Эти два предложения можно более компактно записать в виде одного:
любит( мэри, X) :-
змея( X), !, fail;
животное ( X).
Ту же идею можно использовать для определения отношения
различны( X, Y)
которое выполняется, если Х и Y не совпадают. При этом, однако, мы должны быть точными, потому что "различны" можно понимать по-разному:
- Х и Y не совпадают буквально;
- Х и Y не сопоставимы;
- значения арифметических выражений Х и Y не равны.
Давайте считать в данном случае, что Х и Y различны, если они не сопоставимы.
Вот способ выразить это на Прологе:
Если Х и Y сопоставимы, то
цель различны( X, Y) терпит неуспех
иначе цель различны( X, Y) успешна.
Мы снова используем сочетание отсечения и fail:
различны( X, X) :- !, fail.
различны( X, Y).
То же самое можно записать и в виде одного предложения:
различны( X, Y) :-
Х = Y, !, fail;
true.
Здесь true - цель, которая всегда успешна.
Эти примеры показывают, что полезно иметь унарный предикат "not" (не), такой, что
nоt( Цель)
истинна, если Цель не истинна. Определим теперь отношение not следующим образом:
Если Цель
успешна, то not( Цель) неуспешна,
иначе not( Цель)
успешна.
Это определение может быть записано на Прологе так:
not( Р) :-
P, !, fail;
true.
Начиная с этого момента мы будем предполагать, что not - это встроенная прологовская процедура, которая ведет себя так, как это только что было определено. Будем также предполагать, что оператор not определен как префиксный, так что цель
not( змея( X) )
можно записывать и как
not змея( X)
Многие версии Пролога поддерживают такую запись. Если же приходится иметь дело с версией, в которой нет встроенного оператора not, его всегда можно определить самим.
Следует заметить, что not, как он здесь определен с использованием неуспеха, не полностью соответствует отрицанию в математической логике. Эта разница может породить неожиданности в поведении программы, если оператором not пользоваться небрежно. Этот вопрос будет рассмотрен в данной главе позже.
Тем не менее not - полезное средство, и его часто можно с выгодой применять вместо отсечения. Наши два примера можно переписать с not:
любит( мэри, X) :-
животное ( X),
not змея( X).
различны( X, Y) :-
not( Х = Y).
Это, конечно, выглядит лучше, нежели наши прежние формулировки. Вид предложений стал более естественным, и программу стало легче читать.
Нашу программу теннисной классификации из предыдущего раздела можно переписать с использованием not так, чтобы ее вид был ближе к исходным определениям наших трех категорий:
класс( X, боец) :-
победил( X, _ ),
победил( _, X).
класс( X, победитель) :-
победил( X, _ ),
not победил( _, X).
класс( X, спортсмен) :-
not победил( X, _ ).
В качестве еще одного примера использования not
рассмотрим еще раз программу 1 для решения задачи о восьми ферзях из предыдущей главы (рис. 4.7).Мы определили там отношение небьет между некоторым ферзем и остальными ферзями. Это отношение можно определить также и как отрицание отношения "бьет". На рис. 5.3 приводится соответствующим образом измененная программа.
