ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 17.04.2021
Просмотров: 601
Скачиваний: 1
1
2. Дизъюнктивные нормальные формы (ДНФ).
2.1. Понятие ДНФ, проблема их минимизации.
Определение.
Выражение
1
2
1
2
r
r
i
i
i
K
x
x
x
называют элементарной
конъюнкцией переменных
1
2
,
,
,
r
i
i
i
x
x
x
ранга
r
. Константы 0 и 1 будем тоже
считать элементарными конъюнкциями по определению.
Пример.
Этот пример свидетельствует о том, что каждая функция алгебры логики может
быть представлена различными ДНФ. Естественно возникает вопрос о
минимизации ДНФ, реализующей булеву функцию.
Определение.
Функционал
L
, определённый для любой ДНФ, со
значениями в
R
R : a
0
a
будем называть
индексом простоты ДНФ
, если
для него выполнены следующие аксиомы:
2
Тривиальный алгоритм поиска МДНФ для
1
2
, ,
,
n
f x x
x
.
1. выписать все возможные элементарные конъюнкции с переменными из
множества
1
2
, ,
,
n
x x
x
(их
3
n
);
2. составить из полученных элементарных конъюнкций все возможные ДНФ (их
3
2
n
);
3. выбрать те из построенных ДНФ, которые реализуют данную функцию
f
(логически эквивалентны ей);
4. вычислить для каждой из отобранных ДНФ индекс простоты (
Б
L
) и путём
сравнения выбрать МДНФ.
3
2.2. Упрощение ДНФ, тупиковые ДНФ (ТДНФ).
Алгоритм упрощения ДНФ.
4
Пример.
Для СДНФ
рассмотрим работу алгоритма упрощения.
1. Первую конъюнкцию удалить нельзя, но в ней можно удалить
, т.к.
получится конъюнкция
, из которой нельзя больше
удалить ни одного множителя.
Для той же СДНФ с другой упорядоченностью
5
алгоритм даёт другую ТДНФ
.
Поскольку у СДНФ есть конечное число упорядочиваней, то получив из них все
ТДНФ для рассматриваемой функции, можно из них выбрать МДНФ сравнением
значения индекса простоты для полученных ТДНФ.
2.2.1. Упражнение.
С помощью тривиального алгоритма найти МДНФ для
функции
f
.
2.2.2. Упражнение.
С помощью алгоритма упрощения найти МДНФ для
функции
f
.