RUS  ENG
Full version
JOURNALS // Matematicheskie Zametki // Archive

Mat. Zametki, 2012 Volume 92, Issue 2, Pages 181–191 (Mi mzm7833)

This article is cited 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.

UDC: 512.563

Received: 26.04.2009
Revised: 19.12.2010

DOI: 10.4213/mzm7833


 English version:
Mathematical Notes, 2012, 92:2, 166–175

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2026