создавать устройства, реализующие сложные преобразования. Наибо-
лее распространенное средство моделирования указанных устройств —
схемы, состоящие из функциональных элементов, реализующих функ-
ции алгебры логики (булевы функции). В настоящей статье рассмо-
трены вопросы оптимальной реализации булевых функций схемами
из функциональных элементов в произвольном базисе.
Функция, переменные которой принимают значения из множества
{
0
,
1
}
и которая принимает значения из этого множества, называется
булевой. Множество всех булевых функций обозначим как
P
2
.
Задача реализации функций из множества
P
2
схемами из функцио-
нальных элементов в произвольном базисе заключается в следующем.
Пусть
Φ
— произвольная конечная полная система функций мно-
жества
P
2
, каждая из которых (кроме функций, тождественно равных
константе) существенно зависит от конечного числа всех своих пере-
менных. Константы полагаем функциями одной переменной. Системе
Φ
сопоставим базис
B
, состоящий из реализующих ее функции эле-
ментов с одним состоянием, каждому из которых соответствует поло-
жительное число (вес элемента). Из элементов базиса строим схемы,
в которых каждый вход каждого элемента присоединен либо к выходу
другого элемента, либо к входу схемы. При этом запрещается соеди-
нять выходы различных элементов и образовывать “петли обратной
связи” (ориентированные циклы). Выходами схемы являются выходы
некоторых элементов. Известно, что каждая схема реализует систему
булевых функций. Отметим, что любой элемент базиса имеет один
выход.
Критерием оптимальности схемы принимаем сумму весов ее эле-
ментов, которую назовем
сложностью
схемы
S
и обозначим как
L
(
S
)
.
На практике наиболее востребована задача нахождения функцио-
нала
L
B
(
f
)
, равного минимальной сложности схем в базисе
B
, реали-
зующих функцию
f
. В настоящее время эффективного метода (отлич-
ного от перебора схем) решения этой задачи в случае произвольных
булевых функций не существует. Ввиду этого часто рассматривают за-
дачу исследования асимптотического поведения функционала
L
B
(
n
)
,
равного максимуму функционалов
L
B
(
f
)
,
f
2
P
n
2
, где
P
n
2
— множество
булевых функций переменных
x
1
, x
2
, . . . , x
n
.
Для элемента базиса, имеющего не менее двух входов, его приве-
денным весом называется отношение веса к уменьшенному на едини-
цу числу входов. Приведенный вес базиса — это минимум приведен-
ных весов его элементов.
Задача асимптотически наилучшей реализации булевых функций
схемами в произвольном полном конечном булевом базисе решена
О.Б. Лупановым [1]. Однако в отличие от разработанного им же мето-
да асимптотически наилучшей реализации булевых функций схемами
102 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2014. № 1
