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