Лекции.Орг


Поиск:




Категории:

Астрономия
Биология
География
Другие языки
Интернет
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Механика
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Транспорт
Физика
Философия
Финансы
Химия
Экология
Экономика
Электроника

 

 

 

 


Отрицание как недостижение цели




Рассмотрим, каким образом может быть представлено на языке Prolog утвержде­ние ''Мэри нравятся все животные, кроме змей". Одну часть этого утверждения мож­но представить легко: Мэри нравится любой X, если X — животное. На языке Prolog это можно выразить следующим образом:

likesl тагу, X}:- animal (X).

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

Если х - змея, то утверждение 'Мэри нравится X не является истинным. В противном случае, если X - животное, «о Мэри нравится X

Утверждение "нечто не является истинным" можно выразить на языке Prolog с использованием особой цели, fail, попытка достичь которой всегда оканчивается неудачей, вынуждая тем самым окончиться неудачей попытку достичь родительской цели. Приведенную выше формулировку можно перевести на язык Prolog с примене­нием цели fa il следующим образом:

likes! тагу, X): -snake (. X),!, fail.

likes! тагу, X): -animal' X).

В этой программе первое правило посвящено змеям: если X — змея, то оператор отсечения предотвращает перебор с возвратами (исключая тем самым второе прави­ло), а цель fail вызывает неудачное завершение. Эти два предложения могут быть записаны более компактно в виде одного предложения: likes; тсагу, X):-snake i X),!, fail

animal! X!.


Глава Б. Управление перебором с возвратами



Такую же идею можно использовать для определения отношения different < У.г Y)

которое принимает истинное значение, если X и Y являются различными. Но необхо­димо уточнить рассматриваемую задачу, поскольку слово "различный" можно трак­товать несколькими способами, следующим образом:

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

• X и Y не согласуются;

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

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

Если X и Y согласуются, аызоб отношения different (X, Y> оканчивается неудачей, в противном случае вызов отношения different! X, "£) завершается успешно.

Снова воспользуемся сочетанием оператора отсечения и цели fail следующим об­разом:

different; X, X):-!, fail.

different; X, Y).

Кроме того, эту программу можно также записать Б виде одного предложения:

different; X, Y):-х = Y,!, fail

-rue.

Применяемая здесь цель true всегда достигается.

Эти примеры показывают, что было бы удобно иметь унарный предикат not, та­кой, -что вызов

not { Goal)

возвращал бы истинное значение, если цель Goal не является истинной. Определим отношение net, как показано ниже.

Если Goal достигается, то not I Goal) не достигается, в противном случае not I Goal! достигается.

Это определение может быть записано на языке Prolog следующим образом:

aotlP):-

Р,!, fail

t Г L3£.

В дальнейшем предполагается, что not — встроенная процедура Prolog, которая действует в соответствии с приведенным здесь определением. Предполагается также, что определен префиксный оператор hot. поэтому цель

not! snake(X) )

может быть записана также как not snake! X)

Некоторые реализации Prolog действительно поддерживают такую систему обо­значений, Б ином случае мы можем всегда определить отношение not самостоятель­но. Возможен также вариант, при котором not Goal записывается как \+Goal. Та­кое менее наглядное обозначение рекомендовано и в стандарте Prolog по следующей причине: отношение not, определенное как недостижение цели (как в данном слу­чае), не полностью соответствует понятию отрицания в математической логике. А ес­ли это различие не учитывается в программе, то может стать причиной непредска­зуемого поведения программы из-за того, что при использовании отношения net не соблюдаются меры предосторожности. Эта тема рассматривается ниже в данной главе.

130 Часть I. Язык Prolog


Тем не менее отношение not — полезное средство и может часто с успехом при­меняться вместо оператора отсечения. Рассматриваемые два примера могут быть пе­реоформлены с применением оператора not следующим образом:

likes (шагу, X):-

animal [ X), not snake (X).

different (x, Y):-

not! X = Y).

Безусловно, такие программы выглядят лучше по сравнению с первоначальными формулировками. Они являются более естественными и удобными для чтения.

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

class (X, fighter!: -beat< X, _], beat{_, x;.

class (X, winner):-beat(x,), not beat C_, X),

class; X, sportsman):-

not beat (X, _).

В качестве еще одного примера использования оператора not снова рассмотрим программу 1 для решения задачи с восемью ферзями из предыдущей главы (см. лис­тинг 4.2). В ней было определено отношение no_attack между одним ферзем и дру­гими ферзями. Это отношение можно также сформулировать как отрицание отноше­ния attack. Программа, откорректированная соответствующим образом, приведена в листинге 5.1.

Листинг 5.1. Еще одна программа решения задачи с восемью ферзями

solution С {]}.

solution; [X/Y Others]):-

solution (Others),

member (Y, [ 1, 2, 3, 4, 5, 6, 1, 8]>, % Обычный предикат member

not attacks! X/Y, Others).

attacks! x/Y, Others):-memberC Xl/Yl, Others),

( Yl - Y; Yl is Y + Xl - X; Yl is Y -XI + X).

Упражнения

5.4. Предположим, что даны два списка, Candidates и RuledOut, в которых ука­заны кандидаты в депутаты и лица, выбывшие из предвыборной борьбы. На­пишите последовательность целей (с использованием отношений member и not), которая позволяет с помощью перебора с возвратами найти все элементы в списке Candidates, не находящиеся в списке RuledOut.

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

set_difference(Setl, Set2, EetDifference)

в котором все три множества представлены в виде списков, например:

set_difference| [a,b,c,d], [b,d,e,f], [а, с])


Глава 5. Управление перебором с возвратами



5.6. Определите предикат

unifiablef List!, Term, List2)

Здесь List2 представляет собой список всех элементов списка Listl, которые'-!

согласуются с термом Term, но не конкретизируются в результате этого согла­-j

сования, например:

?- unifiable([X, b, tm], t(a), List)

List - [X, t (Y) ]

Обратите внимание на то, что X и У должны оставаться неконкретизированны-

ми, несмотря на то, что согласование с термом t(a) может вызвать такую

конкретизацию. Подсказка: используйте правило not (Terml = Тегт2);если

цель Terml = Terrr.2 достигается, то попытка достичь цели not (Terml =

Term2) оканчивается неудачей и в результате этого конкретизация отменяется!





Поделиться с друзьями:


Дата добавления: 2015-10-01; Мы поможем в написании ваших работ!; просмотров: 415 | Нарушение авторских прав


Поиск на сайте:

Лучшие изречения:

Наглость – это ругаться с преподавателем по поводу четверки, хотя перед экзаменом уверен, что не знаешь даже на два. © Неизвестно
==> читать все изречения...

2675 - | 2239 -


© 2015-2025 lektsii.org - Контакты - Последнее добавление

Ген: 0.011 с.