Отрицание как недостижение цели
Рассмотрим, каким образом может быть представлено на языке Prolog утверждение ''Мэри нравятся все животные, кроме змей". Одну часть этого утверждения можно представить легко: Мэри нравится любой X, если X — животное. На языке Prolog это можновыразить следующим образом:
likesl тагу, X}:- animal( X).
Но нам необходимо исключить змей. Такую задачу можно выполнить, используя другую формулировку, как показано ниже.
Если х - змея, то утверждение 'Мэри нравится X не является истинным. В противном случае, если X - животное, «о Мэри нравится X
Утверждение "нечто не является истинным" можно выразить на языке Prolog с использованием особой цели, fail, попытка достичь которой всегда оканчивается неудачей, вынуждая тем самым окончиться неудачей попытку достичь родительской цели. Приведеннуювыше формулировку можно перевести на язык Prolog с применением цели fa ilследующим образом:
likes! тагу, X) : -snake (. X) , !, fail.
likes! тагу, X) : -animal' X).
В этой программе первоеправило посвящено змеям: если X — змея, то оператор отсечения предотвращает перебор с возвратами (исключая темсамым второе правило), а цель fail вызывает неудачное завершение. Эти два предложения могут быть записаны более компактно в виде одного предложения: likes ; тсагу, X) :-snake i X) , !, fail
animal! X!.
Глава Б. Управление перебором с возвратами
Такую же идею можно использовать для определения отношения different < У.г Y)
которое принимает истинное значение, если X и Y являются различными. Но необходимо уточнить рассматриваемую задачу, поскольку слово "различный" можно трактовать несколькими способами, следующим образом:
• X и Y не являются буквально одинаковыми;
• X и Y не согласуются;
• значения арифметических выражений X и Y не равны.
В данном случае выберем вариант, при котором X и Y являются различными, если они не согласуются. Ключом к решению задачи по оформлению этого утверждения на языке Prolog является приведенное ниже рассуждение.
Если X и Y согласуются, аызоб отношения different (X, Y> оканчивается неудачей, в противном случае вызов отношения different! X, "£) завершается успешно.
Снова воспользуемся сочетанием оператора отсечения и цели fail следующим образом:
different; X, X) :- !, fail.
different; X, Y) .
Кроме того, эту программу можно также записать Б виде одного предложения:
different; X, Y) :-х = Y, !, fail
-rue.
Применяемая здесь цель true всегда достигается.
Эти примеры показывают, что было бы удобно иметь унарный предикат not, такой, -что вызов
not { Goal)
возвращал бы истинное значение, если цель Goal не является истинной. Определим отношение net, как показано ниже.
Если Goal достигается, то not I Goal) не достигается, в противном случае not I Goal! достигается.
Это определение может быть записано на языке Prolog следующим образом:
aotlP) :-
Р, !, fail
t Г L3£ .
В дальнейшем предполагается, что not — встроенная процедура Prolog, которая действует в соответствии с приведенным здесь определением. Предполагается также, что определен префиксный оператор hot. поэтому цель
not! snake(X))
может быть записана также как not snake ! X)
Некоторые реализации Prolog действительно поддерживают такую систему обозначений, Б ином случае мы можем всегда определить отношение not самостоятельно. Возможен также вариант, при котором not Goal записывается как \+Goal. Такое менее наглядное обозначение рекомендовано и в стандарте Prolog по следующей причине: отношение not, определенное как недостижение цели (как в данном случае), не полностью соответствует понятию отрицания в математической логике. А если это различие не учитывается в программе, то может стать причиной непредсказуемого поведения программы из-за того, что при использовании отношения net не соблюдаются меры предосторожности. Эта тема рассматривается ниже в данной главе.
130 Часть I. Язык Prolog
Тем не менее отношение not — полезное средство и может часто с успехом применяться вместо оператора отсечения. Рассматриваемые два примера могут быть переоформлены с применением оператора not следующим образом:
likes ( шагу, X) :-
animal [ X), not snake ( X) .
different ( x, Y) :-
not ! X = Y) .
Безусловно, такие программы выглядят лучше по сравнению с первоначальными формулировками. Они являются более естественными и удобными для чтения.
Кроме того, с использованием not может быть переоформлена программа классификации игроков в теннис из предыдущего раздела, в результате чего эта программа будет в большей степени соответствовать первоначальному словесному определению трех категорий:
class ( X, fighter! : -beat< X, _], beat{_, x; .
class ( X, winner) :-beat( x, ) , not beat C_, X) ,
class; X, sportsman) :-
not beat ( X, _) .
В качестве еще одного примера использования оператора not снова рассмотрим программу 1 для решения задачи с восемью ферзями из предыдущей главы (см. листинг 4.2). В ней было определено отношение no_attack между одним ферзем и другими ферзями. Это отношение можно также сформулировать как отрицание отношения attack. Программа, откорректированная соответствующим образом, приведена в листинге 5.1.
Листинг 5.1.Еще одна программа решения задачи с восемью ферзями
solution С {]} .
solution; [X/Y Others]) :-
solution ( Others),
member ( Y, [ 1, 2, 3, 4, 5, 6,1, 8]> , % Обычный предикат member
not attacks! X/Y, Others).
attacks! x/Y, Others) :-memberC Xl/Yl, Others),
(Yl - Y;Yl is Y +Xl - X; Yl is Y -XI + X ) .
Упражнения
5.4. Предположим, что даны два списка, Candidates и RuledOut, в которых указаны кандидаты в депутаты и лица, выбывшие из предвыборной борьбы. Напишите последовательность целей (с использованием отношений member и not), которая позволяет с помощью перебора с возвратами найти все элементы в списке Candidates, не находящиеся в списке RuledOut.
5.5. Определите отношение для вычитания множеств
set_difference( Setl, Set2, EetDifference)
в котором все три множества представлены в виде списков, например:
set_difference| [a,b,c,d], [b,d,e,f] , [а, с] )
Глава 5. Управление перебором с возвратами
5.6. Определите предикат
unifiablef List!, Term, List2)
Здесь List2 представляет собой список всех элементов списка Listl, которые'-!
согласуются с термом Term, но не конкретизируются в результате этого согла-j
сования, например:
?- unifiable( [X, b, tm], t(a), List)
List - [X, t (Y) ]
Обратите внимание на то, что X и У должны оставаться неконкретизированны-
ми, несмотря на то, что согласование с термом t(a) может вызвать такую
конкретизацию. Подсказка: используйте правило not ( Terml = Тегт2);если
цель Terml = Terrr.2 достигается, то попытка достичь цели not ( Terml =
Term2) оканчивается неудачей и в результате этого конкретизация отменяется!