RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретная математика // Архив

Дискрет. матем., 2018, том 30, выпуск 4, страницы 88–96 (Mi dm1513)

Эта публикация цитируется в 1 статье

Обобщенная сложность линейных булевых функций

Н. П. Редькин

МГУ имени М. В. Ломоносова

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

Ключевые слова: булева функция, схема из функциональных элементов, сложность булевой функции, функция Шеннона.

УДК: 519.714.4

Статья поступила: 03.04.2018

DOI: 10.4213/dm1513



Реферативные базы данных:


© МИАН, 2024