Article collection "Mathematical Problems of Cybernetics" №19, Moscow, 2019
On a lower bound of elementary symmetric functions system implementation by switching circuits
We consider the problem of implementing elementary symmetric algebra of logic functions by switching circuits. In the present article we show that a switching circuit without parasite paths that implements the system of all elementary symmetric functions of n variables contains at least n(n+3)/2 switches.
elementary symmetric functions, switching circuits, complexity theory