2.6. Проблема минимизации булевых функций
Пусть задан алфавит переменных {x1, …, xn}.
Определение: Выражение
(iμ≠
iν
при μ≠ν)
называется элементарной конъюнкцией. Число r называется рангом элементарной конъюнкции.
По определению считаем константу 1 элементарной конъюнкцией ранга 0.
Определение: Выражение
(ki≠kj
при i≠j),
где ki – элементарная конъюнкция ранга ri называется дизъюнктивной нормальной формой (д.н.ф.).
Очевидно д.н.ф. R реализует некоторую булеву функцию
f(x1, …, xn).
В качестве реализующей функции f(x1, …, xn) д.н.ф. можно взять, например совершенную д.н.ф.
.
Пример: Рассмотрим f(x1, x2, x3), заданную таблицей.
Таблица 10
-
x1
x2
x3
f(x1, x2, x3)
0
0
0
1
0
0
1
0
0
1
0
0
0
1
1
0
1
0
0
1
1
0
1
1
1
1
0
1
1
1
1
1
Тогда ее можно представить в виде совершенной д.н.ф.
R1 = V x1 V x1 x3 V x1x2 V x1x2x3.
С другой стороны, непосредственной проверкой убеждаемся, что эта функция может быть представлена формами
R2 = V x1x3 V x1x2
R3 = V x1 V x1x2x3
R4 = V x1.
V x3 V x2x3 V x1 V x1x2 V x1x2x3 =
= V x2x3 V x1 V x1x2 V x1x2x3 =
= V x2x3 V x1
x1x2 V V x3
1=
V 1= ( V 1) =
Таблица 11
-
x1
x2
x3
x2x3
x1x2x3
Φ
x2x3
1
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
1
0
1
0
0
0
0
0
0
0
1
1
0
0
0
0
1
1
0
0
1
0
1
1
0
1
0
1
0
0
0
0
0
1
1
0
0
0
0
0
0
1
1
1
0
1
1
1
V x3 V x2x3 V x1 V x1x2 V x1x2x3 =
= V x3 V x1x2
V x3 V x2x3 V x1 V x1x2 V x1x2x3 =
= V x1x2
V x1 V x1 x3 V x1x2 V x1x2x3 =
= V x1x3 V x1x2 I
= V x1x2 V x1 x3 II
V x1 V x1 x3 V x1 V x1x2 V x1x2x3 =
= V x2 V x1x2= V x1
V x1 V x1 x3 V x1 V x1x2 V x1x2x3 =
= V x1x3 V x1 = V x1
Этот пример показывает, что функция алгебры логики определяется с помощью д.н.ф. не единственным образом. Возникает возможность выбора более предпочтительной реализации. Для этого вводится индекс простоты L(R).
Встречаются следующие индексы простоты:
1. LБ(R) – число букв переменных в записи д.н.ф. R
LБ(R1)=15; LБ(R2)=7; LБ(R3)=7; LБ(R4)=3.
2. LК(R) – число элементарных конъюнкций, входящих в R
LК(R1)=5; LК(R2)=3; LК(R3)=3; LК(R4)=4.
3. LО(R) – число символов отрицания в R
LО(R1)=7; LО(R2)=2; LО(R3)=3; LО(R4)=2.
Так
как над алфавитом {x1,
…, xn}
можно построить 3n
различных элементарных конъюнкций,
следовательно, число д.н.ф. над этим
алфавитом равно
.
Обычно простейшую д.н.ф. относительно LБ(R) называют минимальной, а относительно LК(R) – кратчайшей.
Задача выбора минимальной д.н.ф. для f(x1, …, xn) может быть решена тривиальным перебором д.н.ф., но этот путь порочен ввиду громоздкости.