Page 51 - ЭВМ

Например, необходимо составить СДНФ для таблично заданной
функции:

x 1 x 2 x 3 z
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 0

(
Воспользовавшись правилом построения СДНФ z = f x x 2 3 ) ,,x ,
1
получим:

z = x xx ∨ ⋅ 3 x x x ∨ ⋅ 3 x xx ∨ ⋅ 3 x x x .
⋅
⋅
⋅
⋅
⋅
1
2
1
2
1
1
2
3
2

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

)
z = ( x ∨ 2 x ⋅ 3 )x ∨ ( 1 x ∨ x ∨ 2 x ⋅ 3 ) 1 ( 1 x ∨ 2 x ⋅ 3 ) ( 1 x ∨ 2 x .
x ∨
x ∨
3

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

вило, практический интерес представляют формы, имеющие мини-
мальную цену. Такая оптимизация нужна для упрощения сложных
схем [1–4].
Минимизация – это процесс приведения булевых функций к та-
кому виду, который допускает наиболее простую, с наименьшим чис-
лом элементов физическую реализацию функции. Частная задача

минимизации булевой функции сводится к такому представлению

51