Назад | Содержание| Вперёд 5. 3. Отрицание как неуспех "Мэри люби...

Назад | Содержание| Вперёд

5. 3. Отрицание как неуспех

"Мэри любит всех животных, кроме змей". Каквыразить это на Прологе? Одну часть этогоутверждения выразить легко: "Мэри любитвсякого 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 приводитсясоответствующим образом измененная программа.

Упражнения

5. 4. Даны два списка Кандидатыи Исключенные, напишитепоследовательность целей (используя принадлежити not), которая, при помощи перебора,найдет все элементы списка Кандидаты,не входящие в список Исключенные.

Посмотреть ответ

5.5. Определите отношение,выполняющее вычитание множеств:

решение( [ ]).

решение( [X/Y |Остальные] ) :-

решение( Остальные),

принадлежит( Y, [1, 2, 3, 4, 5, 6, 7, 8] ),

not бьет( X/Y, Остальные).

бьет( X/Y, Остальные):-

принадлежит( X1/Y1, Остальные),

( Y1 = Y;

Y1 is Y + X1 - X;

Y1 is Y - X1 + X ).

принадлежит( А, [А | L]).

принадлежит( А, [В | L]) :-

принадлежит( А, L).

% Шаблон решения

шаблон( [1/Y1,2/Y2, 3/Y3, 4/Y4, 5/Y5, 6/Y6, 7/Y7, 8/Y8]).

Рис. 5. 3. Еще однапрограмма для решения задачи о восьми ферзях.

разность(Множ1, Множ2, Разность)

где все три множества представлены в видесписков. Например,

разность( [a, b, c, d], [b,d, e, f], [a, c] )

Посмотреть ответ

5. 6. Определите предикат

унифицируемые(Спис1, Терм, Спис2)

где Спис2 - список всех элементов Спис1,которые сопоставимы с Терм'ом, но неконкретизируются таким сопоставлением.Например:

?- унифицируемые([X, b, t( Y)], t( a), Спис).

Спис = [ X, t( Y)]

Заметьте, что и Х и Y должны остатьсянеконкретизированными, хотя сопоставление с t( a)вызывает их конкретизацию. Указание: используйтеnot ( Терм1 = Терм2). Если цель Терм1 =Терм2 будет успешна, то not( Терм1 = Tepм2)потерпит неудачу и получившаяся конкретизациябудет отменена!

Посмотреть ответ

Назад | Содержание| Вперёд

Оглавление