Reports of the Academy of Sciences of the USSR
1964. Volume 154, No. 4

MATHEMATICS

E. I. NECHIPORUK

ON THE SYNTHESIS OF CIRCUITS FROM THRESHOLD ELEMENTS

(Presented by Academician P. S. Novikov on 2 X 1963)

1°. Let us consider the realization of Boolean functions by circuits in a basis consisting of all possible threshold elements \((^1)\), to each of which is assigned a weight equal to one. The Shannon function \(L(n)\) for this basis is the minimum number of threshold elements by means of which every Boolean function of \(n\) arguments can be realized.

Theorem.
\[ 2\left(\frac{2^n}{n}\right)^{1/2}\leqslant L(n)\leqslant 2\sqrt{2}\left(\frac{2^n}{n}\right)^{1/2}{}^{*}. \]

We give the proof of the lower estimate.

2°. We shall consider Euclidean space \(\mathfrak A^h\) of vectors of dimension \(h\). The linear hull of a nonempty set \(R\) in \(\mathfrak A^h\) is the set of all vectors representable by sums \(\sum_j c_j\tilde a^j\), where
\[ \sum_j c_j=1 \]
and \(\tilde a^j\in R\) for every \(j\); the linear hull of the empty set is called the empty set. The dimension of a set is the dimension of its linear hull; the dimension of the set \(R\) is denoted by \(d(R)\). A basis of a set \(R\) is any system of \(d(R)+1\) vectors of this set having dimension \(d(R)\). The distance between vectors \(\tilde a,\tilde b\) is denoted by \(|\tilde a-\tilde b|\). Let \(\tilde a=\{a_i\}_1^h,\ \tilde b=\{b_i\}_1^h\); we write \(\tilde a\leqslant \tilde b\) if \(a_i\leqslant b_i\) for every \(i\); we write \(\tilde a<\tilde b\) if \(\tilde a\leqslant\tilde b\) and \(a_i<b_i\) for some \(i\). We say that the vectors \(\tilde a,\tilde b\) are incomparable if \(\tilde a\nleqslant\tilde b\) and \(\tilde b\nleqslant\tilde a\). A vector \(\tilde a\) is called positive if \(\tilde 0<\tilde a\) (by \(\tilde 0\) and \(\tilde 1\) we denote the vectors all of whose components are zeros and ones, respectively).

We shall consider hyperplanes in \(\mathfrak A^h\) of dimension \(h-1\). A hyperplane is called positive if it intersects every coordinate axis and the corresponding intersection vectors are positive.

Lemma 1. Let \(U\) be a positive hyperplane. Then: 1) if \(\tilde a\in U,\ \tilde a^0<\tilde a<\tilde a^1\), then the vectors \(\tilde a^0,\tilde a^1\) lie on different sides of the hyperplane \(U\); 2) if \(\tilde a^1,\tilde a^2\in U,\ \tilde a^1\ne\tilde a^2\), then the vectors \(\tilde a^1,\tilde a^2\) are incomparable.

We number the sides of every hyperplane by the numbers \(0,1\); then every hyperplane \(U\) determines a decomposition of the space \(\mathfrak A^h\):
\[ \mathfrak A^h=\mathfrak A_0^h\cup U\cup\mathfrak A_1^h, \]
where \(\mathfrak A_0^h,\mathfrak A_1^h\) are open half-spaces adjacent to the correspondingly numbered sides of the hyperplane. Let \((R_0,R_1)\) be an ordered pair of sets in \(\mathfrak A^h\). We say that the hyperplane \(U\) separates the pair \((R_0,R_1)\) if \(R_0\subset\mathfrak A_0^h,\ R_1\subset U\cup\mathfrak A_1^h\); we say that the pair \((R_0,R_1)\) is separable if there exists a hyperplane separating it.

3°. Let
\[ \tilde r(\tilde z)=(r_1(\tilde z),\ldots,r_h(\tilde z)) \]
be a vector of arbitrary Boolean functions of the arguments \(\tilde z=(z_1,\ldots,z_m)\), and let \(R\) be the set of Boo—

\[ {}^{*}\ \text{It follows from the theorem that the estimate of V. I. Varshavskii } L(n)\leqslant n+1\ ({}^{2-5}) \text{ is erroneous.} \]

Boolean vectors from \(\mathfrak A^n\), run through by the vector \(\tilde z(\tilde z)\), when the vector \(\tilde z\) runs through the set of all Boolean vectors of dimension \(m\). Denote by \(N(\tilde r(\tilde z))\) the number of distinct functions \(X(\tilde z)=P(\tilde r(\tilde z))\), for a fixed vector \(\tilde r(\tilde z)\) and an arbitrarily varying threshold function \(P\) of \(h\) arguments. Put \(N(m,h)=\max N(\tilde r(\tilde z))\), where the maximum is taken over all possible vectors \(\tilde r(\tilde z)\) for fixed \(m\) and \(h\).

Lemma 2. \(N(m,h)\leq 2+2^h C_{2m+1}^{h}\).

Proof. For a fixed vector \(\tilde r(\tilde z)\) there exists a one-to-one correspondence between the functions \(X(\tilde z)\) and all possible partitions of the set \(R\) into an ordered pair \((R_0,R_1)\) of separable sets. Let us estimate the number of such pairs. Exclude the two cases when one of the sets of the pair is empty. Associate arbitrarily with each pair a hyperplane separating it; here it may be assumed that every hyperplane intersects every coordinate axis and contains no Boolean vector. Denote the set of these hyperplanes by \(\mathfrak U\). Denote by \(\varepsilon(U,\tilde a)\) the distance between the hyperplane \(U\) and the vector \(\tilde a\), and by \(\delta_i(U)\) the \(i\)-th (i.e., nonzero) component of the vector of intersection of the hyperplane \(U\) with the \(i\)-th coordinate axis. Put

\[ \varepsilon=\frac12 \min_{U,\tilde a}\varepsilon(U,\tilde a),\qquad \delta=2\max_{U,i}|\delta_i(U)|, \tag{1} \]

where \(U\in\mathfrak U\) and \(\tilde a\) is an arbitrarily varying Boolean vector.

Divide the set \(\mathfrak U\) into \(2^h\) groups \(\mathfrak U_{\tilde u}\): \(U\in\mathfrak U_{\tilde u}\) if \((\operatorname{sign}\delta_1(U),\ldots,\operatorname{sign}\delta_h(U))=\tilde u\). We shall give a general estimate for the number of hyperplanes in each group.

Consider the group \(\mathfrak U_{\tilde 1}\). For each nonzero vector \(\tilde a\) from \(R\) choose arbitrary positive vectors \(\tilde b^0(\tilde a)\), \(\tilde b^1(\tilde a)\) such that \(\tilde b^0(\tilde a)<\tilde a<\tilde b^1(\tilde a)\), \(|\tilde b^0(\tilde a)-\tilde a|=|\tilde b^1(\tilde a)-\tilde a|=\varepsilon\). On the \(i\)-th coordinate axis choose positive vectors \(\tilde e_\varepsilon^i,\tilde e_\delta^i\) at distances \(\varepsilon,\delta\) from the vector \(\tilde 0\). Form the set

\[ A=\bigcup_{(\tilde a\in R,\ \tilde a\ne 0)} \bigl(\tilde b^0(\tilde a)\cup \tilde b^1(\tilde a)\bigr) \cup \bigcup_{1\leq i\leq h} \bigl(\tilde e_\varepsilon^i\cup \tilde e_\delta^i\bigr). \]

Call standard any hyperplane containing a basis in \(A\). Associate with every hyperplane \(U\) from \(\mathfrak U_1\) a standard hyperplane \(V\) separating the same pair \((R_0,R_1)\) that the hyperplane \(U\) separates.

The hyperplane \(V\) is obtained from the hyperplane \(U\) by a continuous displacement; denote the displaced hyperplane by \(W\), with the hyperplanes \(U\) and \(V\) being respectively its initial and final positions. Denote by \(\tilde w^i\) the vector of intersection of the hyperplane \(W\) with the \(i\)-th coordinate axis. The displacement is carried out so that all vectors from the set \(A\) that have entered the hyperplane \(W\) at any moment of the displacement remain in it until the end. Call special the initial moment and those moments of the displacement at which new vectors from \(A\) enter \(W\). Number the special moments in their order of occurrence by the numbers \(t=0,1,2,\ldots\). The displacement ends at the first special moment at which \(d(W\cap A)=h-1\). If at the \(t\)-th special moment \(d(W\cap A)<h-1\), then the set \(W\cap A\) is supplemented inside \(W\) arbitrarily to a set of dimension \(h-2\), which remains fixed and lies in \(W\) until the next, \((t+1)\)-st, special moment. Denote this set by \(\mathcal A_t\). Since \(d(\mathcal A_t)=h-2\), there exists a coordinate axis with number \(i(t)\),

which does not intersect the linear hull of the set \(\mathcal A_t\). The displacement of \(W\) between the \(t\)-th and \((t+1)\)-st special moments is determined by the displacement of the vector \(\widetilde w^{\,i(t)}\) in the direction of the vector \(\widetilde e_{\delta}^{\,i(t)}\).

The hyperplane \(W\) remains positive throughout the entire displacement. The opposite is possible only in cases where some vector \(\widetilde w^{\,i}\) goes to \(+\infty\) or passes through the vector \(\widetilde 0\). Both cases, however, are excluded, since, by (1), every vector \(\widetilde w^{\,i}\) is enclosed between the vectors \(\widetilde e_{\delta}^{\,i}\), \(\widetilde e_{\delta}^{\,i}\). Further, at no moment of the displacement does any vector from \(R\) enter \(W\). Indeed, by the definition of \(\varepsilon\), the hyperplane \(U\) separates none of the pairs
\[ (\widetilde b^{\beta}(\widetilde a),\widetilde a),\quad (\widetilde a,\widetilde b^{\beta}(\widetilde a)) \]
for any nonzero vector \(\widetilde a\) from \(R\) and \(\beta=0,1\). Therefore, if at a moment \(\tau\) a vector \(\widetilde a\) from \(R\) were to enter \(W\), then earlier one of the vectors \(\widetilde b^{0}(\widetilde a)\) or \(\widetilde b^{1}(\widetilde a)\) would have entered \(W\) (Lemma 1,1), and at the moment \(\tau\) both of these vectors would be contained in \(W\); then at that moment the hyperplane \(W\) would not be positive (Lemma 1,2). It follows that the hyperplane \(V\) separates the same pair that the hyperplane \(U\) separates.

Since the set \(A\) contains no more than \(2^{m+1}+2h\) vectors and the basis of every hyperplane contains \(h\) vectors, for the number of hyperplanes in \(\mathfrak U_{\widetilde 1}\) we obtain the estimate
\[ C_{2^{m+1}+2h}^{h}. \]
The assertion of the lemma follows from the fact that all the groups \(\mathfrak U_{\widetilde u}\) are “mirror-similar” in the sense of the derivation of this estimate. The lemma is proved.

Let \(N(m)\) denote the number of distinct threshold functions of \(m\) arguments.

Corollary. \(\lg_{2} N(m)\leq m^{2}\).

4°. Lemma 3. \(L(n)\leq 2^{n}\).

The synthesis method giving this estimate consists in simulating the method of synthesizing contact-valve circuits \({}^{(6)}\).

Lemma 4. \(2\left(\dfrac{2^{n}}{n}\right)^{1/2}\leq L(n)\).

Proof. We shall assume that in the circuits each element has, among its other inputs, \(n\) inputs to which the arguments \(x_{1},\ldots,x_{n}\) are applied, and also that the outputs of all preceding elements are connected to the inputs of each element. With such connections, all possible circuits with a given number of elements can be obtained by varying only the coefficients of the threshold elements, since, when the coefficients are zero in the linear form describing the threshold function, the dependence of the output of the threshold element on the corresponding inputs is eliminated. Denote by \(S(n,h_n)\) the number of functions of the arguments \(x_{1},\ldots,x_{n}\) that can be realized by circuits of \(h_n\) threshold elements. Let
\[ \tfrac12 L(n)\leq h_n\leq L(n). \tag{2} \]

By Lemma 2,
\[ S(n,h_n)\leq \prod_{1\leq j\leq h_n} N(n,n+j-1) \leq \prod_{1\leq j\leq h_n} \{2+[2(2^{n+1}+2(n+j-1))]^{\,n+j-1}\}, \]

and, as \(n\to\infty\), by (2) and Lemma 3,
\[ \lg_{2} S(n,h_n)\leq n h_n(n+h_n). \]

Hence, by virtue of the equality \(\lg_{2} S(n,L(n))=2^{n}\), we have
\[ \left(\frac{2^{n}}{n}\right)^{1/2}\leq L(n). \tag{3} \]

Let us now refine this estimate. Put \(h_n^*=\left[\dfrac{2^{n/2}}{n}\right]\). Then

\[ \lg_2 S(n,h_n)\leq \sum_{1\leq j<h_n^*}\lg_2 N(n,n+j-1)+ \sum_{h_n^*+1\leq j<h_n}\lg_2 N(n,n+j-1)\leq \]

\[ \leq nh_n^*(n+h_n^*)+ \sum_{h_n^*+1\leq j<h_n} j\,\frac n2 \leq \frac{nh_n^2}{4} \]

(by Stirling’s formula, by virtue of (2), (3), and Lemmas 2 and 3). Hence, as above, the assertion of the lemma follows.

Leningrad State University
named after A. A. Zhdanov

Received
21 IX 1963

REFERENCES

¹ S. Muroga, I. Toda, S. Tokasu, J. Franklin Inst., 271, 5, 376 (1961).
² V. I. Varshavskii, DAN, 139, No. 5, 1071 (1961).
³ V. I. Varshavskii, DAN, 139, No. 6, 1325 (1961).
⁴ V. I. Varshavskii, Collection Questions of the Theory of Mathematical Machines, vol. 2, Moscow, 1962, p. 52.
⁵ V. I. Varshavskii, T. N. Semenova, Collection Principles of the Construction of Self-Learning Systems, Kiev, 1962, p. 27.
⁶ O. B. Lupanov, DAN, 111, No. 6, 1171 (1956).