Неизвестно - Prolog

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

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

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

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

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

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

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

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

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

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

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

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

р :- а, b.

р :- с.

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

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

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

p :- а, !, b.

р :- с.

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

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

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

р :- с.

р :- а, !, b.

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

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

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