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

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

"Мэри любит всех животных, кроме змей". Как выразить это на Прологе? Одну часть этого утверждения выразить легко: "Мэри любит всякого X, если Х - животное". На Прологе это записывается так:

        любит( мэри, X) :- животное ( X).

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

        Если Х - змея, то "Мэри любит X" - не есть
              истина,
        иначе, если Х - животное, то Мэри любит X
.

Сказать на Прологе, что что-то не есть истина, можно при помощи специальной цели fail (неуспех), которая всегда терпит неудачу, заставляя потерпеть неудачу и ту цель, которая является ее родителем. Вышеуказанная формулировка, переведенная на Пролог с использованием fail, выглядит так:

        любит( мэри, X) :-
                змея( X),  !,  fail.

        любит( Мэри, X) :-
                животное ( X).

Здесь первое правило позаботится о змеях: если Х - змея, то отсечение предотвратит перебор (исключая таким образом второе правило из рассмотрения), а fail вызовет неуспех. Эти два предложения можно более компактно записать в виде одного:

        любит( мэри, X) :-
                змея( X),  !,  fail;
                животное ( X).

Ту же идею можно использовать для определения отношения

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

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


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