Простые системы альтернатив есть метод организации и обработки данных в интересах решения переборных задач. В АСИЗ задачи такого рода возникают при реализации блока анализа протоколов. Кроме того, простые системы альтернатив допускают использование в качестве метода реализации баз знаний (п. 1.2.5).

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

2.1 Основные понятия

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

Определение 2.1
Простой системой альтернатив или ПА-системой называется тройка конечных множеств (S,C,A), где S - множество основных фактов, C - множество вспомогательных фактов (причем S ∪ C = ∅), A - совокупность подмножеств из S ∪ C. Элементы множества A называются альтернативами.

Соглашение.
(1)	В дальнейшем для обозначения объединенного множества фактов будем использовать символ "H".
(2)	Не ограничивая общности множества S, C и H можно считать упорядоченными S = {s1, ..., sk}, C = {c1, ..., cn}, H = {s1, ..., sk, c1, ..., cn}.
(3)	Для обозначения альтернатив будем использовать специальные скобки: <h1, ..., hm> ∈ A.
(4)	Будем рассматривать только такие ПА-системы, в которых каждый факт входит, по крайней мере, в одну альтернативу, что позволяет задавать ПА-системы простым перечислением альтернатив.

Пусть R - ПА-система (S,C,A). Рассмотрим множество характеристических функций f : H → {0,1}.

Определение 2.2
Будем говорить, что характеристическая функция f удовлетворяет ПА-системе R, если для любой альтернативы <h₁, ..., h_m> из A имеет место равенство

Если f - характеристическая функция, заданная на множестве X, и Y - подмножество X, то функция f однозначно определяет подмножество f(Y). f(Y) = {x ∈ Y | f(x) = 1}. Используя это обозначение, определим для ПА-системы R два множества.

Определение 2.3
Q(R) = {f(H) | f ∈ F(R)},
K(R) = {f(S) | f ∈ F(R)}. Множество K(R) называется классом распознавания ПА-системы.

Элементы класса распознавания описывают (путем перечисления) допустимые комбинации основных фактов. Очевидно, что K(R) = {S ∪ q | q ∈ Q(R)}.

Рассмотрим задачу построения класса распознавания по известной системе альтернатив.

Задача 2.4 (Прямая задача)
Дано. ПА-система R = (S,C,A).
Требуется. Построить класс распознавания K(R).

Приведем подход к решению задачи 2.4. Обозначим: E - вектор размерности ||A||, состоящий из всех единиц, X - вектор неизвестных размерности p = ||H||:

где x - некоторый фиксированный символ. Каждый элемент вектора X может принимать значения 0 или 1. По множеству A построим матрицу M размерности ||A|| х ||H||. Для каждой альтернативы a матрица содержит строку m₁ ... m_p, где

По построению система булевых целочисленных уравнений MX = E содержит все соотношения, которым должны удовлетворять функции из множества F(R). Таким образом, система MX = E, с учетом разбиения множества неизвестных на два класса

Каждое решение

Отметим, что описанный подход к решению прямой задачи позволяет находить не только класс распознавания, но и множество Q(R).

В интересах реализации баз знаний интерес представляет задача построения ПА-системы с заданным классом распознавания.

Задача 2.5 (Обратная задача)
Пусть S = {s₁, ..., s_k} - исходное множество основных фактов. Кроме того, известно множество K₀ ⊂ 2^S.
Требуется построить ПА-систему R такую, что K(R) = K₀.

Покажем, что обратная задача разрешима.

Прежде всего построим множество вспомогательных фактов. Положим C - множество всевозможных функций c : S → {0,1}. Очевидно, что ||С|| = 2^k.

Построим ПА-систему R₁ = (S,C,A₁), в которой A₁ = {C, a₁, ..., a_k}. Здесь C - альтернатива, содержащая все вспомогательные факты, а состав фактов альтернативы a_j (j=1,..., k) определяется по формуле

Каждому вспомогательному факту c сопоставим функцию

Свойство системы R₁ сформулируем в виде леммы.

Лемма 2.6
F(R₁) = {f_с | c ∈ C}.

Доказательство проведем в два этапа.

(1) Пусть c - произвольный элемент из C. Покажем, что f_c удовлетворяет ПА-системе R₁.

Альтернативе C функция f_c удовлетворяет по построению. Рассмотрим альтернативу a₁. Теоретически для f_c возможны два варианта: либо f_c(s₁) = 0, либо f_c(s₁) = 1. В первом случае равенство из определения 2.2 выполняется за счет значения f_c(c). Во втором случае c(s₁) = 1 и, следовательно, c ∈ a₁, т.е. равенство из определения 2.2 выполняется за счет значения f_c(s₁). Аналогично рассматриваются и остальные альтернативы. Таким образом,

(2) Пусть f ∈ F(R₁). Из альтернативы C следует, что f(c) = 1 для некоторого c. Предположим, что f ≠ f_c. Это означает существование некоторого основного факта s_j такого, что f(s_j) ≠ c(s_j). Теоретически для функции f возможны два варианта:
либо f(s_j) = 0 и тогда c(s_j) = 1,
либо f(s_j) = 1 и тогда c(s_j) = 0.

В первом случае для альтернативы a_j, учитывая, что c ∈ a_j, имеем

Во втором случае для этой же альтернативы получим

Окончательный ответ о принципиальной возможности решения обратной задачи дает

Теорема 2.7
K(R) = K₀, где     R = (S, C, A₁ ∪ {a₀}),     a₀ = <c ∈ C | c(S) ∈ K₀>.

Доказательство. По определению класса распознавания

Множество F(R) составляют функции из F(R₁), дополнительно удовлетворяющие альтернативе a₀. В соответствии с леммой 2.6, элементы F(R₁) есть функции вида f_c, для которых f_c(c) = 1. Учитывая, что a₀ ⊂ C, имеем:

K(R) = {c(S) | c(S) ∈ K₀} = K₀.

Пример.
Пусть k = 3, S = {s₁,s₂,s₃},

Замечание 2.8
Поскольку a₀ ⊂ C, то ПА-систему R из теоремы 2.7 можно упростить следующим образом: (S, a₀, {a₀,a'₁, ..., a'_k}), где a'_i = a_i \ (C \ a₀) (i=1,..,k).

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

2.2 Логический вывод в системах альтернатив

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

Перейдем к подробному анализу задачи логического вывода. Пусть R = (S,C,A) - некоторая ПА-система и L⁺ и L^- - подмножества фактов из H. Прежде всего нас будет интересовать следующее множество.

Определение 2.9
Q(R,L⁺,L^-) = {q ∈ Q(R) _ L⁺ ⊂ q, L^- ∪ q = ∅}.

Подмножество Q(R,L⁺,L^-) образуют элементы из Q(R), подтверждающие факты из L⁺ и опровергающие факты из L^-.

Соглашение.
В связи с тем, что запись "Q(R,L⁺,L^-)" используется достаточно часто, будем использовать ее краткий эквивалент "QL".

Для заданного множества QL определим два множества фактов.

Определение 2.10

Установленные факты являются общими для всех элементов QL, в частности, L⁺ ⊂ H⁺. Множество H^- образуют все факты, которые ни разу не встречаются в QL; очевидно, что L^- ⊂ H^-.

Задача 2.11 (Задача логического вывода)
Дано. ПА-система R = (S,C,A) и два непересекающихся подмножества L⁺ и L^- из S.
Требуется. Проверить условие QL = ∅, и, в случае QL ≠ ∅, найти подмножества фактов

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

Метод. (Полное решение задачи логического вывода)

Этап 1.	По известной ПА-системе R = (S,C,A) решить задачу 2.4 и построить множество Q(R).
Этап 2.	Используя определение 2.9, построить множество QL. Если QL = ∅, то закончить вычисления с сообщением "Выход за пределы класса распознавания". В противном случае перейти к этапу 3.
Этап 3.	Используя определение 2.10, построить множества H+ и H-.
Этап 4.	Построить искомые множества

⌫

Таким образом, полное решение задачи логического вывода предполагает решение системы булевых целочисленных уравнений (этап 1).

Рассмотрим второй (основной) подход к решению поставленной задачи логического вывода.

Метод 2.12 (Процедура логического вывода)
Выполнить присваивания U⁺ = L⁺ и U^- = L^-.
Применить к системе альтернатив (в произвольном порядке) следующие четыре правила вывода/преобразования.

Правило 2.12(1)

Правило 2.12(2)

Правило 2.12(3)

Метод заканчивает свою работу либо в результате применения правила 2.12(4), либо тогда, когда первые три правила не приносят более новой информации о множествах A, U⁺ и U^-. В последнем случае решением задачи является множества S⁺ = S ∪ U⁺ и S^- = S ∪ U^-.

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

Правило 2.12(1) утверждает, что если для некоторого уравнения f(h_k) = 0, то это уравнение можно переписать в виде

Правило 2.12(2) утверждает, что если для некоторого уравнения f(h_k) = 1, то f(h_i) = 0 (i=1,...,k-1,k+1,...,m).

Правило 2.12(3) утверждает, что если некоторое уравнение имеет вид f(h) + 0 = 1 (т.е. m = 1), то f(h) = 1.

Правило 2.12(4) утверждает, что наличие в системе уравнения 0 = 1 (т.е. m = 0) означает, что система уравнений не имеет решения.

Учитывая приведенную интерпретацию правил, примем следующее

Соглашение.
Будем считать, что правило 2.12(1) выполняет замену альтернативы:

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

Пример.
Рассмотрим ПА-систему R = (S,C,A), где S = {i,j,k,m,n}, C = {x,y,z} и A = {, , , }. Приведем возможную трассу процедуры логического вывода для случая L⁺ = {i}, L^- = ∅.

Применяемое правило. Альтернатива [и факт].	(Остаточная) система альтернатив				U+	U-
	1	2	3	4
	<i,x,y>	<j,x>	<j,k,y>	<m,n,y,z>	i
2.12(2)     1 и i
	<i>	<j,x>	<j,k,y>	<m,n,y,z>	i	x    y
2.12(1)     2 и x
	<i>	<j>	<j,k,y>	<m,n,y,z>	i	x    y
2.12(3)     2
	<i>	<j>	<j,k,y>	<m,n,y,z>	i j	x    y
2.12(2)     3 и j
	<i>	<j>	<j>	<m,n,y,z>	i j	x    y    k
2.12(1)     4 и y
	<i>	<j>	<j>	<m,n,  ,z>	i j	x    y    k
Конец.

Результаты вывода:

В рассмотренном примере U⁺ = H⁺ и U^- = H^-, однако так бывает не всегда. В случае непротиворечивого вывода (QL ≠ ∅) имеют место соотношения U⁺ ⊂ H⁺, U^- ⊂ H^- и, соответственно,

Замечание.
Результатом работы процедуры логического вывода наряду с множествами S⁺ и S^- можно считать множества U⁺ и U^-.

Правила 2.12(2) и 2.12(3) позволяют расширять множества U⁺ и U^-. Они являются простейшими образцами для распознавания состояний остаточной системы альтернатив. В конкретных реализациях мощность процедуры логического вывода может быть увеличена за счет добавления более изощренных образцов.

Правило 2.12(4) позволяет в некоторых случаях установить равенство QL = ∅, что означает наличие противоречий в исходной системе альтернатив и заданных множествах L⁺ и L^-. Однако, возможны такие конструкции альтернатив, для которых правило 2.12(4) не способно выявить равенство QL = ∅. Например, если остаточная система содержит изолированные альтернативы

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

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

2.3. Модули знаний в системах альтернатив

Рассмотрим абстрактную ситуацию конструирования в виде системы альтернатив заранее известной базы знаний. Исходным материалом является множество основных фактов, выбранных для описания проблемной области. На каждом шаге построения разработчик базы выбирает некоторое (вообще говоря, весьма ограниченное) подмножество фактов S_i и связывает их в определенной функциональной зависимости, т.е. фактически создает мини-систему альтернатив R_i= (S_i, C_i, A_i). В дальнейшем такие системы будем называть модулями знаний. В конечном итоге, база знаний, содержащая n модулей, может быть представлена ПА-системой R = (S, C, A), в которой

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

Лемма 2.13
Для любого модуля R_i имеет место вложение

Доказательство. Пусть D - произвольный элемент K(R), и R_i - некоторый модуль. Покажем, что D ∩ S_i ∈ K(R_i).

f_i(S_i) = { s ∈ S_i | f_i(s) = 1 } = { s ∈ S_i | f(s) = 1 } = { s ∈ S | f(s) = 1} ∩ S_i = D ∩ S_i.

При построении базы знаний, во всяком случае, на этапе ее первоначального составления, принимается гипотеза о том, что все модули являются независимыми и в процессе логического вывода могут соединяться в произвольные цепочки причинно-следственных связей для достижения поставленных целей. Применительно к системам альтернатив гипотеза о независимости состоит в том, что для любой пары модулей R_i и R_j (i ≠ j) имеет место равенство C_i ∩ C_j = ∅. Т.е. каждый модуль имеет свое собственное множество вспомогательных фактов. Конечно, в реальных системах гипотезу о независимости модулей приходится ослаблять, вместе с тем возможности ослабления обусловливаются спецификой представления модулей.

Ранее была доказана теорема 2.7, согласно которой разработчик базы знаний может построить модуль с произвольным классом распознавания. Доказательство содержит универсальный метод построения модулей, но этот метод является неэффективным, поскольку согласно замечанию 2.8 предполагает построение ||K(R)|| вспомогательных утверждений. Рассмотрим некоторые конструкции модулей, представляющие интерес с практической точки зрения.

2.3.1. Модуль альтернативы

Прежде всего необходимо отметить, что саму альтернативу

Очевидно K(R_a) = { {s₁}, ..., {s_m} }.

В ходе выполнения процедуры логического вывода модуль может функционировать двумя способами.
1).Если s_i ∈ L⁺ для некоторого s_i из S, то S \ {s_i} ⊂ U^-.
2).Если S \ {s_i} ⊂ L^- для некоторого s_i из S, то s_i ∈ U⁺.

Схематично оба вида функционирования для случая, скажем, m = 3 и i = 2 могут быть представлены следующими диаграммами:

Приведенные схемы функционирования справедливы также и для альтернатив, содержащих вспомогательные факты.

Замечание.
Если факты s₁, ..., s_m рассматривать как высказывания, тогда класс распознавания альтернативы < s₁, ..., s_m > можно рассматривать как множество всех интерпретаций, при которых истинна некоторая правильно построенная формула Ф. Упомянутое множество интерпретаций содержит ровно m наборов:

С использованием традиционных для логики высказываний [49] связок { ¬, И, ИЛИ } формула Ф может быть представлена весьма сложной ДНФ:

Легко показать, что в случае m > 2 не существует бинарной, ассоциативной и коммутативной операции * такой, что

Замечание.
Интересно отметить, что любую альтернативу < h₁, ..., h_m >, содержащую более трех фактов (m > 3) можно представить в виде эквивалентного модуля знаний:

Замечание 2.14
Если s - некоторый факт и < s,h > ∈ A, то факт h можно рассматривать, как ¬s. То есть:
    Если s ∈ L⁺, то h ∈ U^-;
    Если s ∈ L^-, то h ∈ U⁺.

2.3.2. Модуль несовместимости

Модулем несовместимости R_н для фактов s₁, ..., s_m называется альтернатива

В отличии от альтернативы, для модуля несовместимости возможен только первый вид функционирования.

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

Соглашение.
Запись [ h₁, ..., h_m ] будем понимать как краткий эквивалент альтернативы < h₁, ..., h_m, c> с уникальным вспомогательным фактом c.

2.3.3. Модуль запрета

Модулем запрета [13] R_з для фактов S = { s₁ , ..., s_m } называется ПА-система

Класс распознавания этого модуля содержит все подмножества основных фактов, кроме самого S.

Доказательство. Предположим, что S ∈ K(R_з), тогда существует функция f ∈ F(R_з), для которой f(S) = S. Рассмотрим свойства этой функции. Из альтернативы [ s_i, c_i ] (i = 1, ..., m) следует, что f(c_i) = 0. >Следовательно, для альтернативы < с₁, ..., c_m > имеем: f(c₁) + ... + f(c_m) = 0, то есть f ∉ F(R_з), а значит S ∉ K(R_з).

Рассмотрим произвольное подмножество S' из S такое, что S \ S' ≠ ∅. Не ограничивая общности, можно считать, что S' = {s₁, ..., s_k}, где k < m. Определим функцию f_m следующим образом:

Модуль позволяет опровергать один факт при наличии всех остальных. Другими словами, если S \ {s} ⊂ L⁺ для некоторого s, то s ∈ U^-.

Пример, m = 3, L⁺ = {s₁, s₃}.

Соглашение.
Для сокращения записи модуль запрета для фактов s₁, ..., s_m будем обозначать

ЗАПРЕТ(s₁, ..., s_m).

Замечание.
Если факты s₁, ..., s_m рассматривать как высказывания, тогда ЗАПРЕТ(s₁, ..., s_m) представляет собой утверждение

Учитывая замечание 2.14, с помощью модуля запрета можно построить любую элементарную дизъюнкцию. В частности, система альтернатив

s₁ ИЛИ ... ИЛИ s_m.

Замечание.
Для m = 2 модули [ s₁, s₂ ] и ЗАПРЕТ(s₁, s₂) эквивалентны друг другу.

2.3.4. Модуль импликации

Модулем импликации R_и для фактов S = {s₀, s₁, ..., s_m } называется ПА-система

Рассмотрим класс распознавания модуля импликации. K(R_и) = K⁺ ∪ K^-, где

Множеству K⁺ соответствует остаточная система альтернатив, полученная из R_и при L⁺ = {s₀} и L^- = ∅. Эта система имеет вид: < s₀ >, [ s₁ ], ..., [ s_m ], т.е. допускает любые подмножества из S' = { s₁, ..., s_m }. Следовательно, K⁺ = {D ∪ {s₀} | D ⊂ S'}.

Аналогично, множеству K^-соответствует остаточная система альтернатив

K^- = 2^S' \ {S'}.

Таким образом, имеем

ПА-система R_и в ходе выполнения процедуры логического вывода может функционировать двумя способами.

1). Если S' ⊂ L⁺, то s₀ ∈ U⁺.
Например, m = 2, L⁺ = {s₁, s₂}.

2). Если s₀ ∈ L^- и S' \ {s} ⊂ L⁺ для некоторого s ∈ S', то s ∈ U^-.
Например, m = 3, L⁺ = {s₁, s₂}, L^- = {s₀}.

Первый вид функционирования соответствует правилу "ЕСЛИ s₁ и ... и s_m, ТО s₀". Второй вид реализует возможность рассуждений "от противного".

2.3.5. Модуль продукции

Продукцией для фактов S = { s₀, s₁, ..., s_m } называется ПА-система R_п:

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

Пример m = 3, L⁺ = { s₁, s₂}, L^- = { s₀ }. В этом случае процедура логического вывода строит остаточную систему альтернатив

2.3.6 Структурирование систем альтернатив

В современных системаx искусственного интеллекта модули знаний представляют не единым "мешком", а структурой автономных фрагментов, подключающихся к работе в зависимости от тех или иных условий. С этой точки зрения представляют интерес возможности структурирования ПА-систем.

Свяжем с некоторым модулем знаний R = (S,C,A) факт s_R. Будем говорить, что модуль R является необязательным, если его альтернативы не участвуют в выводе до тех пор, пока s_R ∉ U⁺. Факт s_R называется флагом существования модуля R.

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

Непосредственной проверкой легко убедиться, что

Рассмотрим функциональные характеристики этого модуля. Если s_R ∈ U⁺, то {c₁,c₂} ⊂ U^- и остаточная система имеет вид: < c₃, s₁ >, < c₃,s₂ >, что гарантирует следующее поведение: s₁ ∈ U⁺ (s₁ ∈ U^-) тогда и только тогда, когда s₂ ∈ U⁺ (s₂ ∈ U^-). Если s_R ∈ U^-, то, как следует из состава класса распознавания, факты s₁ и s₂ независимы друг от друга. Итак, только при установленном флаге существования факты s₁ и s₂ проявляют себя одинаково в ходе логического вывода.

Введем для альтернатив ПА-системы R⁼ следующее обозначение: eq(s₁,s₂ | s_R).

Рассмотрим теперь произвольный модуль R = (S,C,A) и факт s_R, s_R ∉ S, который должен выступать в роли флага существования модуля R. Построим необязательный модуль знания R' следующим образом:

Пример.
Необязательный модуль альтернативы < s₁, s₂, s₃ > имеет вид:

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

2.4. Реализация процедуры логического вывода

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

Соглашение.

(1)	Будем предполагать, что в системе альтернатив изначально отсутствуют пустые альтернативы и альтернативы, содержащие ровно один факт.
(2)	Будем предполагать, что для каждого факта h из H известно множество альтернатив A(h), использующих h: A(h) = {a ∈ A | h ∈ a}.

Принятые соглашения позволяют рассматривать правила 2.12(3) и 2.12(4) как процедуры анализа альтернативы, полученной в результате применения правила 2.12(1).

Работу машины вывода определяют четыре основные процедуры:
— FIX(h : факт);
— REF(h : факт);
— EXTFIX(h : факт; var a : альтернатива);
— EXTREF(h : факт; var a : альтернатива).

В данном случае для описания процедур используется нотация языка ПАСКАЛЬ. При определении процедур термин "активизировать" будем понимать как аналог команды FORK [50], которая инициирует развитие нового независимого процесса вычислений соответствующей процедуры.

Процедура FIX.
Если h ∈ U⁺, то
(1) квалифицировать факт h как установленный: U⁺ = U⁺ ∪ {h};
(2) для всех альтернатив a из A(h) активизировать EXTFIX(h,a).

Процедура REF.
Если h ∈ U^-, то
(1) квалифицировать факт h как опровергнутый: U^- = U^- ∪ {h};
(2) для всех альтернатив a из A(h) активизировать EXTREF(h,a).

Процедура EXTFIX.
(1) уничтожить в A альтернативу a: A = A \ {a}.
(2) реализовать правило 2.12(2) с альтернативой a и фактом h: для всех фактов h' (h' ≠ h и h' ∈ a) активизировать REF(h').

(1)	уничтожить в A альтернативу a:  A = A \ { a }; уничтожить в a факт h:  a = a \ { h }; произвести замену альтернативы:  A = A ∪ { a }.
(2)	анализировать состояние остаточной альтернативы a: Правило 2.12(4).     Если a = < >, то СТОП("Выход за пределы класса распознавания"); Правило 2.12(3).     Если a = < h' >, то активизировать FIX(h').

При запуске алгоритма логического вывода активизируются процедуры FIX(h) для h ∈ L⁺ и REF(h) для h ∈ L^-.

Все активизированные процедуры могут выполняться в любом порядке, независимо друг от друга, что позволяет естественным образом распараллеливать работу процедуры логического вывода. Отметим, что в системе ФИАКР машина вывода реализована на однопроцессорной ЭВМ, при этом активизированные процедуры заносятся в так называемую очередь процессов и обрабатываются последовательно. Очередь организована таким образом, чтобы сократить количество обращений к памяти на внешних носителях, где, собственно, и хранится система альтернатив.

С целью формирования трассы причинно-следственных связей, возникающих в ходе логического вывода, процедуры FIX и REF дополняются еще одним параметром - указателем на альтернативу, в которой данный факт был установлен или опровергнут. Для исходных фактов из L⁺ и L^- используется специальное значение указателя. Другими словами, для каждого факта из U⁺ ∪ U^- хранится указатель на альтернативу, объясняющую его текущее состояние. Расшифровку и интерпретацию причинно-следственных связей осуществляет подсистема объяснений.

Наибольшие затруднения при программной реализации процедуры логического вывода вызывает применение правила 2.12(4), поскольку действия, предписываемые этим правилом, непосредственно в системах альтернатив не предусматриваются. Проблема состоит в том, что при возникновении ситуации выхода за пределы класса распознавания - в интересах подсистемы объяснений - необходимо каким-то разумным способом остановить все активизированные в настоящий момент процессы. В связи с этим предлагается стандартная модификация системы альтернатив и процедуры логического вывода, снимающая указанные затруднения.

2.5 Модифицированные системы альтернатив

Зафиксируем ПА-систему R = (S,C,A). Введем новый вспомогательный факт t (t ∉ H) и связанное с ним множество T, T = { t }. По системе R построим ПА-систему

Если, например, система R состоит из альтернатив

Связь между системами R и R определяет следующая
Теорема 2.15
Q(R) = Q(R) ∪ { T }.

Доказательство. Множество F(R) можно разбить на два непересекающиеся подмножества
F^- = {f ∈ F(R) | f(t) = 0} и
F⁺ = {f ∈ F(R) | f(t) = 1}.

Множеству F^- соответствует остаточная система альтернатив, полученная из R при L⁺ = ∅ и L^- = T. По определению ПА-системы R остаточная система есть R. Следовательно, подмножество F составляют функции класса F(R), доопределенные значением 0 для факта t. Поэтому { f() | f ∈ F^- } = Q(R).

Рассмотрим произвольную функцию f из F⁺. В соответствии с принятыми соглашениями, каждый факт h (h ≠ t) входит, по-крайней мере, в одну альтернативу. Для этой альтернативы равенство из определения 2.2 имеет вид

Окончательно имеем:

Q(R) = {f(H) | f ∈ F^-} ∪ {f(H) | f ∈ F⁺} = Q(R) ∪ T.

Следствие. K(R) = K(R) ∪ {∅}.

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

Метод 2.16
Выполнить присваивания: V ^- = L^-, V⁺ = L⁺, V = ∅.
Применить к системе альтернатив R (в произвольном порядке) следующие правила вывода/преобразования:

Правило 2.16(1)

Правило 2.16(2)

Правило 2.16(2')

Правило 2.16(3)

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

Результатом работы метода являются множества V ^-, V и V⁺.

Правила вывода из метода 2.16 реализуют некоторые приемы преобразования и решения системы булевых уравнений вида

Правила 2.16(3) и 2.16(4) фиксируют наличие в системе двух частных случаев уравнений: f(h) + f(t) = 1 и f(t) = 1.

Правило 2.16(1) утверждает, что если для некоторого уравнения f(h_k) = 0, то это уравнение можно переписать в виде

Правило 2.16(2) утверждает, что наличие в системе уравнения

Правило 2.16(2') утверждает, что если для некоторого уравнения f(t) = 1, то f(h_i) = 0 (i=1,...,m).

Факты из множества V \ L⁺, полученные с помощью правила 2.16(3), переходят в разряд установленных только в том случае, когда опровергается факт t. Поэтому факты этого класса можно считать установленными условно впредь до проверки равенства QL = ∅.

Как отмечалось ранее, правила 2.12(1), 2.12(2), 2.12(3) и 2.12(4) не всегда способны проверить наиболее критичное для логического вывода условие QL = ∅. Поэтому, с концептуальной точки зрения, именно условный вывод в наибольшей степени отвечает природе систем альтернатив. Можно считать, в модифицированной системе R факт t есть символический эквивалент условия QL = ∅ для ПА-системы R. Перед запуском процедуры вывода t находится в неопределенном состоянии, то есть не принадлежит ни одному из множеств V ^-, V и V⁺. Правила вывода 2.16(1), 2.16(2) и 2.16(3) позволяют делать выводы в условиях неопределенного факта t. Правило 2.16(4) позволяет установить t, что соответствует выходу за пределы класса распознавания в системе R, и, наконец, правило 2.16(2') непротиворечивым образом доопределяет действия процедуры вывода в этом случае.

Соотношение между методами 2.12 и 2.16 определяет следующая

Теорема 2.17
Пусть R = (S,C,A) - ПА-система. Для любых подмножеств L⁺ и L^- из H, удовлетворяющих условию QL ≠ ∅, имеют место равенства V = U⁺, V ^- = U^- и V⁺ = ∅.

Доказательство. Для упрощения последующих выкладок введем обозначение: Q = Q(R,L^-,L⁺). Доказательство теоремы проведем в два этапа. Сначала докажем, что t ∉ V⁺.

Предположим обратное: t ∈ V⁺. Тогда в соответствии с правилом 2.16(2') Q = {T}. С другой стороны имеем:

Перейдем ко второму этапу доказательства. Так как t ∉ V⁺, то при построении множеств V⁺, V^- и V использовались только правила 2.16(1), 2.16(2) и 2.16(3). Непосредственно из условия теоремы вытекает, что при построении множеств U⁺ и U^- использовались правила 2.12(1), 2.12(2) и 2.12(3).

В системе R и правилах 2.16(1), 2.16(2) и 2.16(3) произведем следующие преобразования альтернатив: a = a \ T. Полученная таким образом ПА-система R₁ совпадает с системой R. Соответственно, правила 2.16(1), 2.16(2) и 2.16(3) трансформируются в правила 2.12(1), 2.12(2) и 2.12(3) с точностью до переименования множеств V и V ^- во множества U⁺ и U^-.

Таким образом, переход от системы альтернатив R (с процедурой вывода 2.12) к системе R (с процедурой вывода 2.16) не влияет на мощность логического вывода. Кроме того, все правила из 2.16 реализуются в терминах систем альтернатив, что упрощает программирование машины вывода.

С точки зрения практической реализации совсем не обязательно переходить от исходной ПА-системы R к модифицированной системе R. Того же результата можно добиться, модифицируя лишь правила вывода 2.16.

Метод 2.18 (Условный логический вывод)
Выполнить присваивания: V ^- = L^-, V⁺ = L⁺, V = ∅.
Применить к системе альтернатив R (в произвольном порядке) следующие правила вывода/преобразования:

Правило 2.18(1)

Правило 2.18(2)

Правило 2.18(2')

Правило 2.18(3)

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

Если V ≠ ∅, то результатом работы метода являются множества S⁺ = S ∪ V и S= S ∪ V ^-.

Формальный аппарат простых систем альтернатив используется:
— в инструментальной экспертной системе ФИАКР (глава III) в качестве метода реализации баз знаний;
— в эвристическом методе восстановления контекстно-свободных языков (п. 4.4.3) для выбора однотипных структур;
— в блоках анализа протоколов АСИЗ (п. 6.2.2) для построения согласованных интерпретаций.