йНМЯОЕЙР ОН МЮВЕПРЮРЕКЭМНИ ЦЕНЛЕРПХХ хМФЕМЕПМЮЪ ЦПЮТХЙЮ юПУХРЕЙРСПЮ щбл хМТНПЛЮРХЙЮ Х ХМТНПЛЮЖХНММШЕ РЕУМНКНЦХХ

Предыдущий разделУровень вышеСледующий раздел

Решение логических задач

Интерпретатор Пролога можно заставить решать логические задачи, что недоступно большинству процедурных языков.

Многие логические задачи связаны с рассмотрением нескольких конечных множеств с одинаковым количеством элементов, между которыми устанавливается взаимно-однозначное соответствие. На языке Пролог эти множества можно описывать как базы данных, а зависимости между объектами устанавливать с помощью правил.


Пример
В автомобильных гонках три первых места заняли Алеша, Петя и Коля. Какое место занял каждый из них, если Петя занял не второе и не третье место, а Коля - не третье?

ИмяI местоII местоIII место
Алеша   
Петя --
Коля  -

Традиционным способом задача решается заполнением таблицы.По условию задачи Петя занял не второе и не третье место, а Коля - не третье. Это позволяет поставить символ '-' в соответствующих клетках. Между множеством имен участников гонки и множеством мест должно быть установлено взаимно-однозначное соответствие. Поэтому определяем занятое место сначала у Пети, затем у Коли и, наконец, у Алеши. В соответствующих клетках проставляем знак '+'. В каждой строке и каждом столбце должен быть только один такой знак.

ИмяI местоII местоIII место
Алеша--+
Петя+--
Коля-+-

Из последней таблицы следует, что Алеша занял третье место, Петя - первое, Коля - второе.

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

 /* База данных имен */ имя(алеша). имя(петя). имя(коля). 
/* База данных призовых мест */ место(первое). место(второе). место(третье). /* 
Устанавливаем взаимно-однозначное соответствие между базами данных, X - элемент 
из базы данных имен, Y - элемент из базы данных занятых мест */ /* Петя занял 
не второе и не третье место */ соответствие(X, Y) :- имя(X), X=петя, место(Y), 
not(Y=второе), not(Y=третье). /* Коля занял не третье место */ соответствие(X, 
Y) :- имя(X), X=коля, место(Y), not(Y=третье). соответствие(X, Y) :- имя(X), X=алеша, 
место(Y). /* У всех ребят разные места */ решение(X1,Y1,X2,Y2,X3,Y3) :- X1=петя, 
соответствие(X1,Y1), X2=коля, соответствие(X2,Y2), X3=алеша, соответствие(X3,Y3), 
Y1\=Y2, Y2\=Y3, Y1\=Y3. 

Для получения ответа следует выполнить запрос

 ?- решение(X1,Y1,X2,Y2,X3,Y3). 

В ответ Пролог выдаст имена ребят и занятые ими места. Проверьте, есть ли другие варианты ответов.


Пример
Витя, Юра и Миша сидели на скамейке. В каком порядке они сидели, если известно, что Миша сидел слева от Юры, а Витя слева от Миши.

В условии задачи перечисляются объекты одного типа, связанные между собой. Заполним базу данных:

 /* Миша 
сидел слева от Юры */ слева(юра,миша). /* Витя сидел слева от Миши */ слева(миша,витя). 

Правило для установления следования объектов друг за другом будет таким:

 /* Объекты X, Y и Z образуют ряд, если X слева от Y и Y слева от Z */ ряд(X, 
Y, Z) :- слева(Y, X), слева(Z, Y). 

Количество аргументов в голове данного правила равно количеству объектов в задаче. Запрос

 ?- ряд(X, Y, Z). 
даст нам решение задачи.


Задание
Решите следующие логические задачи с помощью интерпретатора Пролога.

  1. Трое ребят вышли гулять с собакой, кошкой и хомячком. Известно, что Петя не любит кошек и живет в одном подъезде с хозяйкой хомячка. Лена дружит с Таней, гуляющей с кошкой. Определить, с каким животным гулял каждый из детей.
    Подсказка: прежде всего составьте таблицу, как в примере 1.
  2. Витя, Юра и Миша сидели на скамейке. В каком порядке они сидели, если известно, что Юра сидел слева от Миши и справа от Вити.

Предыдущий разделУровень вышеСледующий раздел

мЮВЕПРЮРЕКЭМЮЪ ЦЕНЛЕРПХЪ Х ХМФЕМЕПМЮЪ ЦПЮТХЙЮ, ОЕПЯОЕЙРХБЮ