Отрицание как недостижение цели

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