Алгоритм формирования и минимизации логического представления дерева отказов

УДК 504.56

А.Н. СЕРЕБРОВСКИЙ, Л.П. СИТНИЧЕНКО, В.Г. ПИЛИПЕНКО

АЛГОРИТМ ФОРМИРОВАНИЯ И МИНИМИЗАЦИИ ЛОГИЧЕСКОГО ПРЕДСТАВЛЕНИЯ ДЕРЕВА ОТКАЗОВ

Abstract: The algorithms of proсedures, which realizes the function of input data of the hazardous event in the form of fault tree and forming and minimization of the fault tree disqunctive for. The given algorithms can be used for development of crisis centres software.

Key words: fault tree, hazardous event, disjunctive normal form.

Анотація: Пропонуються алгоритми процедур, що реалізують функції введення опису небезпечної події у формі дерева відмовлень; формування та мінімізації диз'юнктивно-нормальної форми дерева відмовлень. Дані алгоритми можуть бути використані при розробці програмного забезпечення кризових центрів. Ключові слова: дерево відмовлень, небезпечна подія, диз'юнктивна нормальна форма.

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

Ключевые слова: дерево отказов, опасное событие, дизъюнктивная нормальная форма.

1. Введение

Одной из главных целей кризисных центров является предотвращение аварий и чрезвычайных происшествий (ЧП) на потенциально опасных объектах (ПОО). Эффективным средством предотвращения аварий и ЧП на ПОО являются автоматизированные системы оценки и анализа ситуаций (АСОАС). Обобщенная схема АСОАС представлена на рис. 1. АСОАС состоит из подсистем “Конфигуратор”, “Оценка и вероятностный анализ безопасности” и БД.

Функциями подсистемы “Конфигуратор” являются:

- создание таблиц справочников и таблиц данных системы;

- заполнение таблиц справочников объектной области “Справочники”;

- построение деревьев отказов;

- построение деревьев событий и заполнение таблиц данных объектной области “Деревья событий”;

- заполнение таблиц данных объектных областей “Деревья отказов” и “Деревья событий”; Функциями подсистемы “Оценка и вероятностный анализ безопасности” являются:

- мониторинг ситуаций на ПОО, наблюдение за контрольными параметрами и факторами опасности;

- предварительная оценка степени опасности ситуации (безопасная, вызывающая подозрение, критическая или близкая к ней);

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

В вероятностном анализе безопасности (ВАБ) модель дерева отказов БД АСОАС является базовым средством информационного отображения процессов возникновения и развития техногенной опасности [1, 2].

© Серебровский А.Н., Ситниченко Л.П., Пилипенко В.Г., 2009 ISSN 1028-9763. Математичні машини і системи, 2009, № 1

Оценка и вероятностный анализ безопасности

К принятию решений по предотвращению опасных событий

Рис. 1. Общая схема функционирования автоматизированной системы оценки анализа ситуаций АСОАС

Дерево отказов (ДО) - графическая модель различных параллельных и последовательных сочетаний элементарных нежелательных событий (базисных событий), которые могут привести к реализации заранее определенного опасного события. Базисные события (БС) представляют собой отказы отдельных элементов опасных объектов, ошибки персонала, события, источниками которых являются различные влияния внешней окружающей среды. Вероятности возникновения БС существенным образом зависят от ситуаций, возникающих на ПОО. Методы расчетов оценки вероятностей БМС приведены в работе [3]. БС в ДО соединены логическими операциями “И”, “ИЛИ”, образуя промежуточные события. Завершающее промежуточное событие называют верхним событием. Верхнее событие аналитически может быть представлено дизъюнктивнонормальной формой (ДНФ) [4], переменными которой являются базисные события. Это дает возможность оценивать вероятности верхних событий ДО на основании данных о вероятностях БС согласно формулам

Р

)=Пр(а;) •

где А - верхнее событие ДО;

- сечение отказа с номером q (сечение есть совокупность БС, реализация которых приводит к верхнему событию ДО);

а

базисное событие из сечения ;

І

q

Q - совокупность индексов сечений ДО;

- совокупность индексов базисных событий из сечения Я,;

Р( л) - вероятность верхнего события ДО; р(Я,) - вероятность сечения Я,.

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

В данной статье рассмотрены вопросы ввода и представления деревьев отказов в БД и преобразования их в форму, удобную для оценок вероятностей верхних событий.

2. Ввод и представление деревьев отказов в БД АСОАС

База данных АСОАС представлена на рис. 2 и состоит из следующих объектных областей: “Справочники”, “Деревья отказов”, “Деревья событий”, “Текущая ситуация”. Каждая из объектных областей БД включает следующие таблицы:

- объектная область БД “Справочники”: таблицы “Объекты ПОО”, “Опасные события”, “Базисные события”;

- объектная область БД «Деревья отказов»: таблицы “Деревья отказов”, “Узлы деревьев отказов”, “Сечения ВС ”, “Базовые события сечений ВС”;

- объектная область БД “Деревья событий”: таблицы “Деревья событий”, “Узлы деревьев событий”, “Цепи деревьев событий”, “Сечения цепей”, “Базисные события сечений цепей”;

- объектная область БД “Текущая ситуация”: таблица “Изменения вероятностей базисных событий”, “Подозрительные ситуации”, “Опасные ситуации”.

Дерево отказов строится посредством последовательного задания данных о расположении и описании элементов ДО. При описании ДО применяется терминология, используемая в [5]. Построение ДО возможно двумя способами: от верхнего события (корня дерева) к базисным событиям (листьям) и, наоборот, от БС к верхнему событию. Опишем здесь первый способ.

Для формирования ДО предусмотрены операции: создание, удаление и редактирование элементов ДО.

Построение ДО состоит из следующих шагов:

1. Указание элемента-“предка”, относительно которого создается новый вводимый элемент.

2. Задание свойств узла: наименования элемента, его идентификатора, тип логической операции (“И”, “ИЛИ”), с помощью которой формируется вводимый элемент.

3. Выполнение операции: “Создать новый элемент ДО”.

После завершения построения всех элементов дерева отказов необходимо выполнить операцию “Сохранить данные о дереве отказов в БД”. В таблице “Деревья отказов” сохраняются идентификатор и наименование дерева отказов. В таблице “Узлы дерева отказов” сохраняются

данные из топологии дерева: номер узла, номер узла-предка, количество узлов-потомков, уровень узла, а из свойств узлов: тип узла, идентификатор узла, наименование узла.

Данные таблицы “Узлы дерева отказов” позволяют построить минимальную дизъюнктивнонормальную форму (МДНФ) для верхнего события дерева отказов. Затем, используя МДНФ, заполнить таблицы БД: “Сечения ВС”, “Базисные события сечений ВС”.

3. Построение и минимизация дизъюнктивно-нормальной формы ДО

Дизъюнктивно-нормальной формой верхнего события А ДО есть логическая сумма сечений ДО, т.е.

Минимальным сечением ДО является такое сечение, которое не приводит к верхнему событию ДО, если из него удалить хотя бы одно БС.

Минимальной дизъюнктивно-нормальной формой ДО является такая ДНФ, у которой все сечения являются минимальными.

3.1. Построение дизъюнктивно-нормальной формы

3.1.1. Выполняется последовательная подстановка логических элементов ДО, находящихся на более высоких уровнях, в логические элементы более низких уровней, начиная с базисных событий до верхнего события ДО. Полученное логическое выражение верхнего события ДНФ в своем составе содержит сечения, состоящие только из базисных событий, между которыми установлены отношения логического умножения (“&”) или логического сложения (“+”) [5].

3.1.2. Удаление в сечениях ДНФ базисных событий, которые повторяются как сомножители. При этом применяется правило:

где С и и - конъюнкция базисных событий.

Процедура минимизации сводится к действиям, описанным в п.п. 3.2.1-3.2.4.

3.2.1. Сортировка сечений ДНФ по возрастанию числа базисных событий в сечении.

3.2.2. Попарное сравнение всех сечений ДНФ друг с другом с использованием формулы (6).

3.2.3. Если сечение с большим номером содержит в своем составе все базисные события сечения с меньшим номером, то сечение с большим номером исключается из ДНФ, в противном случае изменения в ДНФ не происходят.

3.2.4. Формирование выходного сообщения о завершении минимизации ДНФ и занесение МДНФ в таблицу БД “Деревья отказов”.

где

Номер ДО

Идентификатор ДО

Наименование ДО

Вероятность ВС

Мин. ДНФ ВС

Сечения ВС

Номер ДО

Номер сечения ВС

Вероятность сечения ВС

БС сечений ВС

Номер сечения ВС

Номер БС

Вероятность БС

Номер узла ДО

Номер ДО

Номер узла-предка

Кол-во узлов-потомков

Тип узла

Наименование события

Номер узла ДС

Номер ДС

Номер узла-предка

Кол-во узлов-потомков

Номер ДО

Нацменов, события

Номер ДС

Идентификатор ДС

Наименование ДС

Описание ДС

Цепи ДС

Номер ДС

я Номер цепи ДС

Вероятность цепи ДС

Сечения цепей ДС

Номер цепи ДС

Номер сечен, цепи ДС

Вероятность сечения цепи ДС

БС сечений цепей ДС

Номер сечен, цепи ДС Номер БС Вероятность БС

Сокращения: СФ-скобочная форма; ДИФ-дизъюнктивно-нормальная форма; МДНФ-минимальная дизъюнктивно-нормальная форма; ДО-дерево отказов; ДС-дерево событий; В С-базисное событие ДО; ВС-верхнее событие ДО

Рис. 2. Логическая структура БД

4. Пример. Построить минимизированную ДНФ для ДО, представленного на рис. 3 [6].

Верхним событием является возникновение пожара в гараже, базисными событиями являются:

Е1 - отсутствует пожарная сигнализация;

Е 2 - отсутствуют средства индивидуального пожаротушения;

Е 3 - низкая дисциплина персонала;

Е4 - наличие горючих и смазочных материалов;

Е5 - наличие мусора;

Е6 - неисправность двигателя автомобиля;

Е 7 - низкое техническое состояние электропроводки в гараже;

Е 8 - неисправность электропроводки автомобиля;

Е9 - отсутствие заземления массы автомобиля.

Описание дерева отказов в БД представлено в таблицах “Деревья отказов” и “Узлы ДО”. Используя таблицу “Узлы ДО”, строим логическое представление верхнего события 011:

^G1=

G2=

G3=

G4=

G5=

Л G6=

G7=

G8=

G9=

G10=

\д11=^^10)

После исключения промежуточных событий 01 - 010 из (7) получаем скобочные

выражения для всех промежуточных событий ДО:

ГG1=

G2=

G3=

G4=

G5=

) G6=

Л G7=

G8=

G9=

G10=

G11=

Раскрывая скобки в 011 из (8), получаем ДНФ верхнего события. При этом выполняется правило транзитивности логического умножения относительно логического сложения:

011 = Е1* Е 2* Е 3* Е 5 + Е1* Е 2* Е 3* Е 4 + Е1* Е 2* Е 8* Е 9 +

+ Е1* Е 2* Е 7 + Е1* Е 2* Е 6 + Е1* Е 8* Е 9 + Е1* Е 7.

В выражении (9) сечения Е1*Е2*Е7 и Е1*Е2*Е8*Е9 , согласно правилу (6), являются

избыточными относительно сечений Е1*Е7 и Е1*Е8*Е9 соответственно, поэтому они могут быть удалены из ДНФ. Результатом является минимизированная ДНФ, имеющая вид

011 = Е1* Е 7 + Е1* Е 8* Е 9 + Е1* Е 2* Е 6 + Е1* Е 2* Е 3* Е 4 + Е1* Е 2* Е 3* Е 5.

09

ИЛИ

©

08

И

02

И

© ©

07

И

06

ИЛИ

03

ИЛИ

01

И

©

05 04

И ИЛИ

Обозначения элементов: Наименования элементов:

Р1, Р2, Р3, Р4, Р5, Р6, Р7, Р8, Р9 - базисные события

- базисное событие

| 01, 02, 03, 04, 05, 06, 07, 08, 09, 010 - промежуточные

I ' I - промежуточное событие “И”/”ИЛИ” события

011 - верхнее событие Рис. 3. Дерево отказов возникновения пожара в гараже

5. Заключение

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

- ввод дерева отказов опасного события в БД;

- формирование дизъюнктивно-нормальной формы (ДНФ) верхнего события дерева отказов;

- минимизация ДНФ.

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

СПИСОК ЛИТЕРАТУРЫ

1. Швыряев Ю.В. Вероятностный анализ безопасности атомных станций. Методика выполнения. - М.: ИАЭ им. И.В. Курчатова, 1992. - 264 с.

2. Хенли Э.Дж., Кумамото Х. Надежность технических систем и оценка риска. - М.: Машиностроение, 1984.

3. Серебровский А.Н. Анализ подходов оценивания вероятностей базисных событий техногенной опасности // Математичні машини і системи. - 2008. - № 2. - С. 122 - 127.

4. Рябинин И.А. Надежность и безопасность структурно-сложных систем. - Санкт-Петербург: Политехника, 2000. - 248 с.

5. Кнут Д. Искусство программирования для ЭВМ. - М.: Мир, 1976. - Т. 1. - С. 382 - 500.

6. Бегун В.В., Науменко І.М. Безпека життєдіяльності. - Київ: УАННП “Фенікс”, 2004. - 328 с.

Стаття надійшла до редакції 17.09.2008