?
Сложность реализации симметрических булевых функций схемами в базисе антицепных функций
Дискретная математика. 2015. Т. 27. № 3. С. 95–107.
Podolskaya O.
Keywords: сложность булевых функций
Mikhailovich A., Kochergin V., XXI век: итоги прошлого и проблемы настоящего плюс 2017 № 4(38) С. 98–105
The problem of the effective realization of Boolean functions and multi-valued logic functions by circuits in some infinite bases is considered. The bases consist of all monotone functions and finite number of non-monotone functions. The measure of the realization efficiency is non-monotone complexity. That is the number of non-monotone elements in the circuit (we assume ...
Added: September 28, 2017
Podolskaya O., В кн.: Материалы XII Международного семинара "Дискретная математика и её приложения" имени академика О.Б. Лупанова (Москва, МГУ, 20-25 июня 2016г.).: М.: Изд-во механико-математического факультета МГУ, 2016. С. 150–152.
В работе изучается сложность реализации булевых функций схемами из функциональных элементов в двух бесконечных полных базисах. Первый базис состоит из линейных и антицепных функций от любого числа переменных. В этом базисе установлена верхняя оценка сложности реализации произвольной булевой функции от n переменных порядка (logn)*n^{1/2}. Также в этом базисе доказана нижняя оценка порядка n^{1/2} наибольшей сложности ...
Added: March 14, 2017
Podolskaya O., Вестник Московского университета. Серия 1: Математика. Механика 2016 № 2 С. 51–52
Изучается сложность реализации булевых функций схемами из функциональных элементов в базисе, состоящем из всех характеристических функций антицепей булева куба. Установлено, что сложность реализации функции четности от $n$ переменных есть $\lfloor \frac{n+1}{2} \rfloor,$ сложность ее отрицания равна сложности функции голосования от $n$ переменных и составляет $\lceil \frac{n+1}{2} \rceil$. ...
Added: March 14, 2017
Kochergin V., Mikhailovich A., Прикладная дискретная математика 2015 № 4 С. 24–31
Complexity of realization of Boolean functions and Boolean function systems over a basis which consist of all monotone functions and finite number of non-monotone funcitons is investigated. The weight of any monotone function from the basis equal 0. The weight of non-monotone function is positive. A. A. Markov studied special case of such basis. The ...
Added: December 8, 2015
A.V. Mikhailovich, V. V. Kochergin, / Series math "arxiv.org". 2015.
The minimum number on NOT gates in a Boolean circuits computing a Boolean function f is called inversion complexity of f. In 1957, A.A. Markov determined inversion complexity of every Boolean function. In the paper we consider circuits over arbitrary basis that consist of all monotone functions (with zero weight) and finite nonempty set of nonmonotone functions (with ...
Added: June 15, 2015