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
*n*-variable majority function
which is

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