Complexity of implementation of Boolean functions by real-valued formulas. (English. Russian original) Zbl 1212.06032

Mosc. Univ. Math. Bull. 63, No. 2, 76-78 (2008); translation from Vestn. Mosk. Univ., Ser. I 2008, No. 2, 47-49 (2008).
The authors establish upper bounds for the complexity of the implementation of Boolean functions by formulas in bases consisting of a finite number of continuous real functions and a continuum of constants. For several bases the order of the upper bounds coincides with the order of the lower bounds.


06E30 Boolean functions
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
Full Text: DOI