Математическая логика событий

1.1 Булева концепция алгебры высказываний о событиях

" Ученые объяснения большей частью производят то впечатление, что бывшее ясно и понятно становится темно и запутанно".

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

Определение 2. Событие выражается высказыванием о его свершении.

Высказыванию о событии (далее - просто высказывание, считая событие и высказывание о нем синонимами) можно поставить в соответствие переменную, которая в рамках булевой концепции может принимать значение ИСТИНА (1) или ЛОЖЬ (0).

Например:

x = <поезд опоздал на пять минут>;
 y = <в данной операции принимал участие Вася> 
   (достаточно сообщить лишь имя);
 z = <скорость автомобиля принадлежит диапазону (120-140 км/ч)> 
     (достаточно кратко обозначить диапазон в известном контексте, 
      как условие свершения некоторого действия, 
      приведшего к автокатастрофе).

Очевидно, что каждая переменная x, y, z может принимать одно из двух значений - 0 или 1.

Над высказываниями производятся логические операции. В рамках последующих построений потребуются четыре операции: отрицание ( $$\neg x$$, НЕx, x ), конъюнкция ( $$\wedge,$$ И, AND, x ), дизъюнкция ( $$\vee,$$ ИЛИ, OR ), импликация или операция следования ( $$\to$$ ). Результаты операций определяются таблично.

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

одноместная операция отрицания меняет значение переменной на противоположное;

двуместная операция конъюнкции над двумя и (рекурсивно) более переменными порождает значение 1 тогда и только тогда, когда все переменные имеют значение 1;

двуместная операция дизъюнкции над двумя и (рекурсивно) более переменными порождает значение 1, когда хотя бы одна переменная имеет значение 1;

переменная справа от знака операции следования (импликации) принимает значение 1 тогда и только тогда, когда выражение слева от этого знака имеет значение 1.

Кроме того, ниже используется операция ИСКЛЮЧАЮЩЕЕ ИЛИ, предполагающая возможность лишь единственного вхождения переменной со значением 1 в операцию дизъюнкции, объединяющую несколько переменных.

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

Закон коммутативности:

$$\begin{array}{l}x\wedge y=y\wedge x;\\ x\vee y=y\vee x \end{array}$$

Закон ассоциативности:

$$\begin{array}{l} x\vee ( y\vee z)= ( x\vee y)\vee z;\\ x\wedge ( y\wedge z)= ( x\wedge y) \wedge z \end{array}$$

Закон дистрибутивности:

$$\begin{array}{l} x\wedge ( y\vee z)= ( x\wedge y)\vee(x\wedge z);\\ x\vee ( y\wedge z)= ( x\vee y) \wedge (x\vee z) \end{array}$$

Закон де Моргана:

$$\begin{array}{l} \overline{x\vee y}=\overline{x}\wedge \overline{y};\\ \overline{x\wedge y}=\overline{x}\vee \overline{y} \end{array}$$

Закон идемпотенции:

$$\begin{array}{l} x\vee x=x;\\ x\wedge x=x \end{array}$$

Закон поглощения:

$$\begin{array}{l} x\vee(x\wedge y) =x;\\ x\wedge (x\vee y)=x \end{array}$$

Закон склеивания:

$$\begin{array}{l} (x\wedge y)\vee(\overline{x}\wedge y) =y;\\ (x\vee y)\wedge(\overline{x}\vee y) =y \end{array}$$

Операция переменной с инверсией:

$$\begin{array}{l} x\vee \overline{x} =1;\\ x\wedge\overline{x}=0 \end{array}$$

Операция с константами:

$$\begin{array}{ll} x\wedge 0 = 0, x\wedge1 =x;\\ x\vee 0 = x, x\vee1 =1 \end{array}$$

Двойное отрицание:

$$\overline{\overline{x}} = x$$

Несмотря на наличие дистрибутивных операций, существует ранжирование операций - в сторону понижения (ранга) слева направо: $$\neg (x)$$, $$\wedge,$$ $$\vee.$$ То есть если написано без скобок $$\neg x\vee y\wedge z$$, то с помощью эквивалентного обозначения и скобок можно выявить следующий порядок действий: $$\overline{x}\vee (y\wedge z)$$.

1.2. Логические функции высказываний

Множество логических переменных - высказываний о событиях {x1, x2, ..., xn} в контексте некоторого приложения образует пространство событий размерности n. Точка этого пространства является ситуацией.

Можно записать произвольную композицию на основе заданного множества переменных-высказываний и логических операций, например, $$\neg \vee xy\wedge z$$, $$(x\vee \overline{y}) \wedge (y\wedge z)$$. Почему первую композицию следует считать бессмысленной? По-видимому, потому, что она содержит конструкции, не определенные в терминах алгебры логики, и не может быть исчерпывающим образом преобразована в таковые на основе применения (1)-(10). Тогда вторая приведенная композиция имеет смысл, т.к. полностью подвержена основным определениям операций алгебры логики и правилам преобразования в ней.

Высказывания (о событиях ) в качестве переменных могут входить в состав сложных формирований - логических функций, принимающих (булевы) значения 1 (ИСТИНА) или 0 (ЛОЖЬ).

Определение 3. Имеющая смысл линейно-скобочная композиция операций $$\neg,$$ $$\vee,$$ $$\wedge$$ над переменными-высказываниями x1, x2, ..., xn, образующими пространство событий, задает логическую функцию f(x1, x2, ..., xn), принимающую для различных ситуаций, т.е. наборов значений переменных, значения 0 или 1.

Таким образом, логическая функция является булевой функцией ситуаций.

В классической теории булевых функций [1] показывается, что каждая такая функция может быть представлена дизъюнктивной и (или) конъюнктивной нормальной формой. В первом случае ее структура выражается как дизъюнкция конъюнкций, во втором - как конъюнкция дизъюнкций.

Рассмотрим две логические функции

$$Y = x_{1}\vee (x_{2}\wedge \overline{x_{1}}\vee x_{3})$$ и

$$Z = (x_{1}\vee \overline{x_{2}})\wedge ( \overline{x_{3}}\vee x_{2})$$.

Выражение Y представлено дизъюнктивной нормальной формой ( ДНФ ). Выражение Z соответствует конъюнктивной нормальной форме (КНФ), практически не применяемой.

Преобразуем

$$Z = (x_{1}\wedge \overline{x_{3}})\vee (x_{1} \wedge x_{2})\vee (\overline{x_{2}}\wedge \overline{x_{3}})$$. (Учитывается, что $$\overline{x_{2}}\wedge x_{2} = 0$$.)

Это - дизъюнктивная нормальная форма.

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

$$\begin{array}{rl} f=f(0, 0, 0) \wedge (\overline{x_1}\wedge\overline{x_2}\wedge\overline{x_3}) \vee f(0, 0, 1) \wedge (\overline{x_1}\wedge\overline{x_2}\wedge x3)\vee\\ f(0, 1, 0)\wedge (\overline{x_1}\wedge x_2 \wedge \overline{x_3}) \vee f(0, 1, 1)\wedge (\overline{x_1}\wedge x2\wedge x3)\vee\\ f(1, 0, 0)\wedge (x1 \wedge \overline{x_2}\wedge\overline{x_3}) \vee f(1, 0, 1)\wedge (x1\wedge \overline{x_2}\wedge x3)\vee \\ f(1, 1, 0) \wedge (x1 \wedge x2 \wedge \overline{x_3}) \vee f(1, 1, 1) \wedge (x1 \wedge x2 \wedge x3)\end{array}$$

Для всех значений переменных рассчитаем значения приведенных выше логических функций Y и Z (табл. 1.1).

Значения логических функций

x1	x2	x3	Y	Z
0	0	0	0	1
0	0	1	0	0
0	1	0	0	0
0	1	1	1	0
1	0	0	1	1
1	0	1	1	0
1	1	0	1	1
1	1	1	1	1

Попытаемся построить приведенные выше функции Y и Z на основе их СДНФ, т.е. проверим правильность такого подхода:

$$Y^* = \overline{x_1}\wedge x_2 \wedge x_3 \vee x_1 \wedge \overline{x_2}\wedge \overline{x_3} \vee x_1 \wedge \overline{x_2}\wedge x_3 \vee x_1 \wedge\\ x_2 \wedge \overline{x_3}\vee x_1 \wedge x_2 \wedge x_3$$

После эквивалентных преобразований (начинающихся с вынесения x1 "за скобку") получим

$$Y^* = \overline{x_1}\wedge x_2 \wedge x_3 \vee x_1$$, что совпадает с видом Y.

Аналогично,

$$Z^* = \overline{x_1}\wedge \overline{x_2} \wedge \overline{x_3} \vee x_1 \wedge \overline{x_2}\wedge\overline{x_3} \vee x_1 \wedge x_2 \wedge \overline{x_3} \vee x_1 \wedge x_2 \wedge x_3$$

После эквивалентных преобразований находим

$$Z^* = (\overline{x_2} \wedge \overline{x_3}) \vee (x_1 \wedge x_2)$$

Из табл. 1.1 видно, что все значения Z и Z* от одних и тех же наборов значений переменных совпадают. Однако Z* образуется только двумя "слагаемыми" Z. Конъюнкция $$x_{1}\wedge \overline{x_{3}}$$ оказалась "лишней", не влияющей на результат. Это говорит о том, что формирование аналитического вида логической функции по ее табличному заданию, с помощью СДНФ, позволяет получить простейшее (лаконичное) представление, без лишних конструкций, не влияющих на результаты вычислений.

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

$$f = f(x_1\wedge x_2\wedge 0\wedge 0)\wedge \overline{x_3} \wedge \overline{x_4} \vee f(x_1\wedge x_2\wedge 0\wedge 1)\wedge\\ \wedge \overline{x_3}\wedge x_4 \vee f(x_1\wedge x_2\wedge 1\wedge 0)\wedge x_3\wedge _ \vee f(x_1\wedge x_2\wedge 1\wedge 1) \wedge x_3 \wedge x_4.$$

1.3. Исчерпывающее множество событий

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

Определение 4. Исчерпывающее множество событий (ИМС) образуют те события, совокупность высказываний, о которых покрывает весь возможный смысловой диапазон проявления объекта высказывания, и каждая допустимая ситуация характеризуется тем, что значение ИСТИНА (1) может принимать единственное высказывание из этой совокупности. (Значение 0 могут принимать все высказывания.)

Рассмотрим примеры.

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

Наказуемое превышение скорости автомобиля делится на диапазоны: до 10%, от 10% до 20%, свыше 20%. Однако если в регламентирующем документе заданы только диапазоны до 10% и от 10% до 100%, то это не будет соответствовать исчерпывающему множеству событий. Такие нестрогие определения возможного диапазона ситуаций являются причиной юридической казуистики, требующей дальнейшего исследования прецедента.

Итак, ИМС, которому соответствует множество высказываний А= {x1, ..., xn}, характеризуется тем, что при соответствующих обстоятельствах одно и только одно высказывание из этого множества может принимать значение 1. Это и определяется операцией ИСКЛЮЧАЮЩЕЕ ИЛИ, которую будем обозначать $$\dot\vee$$.

Очевидны главные свойства высказываний о событиях из ИМС:

$$\overline{x_i}= x_1\dot\vee …\dot\vee x_{i-1}\dot\vee x_{i+1}\dot\vee …\dot\vee x_{n}$$ $$x_{i}\cdot x_{j}=\left \{ \begin{array}{1} 0, \quad\mbox{при } i\ne j\\ 1, \quad\mbox{при } i=j\end{array}\right$$

Теорема. Логическая функция от переменных-высказываний о событиях, образующих исчерпывающее множество событий, преобразуется в дизъюнкцию ИСКЛЮЧАЮЩЕЕ ИЛИ переменных-высказываний о событиях из этого множества.

Доказательство. Поясним доказательство теоремы анализом примера. На множестве высказываний {x1, x2, x3}, СДНФ имеет вид

$$f(x_1,x_2,x_3)= f (0,0,0)\wedge \overline{x_1}\wedge \overline{x_2}\wedge \overline{x_3}\vee \\\vee f (0,0,1)\wedge \overline{x_1}\wedge \overline{x_2}\wedge x_3 \vee f (0,1,0)\wedge \overline{x_1}\wedge x_2\wedge \overline {x_3}\vee \\\vee f (0,1,1)\wedge \overline{x_1}\wedge x_2\wedge x_3 \vee f (1,0,0)\wedge x_1\wedge \overline {x_2} \wedge \overline {x_3}\vee \\\vee f (1,0,1)\wedge x_1\wedge \overline{x_2} \wedge x_3 \vee f (1,1,0)\wedge x_1\wedge x_2 \wedge \overline{x_3}\vee \\\vee f (1,1,1)\wedge x_1\wedge x_2 \wedge x_3$$

Применив (1.12) и воспользовавшись свойством дистрибутивности ("раскрыв скобки") в соответствии с (1.3), обнаружим, что каждая вновь полученная конъюнкция может принимать значение некоторой переменной, согласно (1.13), тогда и только тогда, когда эта переменная входит в нее ровно 3 раза (п раз). Это возможно лишь в тех конъюнкциях исходной СДНФ, где переменная, а не ее отрицание, входит при условии, что другие переменные входят со знаком отрицания. На такую ситуацию указывают те значения f, которые отмечены единственной единицей в составе переменных. Для приведенного примера СДНФ принимает вид:

$$f(x_1,x_2,x_3)= f (0,0,1) \wedge x_3\vee f (0,1,0) \wedge x_2\vee f (1,0,0) \wedge x_1$$

Теорема доказана.

Чтобы подчеркнуть, что задание ситуаций подчиняется условию операции , используем обозначение этой операции для получения окончательного вида СДНФ логической функции, заданной на ИМС:

$$f(x_1,\ldots,x_n)= f (1,0,\ldots, 0,0)\wedge x_1 \vee f (0,1,\ldots, 0,0)\wedge x_2 \vee \ldots \vee \\f (0,0,\ldots, 1,0) \wedge x_{n-1}\vee f (0,0,\ldots, 0,1)\wedge x_n$$

Отметим важные свойства выражения (1.14).

Каждая переменная, участвующая в формировании этого выражения, входит в него единственный раз.

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

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

В чем еще смысл Теоремы 1?

Представим себе ход рассуждения следователя, сокращающего круг подозреваемых. Первоначально он установил, что преступником мог быть либо Иванов, либо Петров, либо Сидоров, первоначально составляющие ИМС. Однако, исследовав некоторую логическую функцию f алиби или участия в преступлении, он установил, что f(Иванов = 1, Петров = 0, Сидоров = 0) = 0, в то время как f(Иванов = 0, Петров = 1, Сидоров = 0) = 1, f(Иванов = 0, Петров = 0, Сидоров = 1) = 1. Таким образом, f(Иванов, Петров, Сидоров) = Петров $$\dot\vee$$ Сидоров. Это резко сужает круг подозреваемых, т.к. скорректированным исчерпывающим множеством событий является {Петров, Сидоров}.

1.4. Композиция исчерпывающих множеств событий. Дерево логических возможностей. Факторное пространство событий

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

Рассмотрим пример.

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

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

Бабушка пишет внуку: "Зимой я после завтрака катаюсь на лошади, и летом я после завтрака катаюсь на лошади, а также весной после завтрака прогулка бывает на лошади". … Что-то ей не нравится, и она строит схему своего составного высказывания: $$f = x_{1} \wedge x_{7} \wedge x_{14} \vee x_{1} \wedge x_{5} \wedge x_{14} \vee x_{1} \wedge x_{4} \wedge x_{10} \wedge x_{14}$$. Несколько поразмыслив, бабушка использует вынесение за скобку: $$f = x_{1}\wedge x_{14} \wedge (x_{5} \vee x_{7} \vee x_{4} \wedge x_{10})$$. Тогда окончательный текст сообщения принимает вид: "После завтрака я катаюсь на лошади летом или зимой, а также, бывает, и весной, - вместо прогулки". Как же бабушка определила форму того логического выражения - функции, отображающей все возможные варианты, и даже пути, ведущие к свершению интересующего события?

Ответ следующий: необходимо на каждом пути в дереве логических возможностей, ведущем к заданному событию, построить конъюнкцию событий, образующих этот путь. Затем все такие конъюнкции объединить операцией дизъюнкции. Поскольку используются только исчерпывающие множества событий, очевидно, что эта дизъюнкция выполняется с помощью операции $$\vee$$, т.е. ИСКЛЮЧАЮЩЕЕ ИЛИ (хотя можно пользоваться значком $$\vee,$$ опираясь на действительный, "физический" смысл возможных событий ).

Полученная таким способом функция подвергается дистрибутивному преобразованию - "вынесению за скобки".

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

Например, функция, отображающая такое событие в жизни бабушки, как езда на велосипеде, имеет вид

$$g = x_{1} \wedge x_{4} \wedge x_{10} \wedge x_{13} \dot\vee x_{1} \wedge x_{5} \wedge x_{13} = x_{1} \wedge x_{13} \wedge (x_{4} \wedge x_{10} \dot\vee x_{5}).$$ (рис 1.1) Полное дерево логических возможностей

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

Определение 5. Совокупность всех исследуемых в данном контексте событий, т.е. множество - объединение всех рассматриваемых ИМС - образует факторное пространство событий .

Как и ранее, точку факторного пространства (ситуацию) будем обозначать {x1, ..., xn}.

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

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

Например, можно отдельно исследовать факторное подпространство, сформированное на основе первых двух уровней ветвления (рис. 1.2) в приведенном на рис. 1.1 дереве логических возможностей. Это может быть необходимо при планировании финансовых расходов пансионата на питание.

(рис 1.2) Факторное подпространство для исследований финансовых затрат на питание

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

(рис 1.3) Факторное пространство для планирования использования спортивного инвентаря

1.5. Система принятия решений

Для некоторой логической функции f от переменных из факторного пространства событий воспользуемся операцией следования (импликации) и сформируем логическое выражение вида

$$f(x_{1}, \dots , x_{n}) \to R$$

Здесь f следует рассматривать как выражение, определяющее условие, сложившуюся ситуацию, посылку, а R - высказывание, которое рассматривается как следствие: правило поведения, значение векторной функции, указание к действию и т.д. Таким образом, возможно формирование связей вида "посылка - следствие", "если $$\dots$$, то $$\dots$$ ". При этом функция f задается на множестве ситуаций и указывает на то, что, если на некоторой ситуации она принимает значение 1 (ИСТИНА), то такое же значение принимает высказывание R, являясь руководством к действию, к принятию определенного решения.

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

$$\begin{array}{l} f_{1}(x_{1}, \dots , x_{n}) \to R_{1}\\ \dots \dots \dots \dots \dots \dots \dots \\ f_{m}(x_{1}, \dots, x_{n}) \to R_{m}\end{array}$$

Определение 6. Система логических выражений вида (1.16), заданная на факторном пространстве (подпространстве) событий, обладающая полнотой и непротиворечивостью, называется системой принятия решений .

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

То, что система функций f1, ..., fm является полной, означает, что любая точка факторного пространства событий входит в область задания хотя бы одной из этих функций. Непротиворечивость означает, что по каждой ситуации одна и только одна из этих функций принимает значение 1, приводящее к истинности соответствующего высказывания - решения. Однако отметим, что в действительности на основе смыслового содержания задачи по каждой или некоторой ситуации может быть известно более одного правильного решения, приводящего к успешным действиям. В таком случае высказывания об этих решениях могут быть объединены операцией ИЛИ, что приводит к приведенному выше предположению о непротиворечивости.

Продолжим рассмотрение примера.

Пусть известная нам бабушка планирует занятия физкультурой и спортом во все времена года по времени дня: после завтрака, после обеда и после ужина. Объединяя высказывания по принципу "если $$\dots$$, то" и пользуясь обозначениями на рис. 1.1, она формирует систему принятия решений, которой, не полагаясь на память, намерена строго следовать, добившись согласия администрации.

Система имеет вид

$$\begin{array}{1lcl} 1. x_1\wedge x_4 \to R_1 = \mbox{Прогулка на велосипеде};\\ 2. x_1\wedge x_6 \vee x_2\wedge x_4 \to R_2 = \mbox{Шахматы};\\ 3. x_2\wedge x_5 \vee x_1\wedge x_7 \to R_3 = \mbox{Верховая езда};\\ 4. x_1\wedge x_5 \vee x_2 \wedge x_6 \to R_4 = \mbox{Байдарка}; \\ 5. x_3 \wedge (x_4 \vee x_6) \to R_5 = \mbox{Дискотека};\\ 6. x_2 \wedge x_7 \to R_6 = \mbox{Пешая прогулка};\\ 7. x_3 \wedge (x_5 \vee x_7) \to R_6 = \mbox{Пешая прогулка}. \end{array}$$

Планируя пешую прогулку, бабушка первоначально получила следующее выражение:

$$x_2 \wedge x_7 \vee x_3 \wedge x_5 \vee x_3 \wedge x_7 \to R_6 = \mbox{Пешая прогулка}$$

Однако выше не напрасно обращается внимание на целесообразность однократного вхождения переменных в подобное выражение (это будет изучено в лекциях 9 и 10). Выражение, полученное первоначально, с помощью дистрибутивных преобразований привести к такому виду не удается. Тогда бабушка решает разбить это выражение на два подобных, сформировав получение одного и того же решения на основе двух условий. Это и послужило появлению в (1.17) двух выражений, определяющих одно решение R6.

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

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

1.6. "Схемотехническое" представление системы принятия решений

Отобразим (c нарушением некоторых стандартов) схемотехнически бабушкину СПР, подобно электронной схеме (рис. 1.4) с помощью конъюнкторов и дизъюнкторов. На вход будем подавать значения истинности переменных-высказываний (ситуации) так, чтобы на одном из выходов формировалась единица - значение истинности соответствующего решения. Задавать значение ситуаций следует корректно, чтобы соблюдать требования вхождения переменных в исчерпывающие множества событий.

(рис 1.4) "Электронная" схема системы принятия решений

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

Например, бабушка хочет вспомнить, чем она должна заниматься летом после обеда. Она полагает x2 = x5 = 1 при нулевых значениях других переменных и запускает программу, моделирующую работу электронной схемы. На выходе R3 формируется сигнал, соответствующий высказыванию "Верховая езда".

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

1.7. Достоверность высказываний о событиях

Говоря о высказываниях как о логических переменных, мы, несомненно, предполагаем наличие субъективного фактора: ведь это кто-то сказал. И мы говорим верному другу: "Я мало доверяю этому человеку, но он сказал $$\dots$$, а дыма без огня не бывает".

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

Таким образом, необходимо ввести понятие достоверность высказывания, которая идеально представляет вероятность того, что данное высказывание о свершении события истинно, т.е. представляющая его логическая переменная равна 1.

В этой оценке достоверности вновь практически преобладает субъективный фактор. Поэтому при построении экспертных систем применяется двойная оценка: оценка, данная экспертом по запросу, и вес самого эксперта. Здесь эффективно используется аппарат нечетких множеств [30].

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

Рассмотрим пример. Информатор сообщает Агенту о том, что видел своими глазами, как Марина передала Васе пачку денег. Призвав на помощь свой богатый опыт, Агент рассуждает логически:

Насколько можно доверять Информатору, который три дня не брился и от которого дурно пахнет?

Мог ли находиться Информатор в это время в нужном месте, чтобы "видеть своими глазами"?

Насколько верно то, что в переданной пачке были деньги?

Можно ли оперативно воспользоваться существующими математическими методами оценки (например, аппаратом нечетких множеств), заодно учитывающими другие факторы, как, например, личные финансовые трудности, или необходимые оценки следует выполнить интуитивно, "с потолка"?

Так какова же должна быть формулировка отчета в Центр для получения максимального вознаграждения за поимку взяточника?

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

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

Однако смущают два обстоятельства:

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

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

Пусть рассмотренные выше переменные-высказывания {xi}, образующие факторное пространство, могут принимать значения достоверности {Pi}, 0 <= Pi <= 1,i = 1,...,M.

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

Перегруппируем события и дополним дерево логических возможностей, представленное на рис. 1.1, указав на его ветвях (стрелках), в качестве весов этих ветвей, значения достоверности событий (рис. 1.5). Получим вероятностное дерево логических возможностей.

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

(рис 1.5) Вероятностное дерево логических возможностей

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

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

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

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

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

0,25 x 0,33 x 0,5 x 0,4 + 0,25 x 0,33 x 0,3 = 0,04125.

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

0,25 x 0,33 x 0,5 x 0,4 + 0,25 x 0,33 x 0,3 + 0,25 x 0,33 x 0,2 = 0,05775.

1.8. Системы принятия решений на основе достоверности высказываний о событиях

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

(рис 1.6) Система принятия решений на основе достоверности событий

Следуя далее по пути приблизительных оценок (ибо практически достоверность, как категория теории вероятностей, принадлежит области весьма приблизительных оценок), разработаем некоторый суррогат операций конъюнкции N1 и дизъюнкции N2 на основе передаточной функции порогового элемента, преобразующего сумму входных величин в выходные значения, которые приближенно "напоминают" результаты упомянутых логических операций. Этот путь - путь ухода от точного выбора решения в сторону выбора решения на основе степени похожести ситуаций на уже известные, - путь ассоциативного мышления.

Существует множество вариантов подбора пороговой передаточной функции, лежащей в основе такого элемента.

Введем сквозную нумерацию всех узлов схемы, реализующих дизъюнкцию и конъюнкцию. Пусть i - номер такого узла, j - номер входа этого узла при количестве mi активных входов (в данном примере каждый узел имеет два входа), $$\omega _{j}$$ - вес входа. Тогда простейшая передаточная функция fi, реализуемая i -м узлом для замены логических операций конъюнкции и дизъюнкции, имеет вид

$$f_i = \left \{ \begin{array} {ll} \sum^m_{j=1} f_j \omega_j, \mbox{если } \sum^m_{j=1} f_j \omega_j \ge 0 \\ 0, \mbox{в противном случае} \end{array} \right$$

Здесь fj - величина сигнала, поступающая на j -й вход.

Тогда элемент N1, подобный конъюнктору, может быть реализован при $$\omega _{j} = 1/m_{i}$$, j =1, ..., mi, с помощью существенно высокого порога (рис. 1.7), где значение $$\delta _{i}$$ обусловлено некоторой поправкой, достаточной, чтобы для преодоления порога сигналы возбуждения с большой степенью уверенности поступали обязательно по всем входам.

(рис 1.7) Элемент N1

На этапе настройки и верификации СПР предполагается, что входные сигналы - булевы переменные, принимающие значения 0, 1. Тогда целесообразно выбрать значение $$\delta _{i} < 1/m_{i}$$. Очевидно, что для того, чтобы преодолеть порог, на всех входах должны быть "1"; недостаток хотя бы одной "1" приведет к тому, что сумма поступивших сигналов будет более чем на 1/mi меньше указанной суммы весов.

При переходе к действительным переменным, когда вместо событий рассматриваются, например, лишь предполагаемые вероятности их наступления, экспериментальный выбор значения $$\delta _{i}$$ может обусловить ту границу, когда считаться с возможностью данной комбинации событий нецелесообразно.

Элемент N2, подобный дизъюнктору, реализуется, наоборот, при низком значении порога и при $$\omega _{j} = 1, j = 1, \dots , m_{i}$$. Порог выбирается так, чтобы уже при возбуждении на одном входе возникал сигнал возбуждения на выходе. При этом сигнал на выходе не превышает "1" (рис. 1.8), а значение $$\delta _{i}$$ выбирается экспериментально достаточно небольшим.

(рис 1.8) Элемент N2

Задав на входе СПР значения достоверности переменных-высказываний и рассчитав значения на выходах пороговых элементов, на выходах схемы получим некоторые значения. Максимальное из этих значений "голосует" в пользу соответствующего решения.

Предложения, касающиеся создания пороговых элементов N1 и N2, носят лишь рекомендательный характер. Здесь неограниченный простор для творчества.

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

На рассмотренном жизненном примере проанализируем принимаемые бабушкой решения на основе двух вариантов СПР: с помощью электронной схемы (рис. 1.4), использующей определенность знания о ситуации, и с помощью схемы, основанной на неопределенности, на предполагаемой достоверности этих знаний (рис. 1.6). Положим (на основе интуиции) $$\delta _{i} = 0,3$$ для всех i.

Данные сведены в табл. 1.2.

Сравнительные оценки получаемых решений

Переменные							Решение по электронной схеме	Решение на основе достоверности событий
x1 (P1)	x2 (P2)	x3 (P3)	x4 (P4)	x5 (P5)	x6 (P6)	x7 (P7)
1				1			R1	R1
	1			1		1	R3	R3
1		1					Нет решения	Нет решения
0,8	0,2			0,4	0,5		Решение не определено	R2
0,2	0,4	0,6	1			0,5	Решение не определено	R2

Более точный выбор значения $$\delta _{i}$$ производится на основе верификации СПР по известным вариантам нахождения решения. В данном случае представляется, что этот выбор произведен успешно.

1.9. Минимизация длины логической цепочки в системе принятия решений

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

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

Очевидно, что в схеме на рис. 1.4 максимальная длина логической цепочки равна двум.

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

(рис 1.9) Преобразование электронной схемы с единичной длиной логической цепочки в однослойную систему принятия решений

Таким образом, доказано следующее утверждение:

Лемма 1. Любая СПР, сформированная на основе логического описания булевыми функциями, способом "размножения" решений преобразуется в однослойную СПР на основе достоверности событий.

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

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

При составлении "электронной" схемы такое объединение производится с помощью операции дизъюнкции, что приводит к длине логической цепочки, равной двум. Но ведь если, формируя структуру СПР, строго следовать порядку построения "электронная схема $$\to$$ система принятия решений ", то и СПР будет иметь максимальную логическую цепочку с длиной, равной 2.

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

"Размножение" решений имеет важное достоинство. Оно позволяет установить причину, найти объяснение принимаемого решения. Это означает, что текст решения может быть дополнен указанием причины принятия именно такого решения.

Например, получив информацию о необходимости заказа велосипеда в отделе спортинвентаря, бабушка может воспользоваться и важным объяснением: "…потому что сейчас, скорее всего, весна, а вы, вероятно, только что сытно позавтракали" (рис. 1.10).

(рис 1.10) Бабушка

В заключение данной лекции следует отметить, что построен алгоритм параллельных вычислений [6] сложных логических конструкций в области действительных переменных, предназначенный для реализации высокого быстродействия в системах управления и принятия решений. Более того, сведение СПР к однослойной приводит к применению лишь тех передаточных функций (элементов N1 на рис. 1.6 и рис. 1.9), которые имитируют конъюнкторы. Это служит повышению достоверности оценок, стандартизации и адекватности природным процессам.