Факты и правила

Факты и правила

Логическое программирование — это направление современного про­грам­мирования, возникшее первоначально в рамках работ по ис­кусствен­ному интеллекту и получившее свое развитие во второй половине вось­мидесятых годов, благодаря японскому проекту ЭВМ пятого по­ко­ле­ния. Наиболее полное выражение идеи логического программирования наш­ли в языке Prolog (PROgramming in LOGic — программирование в терминах логики). Первоначальный вариант языка Prolog был разработан под руководством Алэна Кольмероэ (Alain Colmerauer) в Марсельском уни­верситете в 1972 году. В настоящее время существуют разнообразные версии   для DOS (PDC Prolog, Arity Prolog и др.), Windows (Visual Prolog,  Strawberry Prolog,   Trinc Prolog и др.), Linux (Arity Prolog, Visual Prolog и др.).

Теоретической основой Prolog является раздел символьной  логики, на­зы­ва­емый исчислением  предикатов.  Prolog присущ ряд свойств, ко­то­ры­ми не об­­ладают традиционные языки программирования, что делает его мощным сред­ством в области логического программирования. К та­ким свойствам от­но­сят­­ся механизм вывода с поиском и возвратом,  встро­ен­ный ме­ханизм со­постав­ле­­ния  с образцом  и простая, но   вы­ра­зи­тель­ная струк­тура данных с возможностью ее изменения. В Prolog отсут­ству­­ют ука­за­те­ли, операторы при­сва­ивания и GOTO. Естественным ме­то­дом про­грам­ми­ро­вания является ре­кур­сия.

Программа на Prolog есть  совокупность  утверждений.  Утверж­де­ния состоят из целей. В конце утверждения  ставится  точка  «.».   Иногда   ут­­вер­ж­дение   называется предложением.

Основная операция Prolog  —  доказательство  целей,  входящих  в ут­­верж­дение.

Существуют два типа утверждений:

·        факт — это одиночная цель, которая, безусловно, истинна;

·        правило состоит  из  одной  головной  цели  и  одной  или  более хвостовых целей, которые истинны при некоторых условиях.

Правило обычно имеет несколько хвостовых целей в форме конъюнкции целей.

Конъюнкцию можно рассматривать как логическую  функцию  И.  Таким образом, правило согласовано, если согласованы все его хвостовые цели.

Примеры фактов:

person (john).

мужчина (виктор).

нравиться (джон, мери).

Примеры правил:

человек (Х) :- мужчина(Х).

твистик(Кто_то) if человечек(Кто_то),

                   любит_танцевать(Кто_то, твист).

Выберем для реализации систему Visual Prolog (www.visual-prolog.com).

Решим задачу о родственных отношениях, так как Prolog хорошо приспособлен для обработки нечисловой информации.

Тот факт, что Том является родителем Боба, можно записать на Prolog так:

родитель(том, боб).

Здесь мы выбрали родитель в качестве имени отношения, том и боб — в качестве аргументов этого отношения. Записываем имена, как том, начиная со строчной буквы. Все дерево родственных отношений (семантическая сеть)

пам     том

  \    /   \

   боб    лиз

   /  \

энн   пат

       /

    джим

описывается следующей программой на языке Visual Prolog:

domains

  name=symbol

predicates

 родитель(name,name)

clauses

 родитель(pam,bob).

 родитель(tom,bob).

 родитель(tom,liz).

 родитель(bob,ann).

 родитель(bob,pat).

 родитель(pam,jim).

goal  родитель(bob,pat).

Для программирования необходимо 

1. Запустить систему Visual Prolog.

Рис. 12.1. Окно Visual Prolog 5.0

2. Ввести программу File ® New.

3. Протестировать цель Project®Test Goal.

На заданный вопрос: «Является Боб родителем Пат?» — система ответит  yes (да), найдя такой факт в программе.

Другой вопрос: «Кто является родителем Лиз?»

goal  родитель(X,liz).

Ответ системы

X=tom

1 Solution.

Вопрос «Кто дети Боба?» можно передать в такой форме:

goal родитель(bob, X).

Ответ

X=ann

X=pat

2 Solutions

Программе можно задавать и более общие вопросы: «Кто чей родитель?» Сформулируем его таким образом:

Найти   X  и   Y  такие, что  X   - родитель  Y.

На Prolog это записывается так:

goal родитель(X,Y).

Система будет по очереди находить все пары вида «родитель-ребенок».

X=pam, Y=bob

X=tom, Y=bob

X=tom, Y=liz

X=bob, Y=ann

X=bob, Y=pat

X=pam, Y=jim

6 Solutions

Запрограммируем задачу.

Даны утверждения:

Зевс — отец Ареса. Гера — мать Ареса. Арес — отец Гармонии. Аф­ро­ди­та — мать Гармонии. Карид — отец Семелы. Зевс — отец Диониса. Семела — мать Диониса. Божества — Зевс, Гера, Арес, Афродита. Гармония — царица.

Определить правила: женщина, мужчина, родитель, родители, дедушка, бабушка.

domains

   name=string

predicates

   отец(name, name)  % отец (Кто, Чей)

   мать(name, name)  % мать (Кто, Чья)

   божество(name)    % божество(Имя)

   царица (name)     % царица (Имя)

clauses

   отец("Зевс", "Арес").

   отец("Арес", "Гармония").

   отец("Карид", "Семела").

   отец("Зевс", "Дионис").

   мать( "Гера", "Арес").

   мать("Афродита", "Гармония").

   мать("Семела", "Дионис").

   божество( "Зевс").

   божество("Гера").

   божество("Арес").

   божество("Афродита").

   царица ( "Гармония").

Определим правило женщина, исходя из только описываемого мира.

X является женщиной, если X — мать кого-либо Y  или X — царица.

   женщина (X) if мать (X,_).

   женщина (X) if царица  (X).

Аналогично правило мужчина.

X  является  мужчина, если X — отец кого-либо Y.

   мужчина (X) if отец (X,_).

Правило  родитель.

X  родитель для Y, если X  отец  Y, либо X  мать  Y.

   родитель (X, Y) if отец (X, Y).

   родитель (X, Y) if мать (X, Y).

Правило  родители.

X и Y   родители , если X родитель Z и Y  родитель Z.

   родители (X, Y) if родитель (X, Z),
                           родитель (Y, Z).

Цели можно поставить следующие.

goal  женщина (Kto).% Кто является женщиной?

goal  мужчина (Kto).% Кто является мужчиной?

goal  родитель (X, "Дионис"). % Кто родители Диониса?

Решим задачу о родственных отношениях семьи Романовых, и найдем детей Алексея Михайловича.

     domains

        name=string

     predicates

       родитель(name, name) % родитель (Кто, Чей)

       мужчина(name)         % мужчина (Кто)

       женщина(name)       % женщина (Кто)

       царь(name, integer, integer) 

       % царь(Имя, начало_правления, конец_правления)

     goal родитель("Алексей Михайлович", X).

     clauses

       родитель("Михаил", "Алексей Михайлович").

       родитель("Алексей Михайлович", "Федор").

       родитель("Алексей Михайлович", "Иван").

       родитель("Алексей Михайлович", "Софья").

       родитель("Алексей Михайлович", "Петр I").

       родитель("Петр I", "Алексей").

       родитель("Екатерина II", "Павел I").

       родитель("Петр III","Павел I").

       мужчина("Михаил").

       мужчина("Алексей Михайлович").

       мужчина("Федор").

       мужчина("Иван").

       мужчина("Петр I").

       мужчина("Алексей").

       мужчина("Павел I").

       мужчина("Петр III").

       женщина("Софья").

       женщина("Екатерина II").

       царь("Михаил", 1613, 1645).

       царь("Алексей Михайлович", 1645 ,1676).

       царь("Федор",1676 ,1682).

       царь("Иван",1682 ,1696).

       царь("Софья",1682 ,1689).

       царь("Петр I",1682 , 1725).

       царь("Екатерина II", 1762, 1796).

       царь("Петр III", 1761,1762 ).

       царь("Павел I",1796 ,1801 ).

Ответ системы:

X=Федор

X=Иван

X=Софья

X=Петр I

4 Solutions

Найдем всех цариц с помощью составного вопроса.

goal царь(X,_,_),женщина(X).

X=Софья

X=Екатерина II

2 Solutions

Добавим несколько правил: брат (brother), сколько_правил (how_reign).

predicates

  brother (name,name)

  how_reign (name,integer)

clauses

  brother(X, Y) if родитель(Z, X) and %(1)

                   родитель(Z, Y) and %(1)

                   мужчина(X) and      %(2)

                   X<>Y.               %(3)

  how_reign(Name, H) :- царь(Name, H1, H2),

                        H=H2-H2.

Правило определения брата можно прочитать так:

Для любых X и Y

            X является братом Y, если

            1) у X и Y есть общий родитель , и

            2) X - мужчина, и

            3) X сам себе не брат.

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

Для этого в Prolog существует ограничивающая перебор цель «отсечение» (!),  которая безусловна  верна.

Найдем только одного сына Алексея Михайловича

goal родитель(“Алексей Михайлович”,Son),

     мужчина(Son),!.

Son=Федор

1 solution

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

predicates

  max(integer, integer, integer)

goal max(5,9, Max).

clauses

  max(X,Y,Max) if X>=Y, Max=X.

  max(X,Y,Max) if X<Y, Max=Y.

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

max(X,Y,X) if X>=Y, !.

max(X,Y,Y).

Prolog содержит стандартный предикат, выполнение которого закан­чивается всегда неудачей — fail. Предикат fail инициирует процесс бэктрекинга (backtracking), то есть  поиска новых решений, или передоказательства целей. Покажем на примере.

domains

  name=symbol

predicates

  отец (name, name)

  everybody

clauses

  отец ("Leonard", "Katherine").

  отец ("Carl", "Jason").

  отец ("Carl", "Marilyn").

everybody if

    отец (X, Y) and

    write(X,"является для ",Y," отцом\n") and

    fail.

goal everybody.

Ответ системы:

Leonard является для Katherine отцом 

Carl является для Jason отцом 

Carl является для Marilyn отцом 

no

Цель everybody завершена неудачно.

Для реализации отрицания используется предикат not. Особенность его ис­пользования состоит в том, что все переданные пе­ре­менные должные быть свя­занными, то есть конкретизированными. Например, ответ на вопрос: «Леонард не отец Джейсону?» будет найден.

goal not(отец ("Leonard","Jason")).

yes

Цель

goal not(отец (X,"Jason")).

не будет восприниматься  системой. Можно переформулировать цель: «Кто из известных системе отцов не является отцом Джейсона?».

goal отец (X,_), not(отец (X,"Jason")).

X=Leonard

1 Solution

Таким образом, нельзя получить знание из незнания, и предикат not используется только для проверки целей.

В приведенных программах на Visual Prolog можно выделить и дополнить:

·        секции

·        основная операция, выполняемая на Prolog, — это операция сопоставления (назы­ваемая также унификацией или согласованием). Операция со­по­став­ления может быть успешной или закончиться неудачей;

·        переменные обозначаются последовательностью букв и цифр, на­чи­­нающейся с заглавной буквы. Особый вид переменной — анонимная переменная _, ис­поль­зуемая в ка­честве  аргумента предиката, когда конкретное значение пе­ре­­менной несущественно. На переменные в правилах действуют кванторы общности. Переменные получают свои значения  в результате сопоставления с константами в фактах или правилах. Переменные  служат частью процесса со­поставления, а не «хранилищем» информации. Область действия пе­ре­мен­ной — ровно одно предложение;

·        факты — это предикаты с аргументами-константами, обозначающие от­но­ше­ния между объектами или свойства объектов, именованными этими кон­стантами. Факты в программе считаются всегда безусловно истинными и служат основой доказательства, происходящего при выполнении программы;

·        правила — фразы с заголовком и одной или несколькими подцелями-предикатами, имеют форму

                  <голова правила> :- <список подцелей>.

или

                  <голова правила> if <список подцелей>.