В приведенной схеме использовано специальное обозначение , представляющее фрагмент схемы, имеющий вид:
,
если
= 0
З десь =
, в противном случае.
То есть такое обозначение соответствует либо отрицанию, либо проводнику в схеме. Нетрудно видеть, что всякое вхождение такого фрагмента в с.ф.э. вычисляет функцию x.
Схема, реализующая конъюнкцию k, имеет сложность, равную n - 1 .
Пусть построены схемы 1, . . ., k, вычисляющие все конъюнкции из СДНФ для f. Тогда f реализуется схемой f, представленной на рис.4.3:
x1 x2 xn
.
. .
. . . . . . . . .
1 2 . . . r
. . .
f
Рис 4.3
Определим число функциональных элементов & и, входящих в f.
Понятно,
что
L(f)
=
+
r
- 1
= (n
- 1)
r
+ r
- 1.
В общем случае значение r может изменяться в пределах от 1 до 2n. Если остановиться на “среднем“ случае, когда f принимает значение 1 на половине наборов значений переменных, то r = 2n 1 .
Полученное значение сложности с.ф.э. оказывается слишком большим для того, чтобы схему для практически важных булевских функций можно было считать реализуемой. Например, уже для n = 16 значение L(f) имеет величину, близкую к 16 215 = 219. Последнее значение превосходит 500000.
Поэтому приведенный пример построения с.ф.э., реализующих произвольные б.ф., основанный на представлении функции в виде СДНФ, не применим на практике.
Следовательно, требуется разработка специальных методов построения или синтеза с.ф.э., приводящих к более простым схемам, чем схемы, получаемые по предложенному ранее простому методу синтеза схем.
В определении сложности с.ф.э. не учитывается количество элементов отрицания. Это связано с тем, что практические методы синтеза схем обычно основаны на реализации формул, подобных СДНФ. Поскольку в СДНФ функция отрицания применяется только к отдельным переменным, то для получения значений отрицаний n переменных достаточно включить в схему ровно n элементов, вычисляющих отрицание. Выходы таких элементов могут расщепляться и использоваться в качестве входов для схем вычисления элементарных конъюнкций, входящих в СДНФ.
4.9. Минимальные днф
Представление б.ф. виде СДНФ в общем случае оказывается не компактнее, чем представление в виде табличного задания, поскольку для каждого набора значений переменных, на котором б.ф. f(x1, . . . , xn) равна 1, в СДНФ включается элементарная конъюнкция ранга n. То есть если f принимает значение 1 на значительной части всех наборов, то СДНФ этой функции по размерам сравнима с табличным заданием f.
ОПРЕДЕЛЕНИЕ
Дизъюнктивной нормальной формой (ДНФ) называется всякая формула вида D = K1 . . . Kr , где K1, . . . , Kr это произвольные элементарные конъюнкции.