• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Working paper

Inversion complexity of functions of multi-valued logic

Mikhailovich A. V., Kochergin V. V.
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 one over all increasing chains of tuples of variables values). This result is extended on k-valued functions computing in the paper. Thereupon one can use monotone functions ``for free'' like in Boolean case. It is shown that the minimal sufficient for a realization of the arbitrary k-valued logic function f number of non-monotone gates is equal to [log2(d(f)+1)], if Post negation is used  in NOT nodes  and is also equal to [logk(d(f)+1)], if {\L}ukasiewicz negation is used in NOT nodes. Similar extension for another classical result of A. A. Markov for the inversion complexity of system of Boolean functions to k-valued logic functions has been obtained.