Abstract:
For an arbitrary Boolean function of n variables, we show how to construct formulas of complexity O(2n/2) in the bases
{x−y,xy,|x|}∪[0,1],{x−y,x∗y,2x,|x|}∪[0,1],
where x∗y=max(−1,min(1,x))max(−1,min(1,y)). The obtained estimates are, in general, order-sharp.
Keywords:
Boolean function, complexity of the realization of Boolean functions, Shannon function, Lipschitz condition, continuous basis, almost-finite basis.
Citation:
Ya. V. Vegner, S. B. Gashkov, “Realization of Boolean Functions by Formulas in Continuous Bases Containing a Continuum of Constants”, Mat. Zametki, 92:2 (2012), 181–191; Math. Notes, 92:2 (2012), 166–175