Рассмотрим, каким образом может быть представлено на языке 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) оканчивается неудачей и в результате этого конкретизация отменяется!