|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Обобщенная сложность линейных булевых функций
Н. П. Редькин МГУ имени М. В. Ломоносова
Аннотация:
Изучается обобщенная (по базисам) сложность реализации линейных булевых функций схемами из функциональных элементов в произвольных функционально полных базисах; сложность всякой схемы при этом определяется числом функциональных элементов в ней. Пусть $L^{*}(n)$ — наименьшее возможное число элементов, достаточное для реализации произвольной линейной булевой функции от $n$ переменных схемой в любом функционально полном базисе. Устанавливается, что $L^{*}(0)=L^{*}(1)=3$ и $L^{*}(n)=7(n-1)$ при любом натуральном $n\ge2$.
Ключевые слова:
булева функция, схема из функциональных элементов, сложность булевой функции, функция Шеннона.
Статья поступила: 03.04.2018
Образец цитирования:
Н. П. Редькин, “Обобщенная сложность линейных булевых функций”, Дискрет. матем., 30:4 (2018), 88–96
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm1513https://doi.org/10.4213/dm1513 https://www.mathnet.ru/rus/dm/v30/i4/p88
|
|