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

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

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

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

Имя	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. /* для компенсации особенностей реализации в PIE32 запишем */ X = X.

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

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

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

X1= петя, Y1= первое, X2= коля, Y2= второе, X3= алеша, Y3= третье

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

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

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

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

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

?- ряд(X, Y, Z).

даст нам решение задачи:

X= витя, Y= миша, Z= юра

Дата добавления: 2014-12-27