ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
188
Пусть
2 0
K
–
( , )
q s
-
блок, состоящий из элементов
1
E
и реализу-
ющий систему функций. Выходной набор этой функции на булевом
наборе, являющемся записью числа
, 0
1,
i
i k
≤ ≤ −
будет набор, на
котором функция
2,
k
f
принимает значение
i
.
Схема
0
f
S
имеет
n
входов, один выход и состоит из блока 20 ,
K N
схемы
b
f
S
,
блока
2 0
K
и элемента
2,
k
E
.
Входы блока
20
K N
присо-
единены к входам схемы. Входы схемы
b
f
S
присоединены к выходам
блока
20
K N
.
Входы блока
2 0
K
присоединены к выходам схемы
b
f
S
.
Входы элемента
2,
k
E
присоединены к выходам блока
2 0
K
.
Выхо-
дом схемы
0
f
S
является выход элемента
2,
k
E
.
Нетрудно проверить, что схема
0
f
S
является схемой в базисе
1
B
и
реализует (произвольную) функцию
n
k
f P
∈
.
Таким образом, доказа-
но, что базис
1
B
функционально полон в
k
P
.
Исследуем асимптотическое поведение функционала
1
( , )
B
L k n
.
Вначале рассмотрим случай, когда
k
является степенью 2, т. е.
2
2
log ]log [
q
k
k
= =
.
Пусть
1
C
–
2
( , ]
log [)
r
k
-
блок, состоящий из элементов
1
E
и реа-
лизующий систему функций, выходной набор которой на входном
наборе, являющемся выходным набором элемента
20
K
при равном
, 0
1,
i
i k
≤ ≤ −
значении входа последнего, является двоичной запи-
сью числа
i
.
Пусть
2
K N
– (1,
q
)-
блок, состоящий из блока
20
K
и блока
1
C
.
Входы блока
1
C
присоединены к выходам блока
20
K
.
Входом блока
2
K N
является вход блока
20
K
,
а выходами блока
2
K N
–
выходы
блока
1
C
.
Отметим, что при равном
, 0
1,
i
i k
≤ ≤ −
значении входа блока
2
K N
набор значений его выходов является двоичной записью числа
i
.
Пусть
2
K NN
–
( , )
n qn
-
блок, состоящий из
n
блоков
2
K N
.
Вхо-
дами (выходами) блока
2
K NN
являются входы (выходы) блоков
2
K N
.
Нетрудно проверить, что последовательностью значений вы-
ходов блока
2
K NN
является двоичная запись числа,
k
-
ичной запи-
сью которого является набор значений его входов. Пусть
2
KN
–
(
q
,1)-
блок, состоящий из
( , )
q s
-
блока
2
KO
и элемента
2,
k
E
.
Входы
элемента
2,
k
E
присоединены к выходам блока
2
KO
.
Выходом блока