Точное значение немонотонной сложности булевых функций
A problem of complexity of Boolean functions realization over infinite complete bases of special type is studied. These bases contain all monotone functions with zero weight and finite number of non-monotone functions with unit weight. Exhaustive description of Boolean realization over basis that consists of all monotone functions and one non-monotone function negation has been obtained by Markov. The minimal sufficient number of negations for arbitrary Boolean function f realization (i.e. inversion complexity of the function f) equals ⌈log2(d(f)+1)⌉, where d(f) is the maximal number of function value changes from 1 to 0 over all increasing chains of tuples of variables values. In this paper the result above is generalized to the arbitrary basis of this type. It is shown that the minimal sucient for arbitrary Boolean function f realization number of non-monotone functions equals ⌈log2(d(f)/D(B) + 1)⌉. Here D(B) is the maximum d(ω) over all non-monotone functions ω from the basis B.