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

Article

О сложности схем в базисах, содержащих монотонные элементы с нулевыми весами

Кочергин В. В., Михайлович А. В.

Complexity of realization of Boolean functions and Boolean function systems over a basis which consist of all monotone functions and finite number of non-monotone funcitons is investigated. The weight of any monotone function from the basis equal 0. The weight of non-monotone function is positive. A. A. Markov studied special case of such basis. The non-monotone part of the basis consist of the only negation function. He showed that the minimum number of negation elements which are needed to realize an arbitrary function f equal ]log2(d(f)+1)[. Here d(f) is the maximum number of value changes from 1 to 0 over all increasing chains of arguments tuples.mThe aim of this paper is to prove that the complexity of a boolean function f realization equal ρ]log2(d(f)+1)[-O(1), where ρ is the minimum weight of non-monotone basis elements. Similar generalization of classical Markov result concerning realization of boolean funciton systems was obtained.