Abstract:
For an arbitrary Boolean function of $n$ variables, we show how to construct formulas of complexity $O(2^{n/2})$ in the bases
$$
\{x-y,xy,|x|\} \cup [0,1],\qquad \{x-y,x*y,2x,|x|\} \cup [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.