ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
186
ции называют
не всюду определенными
;
при их реализации схемами
необходимо полное доопределение. Реализация не всюду определен-
ных
булевых
функций – хорошо исследованная область синтеза
управляющих систем (отметим работы Э.И. Нечипорука, Л.А. Шо-
ломова, А.А. Андреева).
Пусть
1
A
и
2
A
–
подалфавиты алфавита
k
A
.
Функцию, значения
аргументов (значения выходов) которой принадлежат
1
A
(
принадле-
жат
2
A
),
назовем (
1
A
,
2
A
)-
функцией. (
k
A
,
2
A
)-
функцию –
( , 2)
k
-
функцией. На практике при реализации функций из
k
P
допустимо рас-
сматривать и базисы, в которых некоторые элементы реализуют (
1
A
,
2
A
)-
функции. При этом на схему накладываются дополнительные
естественные ограничения: вход элемента
E
нельзя присоединять к
выходу элемента, выходные значения которого могут не принадле-
жать входному алфавиту элемента
E
.
Функцию
k
f P
∈
одного аргумента будем задавать вектором,
i
-
й
компонент
которого,
0
1
i k
≤ ≤ −
,
равен
( )
f i
.
Систему
1 2
{ , , ..., }
r
F f f
f
=
2
( , )
k
A A
-
функций одного аргумента назовем
( , 2)
k
-
достаточной
,
если все столбцы
( , )
r k
-
матрицы, строки которой суть
векторы функций из
,
F
различны. Отметим, что
2
]
log [
r
k
≥
.
Пример
(7,2)
-
достаточно
й системы приведен ниже:
x
0 1 2 3 4 5 6
1
f
0 1 0 1 0 1 1
2
f
0 0 1 1 0 0 1
3
f
0 0 0 0 1 1 1
Пусть
1
Φ
–
система функций из
k
P
такая, что с помощью опера-
ций суперпозиции над
1
Φ
можно получить:
•
функционально полную систему булевых функций
1
b
Φ
;
•
( , 2)
k
-
достаточную систему функций
2
1
Φ
;
•
функцию
2,
k
f
,
которая на булевых наборах значений ее аргу-
ментов принимает все значения из алфавита
k
A
.
Нетрудно проверить, что система
2
1
1
b
Φ Φ
∪
является
( , 2)
k
-
полной.
Системе
1
Φ
сопоставим базис
1
B
и покажем, что любую функ-
цию из
k
P
можно реализовать схемой в этом базисе.