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

Article

Asymptotics of growth for non-monotone complexity of multi-valued logic function systems

Siberian Electronic Mathematical Reports. 2017. Vol. 14. P. 1100-1107.
Mikhailovich A.V., Kochergin V.V.

The problem of the complexity of multi-valued logic functions realization by circuits in a special basis is investigated. This kind of basis consists of elements of two types. The 􏰌first type of elements are monotone functions with zero weight. The second type of elements are non-monotone elements with unit weight. The non-empty set of elements of this type is fi􏰌nite.

In the paper the minimum number of non-monotone elements for an arbitrary multi-valued logic function system F is established. It equals ⌈logu(d(F)+1)⌉−O(1). Here d(F) is the maximum number of the value decrease over all increasing chains of tuples of variable values for at least one function from system F; u is the maximum (over all non-monotone basis functions and all increasing chains of tuples of variable values) length of subsequence such that the values of the function decrease over these subsequences.