2015/10/20 by Kochergin, Vadim V., Mikhailovich, Anna V.
#Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1510.05942
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 \lceillog2(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 \lceillog2(d(f)+1)\rceil if Post negation (function x+1 \pmodk) is used in NOT nodes and is also equal to \lceillogk(d(f)+1)\rceil, if Ł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.