Пример: решение логической задачи о волке, козе и капусте
Рассмотрим известную логическую задачу о волке, козе и капусте. Фермер должен переправить на другой берег реки волка, козу и капусту. Грузоподъемность лодки такова, что за один раз можно взять на борт что-нибудь одно: или волка, или козу, или капусту. В присутствии старика никто никого не ест. Если же он отлучится, то волк съест козу, а коза — капусту.
Для решения этой задачи организуем два списка. Один список будет отражать содержимое левого берега, второй — правого. Первоначально все находятся на левом берегу. Список левого берега: [wolf, goat, cabbage], список правого берега пустой: [].
Определим предикаты, описывающие задачу.
stuff (wolf). Хперечисление груза stuff (goat), stuff (cabbage).
/ * условия возникновения конфликта * / conflict (X): - member (wolf, X), member (goat, X). conflict (X): - member (goat, X), member (cabbage, X).
/ * Предикаты, описывающие перемещения лодки:
С левого берега на правый* /
go right ([], _).% условие завершения (список левого берега пуст) go right (L, R): -
stuff (X), % выбираем груз, member (X, L), % который есть на левом берегу
excl (X, L, LL), % исключаем из списка левого берега not (conflict (LL) ), % на левом берегу конфликта
нет
incl (X, R, RR), % включаем в список правого берега write (LL, X, " R), % выводим сообщение
go_left (LL, RR) .% гребем назад / * Движение влево возможно в двух вариантах. Если на правом берегу конфликт не возникает, то фермер едет один * / go_left (L, R): -not (conflict (R) ),
write (L, "< .......", R), % выводим сообщение
go_right (L, R). % вызываем предикат движение вправо / * Если на правом берегу возникает конфликт надо кого- нибудь увезти обратно. Это единственная подсказка, которую мы сообщаем программе. В остальном Пролог будет искать решение вполне самостоятельно * / go_left (L, R): -
stuff (X), % выбираем груз,
member (X, R), % который есть на правом берегу
excl (X, R, RR), % исключаем из списка правого берега not (conflict (RR) ), % на правом берегу конфликта
нет
incl (X, L, LL), % включаем в список левого берега write (L, X, ” --"RR), % выводим сообщение
go_right (LL, RR). % гребем назад Вызов цели должен быть следующим: go_right ([wolf, goat, cabbage], []).
Если запустить эту программу, то быстро обнаружится, что первым рейсом старик отвезет на правый берег козу. Вторым рейсом — волка. Оставить волка с козой на правом берегу нельзя, поэтому он отвезет первый попавшийся груз, а им окажется волк, обратно. И так будет возить его бесконечно.
Недостаток данной программы заключается в том, что фермер не помнит, кого он только что привез. Для укрепления его памяти добавим в предикаты go_left и go_right название последнего перевезенного груза. Финальный вариант программы выглядит следующим образом (изменения выделены полужирным шрифтом):
/ * Задача о волке, козе и капусте * / domains % раздел требуется для PDC-Пролога. В SWI-Прологе не нужен
stuff = wolf; goat; cabbage; nil % создаем свой тип
данных (nil - пустое) list = stuff* % тип данных список predicates % раздел требуется для PDC-Пролога.
В SWI-Прологе не нужен member (stuff, list) incl (stuff, list, list) excl (stuff, list, list) conflict (list)
go_right (list, list, stuff) go_left (list, list, stuff) clauses
stuff (wolf).
stuff (goat).
stuff (cabbage).
member (H, [H | _]).
member (X, [H | T]): - member (X, T).
incl (H, T, [H | T]).
excl (H, [H | T], T).
excl (X, [H, T], [H | TT]): - excl (X, T, TT). conflict (X): - member (wolf, X), member (goat, X). conflict (X); - member (goat, X), member (cabbage, X). go_right (L, R, Last): -
stuff (X), % выбираем 2py3j
X <> Last, % но не mom, что везли только что и member (X, L), % который есть на левом берегу
excl (X, L, LL), % исключаем из списка левого берега
not (conflict (LL) ), % на левом берегу конфликта
нет
incl (X, R, RR), % включаем в список правого берега
write (LL, X, " R), % выводим
сообщение
go_left (LL, RR, X) .% гребем назад
/ * Если на правом берегу конфликт не возникает, то едет один * /
go_left (L, R, Last): - not (conflict (R) ),
write (L, "<-------”, R), % выводил! сообщение
go_right (L, R, nil). % вызываем предикат движение
вправо
% niL - значит, не везли ничего / * Если на правом берегу возникает конфликт надо кого- нибудь увезти обратно, но не того, кого везли только что * /
go_left (L, R, Last): -
stuff (X), % выбираем груз,
X о Last, % не тот} что везли только что и member (X, R), % который есть на правом берегу
excl (X, R, RR), % исключаем из списка правого берега not (conflict (RR) ), % на правом берегу конфликта
нет
incl (X, L, LL), % включаем в список левого берега write (L, X, ” RR), % выводим
сообщение
go_right (LL, RR, X). % гребем назад и помним, что
везли X
goal
go_right ( ([wolf, goat, cabbage], [], nil). / * Конец программы * /
Контрольные вопросы
- 1. Напишите правило для отношения двоюродный брат или сестра. Используйте правила, приведенные в подразд. 1.4.
- 2. Имеется программа, состоящая из двух экземпляров правила а:
а : - Ь, с, !, d, fail.
а : - е.
Какие предикаты будут вызваны при выполнении правила а, если каждый из предикатов b, с, d, е заканчивается успехом, а предикат fail — стандартный предикат для искусственного вызова неудачи? Что изменится, если убрать предикат отсечения?
3. Имеется предикат
dosomething ([]).
dosomething ([Н | Т]): - member (Н, Т), dosomething (Т).
dosomething ([Н | Т]): - write (Н), dosomething (Т).
Какой результат даст вызов dosomething ([1, 0, 0,1, 2, 0,10])?
4. Какое отсечение, красное или зеленое, стоит в следующем правиле? Обоснуйте.
sister (X, Y): - sibling (X, Y), !, female (X).
5. Правомерно ли использование отсечения в следующем правиле? Почему?
grandfather (X, Y): - father (X, Z), !, parent (Z, Y).
