RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор
Подписка
Правила для авторов

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Дискрет. матем.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


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

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

Н. П. Редькин

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

Аннотация: Изучается обобщенная (по базисам) сложность реализации линейных булевых функций схемами из функциональных элементов в произвольных функционально полных базисах; сложность всякой схемы при этом определяется числом функциональных элементов в ней. Пусть $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/dm1513
  • https://doi.org/10.4213/dm1513
  • http://mi.mathnet.ru/rus/dm/v30/i4/p88

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Дискретная математика
    Просмотров:
    Эта страница:179
    Литература:21
    Первая стр.:18
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2021