Войти / Регистрация
Корзина

  • Ваша корзина пуста
Войти / Регистрация
Корзина

  • Ваша корзина пуста

Статья «Сложность реализации симметрических булевых функций схемами в базисе антицепных функций, "Дискретная математика"»

Авторы:
  • Подольская Ольга В1
стр. 95-107
Платно
1 Московский государственный университет имени М.В. Ломоносова
Ключевые слова:
  • сложность булевых функций
  • антицепные функции
  • булевы схемы
  • симметрические булевы функции
  • функция Шеннона.
Аннотация:
Изучается сложность реализации булевых функций схемами из функциональных элементов в бесконечном базисе, состоящем из всех характеристических функций антицепей на булевом кубе. Установлено точное значение сложности реализации произвольной симметрической функции схемами в этом базисе. В частности, для функций четности и голосования от переменных при всех натуральных получены точные значения сложности: и соответственно. Установлено, что наибольшая сложность булевых функций от переменных при реализации схемами в этом базисе по порядку роста равна . Работа выполнена при поддержке Российского фонда фундаментальных исследований, проект 14 01 00598.

Архивные статьи (2015 год и ранее) доступны для ознакомления бесплатно, для скачивания их необходимо приобрести. Для просмотра материалов необходимо зарегистрироваться и авторизоваться на сайте.

Чтобы приобрести доступ к материалу для юридического лица, пожалуйста, свяжитесь с администрацией портала с помощью формы обратной связи либо по электронному адресу libnauka@naukaran.com.  

Действия с материалами доступны только авторизованным пользователям.