О минимальном числе отрицаний при реализации систем функций многозначной логики
In this paper we consider the complexity of realization of k-valued logic functions by logic circuits over an infinite complete basis of special type. This basis contain all monotone functions with zero weight and non-monotone functions with non-zero weight. The problem of the complexity of a Boolean functions realization over basis containing all monotone functions and negation function has been completely solved by A. A. Markov. In 1957 he showed that the minimum number of NOT gates that is enough to realize any Boolean function f (the inversion complexity of the function f) equals log2(d(f)+1)[. Here d(f) is the maximum number of the function f values changes from grater to smaller over all increasing chains of tuples of variables values. In this paper the result of Markov is extended to the case of a k-valued logic function realization. We show that the minimum number of Post negations (i.e. functions of the form x+1 mod k) that is enough to realize an arbitrary function of k-valued logic equals ]log2(d(f)+1)[ and the minimum number of Lukasiewicz negation (i.e. functions of the form k-1-x) that is enough to realize an arbitrary k-valued logic function equals ]logk(d(f)+1)[. In addition, another classical result of Markov dealt with inversion complexity of a system of Boolean functions has been also extended to the k-valued logic functions case.