ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
184
УДК 519.6
В . А . О р л о в
О РЕАЛИЗАЦИИ КОНЕЧНОЗНАЧНЫХ
ОТОБРАЖЕНИЙ
Рассмотрены вопросы реализации конечнозначных функций схемами
из функциональных элементов. Предложено семейство k-значных ба-
зисов и показана их полнота. Для этих базисов построены методы
синтеза схем из функциональных элементов, обеспечивающие асимп-
тотически наилучшие оценки.
Email:
orlovaldr@mail.ru
Ключевые слова:
схемы из функциональных элементов, k-значные
логики, полнота систем функций, сложность схемы, функционалы
Шеннона.
Оптимальная реализация дискретных отображений различными
средствами – актуальная задача теоретической и технической киберне-
тики. Эту задачу часто называют синтезом управляющих систем.
Наиболее исследованной является реализация булевых функций схе-
мами из функциональных элементов. В данной работе рассмотрены
вопросы оптимальной реализации конечнозначных функций схемами
из функциональных элементов.
Функция, переменные которой принимают значения из алфавита
{0,1, ...,
1},
2,
k
A
k k
=
− ≥
и которая сама принимает значения из этого
алфавита, называется
-
k
значной
[1].
Множество всех
k
-
значных
функций обозначается через
k
P
.
Функции из
2
P
часто называют бу-
левыми.
Рассмотрим задачу о реализации функций из
k
P
схемами из
функциональных элементов в произвольном базисе.
Пусть
Φ
–
произвольная конечная полная система функций из
k
P
,
2
k
≥
,
каждая из которых (кроме функций, тождественно равных
константе) существенно зависит от конечного числа всех своих пе-
ременных. Константы считаем функциями от одной переменной. Си-
стеме
Φ
сопоставим базис
B
,
состоящий из реализующих ее функ-
ции элементов с одним состоянием, каждому из которых приписано
положительное число (вес элемента). Базис
B
будем называть
k
-
значным, а булевым – 2-значный базис.
Из элементов базиса строим схемы, в которых каждый вход каж-
дого элемента присоединен либо к выходу другого элемента, либо к
входу схемы. При этом запрещается соединять выходы различных
элементов и образовывать «петли обратной связи» (ориентированные