ВУЗ:
Составители:
Рубрика:
24
Тема. Минимизация булевых функций.
6. Проблема минимизации. Порождение простых
импликантов. Алгоритм Куайна и Мак-Клоски.
Проблема минимизации.
Определение. ДНФ
ϕ
функции f называется
а) минимальной
(минимальной по литералам), если она имеет
наименьшее число символов переменных среди других ДНФ
функции f;
б) кратчайшей
(минимальной по конъюнкциям), если она имеет
минимальное число элементарных конъюнкций.
Число различных элементарных конъюнкций от n переменных
равно 3
n
, т.к. любая переменная может либо входить в
конъюнкцию, либо не входить, либо входить с отрицанием. Тогда
ДНФ от n переменных однозначно определяется вектором длины
3
n
, состоящим из нулей и единиц, где 1 означает, что
соответствующая элементарная конъюнкция входит в ДНФ, а 0 -
не входит. Поэтому число всех ДНФ от “n”переменных равно
n
3
2 .
Для произвольной функции алгебры логики можно написать
много ДНФ. Проблема минимизации
состоит в том, чтобы для
функции f построить минимальную ДНФ в определенном выше
смысле. Эта проблема допускает тривиальное решение,
заключающееся в переборе всех
n
3
2 ДНФ, но очевидно, что такое
решение является чрезвычайно трудоемким даже при небольших
значениях n.
Определение.
Формула
Ψ
влечет формулу
Φ
(обозначение
Ψ
Φ
), если (
Ψ
Φ
)
≡
1, т.е. не существует такого набора
значений переменных, при котором
Ψ
принимает значение 1, а
Φ
- значение 0.
Определение.
Элементарная конъюнкция K называется
импликантом
функции f, если K
f.
Пример 6.1.
Пусть
(, ,)
f
xyz xyz xyz=∨ и пусть K=x y=x
1
y
0
. К=1
⇔
x=1,
y=0. Поскольку f(1,0,z)=1
⋅
1
⋅
z
∨
1
⋅
1
⋅
z
= z
∨
z
≡
1, то К=x y
является импликантом функции f.
Страницы
- « первая
- ‹ предыдущая
- …
- 22
- 23
- 24
- 25
- 26
- …
- следующая ›
- последняя »
