ИНФОРМАТИКА И ВЫЧИСЛИТЕЛЬНАЯ
ТЕХНИКА
УДК 519.6
О РЕАЛИЗАЦИИ БУЛЕВЫХ ФУНКЦИЙ СХЕМАМИ
В ПРОИЗВОЛЬНОМ БАЗИСЕ
В.А. Орлов
МГТУ им. Н.Э. Баумана, Москва, Российская Федерация
e-mail:
Рассмотрены вопросы реализации булевых функций схемами, содержащими
функциональные элементы. Предложен метод асимптотически наилучшей ре-
ализации булевых функций схемами в полном произвольном конечном бази-
се. В этом методе применены разработанная автором модификация метода
О.Б. Лупанова для базиса, состоящего из элементов весом 1, которые реализу-
ют дизъюнкцию, конъюнкцию и отрицание, а также принцип использования не
всюду определенных функций. Такая модификация более универсальна: все блоки
схемы не зависят от реализуемой функции, которая определяет только соеди-
нения входов и выходов блоков. В случае произвольного базиса схема включает
в себя цепочки самых “дешевых” элементов. Указанные цепочки реализуют не
всюду определенные булевы функции, которые на наборе из всех нулей равны
нулю, а на наборах, содержащих одну единицу, — единице.
Ключевые слова
:
схемы из функциональных элементов, булевы функции, слож-
ность схемы, функционалы Шеннона, не всюду определенные булевы функции.
ON IMPLEMENTATION OF BOOLEAN FUNCTIONS
BY LOGIC CIRCUITS IN AN ARBITRARY BASIS
V.A. Orlov
Bauman Moscow State Technical University, Moscow, Russian Federation
e-mail:
Issues of implementation of Boolean functions by logic circuits containing functional
elements are discussed. A method is proposed for asymptotically best possible
implementation of Boolean functions by logical circuits in a complete arbitrary
finite basis. This method uses the O.B. Lupanov’s method modified by the author for
a basis, consisting of elements with a weight of 1, which implement disjunction,
conjunction, and negation, as well as the principle of using incompletely defined
functions. This modification is more universal: all units of the circuit are independent
of the implemented function that defines only the connections between inputs and
outputs of the units. In the case of arbitrary basis, the circuit includes chains of
the “cheapest” elements of the basis. These chains implement incompletely defined
Boolean functions, which are zeroes on the sets consisting only of zeros, while on the
sets containing exactly one 1, they are equal to unity.
Keywords
:
logical circuits, Boolean functions, complexity of a logical circuit,
Shannon’s functions, incompletely defined Boolean functions.
Разработка оптимальных по различным критериям устройств обра-
ботки дискретной информации является актуальной областью совре-
менной науки и техники. В связи с развитием элементной базы можно
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2014. № 1 101
