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

принадлежит( А, [В | 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) потерпит неудачу и получившаяся конкретизация будет отменена!

5.4. Трудности с отсечением и отрицанием

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

(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)

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

В наших примерах из предыдущего раздела мы видели, что удаление отсечений из программы может привести к изменению ее декларативного смысла. Но были также в такие случаи, когда отсечение на него не влияло. Использование отсечений последнего типа требует меньшей осторожности, и поэтому такие отсечения иногда называют 'зелеными отсечениями'. С точки зрения наглядности программы такие отсечения 'невинны' и их использование вполне приемлемо. При чтении программы их можно просто игнорировать.

Напротив, отсечения, влияющие на декларативный смысл, называются 'красными'. Красные отсечения — это такие отсечения, которые делают программу трудной для понимания, и их нужно применять с особой осторожностью.

Отсечение часто используется в комбинации со специальной целью fail. В частности, мы определили отрицание какой-либо цели (not), как ее неуспех. Определенное таким образом отрицание представляет собой просто особый (более ограниченный) вид отсечения. Из соображений ясности программ мы предпочтем пользоваться not вместо комбинации отсечение — неуспех (всюду, где возможно), поскольку отрицание является понятием более высокого уровня, чем отсечение — неуспех.

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

?- not человек( мэри).

система, возможно, ответит 'да'. Не следует понимать этот ответ как 'мэри не человек'. Что в действительности пролог-система хочет сказать своим 'да', так это то, что программе не хватает информации для доказательства утверждения 'Мэри — человек'. Это происходит потому, что при обработке цели not система не пытается доказать истинность этой цели впрямую. Вместо этого она пытается доказать противоположное утверждение, и если такое противоположное утверждение доказать не удается, система считает, что цель not — успешна. Такое рассуждение основано на так называемом предположении о замкнутости мира. В соответствии с этим постулатом мир замкнут в том смысле, что все в нем существующее либо указано в программе, либо может быть из нее выведено. И наоборот — если что-либо не содержится в программе (или не может быть из нее выведено), то оно не истинно и, следовательно, истинно его отрицание. Это обстоятельство