ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
187
Для простоты изложения будем полагать, что система
1
b
Φ
состо-
ит из функции ¬(
1
x
&
2
x
) (
штрих Шеффера). Пусть
1
E
–
элемент с
двумя входами, реализующий эту функцию и имеющий вес 1. Пусть
2 2
2
1 2
,
, ...,
r
E E E
–
элементы, реализующие функции из
2
1
Φ
и имеющие
вес ;
k
2,
k
E
–
элемент, реализующий функцию
2,
k
f
и имеющий рав-
ный
sk
вес (
s
–
число аргументов функции
2,
k
f
).
Нетрудно прове-
рить, что базис
1
B
является нормированным.
Поскольку для доказательства полноты базиса
1
B
сложности
схем не имеют значения, используем упрощенный вариант предло-
женного автором [4]
принципа глобального компактного кодирова-
ния
:
таблице, задающей произвольную функцию
n
k
f P
∈
,
сопоставим
таблицу, задающую систему
2
]
log [
k
булевых функций от
rn
пере-
менных, следующим образом.
Символу
, 0
1,
i
i k
≤ ≤ −
набора значений переменных функции
f
сопоставим булев набор (длины
r
),
являющийся
i
-
м столбцом
матрицы, соответствующей
( , 2)
k
-
достаточной системе
2
1
Φ
.
В табли-
це, задающей произвольную функцию
n
k
f P
∈
,
символ
, 0
1,
i
i k
≤ ≤ −
набора значений переменных заменим его кодом (булевым набором).
Символ
, 0
1,
i
i k
≤ ≤ −
значения функции заменим булевым набором
длины
2
]
log [
k
,
являющимся двоичной записью числа
i
.
В случае
необходимости (
2
log
r
k
≠
)
к полученной таким образом таблице до-
бавим неиспользованные булевы наборы длины
nr
.
На этих наборах
значения функции дополним нулями. Эта (новая) таблица задает си-
стему
0
f
G
(
всюду определенных)
2
]
log [
k
булевых функций от
nr
пе-
ременных.
Имеющая
n
входов и
m
выходов схема называется (
n
,
m
)-
схемой
или (
n
,
m
)-
блоком.
Опишем схему
0
f
S
в базисе
1
B
,
реализующую произвольную
функцию
n
k
f P
∈
.
Пусть
20
K
–
(1, )
r
-
блок, состоящий из элементов
2 2
2
1 2
,
, ...,
r
E E E
,
входы которых присоединены к его входу; выходами блока являются
выходы его элементов. Пусть
20
K N
–
( , )
n rn
-
блок, состоящий из
n
блоков
20
K
.
Входами блока
20
K N
являются входы блоков
20
K
.
Выходами блока
20
K N
являются выходы блоков
20
K
.
Пусть
b
f
S
–
2
( , ]
log [)
nr
k
-
схема, состоящая из элементов
1
E
и ре-
ализующая систему
0
f
G
.