CYBERNETICS AND CONTROL THEORY

V. I. REZNIK

ON THE REALIZATION OF MONOTONE FUNCTIONS BY CIRCUITS OF FUNCTIONAL ELEMENTS

(Presented by Academician M. V. Keldysh on 8 VIII 1960)

In the synthesis of circuits from given elements, the main problem is the construction of the simplest circuits realizing the functions of a certain class. We shall consider the class of monotone functions \((^4)\). The degree of complexity of the circuits constructed in this class can be estimated by means of the function \(L_M(n)\)—the least number such that any monotone function of \(n\) arguments can be realized by a circuit containing no more than \(L_M(n)\) elements. As elements we shall take functional elements realizing conjunction and disjunction. Definitions of functional elements and of circuits of functional elements are given in \((^1)\).

Using E. N. Gilbert’s results on the number of monotone functions of \(n\) arguments \((^5)\) and O. B. Lupanov’s theorem on obtaining lower bounds for the complexity of circuits \((^2)\), it is not difficult to show that \(L_M(n) \geq c_0 2^n/n^{3/2}\).

An upper bound for \(L_M(n)\) can be obtained by a method analogous to Shannon’s method. Shannon’s method is based on the expansion of a function

\[ f(x_1,\ldots,x_n)= \bigvee_{\text{over all sets } \sigma_{k+1},\ldots,\sigma_n} x_{k+1}^{\sigma_{k+1}}\cdots x_n^{\sigma_n} f(x_1,\ldots,x_k,\sigma_{k+1},\ldots,\sigma_n). \]

Circuits constructed by Shannon’s method consist of two parts: a circuit A, realizing all conjunctions \(x_{k+1}^{\sigma_{k+1}}\cdots x_n^{\sigma_n}\), and a circuit B, realizing all functions of the arguments \(x_1,\ldots,x_k\); moreover, these parts are the same for all circuits realizing functions of \(n\) arguments, but for different functions they are connected with one another in different ways. When Shannon’s method is applied to the realization of monotone functions, instead of circuit B one may use a circuit B1, realizing only all monotone functions of the variables \(x_1,\ldots,x_k\). The complexity of the circuit is connected with the number of monotone functions of \(k\) variables.

The application of Shannon’s method to monotone functions makes it possible to obtain the estimate
\[ L_M(n) \leq c_1 2^n \lg \lg n / n\sqrt{\lg n}. \]
Here, however, no use is made of the fact that from a monotone function \(f(x_1,\ldots,x_n)\), by substitutions of constants, not all monotone functions of the arguments \(x_1,\ldots,x_k\) can be obtained. The method proposed in this paper makes it possible, to a certain extent, to take this circumstance into account and to lower the upper bound to
\[ L_M(n) \leq c_2 2^n \lg n / n^{2*}. \]

The circuits here consist of three parts: a circuit \(A^1\), realizing the positive conjunctions of the variables \(x_{k+1},\ldots,x_n\); a circuit \(B^1\), realizing monotone functions of the variables \(x_1,\ldots,x_l\); and a circuit C, realizing (using the results delivered by the circuit \(B^1\)) monotone functions of the variables \(x_1,\ldots,x_k\) that are obtained from the original function as a result of substitutions of constants. The circuits \(A^1\) and \(B^1\) are common for all monotone functions of the arguments \(x_1,\ldots,x_n\), while the circuits C are different for different functions. Owing to this, it is possible to carry the decomposition of functions further than in the case

* This estimate, obtained in the basis \(\vee, \&\), does not change, up to a constant factor, when passing to any other basis.

Shannon’s method (to functions of \(l\) variables). In an analogous way the same upper estimate for \(L_M(n)\) can be obtained for other circuits with oriented elements (for example, for relay-contact circuits).

Extending the method to the case of \(\pi\)-circuits (formulas) makes it possible to obtain, for the corresponding complexity function, the estimate

\[ L_M^\pi(n) \lesssim c_3 \frac{2^n}{n^{1/4}}\lg n \quad \left(\text{the lower estimate } L_M^\pi(n) \gtrsim c_4 \frac{2^n}{n^{1/2}\lg n}\right). \]

Let us call an expression of the form \((x_1 \vee \sigma_1)\cdots(x_n \vee \sigma_n)\), for an arbitrary fixed set \(\sigma_1,\ldots,\sigma_n\), an elementary conjunction. Any monotone function \(f(x_1,\ldots,x_n)\) of \(n\) arguments can be represented in disjunctive normal form not containing negations \((^4)\). Let the length \(N(f)\) of a monotone function \(f(x_1,\ldots,x_n)\) be the number of terms in the corresponding DNF. \(N(f)\le 2^n/\sqrt n\) \((n>2)\) (see \((^5)\)). Denote \(2^n/N(f)=\psi(f)\) (hereafter, instead of \(\psi(f)\), we shall write \(\psi\)). In the paper two cases will be considered separately:

1) \(N(f)\ge 2^{\,n-\sqrt n}\) (this corresponds to \(\lg\psi\le \sqrt n\)); 2) \(N(f)<2^{\,n-\sqrt n}\) (this corresponds to \(\lg\psi>\sqrt n\)).

Suppose we have a monotone function \(f(x_1,\ldots,x_n)\) given in DNF. Expand this function with respect to the last \(n-k\) arguments:

\[ f(x_1,\ldots,x_n)= \]

\[ = \bigvee_{\text{over all sets } \sigma_{k+1},\ldots,\sigma_n} (x_{k+1}\vee\sigma_{k+1})\cdots(x_n\vee\sigma_n)\cdot f_{\sigma_{k+1},\ldots,\sigma_n}(x_1,\ldots,x_k). \tag{1} \]

The expansion is carried out as follows. We fix a set \(\sigma_{k+1},\ldots,\sigma_n\), write the elementary conjunction \((x_{k+1}\vee\sigma_{k+1})\cdots(x_n\vee\sigma_n)\) corresponding to this set; then we turn to the DNF corresponding to the function \(f(x_1,\ldots,x_n)\), and select in it all terms that contain, as a part, the conjunction of variables \((x_{k+1}\vee\sigma_{k+1})\cdots(x_n\vee\sigma_n)\) and contain no other variables from the set \(\{x_{k+1},\ldots,x_n\}\); we factor this conjunction out of the selected terms, and the expression that remains in parentheses forms a function of \(k\) arguments and is denoted by \(f_{\sigma_{k+1},\ldots,\sigma_n}(x_1,\ldots,x_k)\).

If in the initial DNF there is no term containing the elementary conjunction \((x_{k+1}\vee\sigma'_{k+1})\cdots(x_n\vee\sigma'_n)\), where \(\sigma'_{k+1},\ldots,\sigma'_n\) is some fixed set of zeros and ones, then we shall assume

\[ f_{\sigma'_{k+1},\ldots,\sigma'_n}(x_1,\ldots,x_k)\equiv 0. \]

If there is exactly one such term and in it variables from the set \(\{x_1,\ldots,x_k\}\) are absent, then we shall set

\[ f_{\sigma'_{k+1},\ldots,\sigma'_n}(x_1,\ldots,x_k)\equiv 1. \]

All distinct functions of \(k\) arguments obtained in (1), not identically equal to zero, may be regarded as written in DNF. To a monotone function \(f(x_1,\ldots,x_n)\) of \(n\) arguments assign the number \(B(k,f)\)—the number of distinct functions of \(k\) arguments \(x_1,\ldots,x_k\) that are formed by the expansion (1), and let \(r_i(f)\) denote the number of distinct functions of \(k\) arguments \(x_1,\ldots,x_k\) obtained in (1) and having \(i\) terms in their DNF \((0\le i\le s\), where \(s=\max N(f_{\sigma_{k+1},\ldots,\sigma_n}(x_1,\ldots,x_k))\) over all functions of \(k\) arguments obtained in (1)). Obviously, the equalities hold:

\[ \sum_{i=0}^{s} r_i(f)=B(k,f),\qquad \sum_{i=0}^{s} i r_i(f)=N(f). \tag{2} \]

Let us have a sequence \(\alpha=\{a_1,a_2,\ldots\}\) of nonnegative numbers. Denote

\[ S_\alpha(m)=\sum_{i=0}^{m} i a_i; \]

\(p_\alpha(N)\) is the minimal \(m\) for which

\[ S_\alpha(m)\ge N(f) \]

(for convenience of notation we shall henceforth put \(N(f)=N\)). Obviously, in any sum \(S_\alpha(p_\alpha(N))\) one can find a number \(a'_{p_\alpha(N)}\ne 0\),

that \(\alpha'_{p_\alpha(N)} \leqslant \alpha_{p_\alpha(N)}\) and

\[ S_\alpha(p_\alpha(N))-(\alpha_{p_\alpha(N)}-\alpha'_{p_\alpha(N)})\,p_\alpha(N)=N. \tag{3} \]

Lemma 1. Let there exist two sequences of nonnegative numbers \(\alpha=\{\alpha_1,\alpha_2,\ldots\}\), \(\beta=\{\beta_1,\beta_2,\ldots\}\) such that (3) is satisfied for them and \(\alpha_i\geqslant \beta_i\); then: 1) \(p_\alpha(N)\leqslant p_\beta(N)\); 2)

\[ \sum_{i=0}^{p_\alpha(N)-1}\alpha_i+\alpha'_{p_\alpha(N)} \geqslant \sum_{i=0}^{p_\beta(N)-1}\beta_i+\beta'_{p_\beta(N)}. \]

Lemma 2. \(B(k,f)\leqslant \displaystyle\sum_{i=0}^{p_\alpha(N)-1} C_{2^k}^{\,i}+T\), where \(T'\) and \(p_\alpha(N)\) are such that

\[ N=\sum_{i=0}^{p_\alpha(N)-1} iC_{2^k}^{\,i}+p_\alpha(N)T'. \]

Denote

\[ \sum_{i=0}^{p_\alpha(N)-1} C_{2^k}^{\,i}+T'=R(k,N). \]

Lemma 3. \(R(k+1,N)\leqslant R(k,N)\) for \(N<2^{k-1}\cdot 2^{2k}\).

Lemma 4. If \(k=[\lg \psi+\lg n-\lg\lg\psi]-4\), \(\psi\to\infty\) \((n\to\infty)\), then for sufficiently large \(n\) the relation

\[ C_{2k}^{[\,n/\lg\psi\,]}<2^{(1-2/\lg\psi)n} \]

holds.

Lemma 5. If \(\lg\psi\leqslant\sqrt n\), \(k=[\lg n+\lg\psi-\lg\lg\psi]-4\), \(\psi\to\infty\) \((n\to\infty)\), then

\[ R(k,N)\leqslant \frac{2^n}{n\psi}\lg\psi . \]

For the proof it suffices in the expression

\[ R(k,N)=\sum_{i=0}^{t-1} C_{2^k}^{\,i} + \sum_{i=t}^{p_\alpha(N)-1} C_{2^k}^{\,i} +T' < (t-1)C_{2^k}^{\,t-1} + \sum_{i=t}^{p_\alpha(N)-1} C_{2^k}^{\,i} +T' \]

to put \(t=\left[\dfrac{n}{\lg\psi}\right]+1\) and, using (3), to show that

\[ T'+\sum_{i=t}^{p_\alpha(N)-1} C_{2^k}^{\,i} \leqslant \frac{2^n}{\psi(t)} < \frac{2^n\lg\psi}{n\psi}; \]

further, from Lemma 4 it follows that

\[ \frac{(t-1)C_{2^k}^{\,t-1}}{2^n\lg\psi/n\psi}\to 0 \quad\text{as } n\to\infty. \]

Therefore

\[ R(k,N)\leqslant \frac{2^n}{\psi n}\lg\psi . \]

Fig. 1

Denote by \(L_M(n,\psi)\) the least number such that a monotone function \(f(x_1,\ldots,x_n)\) of length \(2^n/\psi\) \((\lg\psi\leqslant\sqrt n,\ \psi\to\infty\ (n\to\infty))\) can be realized by a circuit containing no more than \(L_M(n,\psi)\) functional elements.

Lemma 6. \(L_M(n,\psi)\leqslant a2^n\lg\psi/n\psi\), where \(a\) is a certain constant.

Proof. Consider an arbitrary monotone function of length \(2^n/\psi\). It can be represented in the form (1). We shall construct a circuit realizing the function \(f(x_1,\ldots,x_n)\) from separate blocks (Fig. 1), each of which will be constructed from functional elements realizing conjunction and disjunction. We give a description of these blocks.

1. Block \(B'\) has \(l=[\lg n]\) inputs \(x_1,\ldots,x_l\) and is a universal multi-output network realizing all monotone functions of \(l\) arguments; moreover, its complexity does not exceed \(C_5\cdot l^{C_1[l/2]}\).* (3).

2. Block \(C\) realizes the distinct functions of \(k\) arguments obtained in (2) (different from constants) by a method analogous to the method of G. N. Povarov

* By the complexity of a circuit we mean the number of functional elements.

(6). Let these functions be

\[ \{f_1, f_2, \ldots, f_{B(k,f)}\}. \tag{4} \]

Since these functions are obtained by the decomposition (1) of the function \(f(x_1,\ldots,x_n)\), it follows, by Lemma 2, that \(B(k,f) \leq R(k,N)\). Apply to each function \(f_i(x_1,\ldots,x_k)\) from the system (4) the decomposition (1) with respect to the last argument \(x_k\):

\[ f_i(x_1,\ldots,x_k)=x_k\cdot f'_i(x_1,\ldots,x_{k-1})\vee f_i(x_1,\ldots,x_{k-1},0) \]

\[ (1\leq i\leq B(k,f)). \]

As a result, we select a system of distinct functions of \(k-1\) arguments:

\[ \{f^*_1,f^*_2,\ldots,f^*_{B(k-1,f)}\}. \tag{5} \]

Obviously, the system (6) can also be obtained by decomposing the function \(f(x_1,\ldots,x_n)\) with respect to \(n-k+1\) arguments. Therefore
\[ B(k-1,f)\leq R(k-1,N). \]
Continuing these decompositions until a system of distinct functions of \(l+1\) arguments is obtained, the following inequalities hold:
\[ B(i,f)\leq R(i,N), \quad l+1\leq i\leq k. \]
Since \(l=[\lg n]\) and Lemma 3 is applicable, we have
\[ R(k,N)\geq R(k-1,N)\geq \cdots \geq R(l+1,N). \]
The number of obtained systems of distinct functions is \(k-l\); therefore the complexity of block \(C\) does not exceed
\[ R(k,N)\cdot (k-l)\cdot a, \]
where \(a\) is a constant.

1. The block \(A'\) has inputs \(x_{k+1},\ldots,x_n\) and realizes conjunctions of the form
   \[ (x_{k+1}\vee \sigma_{k+1})\cdots(x_n\vee \sigma_n) \]
   \[ ((\sigma_{k+1},\ldots,\sigma_n)\ne(1,\ldots,1)). \]
   The complexity of block \(A'\) does not exceed \(2^{\,n-k}\).

2. The block \(D\) realizes the function \(f(x_1,\ldots,x_n)\) from the functions realized by the blocks \(A'\) and \(C\). The complexity of block \(D\) does not exceed \(2\cdot 2^{\,n-k}\). Hence it follows that the complexity of a circuit realizing an arbitrary monotone function \(f(x_1,\ldots,x_n)\) of length
   \[ N=\frac{2^n}{\psi}\quad (\psi\leq 2^{\sqrt n}) \]
   does not exceed
   \[ a\cdot R(k,N)\cdot(k-l)+3\cdot 2^{\,n-k}+C_5\cdot l^{C^{[l/2]}}. \]

Put
\[ k=[\lg n+\lg\psi-\lg\lg\psi]-4,\qquad l=[\lg n]. \]
Then \(k-l<\lg\psi\), and, by Lemma 5,
\[ R(k,N)\preccurlyeq \frac{2^n}{n\psi}\lg\psi \]
and
\[ L_M(n,\psi)\preccurlyeq a\frac{2^n}{n\psi}(\lg\psi)^2 +3\cdot 2^5\cdot\frac{2^n}{n\psi}\lg\psi +C_5\cdot l^{C^{[l/2]}}. \]
It is easy to verify that
\[ \frac{C_5\cdot l^{C^{[l/2]}}}{2^n \lg^2\psi/n^{3/2}}\to 0 \quad\text{as } n\to\infty. \]
Therefore, finally, we have
\[ L_M(n,\psi)\preccurlyeq a\frac{2^n}{n\psi}\lg^2\psi. \]

Theorem.
\[ L_M(n)\preccurlyeq b\frac{2^n}{n^{3/2}}\lg^2 n. \]

Proof. 1) Let
\[ N(f)\geq 2^{\,n-\sqrt n}. \]
Then, by Lemma 6,
\[ L_M(n,\psi)\preccurlyeq a\frac{2^n}{n\psi}\lg^2\psi \]
and, taking into account that \(\psi\geq \sqrt n\) (see (5)), we have
\[ L_M(n,\psi)\preccurlyeq b\frac{2^n}{n^{3/2}}\lg^2 n. \]

2) Let
\[ N(f)<2^{\,n-\sqrt n}. \]
The realization of the function \(f\) is carried out by its DNF. The complexity of the corresponding circuit does not exceed
\[ n\cdot 2^{\,n-\sqrt n}. \]
From 1) and 2) it follows that
\[ L_M(n)\preccurlyeq b\frac{2^n}{n^{3/2}}\lg^2 n. \]

The author expresses gratitude to his supervisor O. B. Lupanov for his attention to the work.

Received
2 VIII 1960

CITED LITERATURE

¹ O. B. Lupanov, Izv. Vyssh. Uchebn. Zaved., Radiofizika, No. 1, 120 (1958).
² O. B. Lupanov, Tr. Mat. Inst. im. V. A. Steklova AN SSSR, 51, 158 (1958).
³ S. V. Yablonskii, UMN, 12, No. 6 (1957).
⁴ S. V. Yablonskii, Tr. Mat. Inst. im. V. A. Steklova AN SSSR, 51, 5 (1958).
⁵ E. N. Gilbert, J. Math. and Phys., 33, No. 1, 57 (1954).
⁶ G. N. Povarov, DAN, 100, No. 5, 909 (1955).