Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Bratko_Ivan_Programmirovanie_na_yazyke_Prolog_d...doc
Скачиваний:
14
Добавлен:
01.07.2025
Размер:
1 Мб
Скачать
☆

Упражнения

5.1.  Пусть есть программа:

p( 1).

p( 2) :- !.

p( 3).

Напишите все ответы пролог-системы на следующие вопросы:

(a) ?- p( X).

(b) ?- p( X), p(Y).

(c) ?- p( X), !, p(Y).

5.2.  Следующие отношения распределяют числа на три класса - положительные, нуль и отрицательные:

класс( Число, положительные) :- Число > 0.

класс( 0, нуль).

класс( Число, отрицательные) :- Число < 0.

Сделайте эту процедуру более эффективной при помощи отсечений.

5.3.  Определите процедуру

разбить( Числа, Положительные, Отрицательные)

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

разбить( [3, -1, 0, 5, -2], [3, 0, 5], [-1, -2] )

Предложите две версии: одну с отсечением, другую — без.

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

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

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

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

 Если X — змея, то "Мэри любит X" — не есть истина,

 иначе, если X — животное, то Мэри любит X.

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

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

 змея( X),  !,  fail.

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

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

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

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

 змея( X), !, fail;

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

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

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

которое выполняется, если X и Y не совпадают. При этом, однако, мы должны быть точными, потому что "различны" можно понимать по-разному:

• X и Y не совпадают буквально;

• X и Y не сопоставимы;

• значения арифметических выражений X и Y не равны.

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

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]