Improvement of Nonmonotone Complexity Estimates of $k$-Valued Logic Functions

The problem of determining the nonmonotone complexity of the implementation of $k$-valued logic functions by logic circuits in bases consisting of all monotone (with respect to the standard order) functions and finitely many nonmonotone functions is investigated. In calculating the complexity measure under examination only those elements of the circuit which are assigned nonmonotone basis functions are taken into account. The nonmonotone complexity of an arbitrary $k$-valued logic function is determined with high accuracy, namely, upper and lower bounds which differ by a constant not exceeding $3 \log_2 k+4$ are found.