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

Article

On complexity of multi-valued logic functions over one infinite basis

Journal of Applied and Industrial Mathematics. 2018. Vol. 12. No. 1. P. 40-58.
Kochergin V.V., Mikhailovich A.V.

The complexity of realization of k-valued logic functions by circuits in a special infinite basis is under study. This basis consists of Post negation (i.e. function x+1(mod k)) and all monotone functions. The complexity of the circuit is the total number of elements of this circuit. For an arbitrary function f, we find the lower and upper bounds of complexity, which differ from one another at most by 1. The complexity has the form 3log_3 (d(f)+1)+O(1), here d(f) is the maximum number of the value decrease of the value of f taken over all increasing chains of tuples of variable values. We find the exact value of the corresponding Shannon function which characterizes the complexity of the most complex function of a given number of variables.