Abstract:
The complexity circuits of Boolean functions is studied in a basis consisting of all characteristic functions of antichains over the Boolean cube. It is established that the circuit complexity 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$.
Fulltext:
PDF file (274 kB)