3.2.3. Алгоритмы логического вывода в условиях определенности

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

• нахождение всех возможных заключений из фактов и правил;

• изучение предпосылок заключений с целью определения их истинности.

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

3.2.3.1. Алгоритм прямого вывода

Инициализация состоит в подготовке структур данных к работе с фактами. В частности, здесь в массив VARсостояния логических переменных заносится значениеNI- не инициализировано. В этом массиве размерностьюK, гдеK- число логических переменных в БЗ, отмечается состояние переменной на текущей стадии вывода - инициализирована/не инициализирована.

Затем вводится номер iлогической переменной и ее значение, которое записывается в массивVARзначений логических переменных, после чего устанавливается флагVARI_i(оператор 4) инициализации соответствующей логической переменной. Номер переменной заносится в очередьQпеременных логического вывода. В этой очереди хранятся номера переменных, которые были проинициализированы, но не были рассмотрены следующие из них заключения.

Рис. 4.4. Алгоритм прямого логического вывода

Рис. 4.5. Алгоритм обратного логического вывода

На каждой итерации цикла из Qизвлекается номер логической переменной и производится исследование всех продукций, в которых она входит в левую часть. Всего в БЗ системыNправил, которые содержатся в массиве структурR. Каждая структура включает в себя:C- массив условий правила,CONST- индекс переменной констатирующей части правила,VALC- значение переменной в констатирующей части правила. МассивCтакже состоит из структур следующего состава:VAR- индекс переменной условия,VAL- значение переменной условия. Т.е.j-е правило будет читаться следующим образом:

ЕСЛИ (VAR[R_j->C₁->VAR] =R_j->C₁->VAL) И

(VAR[R_j->C₂->VAR] = R_j->C₂->VAL) И

...

(VAR[R_j->C[M_j]->VAR] = R_j->C[M_j]->VAL)

ТО VAR[R_j->CONST] := R_j->VALC

где M- массив количеств условий в правилах.

В цикле 9-11 выясняется, входит ли очередная переменная в список условий j-го правила (условие 10). Если входит, то запускается следующий вложенный цикл 13-17, в котором определяется истинность условной частиj-го правила. Если соответствующая условная переменная не инициализирована (14), то производится ее ввод. Каждая условная переменная сравнивается с ее значением из правила (условие 17). Выход из цикла производится по обнаружению переменной, не совпадающей с заданным значением, или после проверки всех переменных.

Если все условия выполняются, индикатором чего является прохождение по всему массиву условий (условие 18), устанавливается флаг инициализации переменной констатирующей части правила (20) и ее значение. Ее номер отправляется в очередь Q. Условие 19 позволяет исключить неоднозначности и проигнорировать взаимоисключающие правила.

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

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

3.2.3.2. Алгоритм обратного вывода

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

Обозначения в приведенном ниже алгоритме во многом совпадают с алгоритмом прямого вывода. Программа содержит вызов аналогичной подпрограммы инициализации и рекуррентной функции вывода, которой в качестве входного параметра передается V- номер проверяемого факта.

Функция вывода в цикле проходит по всем правилам системы и, если анализируемая логическая переменная входит в констатирующую часть правила, запускает вложенный цикл, в котором проверяет на равенство заданным величинам логические переменные из условной части правила (условие 10). В случае, если переменная не инициализирована (условие 4), параметры циклов jиkсохраняются в стеке логического выводаS, глобальной переменнойVприсваивается номер анализируемой логической переменной и рекуррентно запускается функция логического вывода. Ориентируясь на языки программирования, можно сказать, что организовывать стекSнет необходимости, т.к. при использовании рекуррентного вызова функции для тех же целей (для сохраненияjиk) автоматически используется сегмент стека программы.

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

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