ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
185
циклы). Выходами схемы являются выходы некоторых элементов.
Известно, что каждая схема реализует систему функций из
k
P
.
Заме-
тим, что любой элемент базиса имеет один выход.
В данной работе критерием оптимальности схемы считаем сумму
весов ее элементов. Эту сумму назовем
сложностью схемы
S
и обо-
значим
( )
L S
.
Практически наиболее востребованной является задача нахожде-
ния функционала
( )
B
L f
,
равного минимальной сложности схем в
базисе
B
,
реализующих функцию
.
f
В настоящее время эффектив-
ного метода (отличного от перебора схем) решения этой задачи нет.
Вследствие этого часто рассматривают задачу исследования асимп-
тотического поведения функционала
( , )
B
L k n
,
равного максимуму
функционалов
( )
B
L f
,
n
k
f P
∈
,
где
n
k
P
–
множество
k
-
значных функ-
ций от переменных
1 2
, ,...,
n
x x x
.
При этом полагают, что
k
–
фиксиро-
вано, а
n
→∞
.
Функционал ( , )
B
L k n
для
2
k
=
обозначим ( )
B
L n
.
От-
метим, что
|
|
n
n
k
k
P k
=
.
Для имеющего не менее двух входов элемента базиса его приве-
денным весом [2] называют отношение веса к уменьшенному на еди-
ницу числу входов. Приведенным весом базиса называется минимум
приведенных весов его элементов.
Базис, приведенный вес которого равен 1, называют
нормирован-
ным
[3].
Без ограничения общности, в дальнейшем будем рассматри-
вать нормированные базисы.
Случай
2
k
=
исследован достаточно хорошо. Приведем исполь-
зуемый далее результат О.Б. Лупанова [2].
Теорема 1.
Для любого нормированного
2
-
базиса
B
2 ( )
.
n
B
L n
n
∼
Отметим, что нижние оценки сложности схем, рассматриваемых
в работе, получаются из «мощностных» соображений: оценивается
число функций и число схем заданной сложности.
Для
3
k
≥
до появления работ [4–6] рассматривалось поведение
функционала
( , )
B
L k n
только при фиксированных базисах
B
(
см.,
например [7]).
Обычно полагают, что функции из
n
k
P
определены на всех
n
k
наборах значений их переменных. Однако рассматривают и функции,
значения которых на некоторых наборах безразличны. Такие функ-