Решение логических задач на языке пролог с использованием метода отсечения

Цель урока: рассмотреть решение логических задач на языке пролог с использованием метода отсечения и отката

Содержание:

Метод отсечения
- Отрицание
- Составные объекты
Решение логических задач на языке Пролог

Метод отсечения

В Прологе предусмотрен специальный механизм — отсечение ненужных решений с помощью встроенного предиката «!» (cut), а в качестве решения принимается первый до отсечения истинный результат.

Отсечение может «работать» в двух режимах:

Вывод конкретного значения (фильтрация):

pravilo:-                # 1. правило
child(Name), Name=diana, # 2. условие отсечения
!,                       # 3. отсечение 
write (Name).            # 4. печать (diana)

Отсечение нижеследующего содержимого:

pravilo:-                # 1. правило
child(Name), 
write (Name),            # 2. печать
Name=diana,              # 3. условие отсечения
!.                       # 4. отсечение

Рассмотрим пример использования метода:

Пример:
Необходимо вывести имена детей до имени Диана включительно.

✍ Решение:

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

domains
	a=symbol
predicates
	child(a)
	make_cut(a)
clauses
	child(sveta).
	child(diana).
	child(ivan).
	child(diana).
	child(igor).
  make_cut(X):-child(X),X=diana, write(" ",X).
goal
  make_cut.

Результат:

диана

Для того чтобы отсечь все имена, следующие за именем Диана, выполним правило show_some с использованием отсечения ! :

domains
	a=symbol
predicates
	child(a)
	make_cut(a)
	show_some
clauses
	child(sveta).
	child(diana).
	child(ivan).
	child(diana).
	child(igor).
make_cut(X):-child(X),X=diana.
show_some :-
	child(Name),
	write("   ", Name), nl,
	make_cut(Name),!.
goal
show_some_of_them.

Результат:

sveta
diana

Здесь важно, что в правиле show_some сначала осуществляется вывод имени (любого) — write(" ", Name), а только потом отсечение имени diana. В другом порядке результат был бы таким:

...
show_some :-
	child(Name),
	make_cut(Name),!,
        write("   ", Name).
...

Результат:

diana

* Задание Prolog 5_1:
Дана информация об автомобилях, их цене, модели и цвете. Используя правило отсечения, выполнить:

Требуется купить яркий автомобиль (применить правило покупка_автомобиля).
Используя правило покупка_автомобиля, перечислить названия всех моделей до той, цвет которой неяркий (последующие отсечь).
Требуется купить яркий автомобиль по цене не выше 25000.

domains
   a=symbol
   b=real
predicates
   покупка_автомобиля(a,a)
   автомобиль(a,a,b)
   цвет(a,a)
clauses
   автомобиль(москвич,зеленый,25000).
   автомобиль(запорожец,красный,24000).
   автомобиль(корвет,черный,26000).
   автомобиль(порш,красный,54000).
   цвет(красный,яркий).
   цвет(черный,неяркий).
   цвет(зеленый,умеренный).
покупка_автомобиля(Модель,Цвет):-
    ?,
    ?,!,?.

Примечание:
Следует обратить внимание на то, что в данной задаче в правиле в качестве аргументов имеющихся фактов указанны переменные:
так, в правиле покупка_автомобиля(Модель,Цвет) — слова Модель и Цвет — это переменные.

* Задание Prolog 5_2:
Составить базу фактов о животных, живущих на земле и в воде. Добавить правило, позволяющее получить ответ на вопрос: «Кто из животных умеет плавать?». С помощью отсечения и отката выберите только млекопитающих, умеющих плавать.

Запросы:

Кто является рыбой?
Какие млекопитающие живут в воде?

domains
название, где = symbol
predicates
  вид(symbol,symbol)
  кто(название,symbol)
  живет(название,где)
  умеет_плавать
clauses
  вид (млекопитающее,животное).
  вид (рыба,животное).
  кто (обезьяна,млекопитающее).
  кто (дельфин,млекопитающее).
  кто (бобр,млекопитающее).
  кто (акула,рыба).
  кто (кит,млекопитающее).
  кто (треска,рыба).
  кто (собака,млекопитающее).
  живет (обезьяна, на_земле).
  живет (дельфин, в_воде).
  живет (бобр, в_воде).
  живет (бобр, на_земле).
  живет (акула, в_воде).
  живет (кит, в_воде).
  живет (треска, в_воде).
  живет (собака, на_земле).
 
умеет_плавать :- ???

Отрицание

На Прологе есть возможность в правиле добавлять отрицание перед фактом:

...
not(факт)
...

Обычно в таком случае используемые объекты имеют некоторое число общих атрибутов.

Рассмотрим пример и выполним задание.

Пример-Задание:
Создать базу фактов для работы с 4-мя европейскими странами (Франция, Германия, Италия, Испания). Используя факты, указать, что Франция с Германией имеет общую границу, так же как и Франция с Испанией, и Франция с Италией. Создать правило вывода стран, которые не имеют общих границ (non_border_pair). Рассмотрите начало решения и выполните задание до конца

✍ Решение:

Шесть утверждений задают все возможные пары четырех выбранных европейских стран:

euro_pair("France","Germany").
euro_pair("France","Spain").
euro_pair("France","Italy").
euro_pair("Germany","Spain").
euro_pair("Germany","Italy").
euro_pair("Spain","Italy").

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

border(country,country)

Франция с Германией имеют общую границу, так же как и Франция с Испанией, и Франция с Италией. То есть, тот факт, что «Германия и Франция имеют общую границу», можно представить в виде утверждения:

border("France", "Germany").

Тогда утверждение какие из стран не имеют общей границы, можно добавить в правило таким образом:

not(border(Country1,Country2))

Выполнить задание до конца, реализовав все факты и правило.

Составные объекты

Использование составных объектов подразумевает отношение, аргументом которого является предикат:

likes("Tom",fruits(apples,orange,banana)).

В данном примере аргументом отношения (предиката) likes служит другой предикат fruits.

Оба предиката должны быть представлены в области predicates. Однако объявлять составные объекты следует в разделе domains, дав название такому объекту:

domains
	personal_liking = fruits(type1,type2,type3)
	person,type1,type2,type3 = symbol

predicates
        likes(person,personal_liking)

Звучит это так: функтор структуры personal_liking имеет имя fruits. Предикат likes использует эту структуру.

Задание Prolog 5_3:
Создать программу для работы с базой данных «Библиотека«. База включает составную структуру personal_library (личная библиотека) с именем book. Эта структура содержит сведения о книгах из личных собраний. Реализовать правило old_books, выводящее коллекционеров и название книг, датируемых ранее 1960 г.

 
/* персональная библиотека = книга(название, автор, издательство, год издания) */

Запросы:

Какие книги принадлежат Смиту (smith)?
Вывести имена владельцев и названия книг, напечатанных в 1958 году.
Как зовут коллекционера, которому принадлежит книга под названием «Database.A Primer.» ?
Каковы названия книг, опубликованных после 1980 года?

* При составлении запросов для свободных переменных (не интересуемых) используйте подчеркивание (_)

domains
   personal_library = book(title,author,publisher,year)
   collector,title,author,publisher = symbol
   year = integer
 
predicates
   collection(collector,personal_library)
   /* коллекция (имя коллекционера, библиотека) */
 
clauses
   collection(kahn,
		book("The Computer and the Brain",
		     "von Neumann",
		     "Yale University Press",
                     1958)).
   collection(kahn,
		book("Symbolic Logic",
		     "Lewis Carroll",
		     "Dower Publications",
                      1958)).
   collection(johnson,
		book("Database: A Primer",
		      "C.J.Date",
		      "Addison-Wesley",
                      1983)).
   collection(smith,
		book("Alice in Wonderland",
		     "Lewis Carroll",
		     "The New American Library",
                      1960)).

Решение логических задач на языке Пролог

* Задание Prolog 5_4:
Беседуют трое друзей: Белокуров, Чернов и Рыжов. Один из них брюнет, другой блондин, третий – рыжий. Брюнет обратил внимание Белокурова на тот факт, что ни у кого из троих цвет волос не соответствует фамилии. Какой цвет волос у каждого из друзей?

domains
  а=symbol
predicates
  фамилия(а)
  цвет_волос(а)
  соответствие(а,а)
clauses
  фамилия(белокуров).				
  фамилия(чернов).
  фамилия(рыжов).
  цвет_волос(русый).
  цвет_волос(рыжий).
  цвет_волос(черный).
  соответствие(Х,Y):-фамилия(Х), цвет_волос(Y), Х=белокуров,
        not(Y=?), not(Y=?).
  соответствие(Х,Y):-фамилия(Х), цвет_волос(Y), Х=чернов, 
        not(Y=?), not(соответствие(?,?)).
  соответствие(Х,Y):- ...

* Обратите внимание, что каждое последующее правило включает результат использования предыдущего (предыдущих) правила!

Предикат concat устанавливает, что строка Str3 является результатом сцепления Str1 и Str2. Он имеет форму:

   concat(Str1,Str2,Str3) # "croco","dile", Str3 = "crocodile"

* Задание Prolog 5_5:
База данных содержит три существительных (мышь, собака, лошадь) и три прилагательных (красивая, пушистая, умная). Вывести сочетания прилагательных и существительных, подходящих друг другу по смыслу.
Изначально известно, что мышь не умная и не красивая, а собака не умная.

* Каждое последующее правило должно включать результат использования предыдущего (предыдущих) правила!

domains
  а=string
predicates
  существительное(а)
  прилагательное(а)
  сочетание(а,а,а)
clauses
  существительное (мышь).
  существительное (собака).
  существительное (лошадь).
  прилагательное (умная_).
  прилагательное (пушистая_).
  прилагательное (красивая_).
  сочетание(А,В,С):– существительное(В), В=мышь,  
		     прилагательное(А), not(А=умная_), 
		     not(А=красивая_), concat(А,В,С).
  сочетание(А,В,С):– существительное(В), В=собака, 
		     прилагательное(А), not(...), 
		     not(сочетание(...)), concat(А,В,С).
  сочетание(А,В,С):- ?, ?, 
		     ?, not(...),    								 
                     not(...), concat(А,В,С).
goal
  сочетание(А,В,С), write( С ), nl, fail.

* Задание Prolog 5_6:
В автомобильных гонках три первых места заняли Алеша, Петя и Коля. Какое место занял каждый из них, если Петя занял не второе и не третье место, а Коля — не третье?

* Каждое последующее правило должно включать результат использования предыдущего (предыдущих) правила!

domains
  a=symbol
predicates
  имя(a)
  место(a)
  соответствие(a,a)
clauses
  имя(алеша).
  имя(петя).
  имя(коля).
  место(первое).
  место(второе).
  место(третье).
соответствие(X,Y):-имя(X),место(Y),X=петя,
                   not(...),not(...).
соответствие(X,Y):-?.
соответствие(X,Y):-?.

* Задание Prolog 5_7:
В бутылке, стакане, кувшине и банке находятся молоко, лимонад, квас и вода. Известно, что вода и молоко не в бутылке, сосуд с лимонадом находится между кувшином и сосудом с квасом, в банке – не лимонад и не вода. Стакан находится около банки и сосуда с молоком. Как распределены эти жидкости по сосудам?

* Каждое последующее правило должно включать результат использования предыдущего (предыдущих) правила!

domains
  a=symbol
predicates
  емкость(a)
  напиток(a)
  распределение(a,a)
clauses
...

* Задание Prolog 5_8:
Три подруги вышли в белом, зеленом и синем платьях и туфлях. Известно, что только у Ани цвет платья и туфель совпадали. Ни туфли, ни платье Вали не были белыми. Наташа была в зеленых туфлях. Определить цвета платья и туфель на каждой из подруг.
Цвета каждого вида одежды у подруг не совпадали.

domains
  a=symbol
predicates
  имя(a)
  туфли(a)
  платье(a)
  одежда(a,a,a)
clauses
  имя(аня).
  имя(валя).
  имя(наташа).
  туфли(белый).
  туфли(синий).
  туфли(зеленый).
  платье(белый).
  платье(синий).
  платье(зеленый).
одежда(X,Y,Z):-имя(X), платье(Y), туфли(Z), X=?,
             		not(?),not(?), not(?), not(Y=Z). 
одежда(X,Y,Z):-имя(X), платье(Y), туфли(Z), X=аня, 
			..., ..., ....
одежда(X,Y,Z):-....

* Задание Prolog 5_9:
На скамейке сидели Петя, Боря и Коля. Петя справа от Бори, Боря справа от Коли. Кто сидел посередине?

domains
  a=symbol
predicates
  справа(a,a).
  ряд(a,a,a).
  крайний_справа(a).
  посередине(a).
  крайний_слева(a).
clauses
  справа(коля,боря).
  справа(боря,петя).
  ряд(X,Y,Z):-справа(?,?),справа(?,?).         
  крайний_справа(X):-....
  посередине(X):-....
  крайний_слева(X):-....

* Задание Prolog 5_10:
Возле университета растут деревья: береза, тополь, липа, акация, каштан, клен. Известно, что береза ниже тополя, липа выше клена, акация ниже каштана, липа ниже березы, акация выше тополя. Как располагаются деревья по высоте? Какое из деревьев самое низкое и самое высокое?

domains
  a=string
predicates
  выше(a,a)
  самое_высокое(a)
  самое_низкое(a)
  ряд(a,a,a,a,a,a)
clauses
выше(?,?).
выше(?,?).
выше(?,?).
выше(?,?).
выше(?,?).
ряд(A,B,C,D,F,G):-....
самое_высокое(X):-....
самое_низкое(X):-....

* Задание Prolog 5_11:
Составить базу фактов по сказке «Репка». Фактами должны быть утверждения типа: тянет(X,Y), (т.е, X тянет Y). Определить весь ряд персонажей сказки. Составить правила, определяющие: кто первый тянет репку; кто последний репку; кто тянет после бабки; кто тянет на четвертом месте.

Ответ: Ряд: A=репка, B=дедка, C=бабка, D=внучка, E=жучка, F=кошка, G=мышка.

domains
  a=symbol
predicates
 тянет(a,a)
 ряд(a,a,a,a,a,a,a)
 первый(a)
 последний(a)
 после_бабки(a)
 четвертый(a)
clauses
  ...

* При использовании материалов обязательна ссылка на источник: Кузнецова Т.К., «Программирование Turbo Prolog» — Задачи и решения, Ростов-на-Дону, ПИ ЮФУ — 2011г.

К оглавлению