Составные цели-запросы

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

В случае связки "или" переменные в подцелях являются локальными, и связывания одноименных переменных не происходит.

Например, в правиле

c(X):-a(X);b(X).

в подцелях a(X) и b(X) переменные X не будут связаны. Это правило можно заменить двумя:

c(X):-a(X).

c(X):-b(X).

ЗАДАНИЕ 2.2

a) Набейте базу:/* авто(Марка,Цена,Цвет,Возраст) - предикат */

авто(москвич,9500,зеленый,1).

авто(москвич,3000,синий,5).

авто(волга,15000,черный,1).

авто(волга,8000,белый,6).

авто('УАЗ',9000,зеленый,3).

авто('ВАЗ',6000,белый,4).

авто('ВАЗ',4000,синий,10).

авто('ВАЗ-2108',8000,серый,2).

b) Задайте вопрос: "Найти автомобиль с ценой меньше 5000, любого цвета, и любым сроком эксплуатации."

c) Добавьте к базе правило: "Следует купить автомобиль, если он зеленый или синий, не дороже некоторой суммы и его срок эксплуатации меньше 3-х лет".

d) Задайте вопрос к полученной программе: "Какие автомобили можно купить за 10000?" Найдите все решения.

СОСТАВНЫЕ ОБЪЕКТЫ

Составные объекты или структуры состоят из имени структуры-функтора и нескольких компонент структуры, которые могут быть любыми объектами, в том числе структурами.

ЗАДАНИЕ 2.3

Нарисуйте деревья для структур:

авто(марка('ВАЗ',2108),цвет(синий),цена($(7500))).

имеет(студент('Олег'),книга('Грибоедов','Горе от ума')).

ЗАДАНИЕ 2.4

a) Введите базу:

имеет('Олег', книга('Пушкин','Капитанская дочка')).

имеет('Лена', книга('Монтень','Опыты')).

имеет('Ира',платок(синий)).

имеет('Лена', платок(красный)).

ЗАМЕЧАНИЕ. Для создания операторной формы предиката с функтором Name можно воспользоваться встроенным предикатом op(Precedence, Type, Name), где Precedence – приоритет вводимого оператора (целое неотрицательное число), Type – тип вводимого оператора (инфиксный, постфиксный и т.п.). Операторная форма позволяет записывать факты, запросы и правила в операторном виде. Разъясним это на примере.

?-op(550,xfx,имеет).

Здесь тип xfx значит, что оператор имеет не обладает ни правой, ни левой ассоциативностью (в отличие от случаев xfy и yfx соответственно). После выполнения такого запроса можно ввести вышеуказанный факт в виде:

'Олег' имеет книга('Пушкин','Капитанская дочка').

Так же можно написать запросы в функциональной и операторной формах:

?- имеет(Б,Ъ).

Б = 'Олег',

Ъ = книга('Пушкин', 'Капитанская дочка').

?- Б имеет Ъ.

Б = 'Олег',

Ъ = книга('Пушкин', 'Капитанская дочка').

Как видно из выполнения запросов операторная и функциональная формы записи предикатов дают один и тот же результат. Подробнее о предикате op/3 можно прочитать во встроенной справке (для запуска справки можно использовать запрос?-help(op). или?-help(op/3).).

b) Задайте вопросы к этой базе данных:

Кто имеет какую-нибудь книгу Монтеня?

Кто какую книгу имеет?

Кто что имеет?

Верно ли, что Лена имеет синий платок?

ОТРИЦАНИЕ В ПРОЛОГЕ

Логическая операция "не" - отрицание в SWI/PROLOG - обозначается через not и применяется к предикатам. Отрицание некоторого предиката является истинным, если невыполнимым является исходный предикат, т.е. не существует возможности доказательства его истины.

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

Чаще всего операция not используется в определении цели "проверка" в схеме программирования "метод генерации и проверки", который состоит в порождении множества кандидатов в решение и дальнейшей их фильтрации:

решение(X):-кандидат(X),проверка(X).

ЗАДАНИЕ 2.5

Задайте к базе из задания 1.5 запросы:

Кто живет ровно в одной среде обитания?

Кто живет хотя бы в двух (ровно в двух) средах обитания?

ЗАДАНИЕ 2.6

a) Опишите базу знаний на Прологе со следующими фактами:

Иван имеет 10000 руб. Иван имеет телевизор. Иван имеет машину-вишневую "Волгу". Иван имеет магнитофон. Петр имеет 5000 руб. Петр имеет телевизор. Петр имеет холодильник. Коля имеет 20000 руб. Коля имеет телевизор.

имеет('Иван',rub(10000)). имеет('Иван','телевизор'). …

b) Задайте к ней вопросы:

Что имеет Петр?

Кто имеет 10000 рублей?

Кто что имеет?

Какие вещи имеет Иван, которых нет у Николая?

(Деньги - не вещь)

c) Добавьте к этой базе данных следующие факты:

Цена машины "Волга"-32000.

Цена телевизора- 8400.

Цена холодильника - 4200.

Цена магнитофона - 3500.

Цена видео - 12000.

Цена приемника - 1300.

Цена часов - 500.

d) Задайте к расширенной базе вопросы:

Может ли Петр купить видео?

У кого больше всего денег?

e) Введите правило, определяющее, что некто может купить вещь, если у него хватит денег и этой вещи у него нет.

f) Задайте вопросы:

Что может купить Коля?

Что может купить Коля из того, что имеет Иван?

g) Добавьте к базе следующие факты:

Анна является женой Коли.

Мария является женой Ивана.

Ольга является женой Петра.

h) Введите правило, что "у жены есть все, что есть у мужа".

i) Задайте вопросы:

Имеет ли Мария машину?

Что может купить Анна, чего не имеет Мария?

РЕКУРСИЯ В ПРОЛОГЕ

ЦЕЛЬ: Знакомство с основным методом программирования в Прологе - рекурсией. Замена рекурсии итерацией (программирование с накопителями). Арифметические предикаты.

РЕКУРСИЯ

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

Рекурсивное правило в общем случае имеет следующий вид:

R:- A,U,В,R,С.

где R - предикат, определяющий рекурсивный вызов, U - предикат, определяющий условие выхода из рекурсии по неуспеху, А,В,С - группы предикатов, не влияющие на рекурсивный вызов. В процессе рекурсии предикаты группы С запоминаются и выполняются лишь по завершении рекурсии ( обратный ход ).

ПРОГРАММА 1.

song:- write('бегу,'),song.

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

?- write('Я '),song.

Как видно, в процессе выполнения программы возникает бесконечно длинная строка. Это пример так называемой бесконечной рекурсии ("зацикливание" программы).

Запустите программу, когда надоест любоваться красотами написания этой песни, нажмите на клавишу b для приостановки бесконечного вывода или e - для выхода из интерпретатора.

Подобные программы не представляют интереса, поскольку в них отсутствует условие выхода. Условием выхода из рекурсии обычно является некий факт или правило, при успешном выполнении которого программа заканчивает свою работу.

Рассмотрим следующий вариант программы.

ПРОГРАММА 2.

song(X):-(X>1),write('бегу,'),(Y is X - 1),song(Y).

song(1).

?-write('Я '),song(3),write('бегу по гаревой дорожке').

В данной программе используются встроенные арифметические предикаты отношения (X > Y) и присваивания (X is A, где X – свободная переменная, а A - арифметическое выражение, конкретизированное числовым значением).

ЗАДАНИЕ 3.1

Запустите программы 1 и 2.

Рассмотрим задачу нахождения факториала некоторого целого неотрицательного числа.

ПРОГРАММА 3.

Рекурсивное вычисление факториала (вариант 0).

factorial(1,1). /* Условие выхода из рекурсии 1!=1 */

factorial(N,F):-

N>1,

N1 is N-1,

factorial(N1, F1),

F is N*F1.

Рассмотрим дерево вывода ответа на вопрос:

?-factorial(3,X).

Слева на рисунке прямой ход до факта, останавливающего рекурсию (шаги с 1 по 9). Обратный ход с подсчетом результата – это шаги 10 и 11. В программе несколько точек возврата, но все альтернативные ветви ложны.

ЗАДАНИЕ 3.2

Запустите программу с отладчиком (переход в режим отладки производится с помошью предиката debug). Не забудьте установить контрольные точки или точки трассировки. Введите запросы:

?-factorial(3,X).

?-factorial(1,X).

?-factorial(0,X).