УДК 519.7

Сложность линейных функций и функции голосования в базисе антицепных функций / О. В. Подольская. // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2016. № 2. С. 51-52.

Изучается сложность реализации булевых функций схемами из функциональных элементов в базисе, состоящем из всех характеристических функций антицепей булева куба. Установлено, что сложность реализации функции четности от n переменных есть \left\lfloor \frac{n+1}{2} \right\rfloor, сложность ее отрицания равна сложности функции голосования от n переменных и составляет \left\lceil \frac{n+1}{2} \right\rceil.

Ключевые слова: антицепная функция, сложность схем, функция четности, функция голосования.

Библиогр. 5.

К оглавлению номера  Go!