Abstract:
We study the complexity of the realization of Boolean functions and multi-valued logic functions by circuits in infinite complete bases containing all monotone functions and finitely many nonmonotone functions. We consider both classical measure of complexity which corresponds to the total number of elements in the circuit and nonmonotone complexity that indicates the number of non-monotone elements of the circuit. The paper reviews our results that extend Markov's theorem of inversion complexity of Boolean function as well as contains new results concerning non-monotone complexity and similar problems.