О реализации булевых функций схемами в произвольном базисе

Рассмотрены вопросы реализации булевых функций схемами, содержащими функциональные элементы. Предложен метод асимптотически наилучшей реализации булевых функций схемами в полном произвольном конечном базисе. В этом методе применены разработанная автором модификация метода О.Б. Лупанова для базиса, состоящего из элементов весом 1, которые реализуют дизъюнкцию, конъюнкцию и отрицание, а также принцип использования не всюду определенных функций. Такая модификация более универсальна: все блоки схемы не зависят от реализуемой функции, которая определяет только соединения входов и выходов блоков. В случае произвольного базиса схема включает в себя цепочки самых "дешевых " элементов. Указанные цепочки реализуют не всюду определенные булевы функции, которые на наборе из всех нулей равны нулю, а на наборах, содержащих одну единицу, - единице.

Литература

[1] Лупанов О.Б. Об одном методе синтеза схем // Изв. вузов. Радиофизика. 1958. Т. 1. № 1. С. 120-140.

[2] Лупанов О.Б. О синтезе некоторых классов управляющих систем // Сб. Проблемы кибернетики. Вып. 10. М.: Физматгиз, 1963. С. 3-97.

[3] Яблонский С.В. Асимптотически наилучший метод синтеза надежных схем из ненадежных элементов // Banach Center Pub. 1982. № 7. P. 11-19.