Основы логического программирования

Лабораторная работа 1

Задания на работу.

1. Используя предикаты parent(name, name), man(name), woman(name), married(name, name), записать факты, описывающие Вашу семью. Записать не менее 8 правил вывода для любых родственных отношений в Вашей семье, например, мать, отец, сестра, брат, племянник, племянница, тетя, дядя, внук, внучка, бабушка, дедушка, двоюродный брат, двоюродная сестра и т.д.

2. Написать факты и правила, моделирующие логический элемент или комбинационную схему согласно Вашему варианту, представленному в табл. 3.

Таблица 3.

Вариант	Логический элемент или комбинационная схема
	И-ИЛИ-НЕ
	ИЛИ-И-НЕ
	НЕ-И-ИЛИ
	НЕ-ИЛИ-И
	ИЛИ-НЕ-И
	И-НЕ-ИЛИ
	Схема мажорирования (голосования 2 из 3-х)
	Синхронный RS-триггер
	Асинхронный RS-триггер
	D-триггер
	JK-триггер
	Схема сложения по модулю 2
	Схема исключающего ИЛИ

Контрольные вопросы.

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

Лабораторная работа 2

Списки

Тема: списки, основные операции над списками.

Основные термины, ключевые слова: список, пустой список, голова списка, хвост, операции над списками.

Инструмент для выполнения работы: интегрированная среда языка Пролог – Strawberry Prolog v.2.3 (SP), интегрированная среда Visual Prolog v.5.2 (VP).

Содержание отчета:

- титульный лист установленного образца;

- краткие теоретические сведения;

- задание на работу;

- описание (изображение) списка в виде дерева;

- текст программы на языке Пролог;

- выводы по работе.

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

[иван, петр, мария, наталия].

Отметим сразу, что список обязательно заключается в квадратные скобки, а элементы списка разделяются символом запятая.

В некотором смысле список является аналогом массива в алгоритмических языках программирования. Однако здесь есть существенные отличия. Во-первых, элементы списка не индексированы и их число не фиксировано, во-вторых, список структура рекурсивная, в-третьих, элементом одного и того же списка могут быть объекты различного «типа», например, [ 1, иван, X1 ]. В отношении последнего отличия необходимо добавить, что в качестве элемента списка может выступать любой прологовский терм, в том числе и список.

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

Для удобства обработки списков в Прологе введены два важных понятия: голова (head) и хвост(tail). По умолчанию головой списка считается первый элемент, в некоторых случаях, несколько первых элементов. Оставшиеся элементы относятся к хвосту. Тогда можно сказать, что список – это структура данных, определяемая следующим образом:

- пустой список, т.е. список, не содержащий элементов, обозначается как [];

- список, состоящий из головы и хвоста. В качестве головы может выступать любой прологовский терм, а в качестве хвоста обязательно список.

Голова соединяется с хвостом при помощи специального функтора, заимствованного из теоретических разделов рекурсивного программирования, это символ точки. В общем виде любой список можно представить в виде:.(Голова, Хвост). Тогда исходный список запишется следующим образом:

.(иван, .(петр, .(мария, .(наталия, [])))).

Подобную структуру удобно представлять в виде дерева, как показано на рис. 1.

иван ٭

петр ٭

мария ٭

наталия []

Рис. 1. Представление списка [иван, петр, мария, наталия]

в виде дерева.

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

Для отделения головы от хвоста в языке предусмотрено расширение нотации представления списков, это символ вертикальной черты, т. е. List = [Head | Tail ]. Этот символ имеет более общий смысл: можно перечислить любое число символов перед «|», а затем – список остальных элементов. Рассмотрим на примере использование этого символа:

head(X, [X|List]).

? -head(Y, [a, b, c]),

write(“Y=”),

write(Y),

nl.

Предикат head имеет следующие аргументы: первый - переменная X, второй List – произвольный список, причем из которого можно увидеть, что X – голова списка. Вопрос к пролог-системе сформулирован следующим образом: «Что является головой произвольного списка? ». Оттранслируйте этот пример в среде Strawberry Prolog и проанализируйте полученный результат.

Следует отметить обратимость операции отделения головы от хвоста. Несколько изменив предикат head (и назвав его new_head), можно не отделять голову от списка, а наоборот добавлять новые элементы в голову существующего списка. Следующий фрагмент демонстрирует сказанное.

new_head(X, List, [X|List]).

? -new_head(z, [a, b, c], Y),

write(" Y=" ),

write(Y),

nl.

Здесь переменная Y выступает в роли списка с новой головой. Оттранслируйте этот фрагмент и проанализируйте полученный результат.

Здесь в явном виде отсекается первый элемент списка, хотя на практике часто бывает необ ходимо отделить не один, а несколько элементов от списка, переместив символ отсечения на необходимое число символов.

Еще одно важное замечание относительно операции отделения головы от списка — это не структуроразрушающая операция. Другими словами, после отделения головы от списка, исходный список остается неизменным. В подтверждение сказанного оттранслируйте и оцените результат следующего фрагмента Пролог-программы.

head(X, [X|List]).

? -List=[a, s, d], head(X, List),

write(" X=" ),

write(X),

nl,

write(" List=" ),

write(List),

nl.

Ответ Пролог-системы будет следующим:

X=a

List=[a, s, d]

Yes.

Необходимо отметить что список, List каким был, таким и остался, т. е. фактического отделения головы от хвоста списка (разрушения списка) не происходит. Этот факт необходимо учитывать в практической работе со списками.

Удаление элемента из списка

Удаление элемента X из списка L можно определить в виде отношения away(X, L, L1), где L1 – это список L, из которого удалили X. Отношение строится на том соображении, что если X – голова списка, то результат отношения – хвост списка. Если X не голова списка, то его необходимо удалить из хвоста.

away(X, [X|T], T).

away(X, [Y|T], [Y|T1]): -away(X, T, T1).

Индивидуальные задания. Выполнить следующие индивидуальные задания согласно варианту.

1. Создайте предикат, заменяющий в исходном списке первое вхождение заданного элемента другим. Создайте предикат, заменяющий в исходном списке все вхождения заданного элемента другим.

2. Создайте предикат, порождающий по заданному натуральному числу N список, состоящий из натуральных чисел от 1 до N (по возрастанию). Создайте предикат, порождающий по заданному натуральному числу N список, состоящий из натуральных чисел от N до 1 (по убыванию).

3. Создайте предикат, порождающий по заданному натуральному числу N список, состоящий из N случайных чисел от 1 до 100. Создайте предикат, порождающий по заданным числам N, M, K список, состоящий из N натуральных чисел из промежутка от M до К

4. Создайте предикат, порождающий по заданным числам M, K список, состоящий из случайного количества случайных чисел от M до K. Создайте предикат, порождающий список, состоящий из случайного количества случайных чисел

5. Создайте предикат, который увеличивает элементы числового списка на единицу. Создайте предикат, переводящий список цифр от 0 до 9 в список соответствующих им названий (строк).

6. Создайте предикат, переводящий список чисел в список соответствующих им названий. Создайте предикат, переводящий список чисел от 0 до 9 в список соответствующих им римских чисел.

7. Создайте предикат, переводящий список арабских чисел в список соответствующих им римских чисел. Создайте предикат, переводящий список римских чисел в список соответствующих им арабских чисел.

8. Создайте предикат, удваивающий значения элементов списка. Создайте предикат, преобразующий список, элементами которого являются числа, в список, элементы которого неотрицательны

9. Создайте предикат, преобразующий исходный список в список позиций отрицательных элементов. Создайте предикат, удаляющий из исходного списка элементы с нечетными номерами

10. Создайте предикат, который разделит исходный список из целых чисел на два списка: список положительных чисел и список отрицательных чисел. Создать предикат, разделяющий исходный список на два, в одном из которых содержатся элементы исходного списка с нечетными номерами, а в другом – с четными.

11. Создайте предикат, вычисляющий по списку и числу, подсписок, начинающийся с элемента с указанным номером. Создайте предикат, осуществляющий удаление указанного количества последних элементов исходного списка.

12. Создать предикат, осуществляющий разделение исходного списка на два подсписка. В первый из них должно попасть указанное количество элементов из начала списка, во второй – оставшиеся элементы. Создать предикат, осуществляющий разделение исходного списка на два подсписка. В первый из них должно попасть указанное количество элементов с конца списка, во второй – оставшиеся элементы

13. Создайте предикат, находящий предпоследний элемент в списке. Создайте предикат, удаляющий предпоследний элемент в списке.

14. Создайте предикат, заменяющий в исходном списке два подряд идущих одинаковых элемента одним. Создайте предикат, удаляющий в исходном списке все повторные вхождения элементов.

15. Создайте предикат, осуществляющий перестановку двух элементов списка с заданными номерами. Создайте предикат, генерирующий все перестановки элементов списка, указанного в качестве первого предиката.

16. Создайте предикат, осуществляющий циклический сдвиг элементов влево (вправо). Создайте предикат, осуществляющий циклический сдвиг элементов списка на заданное количество шагов.

17. Создайте предикат, осуществляющий поэлементное перемножение соответствующих элементов двух списков. Создайте предикат, вычисляющих скалярное произведение векторов, заданных списками целых чисел.

18Создайте предикат, осуществляющий подсчет числа вхождений каждого элемента исходного списка. Ответом должен быть список пар, в которых первая компонента – элемент исходного списка, вторая – число его вхождений в исходный список.

19. Создайте предикат, определяющий первую позицию подсписка в списке. Создайте предикат, возвращающий по списку и двум числам M и N подсписок исходного списка, состоящий из элементов с номерами от M до N.

Контрольные вопросы

1. Список, голова и хвост списка.

2. Что может выступать в качестве элемента списка.

3. Что может выступать в качестве головы списка?

4. Что может выступать в качестве хвоста списка?

5. Основные операции над списками.

Лабораторная работа 3

Лабораторная работа 4

Рекурсия

Тема : основы рекурсивного программирования в языке Пролог.

Основные термины, ключевые слова: рекурсия, простые рекурсивные структуры Пролога, минимально рекурсивная программа.

Содержание отчета:

- титульный лист установленного образца;

- краткие теоретические сведения;

- задание на работу;

- текст программы на языке Пролог;

- выводы по работе.

Основные теоретические сведения. Любое определение, которое описывается в терминах самого себя, называется рекурсивным. Рекурсия – один из приемов, который встречается практически во всех видах программирования. В декларативных языках рекурсия играет доминирующую роль. С одной стороны это связано с рекурсивной внутренней структурой декларативных языков. С другой – в нечисловом программировании часто используются структуры, рекурсивные по своей природе, например, списки, деревья, графы.

В математике рекурсивным началом можно считать натуральное число, если положить, что отправной точкой для любого натурального числа считать цифру 0. Любое натуральное число можно определить как функцию следования S от числа 0, т. е. 0, S(0), S(S(0)), …, S(S(S(…S(0)…))). Благодаря функции следования любое натуральное число представляется как рекурсивная структура с граничным условием, равным нулю. В языке Пролог напрямую запрограммировать функцию следования не представляется возможным, однако, используя математические операции можно ее промоделировать с определенной степенью верности.

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

natural_number(0).

natural_number(X): - Y is X - 1, Y> =0, natural_number(Y), write(X), nl.

? -natural_number(5).

После трансляции этого фрагмента, Пролог-система выдаст следующий ответ:

Compiling the file:

D: \StrawberryProlog\Strawberry Prolog\Examples\test_2

0 errors, 0 warnings.

Yes.

Здесь получена последовательность всех натуральных чисел меньше заданного в вопросе.

Рассмотрим программу более детально. В первом предложении описано условие выхода из рекурсии или граничное условие. Граничное условие (можно сказать – самый простой из всех возможных случаев) в программе должно быть описано раньше, чем рекурсивное определение. Негласный закон рекурсивного программирования можно сформулировать следующим образом: «В начале проверь самое простое, а затем переходи к более сложному». Второе предложение – собственно сама рекурсия, поскольку в определении предиката в правой части осуществляется попытка доказательства цели с тем же именем, что и имя предиката. Кроме того, во втором предложении последовательность целей: Y is X - 1, Y> =0 представляют собой «модель» функции следования S.

Перестановка предложений в программе возможна, но не желательна (см. негласный закон рекурсивного программирования), это напрямую связано с эффективностью программы. Перестановка целей во втором предложении не допустима, так как это приведет к бесконечному циклу. Наличие математических операций в программе, как правило, приводит к перевесу процедурного смысла над декларативным.

Следует отметить тот факт, что в рекурсивном определении, рекурсия присутствует только один раз. Программы такого вида называют минимально рекурсивными. Кроме того, рекурсивная цель в правиле присутствует в конце предложения (операция вывода на экран не в счет), это хвостовая рекурсия.

Над натуральными числами в математике определено конечное множество операций, например, сложение, умножение, возведение в степень, etc. Можно показать, что все это множество подчиняется той же функции следования S. Однако числовые величины не являются предметом изучения декларативных языков программирования. Наиболее подходящей рекурсивной структурой являются списки. Список представляется либо пустым списком – [], либо, если он не пустой, структурой, состоящей из головы(head) и хвоста(tail). Причем в качестве головы может выступать любой объект Пролога, а в качестве хвоста – обязательно список. Подобное определение обязывает список быть рекурсивной структурой, поскольку его хвост сам по себе является списком.

В терминах Пролога список определяется достаточно просто:

list([]).

list([H|T]): - list(T).

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

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

? -X=[a, s, d, f], list(X), write(X), nl.

Compiling the file:

D: \StrawberryProlog\Strawberry Prolog\Examples\test_2

0 errors, 0 warnings.

[a, s, d, f]

Yes.

Если же поставить следующий вопрос:

? -X='a', list(X), write(X), nl.,

то этом случае Пролог ответит не утвердительно.

Этот предикат можно отнести к типовым предикатам, позволяющим, определить к какому типу относится объект, в данном случае – к спискам.

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

binary_tree(_, _, _).

binary_tree(Element, Left, Rigth): -binary_tree(Left), binary_tree(Rigth).

В отличие от списка для двоичного дерева характерна двойная рекурсия, то есть рекурсия по левому и правому поддеревьям. Это хорошо видно из второго предложения. Следует отметить, что эта программа уже не минимально рекурсивная.

Поставьте перед Пролог-системой вопрос

? - binary_tree(a, binary_tree(b, void, void), binary_tree(c, void, void)).

и проанализируйте ответ.

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

tree_member(X, binary_tree(_, _, _)).

tree_member(X, binary_tree(_, Left, _)): -tree_member(X, Left).

tree_member(X, binary_tree(_, _, Rigth)): -tree_member(X, Rigth).

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

Декларативный смысл отношения достаточно очевиден: элемент принадлежит двоичному дереву, если он является корнем дерева. Если элемент не корень, то он принадлежит или левому или правому поддереву.

Имея подобный предикат, пользователь может проверить объект на «тип» дерева, например, задав вопрос:

? -tree_member(b, binary_tree(a, binary_tree(b, void, void), binary_tree(c, void, void))).

Ответ Пролог-системы:

Compiling the file:

D: \StrawberryProlog\Strawberry Prolog\Examples\test_2

0 errors, 0 warnings.

Yes.

Индивидуальные задания. Выполнить индивидуальное задание согласно Вашим вариантам, представленным ниже.

1. В списке S1, S2, S3, …, SN найти первое и последнее вхождение заданного символа и исключить все символы между ними.

2. В списке символов S1, S2, S3, …, SN исключить все последовательности указанного вида, например, [a, b, c, d]

3. В списке символов S1, S2, S3, …, SN найти длину наибольшей последовательности, построенной повторением одного и того же символа. Вывести эту последовательность

4. В списке символов S1, S2, S3, …, Sn каждую последовательность символов заменить другой последовательностью

5. Из списка символов исключить все символы между круглыми скобками

6. Даны два списка целых чисел A1, A2, A3…AN и B1, B2, B3, …, B. Соединить эти списки в один, исключив все повторения и упорядочить список по возрастанию

7. В списке символов подсчитать количество букв в последнем слове, если разделителем между словами является пробел (число пробелов может быть больше одного)

8. В списке символов подсчитать число слов, если разделителем между словами является пробел

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

10. В списке символов найти число слов, начинающихся с заданной буквы. Разделителем между словами является один или несколько пробелов.

11. В списке символов найти длину самого короткого слова. Разделитель между словами один или несколько пробелов.

12. В списке символов найти все вхождения данного слова. Разделитель между словами один или несколько пробелов. Вывести это слово.

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

14. В списке символов найти число слов с одинаковой первой и последней буквами. Разделяются слова одним или более пробелами. Вывести самое длинное слово

15. В списке символов найти среднюю длину слова. Вывести все слова, имеющие эту длину.

16. Из списка целых чисел A1, A2, A3…AN исключить все элементы, совпадающие со значением [(A_max+A_min+A_cp)/3]

17. Преобразовать список целых чисел A1, A2, A3, …, AN следующим образом: исключить все нули, слева записать все положительные числа

18. Список целых чисел A1, A2, A3, …, AN оставить без изменений, если он упорядочен по возрастанию или убыванию. В противном случае: каждый нечетный элемент списка утроить, каждый четный элемент, кратный четырем, удалить

19. В каждой из девяти клеток квадрата 3*3 разместить одно из чисел 1. 2 и 3 так, чтобы сумма чисел, стоящих в каждом вертикальном ряду, в каждом горизонтальном ряду и на каждой диагонали равнялась

20. Для N произвольных заданных костяшек домино необходимо найти все возможные цепочки из этих костяшек длиной N. Если таких цепочек нет, то выдать максимально длинную возможную цепочку

21. Решить упрощенный вариант головоломки «пятнашки» для поля 3*3

22. Для двух произвольных строк символов определить, может ли одна строка быть получена из другой перестановкой символов, без учета пробелов

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

24. Написать программу отыскания кратчайшего пути коня из позиции a1 на стандартной шахматной доске в произвольную позицию

Примечание. Если задание покажется слишком легким, обратитесь за более «интересным» к преподавателю.

Контрольные вопросы

1. Понятие рекурсии.

2. Особенности рекурсии в Прологе.

3. Рекурсивные структуры в декларативном программировании.

4. Порядок предложений и целей в предложениях при рекурсии.

5. Декларативный смысл рекурсивных программ, «процедурные» особенности рекурсии.

6. Минимально рекурсивное отношение.

7. Хвостовая рекурсия.

Лабораторная работа 5

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

Тема : основы программирования логических задач, головоломок.

Основные термины, ключевые слова: логическая игра, головоломка, схема решения.

Содержание отчета:

- титульный лист установленного образца;

- краткие теоретические сведения;

- задание на работу;

- текст программы на языке Пролог;

- выводы по работе.

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

Три друга заняли первое, второе и третье места в соревнованиях универсиады. Друзья – разной национальности, зовут их по-разному, и любят они разные виды спорта.

Майкл предпочитает баскетбол и играет лучше, чем американец. Израильтянин Саймон играет лучше теннисиста. Игрок в крокет занял первое место.

Кто является австралийцем? Каким спортом занимается Ричард?

Подобные логические головоломки изящно решаются посредством конкретизации значений подходящей структуры данных и выделения значения, приводящего к решению. Каждый ключ к решению преобразуется в факт относительно структуры данных. Это может быть сделано с использованием абстракции данных до определения точной формы структуры данных. Проанализируем первый ключ к разгадке: «Майкл предпочитает баскетбол и играет лучше, чем американец». Очевидно, речь идет о двух разных людях. Одного зовут Майкл, и занимается он баскетболом, в то время как второй – американец. Кроме того, Майкл лучше играет в баскетбол, чем американец. Предположим, что Друзья – структура данных, подлежащая конкретизации, тогда искомый ключ может быть выражен следующей конъюнкцией целей:

играет_лучше(Мужчина_1, Мужчина_2, Друзья),

имя(Мужчина_1, Майкл), спорт(Мужчина_1, баскетбол),

национальность(Мужчина_2, американец).

Аналогично второй ключ можно представить конъюнкцией целей:

играет_лучше(Мужчина_1, Мужчина_2, Друзья),

имя((Мужчина_1, Саймон),

национальность(Мужчина_1, израильтянин),

спорт(Мужчина_2, теннис).

Наконец, третий ключ к разгадке выразится следующим образом:

первый(Друзья, Мужчина), спорт(Мужчина, крокет).

Базовый предикат для решения головоломок:

решить_головоломку(Головоломка, Решение)., где Решение является решением головоломки Головоломка. Головоломка представляется структурой головоломка(Ключи, Вопросы, Решение). Общую схему решения головоломки можно представить следующим образом:

решить_головоломку(головоломка(Ключи, Вопросы, Решение), Решение): - решить(Ключи), решить(Вопросы).

решить([]).

решить([Ключ|Ключи]): -решить(Ключ).

Каждый человек имеет три атрибута и представляется структурой вида: друг(Имя, Страна, Спорт)., а в качестве структуры данных последовательность трех элементов, представляющим список: [друг(N1, C1, S1), друг(N2, C2, S2), друг(N3, C3, S3)]. Ключи и вопросы в данном примере предлагается составить самостоятельно. Для проверки: Майкл – австралиец, а Ричард играет в теннис.

Эта схема решения дает представление об общем подходе для решения головоломок. Часто подобную схему называют решателем головоломок. Следует отметить, что «универсального» решателя нет, для каждого конкретного случая необходим свой подход к решению, несмотря на то, что можно выделить наиболее общие моменты, присущие большинству логических задач.

Следующий пример заимствован у Раймонда Смаллиана из серии «Принцесса и тигр» и доведен до «конечного» результата.

«…У Фрэнка Стоктона есть сказка, которая называется " Принцесса или тигр? " В этой сказке один узник должен угадать, в какой из двух комнат находится принцесса, а в какой - тигр. Если он укажет на первую комнату, то женится на принцессе, если на вторую, то его, вполне возможно, растерзает тигр.

В некотором царстве правил король. Однажды он тоже прочитал эту сказку. “В самый раз для моих заключенных! ” - сказал он своему министру. Только я не хочу полагаться на случайности. Пусть на дверях каждой комнаты повесят по табличке, а заключенному будет кое-что сказано о них. Если узник не глупый и способен рассуждать логически, он сумеет сохранить себе жизнь и в придачу заполучить прелестную невесту. “Блестящая идея, ваше величество! ” - согласился министр…».

Испытания первого дня.

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

Первое испытание. «А что, если в обеих комнатах сидят тигры? » - спросил узник. «Что же мне тогда-то делать? » «Считай, не повезло», - ответил король. «А если в обеих комнатах окажется по красавице? » - поинтересовался узник. «Считай, подфартило», - сказал король. «Уж это ты и сам бы мог сообразить! »- «Ну, хорошо, а если в одной комнате принцесса, а в другую посадили тигра, что тогда? » - не успокаивался узник. «Вот тут-то уже все зависит от тебя! Не так ли? » «Да откуда же мне знать, где кто? » - сокрушенно вздохнул узник. Тут король указал на таблички, прикрепленные к дверям каждой из комнат. На них было написано:

В этой комнате находится принцесса, а в другой комнате сидит тигр

В одной из этих комнат находится принцесса, кроме того, в одной комнате сидит тигр

«А это правда, что здесь написано? » - спросил узник. «На одной – правда», - отвечал король, «на другой – нет». А вы как бы ответили на месте узника? (Конечно, если вы предпочитает принцессу тигру.)

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

maybe(tiger, tiger).

maybe(princess, princess).

maybe(princess, tiger).

maybe(tiger, princess).

Двухаргументное отношение maybe задает «расположение» объектов задачи (принцесса – тигр), причем первый аргумент относится к левой комнате, а второй – к правой.

Надпись на табличке первой (левой) двери гласит о том, что «в этой комнате находится принцесса, а в другой комнате сидит тигр». Эту надпись легко описать с помощью следующего отношения room_1(X, Y): -X=princess, Y=tiger. По аналогии для второй двери, надпись на которой можно понимать так, что в любой из этих комнат находится принцесса, а в другой – тигр. Это кодируется следующим отношением room_2(X, Y): -X=princess, Y=tiger; X=tiger, Y=princess.

Конъюнкция этих отношений послужит для определения отношения типа «кто_где» - who_where(X, Y): -maybe(X, Y), room_1(X, Y), room_2(X, Y)., которое позволит найти решение задачи.

А теперь объединим все отношения в единую процедуру, оттранслируем и зададим вопрос.

maybe(tiger, tiger).

maybe(princess, princess).

maybe(princess, tiger).

maybe(tiger, princess).

room_1(X, Y): -X=princess, Y=tiger.

room_2(X, Y): -X=princess, Y=tiger;

X=tiger, Y=princess.

who_where(X, Y): -maybe(X, Y),

room_1(X, Y),

room_2(X, Y).

? -who_where(X, Y), write(" В первой комнате - " ), write(X), nl,

write(" Во второй комнате - " ), write(Y).

Compiling the file:

C: \Program Files\Strawberry Prolog\Examples\isp_1

0 errors, 0 warnings.

В первой комнате - princess

Во второй комнате - tiger

Yes.

Проверьте этот ответ Пролог системы. Совпадает он с вашими выводами

Индивидуальные задания. Выполнить индивидуальное задание согласно Вашему порядковому номеру в группе и плюс задание с номером большим на 10, например, первый вариант выполняет задание с номерами 1 и 11, второй вариант соответственно с номерами 2 и 12 и т. д.

Вариант 1

- Испекла бы ты вкусных крендельков! - как-то раз в холодный летний денек попросил Король Червей Королеву Червей.

- Что толку печь крендели, когда нет варенья?! - яростно возопила Королева. - Ведь самое вкусное в кренделях - это варенье! - Так возьми варенье, - посоветовал Король.- Хотела бы, да не могу, - совсем рассердилась Королева. - Мое варенье кто-то украл! - Не может быть! - изумился Король. - Ты это серьезно? И кто же, по-твоему, украл варенье? Уж не думаешь ли ты, что я украла его? Да если бы я знала, кто похитил варенье, то варенье давным-давно было бы там, где положено, как, впрочем, и голова негодяя. Король приказал своим солдатам сыскать пропавшее варенье, и оно было найдено в домике, где обитали Мартовский Заяц, Болванщик и Соня. Разумеется, все трое были схвачены и предстали перед судом. Я требую, - заявил Король, обращаясь к судье и присяжным, - чтобы вы до конца разобрались в этом деле. Терпеть не могу, когда суют нос ко мне на кухню и воруют мое варенье. Почему? - спросила одна из морских свинок. Подавить эту морскую свинку, - вскричала Королева. Несчастную морскую свинку тотчас же подавили. (Те, кто читал " Приключения Алисы в Стране Чудес", без труда вспомнят, что означает слово " подавить": служители суда взяли большой мешок, сунули в него морскую свинку и, завязав мешок веревочкой, уселись на него.)- Итак, - продолжал Король, когда суматоха, вызванная подавлением морской свинки, улеглась, - я требую, чтобы вы до конца разобрались в этом деле! Вы уже говорили об этом, - заметила вторая морская свинка и тотчас же была беспощадно подавлена. Не вы ли случайно украли варенье? - спросил Король у Мартовского Зайца. Не крал я никакого варенья! - взмолился Мартовский Заяц. (Тут все оставшиеся морские свинки зааплодировали, и, разумеется, были подавлены.).-Ну а что скажете вы? - прорычал Король, обращаясь к Болванщику, который дрожал, как осиновый лист. - Вы случайно не злоумышленник, который украл варенье? Болванщик не мог вымолвить ни слова: он только глоток за глотком отпивал свой чай. Раз ему нечего сказать, то это доказывает его виновность, - заметила Королева. - Отрубить ему голову! Нет, нет! - едва выговорил дрожащим голосом Болванщик. - Варенье украл один из нас, но не я! -Запишите! - приказал Король присяжным. - Это показание может оказаться очень важным! Ну а вы? - продолжал Король, обращаясь к Соне. - Что вы скажете нам обо всем этом? Говорят ли оба ваших соседа., Мартовский Заяц и Болванщик, правду? -По крайней мере один из них сказал правду, - ответила Соня и мгновенно заснула, да так и проспала до конца судебного заседания. Как показало расследование, ни Мартовский Заяц, ни Болванщик не сказали правды одновременно. Кто украл варенье?

Вариант 2

- Теперь у нас снова есть варенье, - обратился Король к Королеве, - и ты сможешь наконец испечь кренделей.
- Как я могу печь крендели, когда у меня нет муки? - спросила Королева.
- Уж не хочешь ли ты сказать, что муку тоже украли?! - вскричал Король.- Вот именно! - сказала Королева. - Найди того, кто это сделал, и отруби ему голову! -Ну-ну! - пробормотал Король. - К чему такая спешка? Стали искать муку, и после некоторых поисков обнаружили ее в домике, где жили Мартовский Заяц, Болванщик и Соня. Разумеется, все трое были арестованы и предстали перед судом. На суде Мартовский Заяц заявил, что муку украл Болванщик. В свою очередь Болванщик и Соня дали показания, которые по каким-то причинам не были записаны, поэтому сообщить вам, о чем они говорили, я просто не в силах. В ходе судебного заседания выяснилось, что муку украл лишь один из трех подсудимых и что только он дал правдивые показания. Кто украл муку?

Вариант 3

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

I По крайней мере в одной из этих комнат находится принцесса

II Тигр сидит в другой комнате

- Истинны ли утверждения на табличках? - спросил второй узник. Может, оба истинны, а может, оба ложны, - ответил ему король. Какую из комнат следует выбрать второму узнику?

Вариант 4

12 3 4 5 6 Следующая ⇒