|
Обобщенная сложность линейных булевых функций
Н. П. Редькин МГУ имени М. В. Ломоносова
Аннотация:
Изучается обобщенная (по базисам) сложность реализации линейных булевых функций схемами из функциональных элементов в произвольных функционально полных базисах; сложность всякой схемы при этом определяется числом функциональных элементов в ней. Пусть $L^{*}(n)$ — наименьшее возможное число элементов, достаточное для реализации произвольной линейной булевой функции от $n$ переменных схемой в любом функционально полном базисе. Устанавливается, что $L^{*}(0)=L^{*}(1)=3$ и $L^{*}(n)=7(n-1)$ при любом натуральном $n\ge2$.
Ключевые слова:
булева функция, схема из функциональных элементов, сложность булевой функции, функция Шеннона.
Финансовая поддержка |
Номер гранта |
Российский фонд фундаментальных исследований  |
18.01.00337 |
Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (проект № 18.01.00337 “Проблемы синтеза, сложности и надежности в теории управляющих систем”). |
DOI:
https://doi.org/10.4213/dm1513
Полный текст:
PDF файл (165 kB)
Первая страница: PDF файл
Список литературы:
PDF файл
HTML файл
Реферативные базы данных:
Тип публикации:
Статья
УДК:
519.714.4 Статья поступила: 03.04.2018
Образец цитирования:
Н. П. Редькин, “Обобщенная сложность линейных булевых функций”, Дискрет. матем., 30:4 (2018), 88–96
Цитирование в формате AMSBIB
\RBibitem{Red18}
\by Н.~П.~Редькин
\paper Обобщенная сложность линейных булевых функций
\jour Дискрет. матем.
\yr 2018
\vol 30
\issue 4
\pages 88--96
\mathnet{http://mi.mathnet.ru/dm1513}
\crossref{https://doi.org/10.4213/dm1513}
\elib{https://elibrary.ru/item.asp?id=36447994}
Образцы ссылок на эту страницу:
http://mi.mathnet.ru/dm1513https://doi.org/10.4213/dm1513 http://mi.mathnet.ru/rus/dm/v30/i4/p88
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
|
Просмотров: |
Эта страница: | 179 | Литература: | 21 | Первая стр.: | 18 |
|