  The minimum number of NOT gates in a logic circuit computing a Boolean
function is called the inversion complexity of the function. In 1957, A. A.
Markov determined the inversion complexity of every Boolean function and proved
that $\lceil\log_{2}(d(f)+1)\rceil$ NOT gates are necessary and sufficient to
compute any Boolean function $f$ (where $d(f)$ is the maximum number of value
changes from greater to smaller over all increasing chains of tuples of
variables values). This result is extended to $k$-valued functions computing in
this paper. Thereupon one can use monotone functions "for free" like in the
Boolean case. It is shown that the minimum sufficient number of non-monotone
gates for the realization of the arbitrary $k$-valued logic function $f$ is
equal to $\lceil\log_{2}(d(f)+1)\rceil$ if Post negation (function $x+1
\pmod{k}$) is used in NOT nodes and is also equal to
$\lceil\log_{k}(d(f)+1)\rceil$, if {\L}ukasiewicz negation (function $k-1-x$)
is used in NOT nodes. Similar extension for another classical result of A. A.
Markov for the inversion complexity of a system of Boolean functions to
$k$-valued logic functions has been obtained.
