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

Working paper

Some Extension of Inversion Complexity of Boolean Functions

A.V. Mikhailovich, V. V. Kochergin.
The minimum number on NOT gates in a Boolean circuits computing a Boolean function f is called inversion complexity of f. In 1957, A.A. Markov determined inversion complexity of every Boolean function. In the paper we consider circuits over arbitrary basis that consist of all monotone functions (with zero weight) and finite nonempty set of nonmonotone functions (with unit weight). Minimal sufficient number of nonmonotone elements for arbitrary Boolean function has been found. Also similar extends of a classical result of A.A. Markov for inversion complexity of system of Boolean functions has been obtained.