Стратегии

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

Выполнение программы на ПРОЛОГЕ следует другой стратегии: отрицание вопроса программы принимается за цель. Далее вычисляются резольвенты, порождаемые целью и каким-либо правилом или фактом, которые просматриваются последовательно сверху вниз. Если резольвента существует при наиболее общей унификации, она вычисляется. Если пустая резольвента с помощью такой стратегии не найдена, то ответ на вопрос отрицателен. В нашем примере резольвентой утверждений: птица(ворона) и птица(Х)откладывает_яйца(Х),имеет_крылья(Х) является дизъюнкт, включающий отрицания двух утверждений: отладывает_яйца(Х) и имеет_крылья(Х). Эта пара становится новой целью, для которой снова ищется резольвента. Очевидно, что если в процессе вычислений найдена пустая резольвента, ответ на заданный вопрос утвердительный. Результатом программы на ПРЛОГЕ являются также и значения переменных, конкретизированные алгоритмом унификации в процессе вычислений - т.е. те значения параметров. при которых справедливо заключение. В примерах далее будем использовать прописные буквы для обозначения переменных, а строчные буквы - для имен конкретных объектов универсума.

Рассмотрим вычисление Программы 1:

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

Рассмотрим вычисление этой же программы с другой целью: 7:?птица(Х), что означает "Существует ли (произвольная) птица?". Пользователя обычно интересует не только сам факт успешного вычисления программы, но и конкретное значение переменной Х, при котором это возможно:

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

Программа_2::

1: Grandparent(X,Y)  Parent(X,Z), Parent(Z,Y)

2: Parent(elizabeth, charles)

3: Parent(charles, william)

4: Parent(charles, henry)

Содержательный смысл утверждений здесь очевиден. В качестве цели может быть выбрана любая из следующих:

5-а: ?Grandparent(elizabeth, henry);

5-b: ?Grandparent(elizabeth, V);

5-c: ?Grandparent(U, henry);

5-d: ?Grandparent(U, V).

Рассмотрим все возможные вычисления программы 2 при цели 5-d:

В качестве последнего примера из [GL88] рассмотрим логическую программу сортировки списка. Будем считать, что если у списка L выделены начальный элемент (голова) H и весь остальной список Т (хвост), то список L будем записывать как L=H:T.

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

1. Sort(H:T,S)Sort(T,L),Insert(H,L,S)

Смысл этого утверждения следующий: "список S является результатом сортировки списка H:T, если L является результатом сортировки списка T и S есть результат вставки элемента H в подходящее место списка L". Это определение справедливо для всех списков, кроме пустых; этот частный случай можно учесть указанием конкретного факта: пустой список уже отсортирован:

2. Sort([],[])

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

3. Insert(X,H:T,X:H:T)  Precedes(X,H)

Это утверждение имеет следующий смысл: "Если элемент X предшествует по порядку элементу Н, то результатом вставки X в отсортированный список H:T является отсортированный список X:H:T".

Если элемент H предшествует элементу X в списке H:T, то этот случай можно описать так:

4. Insert(X,H:T,H:T1)  Precedes(X,H), Insert(X,T,T1)

что можно интерпретировать так: "Результатом вставки X в отсортированный список H:T является список H:T1, если H предшествует X и T1 является отсортированным списком, получаемым после вставки X в отсортированный список T".

Кроме того, следует определить вставку элемента в пустой список:

5. Insert(X,[],[X]).

Таким образом, полная программа сортировки списка имеет пять операторов - утверждений:

Программа_3::

1. Sort(H:T,S)  Sort(T,L), Insert(H,L,S)

2. Sort([],[])

3. Insert(X,H:T,X:H:T)  Precedes(X,H)

4. Insert(X,H:T,H:T1)  Precedes(X,H), Insert(X,T,T1)

5. Insert(X,[],[X]).

Эту программу мы можем использовать многими различными способами, задавая различные цели. Например, "?Sort([dog cat pig], [cat dog pig])". При этой цели вычисление проверит, действительно ли список [cat dog pig] является отсортированной версией списка [dog cat pig]. При цели: "?Sort([dog cat pig], S)" вычислитель Пролога поместит в переменную S отсортированный список [dog cat pig]. При цели: "?Sort(S, [cat dog pig])" в переменную типа список S будут подставляться все перестановки элементов отсортированного списка [dog cat pig].

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

Язык Пролог имеет множество применений. Рассмотрим в качестве простого примера его применения анализ логических схем [C87]. На рис. 2.4 представлена логическая схема полусумматора - основного блока двоичных сумматоров.

Рис. 2.4. Схема полусумматора

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

half_add(A,B,S,C)  xor(A,B,S), nand(A,B,T1), not(T1,C).

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

xor(0,0,0).

xor(0,1,1).

xor(1,0,1).

xor(1,1,0).

nand(0,0,1).

nand(0,1,1).

nand(1,0,1).

nand(1,1,0).

not(0,1).

not(1,0).

Целями Пролога для этой программы могут быть, например, следующие:

? half_add(0,0,S,C).

(Каковы выходы S и C этой схемы при входах 0,0? Ответ - S=0, C=0.)

? half_add(A,B,0,1).

(При каких входах выход S будет единичным, а выход C - нулевым? Ответы - А=0, В=1; А=1, В=0.)

? half_add(А,В,Х,Х).

(При каких входах схемы выходы S и С будут совпадать? Ответ - А=0, В=0, Х=0.)

? half_add(X,X,X,1).

(Может ли быть у схемы выход С равным 1 при одинаковых значениях ее входов и выхода S? Ответ - no.)

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