?
Сложность реализации симметрических булевых функций схемами в базисе антицепных функций
Дискретная математика. 2015. Т. 27. № 3. С. 95–107.
Подольская О. В.
Изучается сложность реализации булевых функций схемами из функциональных элементов в бесконечном базисе, состоящем из всех характеристических функций антицепей на булевом кубе. Установлено точное значение сложности реализации произвольной симметрической функции схемами в этом базисе. В частности, для функций четности и голосования от $n$ переменных при всех натуральных $n\geq1$ получены точные значения сложности: $\lfloor \frac{n+1}{2} \rfloor$ и $\lfloor \frac{n}{2} \rfloor +1$ соответственно. Установлено, что наибольшая сложность булевых функций от $n$ переменных при реализации схемами в этом базисе по порядку роста равна $n$.