|
This article is cited in 1 scientific paper (total in 1 paper)
Realization of Boolean Functions by Formulas in Continuous Bases Containing a Continuum of Constants
Ya. V. Vegner, S. B. Gashkov M. V. Lomonosov Moscow State University
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.
Received: 26.04.2009 Revised: 19.12.2010
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
Linking options:
https://www.mathnet.ru/eng/mzm7833https://doi.org/10.4213/mzm7833 https://www.mathnet.ru/eng/mzm/v92/i2/p181
|
Statistics & downloads: |
Abstract page: | 524 | Full-text PDF : | 193 | References: | 55 | First page: | 12 |
|