Complexity of Linear and Majority Functions in the Basis of Antichain Functions / O. V. Podolskaya. // Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika. 2016. № 2. P. 51-52 [Moscow Univ. Math. Bulletin. Vol. 72, N 2, 2017. P. 82-83].

The complexity of realization of Boolean functions by circuits of functional elements in the basis consisting of all characteristic functions of antichains over a Boolean cube is studied. It is proved that the complexity of realization of an n-variable parity function is \left\lfloor \frac{n+1}{2} \right\rfloor and the complexity of its negation equals the complexity of the n-variable majority function which is \left\lceil \frac{n+1}{2} \right\rceil .

Key words: antichain function, circuit complexity, parity function, majority function.