Abstract:
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 finite.
In the paper the minimum number of non-monotone elements for an arbitrary
multi-valued logic function system $F$ is established.
It equals $\lceil\log_{u}(d(F)+1)\rceil - 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.
Keywords:combinational machine (logic circuits), circuits complexity, bases with zero weight elements, $k$-valued logic functions, inversion complexity, Markov's theorem, Shannon function.
Fulltext:
PDF file (144 kB)