Page 52 - ЭВМ

заданной функции, которое содержит наименьшее возможное число
букв и наименьшее возможное число операций над ними.
Оценить различные представления одной и той же булевой

функции, например дизъюнктивную нормальную форму (ДНФ), мож-
но по количеству входов логических элементов, реализующих задан-
ную функцию. Такую оценку реализации булевой функции называют
ценой реализации булевой функции по Квайну (или ценой покрытия
булевой функции системой логических элементов).
Для изложения методов минимизации введем некоторые опре-

σ
σ
деления. Конъюнкция p = x x Kx σ R R называется элементарной, ес-
1
2
2
1
ли число ее членов меньше некоторого множества переменных n,
σ
причем любая переменная x входит в конъюнкцию только один раз.
i
i
Число членов элементарной конъюнкции определяет ее ранг.
Под импликантной булевой функцией f(x 1, x 2, …, x n) понимается
такая булева функция f 1(x 1, x 2, …, x n), если на любом наборе значений
переменных x 1, x 2, …, x n, на котором значение функции f 1 равно еди-
нице, значение функции f также равно единице.
Под простой импликантной булевой функцией f(x 1, x 2,…, x n) по-
σ
σ
нимается всякое элементарное произведение p = x x Kx σ R R , которое
2
1
2
1
является импликантной функцией ƒ, и никакая собственная часть это-
го произведения в функцию ƒ не входит, т. е. простые импликанты –
элементарные конъюнкции наименьшего ранга, входящие в данную
булеву функцию.
Сокращенной дизъюнктивной нормальной формой булевой
функции называется такая функция, которая равна дизъюнкции всех

своих простых импликант. Несмотря на то, что сокращенная ДНФ бу-
левой функции содержит меньшее число букв, чем СДНФ этой же
функции, она в большинстве случаев допускает дальнейшее упроще-
ние за счет поглощения некоторых простых импликант дизъюнкцией

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

можно решать в следующей последовательности: для заданной функ-
ции находят сокращенную ДНФ, т. е. все простые импликанты, затем
определяют тупиковые ДНФ заданной функции, среди которых вы-
бирают минимальную ДНФ.

52