Аннотация:
Изучается обобщенная (по базисам) сложность реализации линейных булевых функций схемами из функциональных элементов в произвольных функционально полных базисах; сложность всякой схемы при этом определяется числом функциональных элементов в ней. Пусть $L^{*}(n)$ — наименьшее возможное число элементов, достаточное для реализации произвольной линейной булевой функции от $n$ переменных схемой в любом функционально полном базисе. Устанавливается, что $L^{*}(0)=L^{*}(1)=3$ и $L^{*}(n)=7(n-1)$ при любом натуральном $n\ge2$.
Ключевые слова:булева функция, схема из функциональных элементов, сложность булевой функции, функция Шеннона.