R, s, t, u, v, w, x, y, z.

Правила вывода, представленные в виде продукций, таковы:

1) r –> t4)s –> u7)w, x --> y

2) u –> t5) r, t, v –> w8)u, w, x --> z

3) r, u –> v6)u, y –> w9)r, w –> z

Будем считать, что установленными являются утверждения rи sи нашей задачей является установить, выводимо ли утверждение z.

Прямая стратегия.

Результаты работы алгоритма, реализующего прямую стратегию, можно представить в виде таблицы, состоящей из следующих столбцов: № шага, номера активизированных продукций, и факты, попадающие в базу данных в процессе работы алгоритма. Перед началом работы (шаг 0) в базу данных заносятся факты, считающиеся доказанными a priori, т.е. начальные условия. Затем активизируются все продукции, антецеденты которых состоят только из фактов, находящихся в БД. Консеквентны активизированных продукций заносятся в БД. Работа алгоритма прекращается, когда на очередном шаге в БД не будет занесен ни один новый факт. Возможен и другой вариант окончания работы: если требуется вывести указанные утверждения, работу можно закончить, когда все они попадут в БД. Ниже приведена таблица вывода утверждения z при указанных выше начальных условиях.

Вывод получен.

Обратная стратегия.

Алгоритм, реализующий обратную стратегию, осуществляет построение специального дерева вывода. Построение дерева начнем с корня, который пометим утверждением, истинность которого требуется установить. Остальные вершины будем помечать левыми частями продукций (заметим, что при необходимости вывести несколько утверждений, понадобится сформировать «лес» – т.е. по одному дереву для каждого утверждения). Дуги дерева будем помечать номерами в соответствии с порядком их построения и номерами продукций в скобках. На каждом шаге требуется найти продукцию, в правой части которой находится анализируемое утверждение. На первом шаге выберем утверждение, помечающее корень. Дальнейшие шаги алгоритма проиллюстрируем выводом утверждения z в БЗ примера:

Поясним работу алгоритма. Его начальным условием является установленные a priori факты r и s. На первом шаге ищем первую продукцию, в правой части которой находится z. Это продукция 8. В стеке возвратов запоминаем, что дальнейший просмотр продукций при возврате на этот шаг следует начинать с продукции 9. Формируем вершину u,w,x и строим в нее дугу из вершины z. Из вершины u,w,x необходимо построить три вершины и три дуги по продукциям, в правых частях которых находятся утверждения u, w и x. Сначала строим первую пару – вершину s и дугу 2(4). Дуга 2(4) позволяет вывести утверждение u и занести его в список установленных фактов (БД). Затем строим пару r,t,v и дугу 3(5). r – установленный факт, а построение вершин r и r,u и дуг 4(1) и 5(3) позволяет считать выведенными факты t, v и w. Однако утверждение х в правых частях продукций отсутствует. Поэтому продолжение вывода невозможно – возник тупик и данный вариант вывода оказался непродуктивным.

Используя стек возвратов, ищем другое правило для z. Это правило 9. Применив его, завершаем вывод. В таблице в правой части рисунка 2 содержатся списки установленных фактов (содержимое БД) после каждого шага вывода.