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

    (1)        образцом, соответствующим предварительному условию запуска, и

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

Запуск модулей на выполнение происходит при появлении тех или иных конфигураций в информационной среде системы. Такую информационную среду обычно называют базой данных. Наглядное представление о системе рассматриваемого типа дает рис. 16.1.

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

Доказательство теоремы (а=>b)&(b=>с)=>(a=>с)...

На рис. 16.6 показан процесс применения резолюций, начинающийся с отрицания нашей предполагаемой теоремы и заканчивающийся пустым дизъюнктом.

На рис. 16.7 мы видим, как резолюционный процесс можно сформулировать в форме программы, управляемой образцами. Программа работает с дизъюнктами, записанными в базе данных. В терминах образцов принцип резолюции формулируется следующим образом:

        если
                        существуют два таких дизъюнкта  С1  и  С2,   что
                        P   является (дизъюнктивным) подвыражением  С1,
                        а   ~Р  -  подвыражением  С2
        то
                        удалить   Р  из  С1  (результат -  СА),   удалить  ~Р
                        из   С2  (результат -  СВ)  и добавить в базу
                        данных новый дизъюнкт  СА  v  СВ.

На нашем формальном языке это можно записать так:

        [ дизъюнкт( С1), удалить( Р, Cl, CA),
          дизъюнкт( С2), удалить( ~Р, С2, СВ) ] --->
        [ assert( дизъюнкт( СА v СВ) ) ].

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

        сделано( Cl, C2, Р)

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

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

        a  v  b  v   a

в более простое выражение  a  v  b.   Другое правило распознает те дизъюнкты, которые всегда истинны, например,

        a  v  b  v   ~а

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

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

% Противоречие

        [ дизъюнкт( X), дизъзюнкт( ~Х) ] --->
        [ write( 'Обнаружено противоречие'), стоп].

% Удалить тривиально истинный дизъюнкт

        [ дизъюнкт( С), внутри( Р, С), внутри( ~Р, С) ] --->
        [ retract( С) ].

% Упростить дизъюнкт

        [ дизъюнкт( С), удалить( Р, С, С1), внутри( Р, С1) ] --->
        [ заменить( дизъюнкт( С), дизъюнкт( С1) ) ].

% Шаг резолюции, специальный случай

        [ дизъюнкт( Р), дизъюнкт( С), удалить( ~Р, С, С1),
                            not сделано( Р, С, Р) ] --->
        [ аssеrt( дизъюнкт( С1)), аssert( сделано( Р, С, Р))].

% Шаг резолюции, специальный случай

        [ дизъюнкт( ~Р), дизъюнкт( С), удалить( Р, С, С1),
                            not сделано( ~Р, С, Р) ] --->
        [ assert( дизъюнкт( C1)), аssert( сделано( ~Р, С, Р))].

% Шаг резолюции, общий случай

        [ дизъюнкт( С1), удалить( Р, С1, СА),
          дизъюнкт( С2), удалить( ~Р, С2, СВ),
          not сделано( Cl, C2, Р) ] --->
        [ assert( дизъюнкт( СА v СВ) ),
          assert( сделано( Cl, C2, Р) ) ].

% Последнее правило: тупик

       [ ] ---> [ write( 'Нет противоречия'), стоп ].

% удалить( Р, Е, Е1) означает, получить из выражения Е
% выражение Е1, удалив из него подвыражение Р

        удалить( X, X v Y, Y).

        удалить( X, Y v X, Y).

        удалить( X, Y v Z, Y v Z1) :-
                удалить( X, Z, Z1).

        удалить( X, Y v Z, Y1 v Z) :-
                удалить( X, Y, Y1).

% внутри( Р, Е) означает Р есть дизъюнктивное подвыражение
% выражения Е

        внутри( X, X).

        внутри( X, Y) :-
                удалить( X, Y, _ ).

Программирование в терминах типовых конфигураций

Глава 16. ПРОГРАММИРОВАНИЕ В ТЕРМИНАХ ТИПОВЫХ КОНФИГУРАЦИЙ

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

Литература

Waterman and Hayes-Roth (1978) - классическая книга по системам, управляемым образцами. В книге Nilsson (1980) можно найти фундаментальные понятия, относящиеся к задаче автоматического доказательства теорем, включая алгоритм преобразования логических формул в конъюнктивную нормальную форму. Прологовская программа для выполнения этого преобразования приведена в Clocksin and Mellish (1981).

Clocksin F. W. and Mellish С S. (1981). Programming in Prolog. Springer- Verlag. [Имеется перевод: Клоксин У., Мелиш К. Программирование на языке Пролог. - М.: Мир, 1987.]

Nilsson N. J. (1980). Principles of Artificial Intelligence. Tioga; Springer-Verlag.

Waterman D. A. and Hayes-Roth F. (1978, eds). Pattern-Directed Inference Systems. Academic Press.

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

В качестве иллюстрации, рассмотрим элементарное упражнение по программированию - вычисление наибольшего общего делителя  D   двух целых чисел  А  и  В.   Рассмотрим классический алгоритм Евклида:

Для того, чтобы вычислить наибольший общий делитель  D  чисел  А  и  В,   необходимо:

        Повторять циклически, пока  А  и  В  не совпадут:

        если  А > В,   то заменить  А  на  А - В,   иначе заменить  В  на  В - А.

        После выхода из цикла   А  и  В  совпадают; наибольший общий делитель  D  равен
        А  (или  В).

Тот же самый процесс можно описать при помощи двух модулей, управляемых образцами:

Модуль 1

Условие             В  базе данных существуют такие два числа  X  и   Y,  что  X > Y.

Действие           Заменить  X   на разность  X - Y.

Модуль 2

Условие             В  базе данных имеется число  X.

Действие           Выдать результат   X  и остановиться.

Очевидно, что всегда, когда условие Модуля 1 удовлетворяется, удовлетворяется также и условие Модуля 2, и мы имеем конфликт. В нашем случае конфликт можно разрешить при помощи простого управляющего правила: всегда отдавать предпочтение Модулю 1. База данных первоначально содержит числа  А  и  В.

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

Преобразование пропозициональных формул в множество дизъюнктов с записью их в базу данных при помощи assert.

        ?-  транс( ~(( а=>b) & ( b=>c) => ( а=>с))  ),  пуск.

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

% Простой интерпретатор для программ, управляемых образцами
% Работа с базой данных производится при помощи процедур
% assert и retract

        :- ор( 800, xfx, --->).

        пуск :-
                Условие ---> Действие,                                 % правило
                проверить( Условие),                                     % Условие выполнено?
                выполнить( Действие).

        проверить( [ ]).                                                        % Пустое условие

        проверить( [Усл | Остальные]) :-                         % проверить конъюнкцию
                call( Усл),                                                          % условий
                проверить( Остальные).

        выполнить( [ стоп] ) :-   !.                                       % Прекратить выполнение

        выполнить( [ ]) :-                                             % Пустое действие (цикл завершен)
                пуск.                                                          % Перейти к следующему циклу

        выполнить [Д | Остальные] ) :-
                саll( Д),
                выполнить( Остальные).

        заменить( А, В) :-                                             % Заменить в базе данных А на В
                retract( A),  !,
                assert( В).

Простая программа для автоматического докаэательства теорем

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

        р  v ~ р

и означающее  "р  или  не  р",   верно всегда, независимо от смысла утверждения  р.

Мы будем использовать в качестве операторов следующие символы:

    ~           отрицание, читается как  "не"
    &           конъюнкцию, читается как  "и"
    v            дизъюнкцию, читается как  "или"
    =>        импликацию, читается как  "следует"

Согласно правилам предпочтения операторов, оператор "не" связывает утверждения сильнее, чем "и", "или" и "следует".

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

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

        (а  =>  b) & (b   =>  с) => (а  =>  с)

Смысл этой формулы таков: если из  а   следует  b  и из  b  следует   с,  то из  а  следует  с.

        (р1  v  p2   v  ...)  &  (q1  v  q2   v  ...)
                                        &   (r1  v  r2  v  ...)   &  ...

Любую пропозициональную формулу нетрудно преобразовать в такую форму. В нашем случае это делается следующим образом. У нас есть исходная формула

        (а  =>  b)   &  (b  =>  с)  =>  (а  =>   с)

Ее отрицание имеет вид

        ~ ( (а  =>  b) & (b  =>  с) => (а  =>  с) )

Для преобразования этой формулы в конъюнктивную нормальную форму можно использовать следующие известные правила:

    (1)        х  =>   у                     эквивалентно                 ~х   v  у
    (2)        ~(x   v  y)                    эквивалентно                 ~х   &  ~у
    (3)        ~(х   &  у)                   эквивалентно                 ~х   v  ~у
    (4)        ~( ~х)                         эквивалентно                   х

Применяя правило 1, получаем

        ~ ( ~ ( (a  =>  b)   &  (b  =>  с))  v  (а  =>   с) )

Далее, правила 2 и 4 дают

        (а  =>  b)   &  (b  =>  с)  &  ~(а   =>  с)

Трижды применив правило 1, получаем

        (~ а  v  b)   &  (~b  v  с)  &  ~(~а   v  с)

И наконец, после применения правила 2 получаем искомую конъюнктивную нормальную форму

        (~а  v  b)   &  (~b  v  с)  &  а   &  ~с

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

Шаг резолюции порождает третий дизъюнкт:

        Y  v  Z

Нетрудно показать, что этот дизъюнкт логически следует из тех двух дизъюнктов, из которых он получен. Таким образом, добавив выражение (Y   v  Z) к нашей исходной формуле, мы не изменим ее истинности. Резолюционный процесс порождает новые дизъюнкты. Появление "пустого дизъюнкта" (обычно записываемого как "nil") сигнализирует о противоречии. Действительно, пустой дизъюнкт nil  порождается двумя дизъюнктами вида

        x    и     ~x

которые явно противоречат друг другу.

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

Простой интерпретатор для программ, управляемых образцами, показан на рис. 16.5. Следует признать, что в интерпретаторе допущены значительные упрощения. Так, например, в него заложено чрезвычайно простое и жесткое правило разрешения конфликтов: всегда запускать первый из потенциально активных модулей (в соответствии с тем порядком, в котором модули записаны в программе). Таким образом, программисту предоставлено единственное средство управления процессом интерпретации - он может указать тот или иной порядок следования модулей. Начальное состояние базы данных задается в виде прологовских предложений, записанных в исходной программе. Запуск программы производится при помощи вопроса

        ?-  пуск.