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

Дискрет. матем., 2020, том 32, выпуск 2, страницы 32–43 (Mi dm1592)

О сложности реализации булевых функций с малым числом единиц

Н. П. Редькин

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

Аннотация: Рассматривается класс булевых функций $F_{n,k}$, состоящий из всех тех функций от $n$ переменных, каждая из которых обращается в единицу ровно на $k$ наборах значений переменных. При небольших $k$ класс $F_{n,k}$ разбивается на подклассы, и для каждого подкласса находится асимптотика функции Шеннона для сложности реализации функций из этого подкласса схемами из функциональных элементов в базисе $\{x\&y,\overline x\}$ (или в базисе $\{x\vee y,\overline x\}$); весами элементов базисов при этом могут быть любые строго положительные числа.

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

УДК: 519.714.4

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

DOI: 10.4213/dm1592


 Англоязычная версия: Discrete Mathematics and Applications, 2021, 31:4, 271–279

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


© МИАН, 2024