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

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

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

Пример простой логической задачи (два измерения)

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

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

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

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

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

Рис. 5.1. Программа решения простой логической задачи

Практикум 5-1

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

Практикум 5-2

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

Пример задачи (три измерения)

Условия задачи: Четверо ребят: Лева, Коля, Миша и Петя решили позавтракать в разных местах: один – в кафе, другой - в столовой, третий – в закусочной, а четвертый – в буфете.

После завтрака все собрались вместе. Разговор зашел о том, кто как позавтракал.

Выяснилось, что все они пили разные напитки, так как в каждом из тех мест, где они завтракали, оказалось в наличие только по одному напитку: в одном месте – только кофе, в другом – только молоко, в третьем – только кефир, а в четвертом только чай.

В буфете, например, было только молоко, а в столовой не было кефира.

Петя рассказал, что он был в столовой, но пил там не чай.

Лева рассказал, что он пил кефир.

А Миша сказал, что он не был ни в закусочной, ни в буфете.

Кто где завтракал и что при этом пил?

При решении этой задачи удобно использовать списки и предикаты работы со списками (рис.5.2).

Рис. 5.2. Программа решения логической задачи 2

Результат выполнения программы представлен на рис. 5.3

Рис. 5.3. Результат решения логической задачи 2