ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
191
Опишем блоки
, 1
j
T j n
≤ ≤
.
Пусть
, 1
j
M j n
≤ ≤
, –
( , ] [)
k qn
-
матрица, у которой
i
-
я строка,
0
1
i k
≤ ≤ −
,
является двоичной запи-
сью числа
1
j
ik
−
.
Пусть теперь
, 0 ] [ 1
j
t
f
t qn
≤ ≤ −
, –
функция от одного
аргумента, вектором задания которой является
t
-
й столбец матрицы
, 1
j
M j n
≤ ≤
.
Блок , 1
j
T j n
≤ ≤
,
состоит из
] [
qn
(1, 1)-
блоков, реали-
зующих функции
j
t
f
.
Входы этих блоков присоединены к входу блока
j
T
.
Нетрудно
проверить справедливость оценки
4
( )
] [
j
L T c qn
≤
.
Таким образом, получена следующая оценка
2
5
( _ 2 )
.
L K N c n
≤
Пусть
2 _
K
– (]
q
[,1)-
блок, который на булевых наборах выдает
значение, равное числу, двоичной записью которого является набор
значений его входов. Очевидна оценка
6
(2 _ )
L K c
≤
.
Пусть
BFN
–
(] [, ] [)
qn q
-
схема, реализующая систему
] [
q
буле-
вых функций от
] [
qn
переменных, аналогичную системе
f
G
.
На
наборах значений входов схемы
BFN
,
являющихся двоичной запи-
сью чисел больше или равных
,
n
k
значения ее выходов полагаем
равным 0.
Из работы [3] следует оценка
]
log [
(
) ]
log [
.
log log
n
n
k
k k
L BFN
k
n k
k n
≤
=
∼
Таким образом, справедливо следующее утверждение.
Теорема 3.
1
]
log [
( , )
.
log
n
B
k k
L k n
k n
≤
∼
Замечание
.
Разлагая (по аналогии с [6]) функцию
f
по перемен-
ным, можно получить оценку
1
( , )
n
B
k
L k n
n
∼
при любых
k
.
Таким образом, предложено семейство
k
-
значных базисов и пока-
зана их полнота. Для этих базисов построены методы синтеза схем из
функциональных элементов, обеспечивающие асимптотически