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

В данной работе рассматриваются реализации линейных булевых функций схемами из функциональных элементов в базисе Б, состоящем из двухвходовых функциональных элементов, реализующих нелинейные функции, и инвертора. Вес двухвходового элемента в базисе Б принимается равным единице, а вес инвертора – нулю.
В работе дано описание всех минимальных схем, реализующих линейные функции в базисе Б, а именно, показано, что все такие схемы имеют определенный блочный вид.
Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований, проект 11–01–00508, и Программы фундаментальных исследований Отделения математических наук РАН “Алгебраические и комбинаторные методы математической кибернетики и информационные системы нового поколения”, проект “Задачи оптимального синтеза управляющих систем”.