zbMATH — the first resource for mathematics

Realization of Boolean functions by formulas in continuous bases containing a continuum of constants. (English. Russian original) Zbl 1283.06025
Math. Notes 92, No. 2, 166-175 (2012); translation from Mat. Zametki 92, No. 2, 181-191 (2012).
Summary: For an arbitrary Boolean function of \( n \) variables, we show how to construct formulas of complexity \( O (2^{n/2})\) in the bases \[ \left\{ {x - y,xy,\left| x \right|} \right\}\cup {\left[ {0,1} \right], \quad } \left\{ {x - y,x*y,2x,\left| x \right|} \right\}\cup {\left[ {0,1} \right],} \] where \( x * y = \max(-1, \min(1, x ))\max(-1, \min(1, y ))\). The obtained estimates are, in general, order-sharp.
06E30 Boolean functions
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
Full Text: DOI
[1] S. B. Gashkov, ”The complexity of realization of Boolean functions by systems of functional elements and formulas in bases whose elements realize continuous functions,” Probl. Kibern. 37, 57–118 (1980). · Zbl 0482.94035
[2] G. Turán and F. Vatan, ”On the computation of Boolean functions by analog circuits of bounded fan-in,” J. Comput. System Sci. 54(1), 199–212 (1997). · Zbl 0869.68050
[3] S. B. Gashkov and Ya. V. Vegner, ”Complexity of realization of Boolean functions by real-valued formulas,” Vestnik Moskov. Univ. Ser. I Mat. Mekh., No. 2, 47–49 (2008) [Moscow Univ. Math. Bull. 63 (2), 76–78 (2008)]. · Zbl 1212.06032
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.