Realization of Boolean functions by combinational circuits embedded in the hypercube

In recent years, it has become popular to realize Boolean functions by combinational circuits. In many cases, the further use of the scheme constructed requires its geometric realization, i.e., a certain embedding in one or another specific geometric structure. The role of such structure is often played by the unit n-dimensional cube.In this paper, we consider quasihomeomorphic embeddings of combinational circuits in hypercubes such that the nodes of the scheme go into vertices of the hypercube and bundles of arcs go into similar bundles or the so-called transition trees of the hypercube having no common internal vertices.

Let B be a finite complete basis of functional elements and R _B(n) be the minimum dimension of a hypercube such that, for any function f(x ₁, …, x _n ) of Boolean logic, there is a certain scheme of functional elements in basis B realizing f(x ₁, …, x _n ) which can be quasihomeomorphically embedded in this cube. The main result of this work consists in derivation of the following estimates:

$n - \log \log (n) - c_B \leqslant R_B (n) \leqslant n - \log \log (n) + c'_B .$

Here, c _B and c′_B are basis-dependent constants.