Иван Братко - Программирование на языке Пролог для искусственного интеллекта

Давайте считать в данном случае, что X и Y различны, если они не сопоставимы. Вот способ выразить это на Прологе:

Если X и Y сопоставимы, то

цель различны( X, Y)терпит неуспех

иначе цель различны( X, Y)успешна.

Мы снова используем сочетание отсечения и fail:

различны( X, X) :- !, fail.

различны( X, Y).

То же самое можно записать и в виде одного предложения:

различны( X, Y) :-

X = Y, !, fail;

true.

Здесь true — цель, которая всегда успешна.

Эти примеры показывают, что полезно иметь унарный предикат "not" (не), такой, что

nоt( Цель)

истинна, если Цель не истинна. Определим теперь отношение not следующим образом:

Если Цельуспешна, то not( Цель)неуспешна,

иначе not( Цель)успешна.

Это определение может быть записано на Прологе так:

not( P) :-

P, !, fail;

true.

Начиная с этого момента мы будем предполагать, что not — это встроенная прологовская процедура, которая ведет себя так, как это только что было определено. Будем также предполагать, что оператор notопределен как префиксный, так что цель

not( змея( X) )

можно записывать и как

not змея( X)

Многие версии Пролога поддерживают такую запись. Если же приходится иметь дело с версией, в которой нет встроенного оператора not, его всегда можно определить самим.

Следует заметить, что not, как он здесь определен с использованием неуспеха, не полностью соответствует отрицанию в математической логике. Эта разница может породить неожиданности в поведении программы, если оператором notпользоваться небрежно. Этот вопрос будет рассмотрен в данной главе позже.

Тем не менее not — полезное средство, и его часто можно с выгодой применять вместо отсечения. Наши два примера можно переписать с not:

любит( мэри, X) :-

животное ( X),

not змея( X).

различны( X, Y) :-

not( X = Y).

Это, конечно, выглядит лучше, нежели наши прежние формулировки. Вид предложений стал более естественным, и программу стало легче читать.

Нашу программу теннисной классификации из предыдущего раздела можно переписать с использованием notтак, чтобы ее вид был ближе к исходным определениям наших трех категорий:

класс( X, боец) :-

победил( X, _ ),

победил( _, X).

класс( X, победитель) :-

победил( X, _ ),

not победил( _, X).

класс( X, спортсмен) :-

not победил( X, _ ).

В качестве еще одного примера использования notрассмотрим еще раз программу 1 для решения задачи о восьми ферзях из предыдущей главы (рис. 4.7). Мы определили там отношение небьетмежду некоторым ферзем и остальными ферзями. Это отношение можно определить также и как отрицание отношения "бьет". На рис. 5.3 приводится соответствующим образом измененная программа.

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

решение( [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. Еще одна программа для решения задачи о восьми ферзях.

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

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

разность( Множ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)]

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

Используя отсечение, мы кое-что выиграли, но не совсем даром. Преимущества и недостатки применения отсечения были показаны на примерах из предыдущих разделов. Давайте подытожим сначала преимущества:

(1) При помощи отсечения часто можно повысить эффективность программы. Идея состоит в том, чтобы прямо сказать пролог-системе: не пробуй остальные альтернативы, так как они все равно обречены на неудачу.

(2) Применяя отсечение, можно описать взаимоисключающие правила, поэтому есть возможность запрограммировать утверждение:

если условие P, то решение Q,

иначе решение R

Выразительность языка при этом повышается.

Ограничения на использование отсечения проистекают из того, что есть опасность потерять такое важное для нас соответствие между декларативным и процедурным смыслами программы. Если в программе нет отсечений, то мы можем менять местами порядок предложений и целей, что повлияет только на ее эффективность, но не на декларативный смысл. Если же отсечения в ней присутствуют, то изменение порядка предложений может повлиять на ее декларативный смысл. Это значит, что программа с измененным порядком, возможно, будет давать результаты, отличные от результатов исходной программы. Вот пример, демонстрирующий этот факт:

p :- а, b.

p :- с.

Декларативный смысл программы: p истинно тогда и только тогда, когда истинны одновременно и а, и b или истинно с. Это можно записать в виде такой логической формулы:

p <===> (а & b) U с

Можно поменять порядок этих двух предложений, но декларативный смысл останется прежним. Введем теперь отсечение

p :- а, !, b.

p :- с.

Декларативный смысл станет теперь таким:

p <===> (а & b) U ( ~а & с)

Если предложения поменять местами

p :- с.

p :- а, !, b.

декларативный смысл станет таким:

p <===> с U ( а & b)

Важным моментом здесь является то, что при использовании отсечения требуется уделять больше внимания процедурным аспектам. К несчастью, эта дополнительная трудность повышает вероятность ошибок программирования.