Abstract:
We consider generalizations of the concepts of a contact circuit and a parallel-serial contact circuit in the case when the variables assigned to contacts can accept not two as in a Boolean case, but a greater number of values. The conductivity of contacts as well as in a Boolean case remains two-valued (a contact either will close, or will break). We have obtained upper and lower bounds on the complexity of such circuits computing a function $f\colon\{0,1,\dots,q-1\}^n\to\{0,1\}$ which accepts the value 1 at a vector $(\delta_1,\dots,\delta_n)\in\{0,1,\dots,q-1\}^n$ if $\delta_1+\dots+\delta_n\neq0\pmod q$. Bibl. 9.
Keywords:Boolean function, contact circuit, complexity of circuits.