Алгоритм формирования и минимизации логического представления дерева отказов
Предлагаются алгоритмы процедур, которые реализуют функции ввода описания опасного события в форме дерева отказов; формирования и минимизации дизъюнктивно-нормальной формы дерева отказов. Данные алгоритмы могут быть использованы при разработке программного обеспечения кризисных центров....
Gespeichert in:
| Datum: | 2009 |
|---|---|
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут проблем математичних машин і систем НАН України
2009
|
| Schriftenreihe: | Математичні машини і системи |
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/46909 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Алгоритм формирования и минимизации логического представления дерева отказов / А.Н. Серебровский, Л.П. Ситниченко, В.Г. Пилипенко // Мат. машини і системи. — 2009. — № 1. — С. 165–172. — Бібліогр.: 6 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-46909 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-469092025-02-09T12:09:06Z Алгоритм формирования и минимизации логического представления дерева отказов Алгоритм формування і мінімізації логічного пред’явлення дерева відмовлень The algorithms of forming and minimization of logical presenting the fault tree Серебровский, А.Н. Ситниченко, Л.П. Пилипенко, В.Г. Якість, надійність і сертифікація обчислювальної техніки і програмного забезпечення Предлагаются алгоритмы процедур, которые реализуют функции ввода описания опасного события в форме дерева отказов; формирования и минимизации дизъюнктивно-нормальной формы дерева отказов. Данные алгоритмы могут быть использованы при разработке программного обеспечения кризисных центров. Пропонуються алгоритми процедур, що реалізують функції введення опису небезпечної події у формі дерева відмовлень; формування та мінімізації диз’юнктивно-нормальної форми дерева відмовлень. Дані алгоритми можуть бути використані при розробці програмного забезпечення кризових центрів. 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. 2009 Article Алгоритм формирования и минимизации логического представления дерева отказов / А.Н. Серебровский, Л.П. Ситниченко, В.Г. Пилипенко // Мат. машини і системи. — 2009. — № 1. — С. 165–172. — Бібліогр.: 6 назв. — рос. 1028-9763 https://nasplib.isofts.kiev.ua/handle/123456789/46909 504.56 ru Математичні машини і системи application/pdf Інститут проблем математичних машин і систем НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Якість, надійність і сертифікація обчислювальної техніки і програмного забезпечення Якість, надійність і сертифікація обчислювальної техніки і програмного забезпечення |
| spellingShingle |
Якість, надійність і сертифікація обчислювальної техніки і програмного забезпечення Якість, надійність і сертифікація обчислювальної техніки і програмного забезпечення Серебровский, А.Н. Ситниченко, Л.П. Пилипенко, В.Г. Алгоритм формирования и минимизации логического представления дерева отказов Математичні машини і системи |
| description |
Предлагаются алгоритмы процедур, которые реализуют функции ввода описания опасного события в форме дерева отказов; формирования и минимизации дизъюнктивно-нормальной формы дерева отказов. Данные алгоритмы могут быть использованы при разработке программного обеспечения кризисных центров. |
| format |
Article |
| author |
Серебровский, А.Н. Ситниченко, Л.П. Пилипенко, В.Г. |
| author_facet |
Серебровский, А.Н. Ситниченко, Л.П. Пилипенко, В.Г. |
| author_sort |
Серебровский, А.Н. |
| title |
Алгоритм формирования и минимизации логического представления дерева отказов |
| title_short |
Алгоритм формирования и минимизации логического представления дерева отказов |
| title_full |
Алгоритм формирования и минимизации логического представления дерева отказов |
| title_fullStr |
Алгоритм формирования и минимизации логического представления дерева отказов |
| title_full_unstemmed |
Алгоритм формирования и минимизации логического представления дерева отказов |
| title_sort |
алгоритм формирования и минимизации логического представления дерева отказов |
| publisher |
Інститут проблем математичних машин і систем НАН України |
| publishDate |
2009 |
| topic_facet |
Якість, надійність і сертифікація обчислювальної техніки і програмного забезпечення |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/46909 |
| citation_txt |
Алгоритм формирования и минимизации логического представления дерева отказов / А.Н. Серебровский, Л.П. Ситниченко, В.Г. Пилипенко // Мат. машини і системи. — 2009. — № 1. — С. 165–172. — Бібліогр.: 6 назв. — рос. |
| series |
Математичні машини і системи |
| work_keys_str_mv |
AT serebrovskijan algoritmformirovaniâiminimizaciilogičeskogopredstavleniâderevaotkazov AT sitničenkolp algoritmformirovaniâiminimizaciilogičeskogopredstavleniâderevaotkazov AT pilipenkovg algoritmformirovaniâiminimizaciilogičeskogopredstavleniâderevaotkazov AT serebrovskijan algoritmformuvannâímínímízacíílogíčnogopredâvlennâderevavídmovlenʹ AT sitničenkolp algoritmformuvannâímínímízacíílogíčnogopredâvlennâderevavídmovlenʹ AT pilipenkovg algoritmformuvannâímínímízacíílogíčnogopredâvlennâderevavídmovlenʹ AT serebrovskijan thealgorithmsofformingandminimizationoflogicalpresentingthefaulttree AT sitničenkolp thealgorithmsofformingandminimizationoflogicalpresentingthefaulttree AT pilipenkovg thealgorithmsofformingandminimizationoflogicalpresentingthefaulttree |
| first_indexed |
2025-11-25T23:05:14Z |
| last_indexed |
2025-11-25T23:05:14Z |
| _version_ |
1849805415961853952 |
| fulltext |
© Серебровcкий А.Н., Ситниченко Л.П., Пилипенко В.Г., 2009 165
ISSN 1028-9763. Математичні машини і системи, 2009, № 1
УДК 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].
ISSN 1028-9763. Математичні машини і системи, 2009, № 1 166
Дерево отказов (ДО) – графическая модель различных параллельных и последовательных
сочетаний элементарных нежелательных событий (базисных событий), которые могут привести к
реализации заранее определенного опасного события. Базисные события (БС) представляют
собой отказы отдельных элементов опасных объектов, ошибки персонала, события, источниками
которых являются различные влияния внешней окружающей среды. Вероятности возникновения
БС существенным образом зависят от ситуаций, возникающих на ПОО. Методы расчетов оценки
вероятностей БМС приведены в работе [3]. БС в ДО соединены логическими операциями “И”,
“ИЛИ”, образуя промежуточные события. Завершающее промежуточное событие называют
верхним событием. Верхнее событие аналитически может быть представлено дизъюнктивно-
нормальной формой (ДНФ) [4], переменными которой являются базисные события. Это дает
возможность оценивать вероятности верхних событий ДО на основании данных о вероятностях БС
согласно формулам
( ) ( )∑
∈
=
Qq
qSPAP , (1)
( ) )(∏
∈
=
qq
q
Ii
iq aPSP , (2)
где A – верхнее событие ДО;
qS – сечение отказа с номером q (сечение есть совокупность БС, реализация которых
приводит к верхнему событию ДО);
qi
a – базисное событие из сечения qS ;
Рис. 1. Общая схема функционирования автоматизированной системы
оценки анализа ситуаций АСОАС
БД
АСОАС
К принятию решений по предотвращению
опасных событий
Конфигуратор
БД
Мониторинг
ситуаций
Первичная оценка
опасности ситуации
Анализ
подозрительных
ситуаций
Формирование
отчетов
Оценка и
вероятностный анализ
безопасности
ISSN 1028-9763. Математичні машини і системи, 2009, № 1 167
Q – совокупность индексов сечений ДО;
qI – совокупность индексов базисных событий из сечения qS ;
( )AP – вероятность верхнего события ДО;
( )qSP – вероятность сечения qS .
Таким образом, построение ДО опасных событий, заключающееся в вводе ДО в базу
данных и формировании их логических описаний, является необходимой предпосылкой ВАБ.
Поэтому в рамках программных систем ВАБ реализованы функции формирования ДО, которые, в
сущности, являются сервисными по отношению к задачам оценивания вероятности опасных
событий.
В данной статье рассмотрены вопросы ввода и представления деревьев отказов в БД и
преобразования их в форму, удобную для оценок вероятностей верхних событий.
2. Ввод и представление деревьев отказов в БД АСОАС
База данных АСОАС представлена на рис. 2 и состоит из следующих объектных областей:
“Справочники”, “Деревья отказов”, “Деревья событий”, “Текущая ситуация”. Каждая из объектных
областей БД включает следующие таблицы:
– объектная область БД “Справочники”: таблицы “Объекты ПОО”, “Опасные события”,
“Базисные события”;
– объектная область БД «Деревья отказов»: таблицы “Деревья отказов”, “Узлы деревьев
отказов”, “Сечения ВС ”, “Базовые события сечений ВС”;
– объектная область БД “Деревья событий”: таблицы “Деревья событий”, “Узлы деревьев
событий”, “Цепи деревьев событий”, “Сечения цепей”, “Базисные события сечений цепей”;
– объектная область БД “Текущая ситуация”: таблица “Изменения вероятностей базисных
событий”, “Подозрительные ситуации”, “Опасные ситуации”.
Дерево отказов строится посредством последовательного задания данных о расположении
и описании элементов ДО. При описании ДО применяется терминология, используемая в [5].
Построение ДО возможно двумя способами: от верхнего события (корня дерева) к базисным
событиям (листьям) и, наоборот, от БС к верхнему событию. Опишем здесь первый способ.
Для формирования ДО предусмотрены операции: создание, удаление и редактирование
элементов ДО.
Построение ДО состоит из следующих шагов:
1. Указание элемента-“предка”, относительно которого создается новый вводимый элемент.
2. Задание свойств узла: наименования элемента, его идентификатора, тип логической
операции (“И”, “ИЛИ”), с помощью которой формируется вводимый элемент.
3. Выполнение операции: “Создать новый элемент ДО”.
После завершения построения всех элементов дерева отказов необходимо выполнить
операцию “Сохранить данные о дереве отказов в БД”. В таблице “Деревья отказов” сохраняются
идентификатор и наименование дерева отказов. В таблице “Узлы дерева отказов” сохраняются
ISSN 1028-9763. Математичні машини і системи, 2009, № 1 168
данные из топологии дерева: номер узла, номер узла-предка, количество узлов-потомков, уровень
узла, а из свойств узлов: тип узла, идентификатор узла, наименование узла.
Данные таблицы “Узлы дерева отказов” позволяют построить минимальную дизъюнктивно-
нормальную форму (МДНФ) для верхнего события дерева отказов. Затем, используя МДНФ,
заполнить таблицы БД: “Сечения ВС”, “Базисные события сечений ВС”.
3. Построение и минимизация дизъюнктивно-нормальной формы ДО
Дизъюнктивно-нормальной формой верхнего события А ДО есть логическая сумма сечений ДО,
т.е.
∪
Qq
qSA
∈
= , (3)
где
.∩
qq
q
Ii
iq aS
∈
= (4)
Минимальным сечением ДО является такое сечение, которое не приводит к верхнему
событию ДО, если из него удалить хотя бы одно БС.
Минимальной дизъюнктивно-нормальной формой ДО является такая ДНФ, у которой все
сечения являются минимальными.
3.1. Построение дизъюнктивно-нормальной формы
3.1.1. Выполняется последовательная подстановка логических элементов ДО, находящихся на
более высоких уровнях, в логические элементы более низких уровней, начиная с базисных событий
до верхнего события ДО. Полученное логическое выражение верхнего события ДНФ в своем
составе содержит сечения, состоящие только из базисных событий, между которыми установлены
отношения логического умножения (“&”) или логического сложения (“+”) [5].
3.1.2. Удаление в сечениях ДНФ базисных событий, которые повторяются как сомножители. При
этом применяется правило:
BBB =∗ , (5)
где B – базисное событие.
3.2. Минимизация дизъюнктивно-нормальной формы
Минимизация ДНФ реализуется применением к ДНФ правила [4]:
CDCC =+ ∗ , (6)
где C и D – конъюнкция базисных событий.
Процедура минимизации сводится к действиям, описанным в п.п. 3.2.1-3.2.4.
3.2.1. Сортировка сечений ДНФ по возрастанию числа базисных событий в сечении.
3.2.2. Попарное сравнение всех сечений ДНФ друг с другом с использованием формулы (6).
3.2.3. Если сечение с большим номером содержит в своем составе все базисные события сечения
с меньшим номером, то сечение с большим номером исключается из ДНФ, в противном случае
изменения в ДНФ не происходят.
3.2.4. Формирование выходного сообщения о завершении минимизации ДНФ и занесение МДНФ в
таблицу БД “Деревья отказов”.
ISSN 1028-9763. Математичні машини і системи, 2009, № 1 169
ISSN 1028-9763. Математичні машини і системи, 2009, № 1 170
4. Пример. Построить минимизированную ДНФ для ДО, представленного на рис. 3 [6].
Верхним событием является возникновение пожара в гараже, базисными событиями являются:
1F – отсутствует пожарная сигнализация;
2F – отсутствуют средства индивидуального пожаротушения;
3F – низкая дисциплина персонала;
4F – наличие горючих и смазочных материалов;
5F – наличие мусора;
6F – неисправность двигателя автомобиля;
7F – низкое техническое состояние электропроводки в гараже;
8F – неисправность электропроводки автомобиля;
9F – отсутствие заземления массы автомобиля.
Описание дерева отказов в БД представлено в таблицах “Деревья отказов” и “Узлы ДО”.
Используя таблицу “Узлы ДО”, строим логическое представление верхнего события 11G :
G1=(F8*F9)
G2=(F4*F5)
G3=(F7+G1)
G4=(F6+G3)
G5=(F3*G2)
G6=(G5+G4) (7)
G7=(F2*G6)
G8=(F8*F9)
G9=(F7+G8)
G10=(G9+G7)
G11=(F1*G10)
После исключения промежуточных событий 101 GG − из (7) получаем скобочные
выражения для всех промежуточных событий ДО:
G1=(F8*F9)
G2=(F4*F5)
G3=(F7+(F8*F9))
G4=(F6+(F7+(F8*F9)))
G5=(F3+(F4*F5))
G6=((F3*(F4*F5))+(F6+(F7+(F8*F9)))) (8)
G7=(F2*((F3*(F4*F5))+(F6+(F7+(F8*F9))))
G8=(F8*F9)
G9=(F7+(F8*F9))
G10=((F7+(F8*F9))+((F2*((F3*(F4*F5))+(F6+(F7+(F8*F9))))))
G11=(F1*((F7+(F8*F9))+((F2*((F3*(F4*F5))+(F6+(F7+(F8*F9)))))))
ISSN 1028-9763. Математичні машини і системи, 2009, № 1 171
Раскрывая скобки в 11G из (8), получаем ДНФ верхнего события. При этом выполняется
правило транзитивности логического умножения относительно логического сложения:
.71981621721
98214321532111
FFFFFFFFFFF
FFFFFFFFFFFFG
∗∗∗∗∗∗∗
∗∗∗∗∗∗∗∗∗
++++
+++=
(9)
В выражении (9) сечения 721 FFF ∗∗ и 9821 FFFF ∗∗∗ , согласно правилу (6), являются
избыточными относительно сечений 71 FF ∗ и 981 FFF ∗∗ соответственно, поэтому они могут
быть удалены из ДНФ. Результатом является минимизированная ДНФ, имеющая вид
532143216219817111 FFFFFFFFFFFFFFFFG ∗∗∗∗∗∗∗∗∗∗∗ ++++= . (10)
Обозначения элементов: Наименования элементов:
− базисное событие
F1, F2, F3, F4, F5, F6, F7, F8, F9 – базисные события
− промежуточное событие “И”/”ИЛИ”
G1, G2, G3, G4, G5, G6, G7, G8, G9, G10 – промежуточные
события
G11 – верхнее событие
Рис. 3. Дерево отказов возникновения пожара в гараже
5. Заключение
В статье предложены алгоритмы процедур сервисной подсистемы вероятностного анализа
безопасности, включающие следующие функции:
G10
G11
И
F1
ИЛИ
G9
ИЛИ
F7 G8
И
F8 F9
G7
И
F2 G6
ИЛИ
G5
И
G4
ИЛИ
F3 G2
И
F6
F4 F5 F7
G3
ИЛИ
G1
И
F8 F9
ISSN 1028-9763. Математичні машини і системи, 2009, № 1 172
– ввод дерева отказов опасного события в БД;
– формирование дизъюнктивно-нормальной формы (ДНФ) верхнего события дерева
отказов;
– минимизация ДНФ.
Данные алгоритмы могут быть использованы разработчиками математического и
программного обеспечения кризисных центров при создании программно-инструментальных
средств оценки и анализа ситуаций на потенциально опасных объектах.
СПИСОК ЛИТЕРАТУРЫ
1. Швыряев Ю.В. Вероятностный анализ безопасности атомных станций. Методика выполнения. – М.: ИАЭ им.
И.В. Курчатова, 1992. – 264 с.
2. Хенли Э.Дж., Кумамото Х. Надежность технических систем и оценка риска. – М.: Машиностроение, 1984.
3. Серебровский А.Н. Анализ подходов оценивания вероятностей базисных событий техногенной опасности
// Математичні машини і системи. – 2008. – № 2. – С. 122 – 127.
4. Рябинин И.А. Надежность и безопасность структурно-сложных систем. – Санкт-Петербург: Политехника,
2000. – 248 с.
5. Кнут Д. Искусство программирования для ЭВМ. – М.: Мир, 1976. – Т. 1. – С. 382 – 500.
6. Бегун В.В., Науменко І.М. Безпека життєдіяльності. – Київ: УАННП “Фенікс”, 2004. – 328 с.
Стаття надійшла до редакції 17.09.2008
|