2.5 Формальные логические модели на основе исчисления предикатов

Предикат – это функция от одной или нескольких переменных, возвращающая значения true или false.

Предикаты могут быть:

• унарные;

• бинарные.

Пример 2.5

1) Унарный предикат:

директор(Иванов)

2) Бинарный предикат:

является(Иванов, директор)

В общем случае n-арный предикат:

роль1(имя1, значение1) роль2(имя2, значение2) … роль n(имя n, значение n)

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

Пример 2.6

Продавцом товара является фирма «Компьютер и офис», покупателем товара является Иванов, вид товара – компьютер.

1) продавец(Компьютер и офис)  покупатель(Иванов)  товар(ПК)

2) продавец(товар, Компьютер и офис)  покупатель(Иванов)  товар(ПК)

Для записи правил в логической модели используется специальная форма представления правил – клаузальная форма.

заключение :– условие1, условие2

Если истинны все условия, то истинно заключение.

Пример 2.7

Если «Альфа-банк» имеет гарантии платежеспособности клиента, и эти гарантии принимаются для предоставления кредита, то он предоставляет кредит.

Введем:

А – имеет.

В – использует.

С – предоставляет.

Получаем:

С(Альфа-банк, решение о кредите) :–

А(Альфа-банк, гарантии), В(гарантии, решение о кредите).

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

Например:

C(X,Y) :– A(X,Z), B(Z,Y)..

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

Пример 2.8

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

Никто из скалолазов не любит дождь.

Все горнолыжники любят снег.

Майкл любит все то, что не любит Том.

Майкл не любит то, что любит Том.

Джон любит снег.

Том любит снег и дождь.

Вопрос:

Кто есть кто?

Анализируя исходные данные, можно сделать следующие выводы:

Том является только горнолыжником.

Майкл не горнолыжник, а скалолаз.

Джон – горнолыжник.

Domains

Name = tom, mikle, john.

Weather = rain, snow.

Spec = sk, gor.

Predicates

club(Name).

like(Name, Weather).

nolike(Name, Weather).

is(Name, Spec).

question

clauses

club(tom). club(mikle). club(john).

like(tom, snow).

like(tom, rain).

like(john, snow).

like(mikle, X) :- not(like(tom, X)).

nolike(X, Y) :- not(like(X, Y)).

nolike(mikle, Y) :- like(tom, Y).

is(X, gor) :- club(X), like(X, snow).

is(X, sk) :- club(X), nolike(X, rain).

question :- nl, is(Name, sk), not(is(Name, gor)), write(“Только скалолаз”, Name), nl, fail.

question :- nl, is(Name, gor), not(is(Name, sk)), write(“Только горнолыжник”, Name) , nl, fail.

question :- nl, is(Name, sk), is(Name, gor), write(“Горнолыжник и скалолаз”, Name) , nl, fail.

question :- nl, is(tom, Spec), write(“Том -”, Spec) , nl, fail.

question :- nl, write(“Стоп”).

goal

question.

Тема 3. Язык Пролог.

3.1 Пролог с процедурной точки зрения.

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

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

1) Обращение к некоторой цели на Прологе равносильно вызову процедуры, а порядок высказываний, составляющих цели или правила, соответствует последовательности операторов:

A :- B1, B2, … , Bn.

Procedure A()

begin

call B1

call B2

…

call Bn

end.

2) Рекурсивный вызов цели на Прологе подобен рекурсивной функции в обычных языках.

3) Структуры данных в логических программах (термы) соответствуют общим структурам записи в процедурных языках, хотя Пролог является бестиповым языком, в котором объявления данных необязательны.

4) В Прологе используются логические переменные, которые соотносятся с некоторыми объектами, а не с ячейками памяти.

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

5) В логическом программировании обработка данных полностью заложена в алгоритме унификации.

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

Predicates

Z

clauses

Z :- nl, love(anna, flowers), write(“Yes”).

Z :- nl, not(love(anna, flowers)), write(“No”).

Z :- nl, write(“Unknown”).

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

Predicates

action(integer)

clauses

action(1) :- nl, write(“1”), nl, !.

action(2) :- nl, write(“2”) , nl, !.

action(N) :- nl, N<>1, write(“Unknown”).

goal

write(“Select 1 or 2”),

readint(C),

action(C).

Примечание 1: В предикате action переменная С должна быть связанной (иметь значение, которое определяется в предикате readint). Если бы переменная С была свободной, т.е. ее значение было не определено, то Пролог выдал бы ошибку компиляции.

Примечание 2: Предикат «!» задает отсечение, прекращая поиск других альтернатив, если текущая альтернатива сработала. В данном примере используется «зеленое» отсечение, которое не дает большого выигрыша при поиске, но исключает риск ошибок поиска. Другой вариант – «красное» отсечение, которое меняет логику работы программы.

Например:

action(1) :- !, nl, write(“1”).

action(2) :- !, nl, write(“2”).

action(N) :- nl, write(“Unknown”).

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

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

Если нужно найти все возможные решения, даже если цель достигнута хотя бы один раз, то используют специальный предикат fail, который ставит очередной запрос в состояние “false” и автоматически инициализирует поиск с возвратом.

9) Организация циклов в программах на Прологе возможна по аналогии с рекурсией или при откате (срабатывает fail). Операторы for, while, repeat отсутствуют.