# zbMATH — the first resource for mathematics

On formula complexity for products of Boolean functions. (Russian) Zbl 1009.68056
Let $$f(x_1,\dots,x_n)$$ and $$g(x_1,\dots,x_m)$$ be Boolean functions. A function $(f\otimes g)(x_1,\dots,x_{nm})= f\bigl(g(x_1,\dots,x_m),\dots,g(x_{(n-1)m+1},\dots,x_{nm})\bigr)$ is called a repetition-free product of Boolean functions. A criterion is given that makes it possible to check whether a sequence of products of Boolean functions can be computed with linear size formulas in a basis $$B$$.
##### MSC:
 68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) 94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
##### Keywords:
complexity; Boolean function; lower bound; basis; formula