ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
189
2
KN
является выход элемента
2,
k
E
.
Отметим, что блок
2
KN
на бу-
левых наборах выдает значение, равное числу, двоичной записью ко-
торого является набор значений его входов.
Воспользуемся принципом глобального компактного кодирова-
ния: символу
, 0
1,
i
i k
≤ ≤ −
сопоставим булев набор, являющийся
двоичной записью числа
i
(
код символа). В таблице, задающей про-
извольную функцию
n
k
f P
∈
,
символы
, 0
1,
i
i k
≤ ≤ −
заменим их ко-
дами. Полученная таким образом таблица истинности задает систему
f
G
(
всюду определенных)
q
булевых функций от
nq
переменных.
Пусть
GB
– (
qn
,
q
)-
схема, реализующая систему
f
G
.
Пусть
SFN
–
схема, состоящая из блока 2 ,
K NN
схемы
GB
и бло-
ка
2
KN
.
Соединение элементов схемы
SFN
представлено на рис. 1.
Рис. 1. Схема
SFN
Нетрудно проверить, что схема
SFN
реализует функцию
.
f
Очевидно, что
(
) ( 2 ) ( ) (2 ).
L SFN L K NN L GB L KN
=
+
+
Далее
j
c
означены константы.
Оценка
1
( 2 )
L K N c
≤
очевидна (напомним, что значность логики
(
число
k
)
считается величиной постоянной). Отсюда получаем оцен-
ку
1
( 2 )
L K NN c n
≤
.
Оценка
2
(2 )
L KN c
≤
также очевидна.
Из теоремы 1 получаем оценку