Приложение В (справочное). Методы булевой алгебры

Приложение В
(справочное)

Методы
булевой алгебры

В.1 Предварительные замечания

Помимо использования булевых таблиц истинности (см. 11.4) и бинарных диаграмм принятия решений (см. 11.5), анализ RBD использует в основном обычные алгебраические математической формулы. Однако булева алгебра в целом также может быть использована для целей такого анализа и во многих случаях она более эффективна и прямолинейна. В частности, использование булевой алгебры вполне может быть самым простым подходом:

a) для RBD, содержащей повторяющиеся блоки (см. рисунок 37);

b) RBD, содержащей стрелки направлений (см. рисунки 10 и 35);

c) особенно сложной системы;

d) более простого построения логического выражения успеха (или отказа) системы, чем построение RBD;

e) систем, содержащих слишком большое количество блоков, чтобы их можно было обработать по простым формулам.

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

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

В.2 Обозначения

Символы и , обозначающие логические "ИЛИ" и "И", в булевой алгебре играют ту же роль, что и сложение (+) и умножение () в обычной алгебре. Поэтому в дальнейшем оказалось более удобным использовать символ "+" для обозначения логического "ИЛИ" и знака "" для обозначения логического "И" ¹⁾. Как обычно черточка над булевой переменной означает обратную или дополняющую переменную: например, - обозначает "не а". Например, следует интерпретировать как "а И b И, не с И е ИЛИ f И g". Область применения символов должна быть понятной.

------------------------------

¹⁾_{Примечание - Преимущество такого обозначения становится очевидным в приложении В, где часто встречаются выражения вида . Запись этого выражения с использованием символов теории множеств: S = abebedaedсdacd, многим читателям может показаться менее понятной.}

------------------------------

В.3 Анализ наборов соединений (путей успеха) и наборов обрывов (путей отказа)

B.3.1 Понятие наборов обрывов и соединений

В соответствии с 8.1, RBD можно рассматривать как электрическую цепь (см. рисунок 14), эта аналогия полезна для идентификации:

- наборов соединений, которые соответствуют замкнутой электрической цепи и представляют собой комбинации блоков в работоспособном состоянии, ведущих к работоспособному состоянию системы. Наборы соединений также есть пути "успеха" RBD;

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

Использование этой аналогии позволяет преобразовать RBD, представленную на рисунке 10, в электрическую схему, представленную на рисунке 15. Используя это представление, легко определить различные наборы соединений RBD, на рисунках B.1 и В.2 показаны различные примеры комбинаций закрытых переключателей, соответствующих работоспособному состоянию системы.

Рисунок B.1 - Примеры минимальных наборов соединений (путей успеха)

На рисунке В.1 любое размыкание (т.е. любой отказ) переключателей приводит к размыканию (обрыву) цепи и неработоспособному состоянию системы. Все замкнутые переключатели (т.е. блоки в работоспособном состоянии) необходимое и достаточное условие для того, чтобы система была в работоспособном состоянии. Эти комбинации минимальны и называются минимальными наборами соединений.

Рисунок В.2 - Примеры неминимальных наборов соединений (путей успеха)

На рисунке В.2 некоторые открытые переключатели (например, B2 слева или С1 справа) не изменяют работоспособное состояние системы. Не требуется, чтобы переключатели были закрыты (т.е. блоки были в работоспособном состоянии), чтобы система была в рабочем состоянии. Эти комбинации не являются минимальными и называются неминимальными наборами соединений (или просто наборами соединений).

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

Рисунок B.3 - Примеры минимальных наборов обрывов

На рисунке B.3 любое замыкание (означает ремонт) разомкнутых выключателей приводит к замыканию цепи и переходу системы в работоспособное состояние. Все открытые переключатели (т.е. блоки в неработоспособном состоянии) необходимы и достаточны, чтобы система находилась в неработоспособном состоянии. Эти комбинации минимальны и называются минимальными наборами обрывов.

Рисунок В.4 - Примеры неминимальных наборов обрывов

На рисунке В.4 некоторые замыкания открытых переключателей (например, С2 слева или B2 справа) не влияют на изменение неработоспособного состояния системы. Все открытые переключатели (т.е. блоки в неработоспособном состоянии) не являются необходимыми для того, чтобы система находилась в неработоспособном состоянии. Эти комбинации не являются минимальными и называются неминимальными наборами обрывов (или просто наборами обрывов).

B.3.2 Последовательно-параллельное представление с использованием минимальных наборов соединений и обрывов

Применение свойств булевой алгебры позволяет представить работоспособное состояние системы S в виде объединения минимальных множеств соединений (П _i) из RBD, а неработоспособное состояние системы s в виде объединения минимальных наборов обрывов (С _k) из RBD.

Такой подход можно применить к предыдущему примеру, в котором есть четыре минимальных набора соединений, (), (), (), (). В результате:

.

(В.1)

В том же примере имеется четыре минимальных набора обрывов: (), (), (), () что дает:

.

(В.2)

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

Формула (В.2) эквивалентна следующей формуле

.

Преобразование (В.2) предполагает использование законов Де Моргана:

,

.

Это приводит к тому, что:

.

Таким образом:

.

(В.3)

Получено две эквивалентных логических формулы, представляющих RBD в работоспособном состоянии. Формула (В.1) обеспечивает представление с путями успеха, а формула (В.3) (см. рисунок 18) - представление RBD с минимальными наборами обрывов (см. рисунок 19).

В.3.3 Идентификация минимальных наборов обрывов и наборов соединений

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

Это может быть сделано на примере простого RBD, как показано ниже с RBD, изображенной на рисунке В.5.

Рисунок В.5 - Пример RBD с наборами соединений и обрывов различного порядка

Логическая структура этой RBD обеспечивает следующую логическую формулу:

.

(В.4)

Преобразование (В.4) приводит к следующему:

.

Поэтому данная RBD имеет три минимальных пути успеха:

.

Минимальные наборы обрывов можно получить, дополняя (В.4) и используя законы Де Моргана:

,

,

.

Таким образом, найдены семь минимальных наборов обрывов:

.

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

Таким образом, наборы обрывов RBD, приведенной на рисунке В.5, могут быть отсортированы по порядку (см. 3.18, примечание 2):

- набор первого порядка ;

- набор второго порядка (), ();

- набор третьего порядка (), (), (), ().

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

За исключением простых случаев, приведенные выше расчеты на самом деле не поддаются ручной обработке, но имеются мощные алгоритмы в доступных пакетах программ для RBD. Минимальные наборы соединений и обрывов могут быть найдены с помощью, например, бинарных диаграмм принятия решений, рассмотренных в вероятностных вычислениях настоящего стандарта.

В.4 Принципы расчетов

В.4.1 Последовательные структуры

Рассмотрим систему, состоящую из n последовательных блоков (В _i), показанную на рисунке 2. Из рисунка видно, что система в целом находится в работоспособном состоянии, когда все блоки B _i находятся в работоспособном состоянии. Другими словами, логическое выражение успеха системы имеет вид

,

(В.5)

где b _i - логическая переменная, соответствующая работоспособному состоянию блоков В _i.

Если блоки независимы, то вероятность того, что система находится в работоспособном состоянии, равна

.

(В.6)

Поэтому особых вычислительных проблем при вычислении P _s в случае последовательной структуры не существует.

Однако, если приведенная последовательная структура (В.5) относится к более крупной RBD, то этот расчет может быть сделан только в том случае, если ни один блок этой последовательной структуры не повторяется в другом месте более крупной RBD. В противном случае следует применять методы, описанные в В.5 или В.6.

В.4.2 Параллельные структуры

Рассмотрим систему из двух блоков в нагруженном резерве, такую как изображена на рисунке 21. Из рисунка можно видеть, что система в целом находится в работоспособном состоянии при условии, что А или В (или оба) находятся в работоспособном состоянии. Другими словами, логическое выражение успеха системы имеет вид

,

(В.7)

где а и b - булевы переменные, соответствующие работоспособному состоянию блоков А и В соответственно.

Для заданного времени t возникает соблазн заменить а и b на Р _а и Р _b соответственно и переписать формулу (В.7) в виде

.

(В.8)

Как ожидается формула (В.8) дает вероятность P _s того, что система находится в работоспособном состоянии, но, к сожалению, это неверно, поскольку она получена из булева выражения, в котором переменные перекрываются (т.е. ). Выражение (В.8) даже не предусматривает в общем случае приемлемого приближения P _s. Например, P _s = 1,2 при Р _а и Р _b, равных 0,6. Это не верно.

Формула (В.8) должна быть дополнена следующим образом:

.

(В.9)

В отличие от (В.8), формула (В.9) дает точный результат в любом случае,

.

Рассмотрение структуры, состоящей из n параллельных блоков (Bi), приводит к следующему выражению:

.

Обобщение формулы (В.9) называют формулой Сильвестра-Пуанкаре:

.

(В.10)

Это альтернативная сумма убывающих членов, которые сходятся в результате к P _s. Количество членов сильно возрастает при увеличении n, а сходимость очень медленная, если вероятность высока. Это, к сожалению, случай, когда вероятности Р _bi работоспособного состояния блоков близки к 1. Следовательно, формула (В.10) не подходит для оценки P _s из-за необходимости вычисления очень большого количества членов.

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

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

Если а и b не зависят друг от друга, то не зависят также и . Тогда вероятность того, что система находится в неработоспособном состоянии имеет вид

.

И наконец .

Это выражение можно легко обобщить на n параллельных блоков , то есть , полученное с помощью применение законов де Моргана.

.

(В.11)

Формула (В.11), включающая только простые произведения для расчета параллельных структур, является более простой, чем формула Сильвестра-Пуанкаре.

В.4.3 Сочетание последовательных и параллельных структур

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

.

(В.12)

Аналогично для рисунка 5:

.

(В.13)

Для рисунков 6 и 7 можно получить вероятности успеха системы просто умножая (В.12) и (В.13) на P _d.

Тем не менее, за исключением простых случаев по формулам (В.12) или (В.13) нелегко выполнить вручную. Существуют мощные алгоритмы, реализованные в виде пакета программ для RBD. Они основаны на методах, рассмотренных в В.5, В.6 или В.7.

В.4.4 Структура m из n (идентичные элементы)

Среди простых случаев формулы вероятности успеха системы, соответствующие рисункам 8 (2/3) и 9 (3/4), немного сложнее, чем рассмотренные в В.4.3.

Для системы 2/3, представленной на рисунке 8, формула (В.9) дает

.

Если блоки независимы и имеют одинаковую вероятность успеха, р, то .

Это выражение можно преобразовать и, следовательно

.

(В.14)

Формулу (В.14) можно обобщить на структуру m/n, состоящую из n идентичных блоков. В этом случае для успеха системы требуется работоспособность m блоков из n, а вероятность успеха системы P _s имеет вид

.

(В.15)

Применение (В.15) к логической структуре 2/4, представленной на рисунке 9, дает

.

(В.16)

Система m/n находится в работоспособном состоянии, если в работоспособном состоянии находится m блоков. Тогда для того, чтобы эта система находилась в неработоспособном состоянии необходимо, чтобы (n - m + 1) блоков находились в неработоспособном состоянии. Поэтому система m/n по отношению к работоспособному состоянию является системой (n - m + 1)/n по отношению к неработоспособному состоянию и вероятность отказа системы m/n можно получить заменами m на (n - m + 1) и р на (1 - р) в формуле (В.15):

.

(B.17)

Конкретные ситуации.

- Если m = n - 1 (например, 2/3, 3/4 и т.д.) формула (В.15) сводится к

.

(В.18)

- Если n = 2m - 1, система симметрична относительно успеха и отказа: система находится в работоспособном состоянии, если m блоков находятся в работоспособном состоянии, и находится в неработоспособном состоянии, если m блоков находятся в неработоспособном состоянии. Это относится к структурам 1/1, 2/3, 3/5 и т.д. Благодаря этому свойству, структуру 2/3 широко используют в промышленности при проектировании систем безопасности.

Если n элементов не идентичны, рекомендуется использовать более общую процедуру (см. 11.8.2).

В.5 Использование формулы Сильвестра-Пуанкаре для большие RBD и повторяющихся блоков

В.5.1 Общие положения

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

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

В.5.2 Формула Сильвестра-Пуанкаре для наборов соединений

Для состояния успеха системы, имеющей n путей успеха (минимальные наборы соединений), (П _i), можно записать

.

Минимальные наборы соединений П _i не являются независимыми друг от друга, и соответствующая формула Сильвестра-Пуанкаре имеет следующий вид:

.

(В.19)

Формула (В.19) показывает, что вероятность объединения наборов соединений равна

1) сумме вероятностей множества соединений (SP _i);

2) минус сумма вероятностей пересечения наборов соединений 2 х 2 (SP _ij);

3) плюс сумма вероятностей пересечения наборов соединений 3 x 3 (SP _ijk);

4) минус сумма вероятностей пересечения наборов соединений 4 x 4 (SP _ijkl)

5) и т.д.

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

Это можно показать на примере, рассмотренном в 8, который включает четыре минимальных множества соединений: , , , .

Реализация формулы (В.19) приводит к следующим результатам.

a) первый член SP _i:

;

b) второй член SP _ij:

;

c) третий член SP _ijk:

;

d) четвертый член SP _ijkl:

.

Таким образом, для четырех минимальных наборов соединений необходимо идентифицировать и составить 4 + 6 + 3 + 1 = 14 членов.

Поскольку вероятность множества соединений Р(П _i) обычно не мала по сравнению с 1, то вероятности , тоже не маленькие и их нельзя игнорировать.

При наличии трех событий с высокой вероятностью Р _а = Р _b = Р _с = 0,9 можно получить следующие результаты:

,

.

Ни один член не является пренебрежимо малым, и все члены должны быть учтены в расчетах.

Формула (В.19) на практике не подходит для расчетов, потому что для этого требуется получить слишком много членов с подходящей аппроксимацией.

В.5.3 Формула Сильвестра-Пуанкаре для набора обрывов

Состояние отказа системы, имеющей m путей отказа (минимальных наборов обрывов) (С _i) можно записать в виде

.

Это приводит к соответствующей формуле Сильвестра-Пуанкаре:

.

(В.20)

Пример из 8 также включает четыре минимальных набора обрывов

.

Как и в случае с наборами соединений необходимо вычислить 14 членов, однако эта ситуация совсем другая, поскольку вероятности Р(С _i) обычно малы по сравнению с 1.

Тогда вероятности Р(), Р() и т.д. все меньше и меньше и формула (В.20) сходится довольно быстро. Поэтому возможны аппроксимации.

Из формулы видно, что результаты трех событий с высокой вероятностью (Р _а = Р _b = Р _с = 0,9) и трех событий с низкой вероятностью (Р _а = Р _b = Р _с = 0,01) можно сравнить:

- Р(а + b + с) = 2,7 - 2,43 + 0,729 = 0,999 получается при Р _а = Р _b = Р _с = 0,9;

- Р(а + b + с) = 0,03 - 0,0003 + 0,000001 = 0,029701 получается при Р _а = Р _b = Р _с = 0,01.

Тогда в случае с низкими вероятностями

- член SP _i обеспечивает верхнюю границу вероятности: 0,03,

- разность SP _i - SP _ij обеспечивает нижнюю границу: 0,0297, а точный результат принадлежит интервалу [0,0297, 0,03].

Эти результаты могут быть экстраполированы на большое количество событий:

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

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

Формула Сильвестра-Пуанкаре (В.20), использующая наборы обрывов (С _i), которые обычно включают низкие вероятности, является более хорошим кандидатом для получения приемлемого приближения, чем формула (В.19), использующая наборы соединений (П _i). Поэтому при выполнении вероятностных расчетов лучше рассматривать минимальные наборы обрывов (С _i), чем наборы соединений (П _i).

Чем ниже результирующая вероятность P _s, тем быстрее происходит сходимость и в лучшем случае хорошо работает следующая аппроксимация

.

(В.21)

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

В.6 Метод дизъюнкции булевых выражений

В.6.1 Общие сведения и справочная информация

Формула (В.7) может быть записана в эквивалентном виде:

.

(В.22)

Процесс преобразования (В.7) в (В.22) называется дизъюнкцией.

В (В.22) члены а и являются непересекающимися членами. Это означает, что и следовательно, . Тогда P _s сводится к известному результату:

.

(В.23)

Следует заметить, что формулу (В.7) также можно записать в других дизъюнктивных формах, одна из которых имеет вид , что приводит к другому выражению:

.

(В.24)

Очевидно, что (В.23) и (В.24) эквивалентны ранее полученным формулам и .

В отличие от предыдущих выражений количество членов в формуле вероятности совпадает с количеством непересекающихся членов в булевом уравнении. Рассмотрим s, представленную объединением непересекающихся путей успеха:

.

Тогда формула Сильвестра-Пуанкаре принимает вид

.

(В.25)

Аналогично, если s представлена объединением непересекающихся наборов обрывов, то можно записать:

, где .

Формула Сильвестра-Пуанкаре принимает вид

.

(В.26)

Поэтому и при условии минимальных наборов соединений или обрывов формулы (В.25) и (В.26) могут быть использованы для выполнения точных вычислений. Если вероятности отказа блока изменяются во времени, эти формулы могут быть использованы для расчетов показателей готовности, A _S(t) или неготовности U _S(t).

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

Следует отметить, что два члена взаимно не пересекаются, если хотя бы одна переменная в одном члене появляется в другом в виде своего дополнения. Например, термины и не пересекаются из-за переменной s. Верно и обратное. А именно два члена не являются непересекающимися (то есть пересекаются), если ни одна из переменных в одном члене не появляется в другом в виде своего дополнения. Например, два члена и не являются взаимно непересекающимися.

В.6.2 Принцип дизъюнкции

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

Основной принцип заключается в следующем:

- выделяют все переменные в которые не появляются в (такие члены называют относительным дополнением по отношению к ). Предположим, что относительным дополнением является ;

- затем замените на

.

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

Например, чтобы сделать член непересекающимся с членом , необходимо:

- найти относительное дополнение по отношению к : ;

- заменить на

.

Теперь и * являются непересекающимися по отношению друг к другу.

В.6.3 Процедура дизъюнкции

Основная процедура дизъюнкции состоит в следующем:

a) представляют успех системы (обозначаемый s ₁) в виде суммы произведений булевых переменных ¹⁾ (т.е. наборов соединений) и обозначают члены слева направо: ", , , ...";

------------------------------

¹⁾_{Для простых булевых выражений успеха системы могут быть использованы произведения одного, двух и более членов.}

------------------------------

b) выбирают в качестве "основного" члена и сравнивают его с ;

c) при необходимости (т.е. если два члена не являются непересекающимися) делают непересекающимся по отношению к в соответствии с В.6.2:

d) при необходимости делают непересекающимся по отношению к ;

e) продолжают процесс для остальных членов в s ₁;

f) проверяют несколько расширенное (за счет добавленных дополнительных членов) выражение, полученное на этом этапе и упрощают его (где это возможно) с помощью правил булевой алгебры (используя такие правила, как х + х = х, , ). Обозначают полученное выражение s ₂, а его члены слева направо: , , , ...;

q) выбирают второй член () из выражения для s ₂ в качестве "основного" члена и сравнивают с ; так действуют в соответствии с перечислениями с) - f), используя члены s ₂. Обозначают полученное выражение s ₃;

h) продолжают описанную выше процедуру до тех пор, пока все члены не будут использованы в качестве "основных" членов, к этому времени полученное выражение будет полностью дизъюнктивной версией исходного выражения s ₁.

Наконец, формируют набор непересекающихся членов (), относящихся к успеху системы, как описано в В.6.1. Таким образом, для вероятности успеха P _s или коэффициента готовности A _S(t) может быть применена формула (В.25).

Такая процедура может быть использована для получения непересекающихся членов (), относящихся к отказу системы в соответствии с В.6.1. Следовательно, вероятность отказа P _s или коэффициент неготовности U _s(t) системы можно рассчитать, применив формулу (В.26).

Описанная процедура является основной и может быть улучшена так же, как это сделано в примере, приведенном в В.6.4.

В.6.4 Пример применения процедуры дизъюнкции

Предположим, что система состоит из пяти элементов А, В, С, D и Е и что а, b, с, d и е - соответствующие булевы переменные "успеха". Предположим также, что успех системы (s) в булевых переменных определяется следующим выражением, которое включает в себя четыре суммы произведений (т.е. четыре набора соединений):

.

Чтобы сделать приведенное выражение непересекающимся, основная процедура, описанная в В.6.3, может быть усовершенствована и применена следующим образом:

Этап 0 - Классификация путей по возрастанию длины и в алфавитном порядке:

.

Этап 1 - выполнение дизъюнктивной процедуры, начиная с последнего произведения () для преобразования его в непересекающееся со всеми его предшественниками:

1.1: применение процедуры к непосредственному предшественнику () путем:

- идентификация событий, принадлежащих , но не . Это дает с,

- замена выражения в исходной формуле на ;

1.2: повторение этапа 1.1 для следующего члена слева ():

- идентификация событий, принадлежащих , но не . Это дает b,

- замена выражения , измененного на этапе 1.1 (т.е. ) на в исходной формуле;

1.3: нет необходимости в повторении этапа 1.2 со следующим членом слева (), потому что последнее произведение , модифицированное в , не пересекается с . Дизъюнктивная процедура, применяемая к выполнена.

Исходная формула может быть переписана следующим образом:

.

Этап 2 - Повторение описанной выше процедуры (этапы 1.1-1.3) для обеспечения непересекаемости с его предшественниками.

2.1. Как и ранее, применение процедуры к первому непосредственному предшественнику :

- идентификация событий, принадлежащих , но не . Это дает b и е;

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

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

- идентификация событий, принадлежащих , но не . Это дает а;

- замена выражения на в исходной формуле, которая принимает вид:

.

Этап 3 - Повторение дизъюнктивной процедуры для обеспечения непересекаемости с его единственным предшественником :

- идентификация событий, принадлежащих , но не . Это дает а;

- замена выражения на в исходной формуле.

Этап 4 - Поскольку первое произведение (здесь ) всегда остается неизменным, процедура завершена и дает следующую конечную сумму непересекающихся произведений:

.

Получено пять непересекающихся членов

,

,

,

,

.

В соответствии с В.6.1 s можно записать в виде .

Поэтому вероятность успеха P _s или коэффициента готовности A _S(t) системы могут быть вычислены по формуле (В.25)

.

.

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

Конечно, такая же процедура может быть использована с минимальными наборами обрывов для поиска непересекающихся наборов (), позволяющих вычислять вероятность отказа или коэффициент неготовности U _s(t) системы по формуле (В.26):

.

B.6.5 Комментарии

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

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

В.7 Бинарные диаграммы принятия решений

В.7.1 Установление BDD

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

Булева функция, смоделированная RBD, приведенная на рисунке 6, зависит от четырех булевых переменных а, b, с и d.

Декомпозиция Шеннона аналогична таблице истинности булевой функции, моделируемой RBD.

Рисунок В.6 - RBD, приведенная на рисунке 35

Рисунок В.7 - Декомпозиция Шеннона булевой функции, представленной на рисунке В.6

Эта декомпозиция представлена в графическом виде на рисунке В.7. Процесс выполнения состоит в следующем:

1) выбирают одну из переменных (например, а) и помещают ее в верхнюю часть схемы;

2) от этой переменной рисуют две стрелки для представления двух ее возможных состояний: например, 1 слева и 0 справа (сплошные и пунктирные линии использованы для наглядности рисунка);

3) выбирают другую переменную (например, b) и соединяют ее с нарисованными стрелками. Эта переменная появляется два раза;

4) от каждой этой переменной рисуют две стрелки для представления двух ее возможных состояний;

5) выбирают другую переменную (например, с) и соединяют ее с имеющимися стрелками. Эта переменная появляется четыре раза:

6) и так далее до тех пор, пока все переменные не будут обработаны.

Тогда для n переменных получается 2 ⁿ путей. Каждый из них ведет к успеху функции (s = 1) или к ее отказу  = 0. Это можно узнать путем анализа соответствующей RBD.

Рисунок В.8 - Идентификация частей, состояние которых не имеет значения

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

Они выделены пунктирными прямоугольниками на рисунке 8. Например, с левой стороны состояние системы не зависит от состояния переменной d и с правой стороны оно не зависит от состояний переменных с и d.

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

Рисунок В.9 - Упрощение разложения Шеннона

На этой схеме можно выделить 9 путей: 5 путей ведут к успеху S и 4 - к ее отказу. Анализ этих путей по BDD позволяет определить связь между s или и состояниями переменных а, b, с и d:

,

.

Следующим этапом является построение BDD, связанной с RBD. Как показано на рисунке В.10 это делают просто, собирая входы с одинаковыми величинами.

Рисунок В.10 - Бинарная диаграмма принятия решений, соответствующая RBD, приведенной на рисунке В.6

В.7.2 Минимальные пути успеха и наборы обрывов с BDD

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

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

Следовательно, если булева функция монотонна и П _i - путь успеха, содержащий отказавшие блоки, удаление отказавших блоков также обеспечивает путь успеха. Например, если , то тоже путь успеха.

Аналогично, если С _i - набор обрывов, содержащий блоки в работоспособном состоянии, то удаление этих блоков также обеспечивает набор обрывов: например, если - набор обрывов, то также набор обрывов.

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

Рисунок В.11 - Определение путей успеха (наборов соединений) по RBD

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

Рисунок В.12 - Определение путей отказа (наборов обрывов) по RBD

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

BDD также является эффективным методом идентификации минимальных наборов соединений или обрывов.

Принцип идентификации соединений (путей успеха) показан в левой части рисунка В.13. Он справедлив только тогда, когда BDD соответствует "когерентной" RBD, как объяснено в В.7.2.

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

Рисунок В.13 - Наборы обрывов и соединений, выявленные по BDD

Аналогично, принцип поиска наборов обрывов (путей отказа) показан в правой части рисунка В.13. Процесс состоит из начала состояния отказа системы и исследования графа снизу вверх в обратном порядке (переменных) по отношению к использованному при построении BDD. При исследовании ветви если переменная в работоспособном состоянии, то ее обходят и вводят новую линию с переменной чуть выше. И так далее. При рассмотрении графа с правой стороны выявлен следующий набор обрывов: (), (), (), (). Одна из этих комбинаций () не является минимальной.

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

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

В.7.3 Вероятностные расчеты по BDD

В.7.3.1 Общие положения

Структура BDD, представленная на рисунке В.10, очень компактно моделирует все пути к отказу системы и пути к успеху системы. Для одной и той же RBD может быть разработано несколько эквивалентных BDD. Как и для упрощенной декомпозиции Шеннона, размер этих BDD зависит от выбора порядка исследования переменных.

Все пути, закодированные в BDD, являются непересекающимися, BDD можно использовать непосредственно для вероятностных вычислений просто заменой переменных состояния, соответствующими вероятности успеха или отказа (см. рисунок В.14).

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

.

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

.

Рисунок В.14 - Вероятностные расчеты по BDD

В.7.3.2 Вычисление условных вероятностей по RBD

BDD можно использовать для вычисления условных вероятностей. На рисунке В.15 показано как вычислить Р _s|b на левой стороне и Р _s|b на правой стороне. Это основа вычислений, связанных с условным параметром потока отказов (интенсивностью Веселя), безусловным параметром потока отказов (частотой отказов) и показателей значимости (см. приложение D).

Рисунок В.15 - Расчет условных вероятностей с использованием BDD

В.7.4 Основные замечания по использованию BDD

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

BDD также может быть использован для кодирования минимальных наборов соединений (путей успеха) и минимальных наборов обрывов (путей отказа) при когерентных RBD или кодирования первичных импликантов при когерентных RBD.

При наличии n переменных декомпозиция Шеннона (как и таблица истинности) приводит к 2 ⁿ путям. Это невозможно обработать при больших n. Поэтому были разработаны современные алгоритмы построения BDD без построения всей декомпозиции Шеннона. Это позволяет обрабатывать сотни переменных (например, RBD с сотнями блоков) и миллиарды путей успеха или минимальных наборов обрывов. Размер зависит от выбора порядка переменных при разработке BDD и эвристик (доступных для выбора), что в некоторой степени лучше.

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