SOME QUESTIONS OF ANALYSIS AND SYNTHESIS OF THRESHOLD STRUCTURES

D. V. ANISIMOV, V. M. RAZIN

(Presented by the scientific seminar of the Department of Computer Engineering)

A threshold element is a device consisting of a summing unit with several inputs and one output to a discriminator, for which an element with a relay characteristic is most often used. The output of a threshold element takes the value “zero” if the weighted sum of the inputs is less than zero, and the value “one” otherwise and when the weighted sum is equal to zero, i.e.

\[ \operatorname{sgn}\sum_{i=1}^{n+1} a_i x_i = \begin{cases} 0, & \text{if } \displaystyle\sum_{i=1}^{n+1} a_i x_i < 0,\\[6pt] 1, & \text{if } \displaystyle\sum_{i=1}^{n+1} a_i x_i \ge 0, \end{cases} \tag{1} \]

where \(x_i\) is the \(i\)-th input, \(x_i \in \{0,1\}\);

\(a_i\) is the multiplicity (weight) of the \(i\)-th element;

\(n+1\) is the total number of inputs, including the threshold input.

For the weight coefficient of the threshold, when \(x_{n+1}=1\), there exists a notation \(T\), called the threshold. In this case

\[ y=\operatorname{sgn}\left[\sum_{i=1}^{n} a_i x_i - T\right]. \tag{2} \]

As is evident from (2), the function \(y\) takes two values, 0 or 1, in accordance with condition (1).

In this connection, the function \(\operatorname{sgn}\) can be identified with a Boolean function of \(n\) binary variables, also having the value 0 or 1, and then it makes sense to speak of representing a switching function by means of a threshold element. However, not every Boolean function can be realized by means of a single threshold element, whereas every threshold element realizes one or another function. A logical function realized by one threshold element (OTE) is called a threshold function, and functions realized by two, three, etc. threshold elements (TE) are called, respectively, two-threshold and three-threshold functions.

Thus, any Boolean function is realized by a network of TEs, which, however, follows from the fact that a TE realizes all functions included in a functionally complete set, namely:

linear switching functions

\[ (y = x_1 x_2 \ldots x_n,\quad y = x_1 \vee x_2 \vee \ldots \vee x_n); \]

a switching function that does not preserve zero \([y=\bar{x}]\);

a switching function that does not preserve one \([y=\bar{x}]\);

a nonmonotone switching function \([y=\bar{x}]\);

non-self-dual switching functions

\[ (y = x_1 x_2 \ldots x_n,\quad y = x_1 \vee x_2 \vee \ldots \vee x_n). \]

The problem of representing a Boolean function by a network consisting of TEs, as is known, is a synthesis problem, while the problem of analysis includes the task of determining the function realized by a particular network of known TEs.

Analysis of a Threshold Element by Means of Generating Functions

Let the function \(f(x_1, x_2, \ldots x_n)\) have the realization \(T(a_1, a_2, \ldots a_n)\), and suppose it is required to determine the form of the function, i.e., to solve the problem of analyzing a threshold element. We shall call \([a_1, a_2, \ldots a_n; T]\) the weight vector of the threshold element to which the function \((x_1, x_2, \ldots, x_n)\) corresponds. We shall write this correspondence symbolically as follows [1]

\[ [x_1, x_2, \ldots x_n] \to [a_1, a_2, \ldots a_n; T]. \tag{3} \]

As was indicated above, from a given weight vector one can completely determine the form of the function, which is most simply done by comparing sums of weight coefficients with the threshold value; for example, for the weight vector:

\[ [1, 1, 2, 3, 5; 5] \to x_1x_2x_4 \vee x_3x_4 \vee x_5 \]

\[ (a_5 = T;\quad a_3 + a_4 = T;\quad a_1 + a_2 + a_4 = T). \]

A more rigorous analysis can be carried out by means of generating functions borrowed from combinatorial analysis [2].

However, before introducing generating functions, it is necessary to become acquainted with symmetric Boolean functions and the properties of threshold functions.

Symmetric Boolean Functions [3]

A Boolean function of \(n\) variables \(x(x_1, x_2, \ldots x_n)\) is called symmetric if it is invariant under all permutations of the \(n\) variables, or of their negations. Thus the function \(x_1x_2 \vee x_1x_3 \vee x_2x_3\) is symmetric in the variables \(x_1, x_2, x_3\), since any permutation of these variables does not change the form of the function. Thus, a function is symmetric if and only if the condition

\[ f(x_1, x_2, \ldots x_n) = f(x_2, x_1, \ldots x_n) = \ldots = f(x_n, x_1, \ldots x_{n-1}). \tag{4} \]

is satisfied.

A symmetric function is specified by a set of integers \(A(a_1, a_2, \ldots a_x)\) \((X \le n)\), called the set of working numbers, such that the function takes the value one if and only if the number of variables having the value “1” is expressed by the working numbers appearing in the notation of the symmetric function. If the symmetric Boolean function of variables \(x\) with working numbers \(a_1, a_2, \ldots a_x\) \((a_1 < a_2 < \ldots < a_x)\) is denoted by the symbol \(S_{a_1,a_2,\ldots a_x}(x)\), then \(S_{1,3,5}(x_1, x_2, \ldots x_5)=1\) when one, three, and five arguments are equal to one.

By analogy with a symmetric elementary polynomial [3], we shall call symmetric Boolean functions that have as their working numbers the sequence \(k, k+1, \ldots, n-1, n\) \((0 \leq k \leq n)\) elementary. For such functions a special notation is introduced, relating them to algebraic functions—also symmetric—constructed from the sum of all possible combinations of \(n\) elements taken \(k\) at a time:

\[ S_{k,\, k+1, \ldots, n-1, n}(x_1, x_2, \ldots, x_n)=S_n^k. \tag{5} \]

It is very important to note that in the minimal disjunctive normal form (MDNF) of such a function there are no negations, while the conjunctive terms are formed by combinations of \(n\) elements taken \(k\) at a time. For example,

\[ S_{2,3,4}(x_1,x_2,x_3,x_4)=S_4^2=x_1x_2 \vee x_1x_3 \vee x_1x_4 \vee x_2x_3 \vee x_2x_4 \vee x_3x_4. \]

Logical operations on Boolean symmetric functions are very simple [5], since:
the disjunction of symmetric functions of the same variables gives a symmetric function of the same variables with the union of the set of working numbers;
conjunction gives the intersection of the set of working numbers;
negation gives the complement of the set of working numbers.

By virtue of the invariance of a symmetric function with respect to variables, it follows that the weight coefficients for all variables are identical and, for the minimal value, equal to one; moreover, an elementary symmetric function and its complement are threshold functions, which, incidentally, is a consequence of its properties of monotonicity and definiteness of the weight coefficients of the variables. This circumstance makes it possible to regard any threshold function as an elementary symmetric one, and in this case the weight coefficient will show how many times a given argument occurs. Suppose, as an example, that we have the function \(x_1x_2 \vee x_1x_3\) with weight vector \([2, 1, 1; 3]\). This function can be represented as

\[ S_4^3(x_1, x_1, x_2, x_3) = x_1x_1x_2 \vee x_1x_1x_3 \vee x_1x_2x_3 \vee x_1x_2x_3 = x_1x_2 \vee x_1x_3. \]

All symmetric functions, also by virtue of invariance, have weight coefficients with respect to the input variables equal to one; however, because of the discontinuity of the working numbers, the structure of the network becomes more complicated, since it is necessary to introduce a prohibition for the missing working numbers.

Properties of Threshold Functions

Let us proceed to consider properties of threshold functions that can be checked and proved quite simply.

If \(f(x_1,x_2,\ldots,x_n)\to (a_1,a_2,\ldots,a_n;T)\), then

property 1:

\[ f(x_1,x_2,\ldots,\bar{x}_i,\ldots,x_n)\to (a_1,a_2,\ldots,-a_i,\ldots,a_n;\,T-a_i); \tag{6} \]

property 2:

\[ \bar{f}(x_1,x_2,\ldots,x_n)\to (-a_1,-a_2,\ldots,-a_n;\,-T+1); \tag{7} \]

property 3:

\[ \bar{f}[\bar{x}_1,\bar{x}_2,\ldots,\bar{x}_n]\to \left[ a_1,a_2,\ldots,a_n;\,-T+1+\sum_{i=1}^{n}a_i \right]. \tag{8} \]

property 4:

\[ \begin{aligned} &f[x_1,x_2,\ldots,x_{j-1},0,x_{j+1},\ldots,x_n]\to\\ &\qquad\to [a_1,a_2,\ldots,a_{j-1},a_{j+1},\ldots,a_n;T]; \end{aligned} \tag{9a} \]

\[ \begin{aligned} &f[x_1,x_2,\ldots,x_{j-1},1,x_{j+1},\ldots,x_n]\to\\ &\qquad\to [a_1,a_2,\ldots,a_{j-1},a_{j+1},\ldots,a_n;T-a_j]; \end{aligned} \tag{9b} \]

property 5:

if

\[ \begin{gathered} f_1(x_1,x_2,\ldots,x_n)\to (a_1,a_2,\ldots,a_n;T_1),\ \text{and}\\ f_2(x_1,x_2,\ldots,x_n)\to (a_1,a_2,\ldots,a_n;T_2) \end{gathered} \]

and \(T_2>T_1\), then

\[ f_1(x_1,x_2,\ldots,x_n)\supseteq f_2(x_1,x_2,\ldots,x_n); \tag{10} \]

property 6:

if \(f[x_1,x_2,\ldots,x_n]\) is a threshold function, then

\[ f(0\to x_i,\ 1\to x_j)\leq f(1\to x_i,\ 0\to x_j)\quad \text{for } a_i\geq a_j, \tag{11a} \]

\[ f(0\to x_i,\ 1\to x_j)\geq f(1\to x_i,\ 0\to x_j)\quad \text{for } a_i\leq a_j. \tag{11b} \]

Here \(f(0\to A)\) and \(f(1\to A)\) are functions obtained from \(f(x)\) by assigning the variables belonging to the subset \(A\subseteq x\) the values 0 and 1, respectively;

property 7:

let \(x_i\) be the variable whose weight is maximal in the realization of \(f(x)\); then

\[ f(x_1,x_2,\ldots,x_n)=f(1\to x_i)x_i\vee f(0\to x_i); \]

property 8:

\[ f(1\to x_i)\geq f(0\to x_i), \tag{12} \]

if

\[ f_m(x_1,x_2,\ldots,x_m)\to [a_1,a_2,\ldots,a_m;T), \]

then

\[ \begin{aligned} f_n&=x_{m+1}\vee x_{m+2}\vee\ldots\vee x_n\vee f_m(x_1,x_2,\ldots,x_m)\to\\ &\qquad\to [T,T,T,\ldots,T,a_1,a_2,\ldots,a_m;T]; \end{aligned} \tag{13} \]

property 9:

if

\[ f_m(x_1,x_2,\ldots,x_m)\to (a_1,a_2,\ldots,a_m;T), \]

then

\[ \begin{aligned} f_n&\simeq x_{m+1}x_{m+2}\ldots x_n f_m(x_1,x_2,\ldots,x_m)\to\\ &\qquad\to [a_n,a_n,\ldots,a_n,a_1,a_2,\ldots,a_m;(n-m)a_n+T], \end{aligned} \tag{14} \]

where

\[ a_n=\sum_{i=1}^{m}a_i-T+1. \]

Analysis of threshold elements by means of generating functions

The properties of symmetric Boolean functions and the properties of threshold functions presented above can be used in constructing generating functions. As an example, consider the product

\[ (1\vee x_1t)(1\vee x_2t)(1\vee x_3t). \]

Multiplying out and arranging this product by powers of \(t\), we obtain

\[ 1\vee [x_1\vee x_2\vee x_3]t\vee [x_1x_2\vee x_1x_3\vee x_2x_3]t^2\vee x_1x_2x_3t^3. \]

As is easy to see, the brackets contain symmetric Boolean functions having identical weights of the variables \(x_1,x_2,x_3\) and different thresholds.

Here “1” has threshold equal to 0, the function \(x_1 \vee x_2 \vee x_3\) has threshold equal to 1, the function \(x_1x_2 \vee x_1x_2 \vee x_2x_3\) has threshold equal to 2, and, finally, the function \(x_1x_2x_3\) has threshold equal to 3 in their realization by a threshold element, i.e., their thresholds are equal to the exponent of \(t\). As is seen from the example given, with the same weight coefficients, but with different thresholds, the expansion yielded four functions, which are called isobaric threshold functions. In general, a family of threshold functions is called isobaric [5] if it can be realized by one threshold element whose weight coefficients of the \(n\)-inputs are constant, while the threshold value assumes as many different values as there are functions in the family, and is numerically determined by the sequence of natural numbers

\[ 0 \div \sum_{i=1}^{n} a_i . \]

It is clear from this definition how important the representation of threshold functions by generating functions is, since in this case, knowing the weight coefficients, one can determine the entire set of isobaric functions. The functions obtained in the expansion of the generating function with elementary symmetric functions of ordinary algebra are identical; in both cases the number of terms in each bracket is equal to the number of combinations of \(n\) elements taken \(k\) at a time \((n=0,1,2,3)\).

When arguments are repeated, the generating function can be obtained by replacing the former factors \((1 \vee x_k t)\) by factors of the form

\[ 1 \vee x_k t \vee x_k t^2 \vee \ldots \vee x_k t^{a_k} \quad (k=1,2\ldots). \tag{15} \]

In the general case, knowing the series of weight coefficients \(a_1,a_2,\ldots,a_n\) \((a_r>0)\), one can write the generating function in the following form:

\[ \underbrace{(1 \vee x_1 t \vee \ldots \vee x_1 t^{a_1})\ldots(1 \vee x_n t \vee \ldots \vee x_n t^{a_n})}_{n\text{-factors}}. \tag{16} \]

As an example, take the function \((x_1x_2 \vee x_1x_3)\to[2,1,1;3]\), for which, in accordance with (15), the generating function will have the form

\[ (1 \vee x_1 t \vee x_1 t^2)(1 \vee x_2t)(1 \vee x_3t)= \]

\[ =1 \vee (x_1 \vee x_2 \vee x_3)t \vee (x_1 \vee x_1x_2 \vee x_1x_3 \vee x_2x_3)t^2 \vee \]

\[ \vee (x_1x_2 \vee x_1x_3 \vee x_1x_2x_3)t^3 \vee x_1x_2x_3t^4 = \]

\[ =1 \vee (x_1 \vee x_2 \vee x_3)t \vee (x_1 \vee x_2x_3)t^2 \vee (x_1x_2 \vee x_3x_1)t^3 \vee x_1x_2x_3x_4t^4 . \]

As is seen, at \(t^3\) \((T=3)\) the Boolean function indeed appears in the required form.

Let us introduce generating functions for \(a_i<0\), using the properties presented above. As is seen from (6), the appearance of a negative weight coefficient decreases the threshold by an amount equal to \(a_i\). This circumstance can be reflected as follows: the generating function will have the form

\[ t^{-a_i} \vee \bar{x}_i t^{-a_i+1} \vee \ldots \vee \bar{x}_i t^{-1} \vee \bar{x}_i, \tag{17} \]

\[ (1 \vee xt \vee \ldots x_1t^{a_1})\ldots(t^{-a_i} \vee x_i t^{-a_i+1} \vee \ldots \vee x_i)(1 \vee x_n t \vee \ldots \vee x_n t^{a_n}). \tag{18} \]

Using property 2 (7), for the negation of a function we obtain a generating function of the form

\[ (t^{-a_1} \vee \bar{x}_1 t^{-a_1+1} \vee \ldots \vee \bar{x}_1)\ldots(t^{-a_n} \vee \bar{x}_n t^{-a_n+1} \vee \ldots \vee \bar{x}_n). \tag{19} \]

Example: To realize \([-2,-1,-1;-2]\) we have

\[ (t^{-2}\vee \bar{x}_{1},\, t^{-1}\vee \bar{x}_{1})(t^{-1}\vee \bar{x}_{2})(t^{-1}\vee \bar{x}_{3}) = t^{-4}\vee (\bar{x}_{1}\vee \bar{x}_{2}\vee \bar{x}_{3})t^{-3} \]
\[ {}\vee(\bar{x}_{1}\vee \bar{x}_{2}\bar{x}_{3})t^{-2} \vee(\bar{x}_{1}\bar{x}_{2}\vee \bar{x}_{1}\bar{x}_{3})t^{-1} \vee \bar{x}_{1}\bar{x}_{2}\bar{x}_{3}t^{0}. \]

For the self-dual function (8) we have the generating function in accordance with the positive coefficients by formula (15). As is seen from the example, the self-dual function occurs at \(t^{2}: x_{1}\vee x_{2}x_{3}\) (compare with \(x_{1}x_{2}\vee x_{1}x_{3}\)).

Generating functions with respect to properties 4–7 do not differ in form from (15). As for properties (8) and (9), in these cases it is necessary to add terms of the generating function in accordance with realizations (13), (14). Thus one may conclude that for \(a_i>0\) the Boolean function will contain \(x_i\) without negation, and for \(a_i<0\) the function will contain \(x_i\) with negation.

The analysis of threshold symmetric functions is carried out very simply. In this case, from the value of the threshold one immediately constructs a series of isobaric functions, which are elementary symmetric functions. For example:

\[ [1,1,1,1,1;2]\to f[x_{1},\ldots,x_{5}]. \]

A series of isobaric functions \(S^{0}_{5}, S^{1}_{5}, S^{3}_{5}, S^{4}_{5}, S^{5}_{5}\), where the threshold is indicated above.

Decomposition of a Multithreshold Function into Elementary Threshold Functions

Let us introduce the concept of a network of TEs. From various sources several variants of networks of TEs are known, but the network most optimal from the point of view of the minimum number of elements is presented in Fig. 1. Here the output TE combines both the inputs \(x(x_{1},x_{2},\ldots,x_{n})\) and the functional inputs \(f[f_{1}(x), f_{2}(x),\ldots,f_{m-1}(x)]\), with their weight coefficients.

Fig. 1.

In the particular case, a number of coefficients may be equal to zero; in this case part of the connections may be removed. We shall call the structure of the network shown in Fig. 1 maximally connected, and the TE standing at the output a TE with functional thresholds. In this case the synthesis problem consists in finding the weight coefficients for the input signals and for the functions

\[ f_{1}(x),\ f_{2}(x),\ldots,\ f_{m-1}(x). \]

As is seen, in this case the number of the function determines one-, two-, or \(m-1\)-threshold functions. The structure of such a network is described by the system:

\[ f_1=\operatorname{sgn}\left[\sum_{i=1}^{n} a_i x_i - T_1\right], \]

\[ f_2=\operatorname{sgn}\left[\sum_{i=1}^{n} a_{i_2}x_{i_2}+a_{(n+1)_2}f_1-T_2\right], \]

\[ \ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots \]

\[ f_m=\operatorname{sgn}\left[\sum_{i=1}^{n} a_{i_m}x_{i_m}\vee \sum_{j=1}^{m} f_j(x)a_{(n+j)_m}-T_m\right]. \tag{20} \]

For the further exposition we introduce the notation [5] \(f_1, f_2, \ldots, f_m\)—the output functions of threshold elements \(1,2,\ldots,m\), respectively, which are threshold functions both of the input variables and of the functional input signals.

\(f_{2\mid 1}\)—the threshold function realized by the element under the condition that the input function arriving from the output of the element is equal to zero;

\(f_{2/1}\)—the same, under the condition \(f_1=1\);

\(f_{3/\overline{12}}\)—the threshold function realized by the element under the condition
\[ f_1=f_2=0; \]

\(f_{3/12}\)—the same, under the condition \(f_1=1,\ f_2=0\);

\(f_{3/\overline{1}2}\)—the same, under the condition \(f_1=0,\ f_2=1\);

\(f_{3/12}\)—the same, under the condition \(f_1=1,\ f_2=1\).

It is known that every Boolean function admits the decomposition

\[ f_n=f(x_1,x_2,\ldots,x_{j-1},x_j,x_{j+1},\ldots,x_n)= \]

\[ = x_j f(x_1,x_2,\ldots -x_{j-1},1,x_{j+1},\ldots,x_n)\vee \]

\[ \vee \overline{x}_j f(x_1,x_2,\ldots x_{j-1},0,x_{j+1}\ldots x_n) = x_j f_1\vee \overline{x}_j f_2 . \tag{21} \]

If \(f_n\) is a threshold function, then

\[ f_n=x_j=f_1\vee f_2, \tag{21a} \]

or

\[ f_n=\overline{x}_j=f\vee f_1 \tag{21б} \]

in the case of positive or negative weight coefficients, respectively. As is seen from (21), the functions \(f_1\) and \(f_2\) do not depend on \(x_i\).

A threshold function for a network, as we have already shown, must be represented as a function depending not only on the arguments, but also on the preceding functional outputs, which in turn depend on other functions, etc. Thus, for example, a network consisting of three threshold elements has three functions at its output.

The last function is the output one. The function \(f_1\) is a single-threshold function and depends only on the arguments \(\{x\}\); the function \(f_2\) is a two-threshold function and depends both on the arguments and on the function \(f_1\); the function \(f_3\) is a three-threshold function and already depends on the arguments and the functions \(f_1\) and \(f_2\). In the general case, for a three-threshold system the equation of the output function will be

\[ f_3=f\{x,f_1(x),f_2[x,f_1(x)]\}. \]

To obtain a general decomposition formula, every output function of a threshold network is represented as a single-threshold function in the arguments listed above. The decomposition begins

\[ f_2=f[x,f_1(x)]=f_1(x)f(x,1)\vee \overline{f}_1(x)f(x,0)= \]

\[ =f_1(x)f_{2/1}\vee \overline{f}_1(x)f_{2/\overline{1}} = f_1f_{2/1}\vee \overline{f}_1f_{2/\overline{1}} . \]

and is continued until the function \(f_{m;1\ldots}\) contains within it no functional argument. For \(m=3\),

\[ \begin{aligned} f_3&=f_1(x)f_2[x,f_1(x)]f_3(x,1,1)\vee\\ &\vee \bar f_1(x)f_2[x,f_1(x)]f_3(x,0,1)\vee\\ &\vee \bar f_1(x)\bar f_2[x,f_1(x)]f_3(x,1,0)\vee\\ &\vee \bar f_1(x)\bar f_2[x,f_1(x)]f_3(x,1,1)=\\ &=f_1f_{2;1}f_{3;12}\vee \bar f_1f_{2;\bar 1}f_{3;\bar 1 2}\vee f_1\bar f_{2;1}f_{3;1\bar 2}\vee \bar f_1\bar f_{2;\bar 1}f_{3;\bar 1\bar 2}. \end{aligned} \]

Carrying out analogous expansions, we obtain the general formula for \(m=m\)

\[ \begin{aligned} f_m&=f_1f_{2;1}\ldots f_{m-1/12\ldots m-2}f_{m/12\ldots m-1}\vee\\ &\vee \bar f_1f_{2;\bar 1}\ldots f_{m-1/12\ldots m-2}f_{m/\bar 1 2\ldots m-1}\vee\\ &\vee f_1f_{2;1}\ldots \bar f_{m-1/12\ldots m-2}f_{m/12\ldots \overline{m-1}}\vee\\ &\vee \bar f_1f_{2;\bar 1}\ldots \bar f_{m-1/12\ldots \overline{m-2}}f_{m/\bar 1 2\ldots \overline{m-1}}. \end{aligned} \tag{22} \]

Formula (22) can be simplified under the condition that all coefficients of the functional thresholds are either positive or negative. For positive weights of the functional inputs,

\[ f_{m/12\ldots m-1}\supset \frac{f_{m/12\ldots \overline{m-1}}}{f_{m/\bar 1 2\ldots m-1}} \supset \ldots \supset \frac{f_{m/\bar 1 2\ldots \overline{m-1}}}{f_{m/\bar 1 2\ldots m-1}} \supset f_{m/\bar 1 2\ldots \overline{m-1}} \]

\[ \overline{\phantom{f_{m/12\ldots m-1}\supset \frac{f_{m/12\ldots \overline{m-1}}}{f_{m/\bar 1 2\ldots m-1}} \supset \ldots \supset \frac{f_{m/\bar 1 2\ldots \overline{m-1}}}{f_{m/\bar 1 2\ldots m-1}} \supset f_{m/\bar 1 2\ldots \overline{m-1}}}} \]

\[ f_{2;1}\supset f_{2;\bar 1} \]

and

\[ \begin{aligned} f_m&=f_1f_{2;1}\ldots f_{m-1/12\ldots m-2}f_{m/12\ldots m-1}\vee\\ &\vee f_{2;\bar 1}\ldots f_{m-\bar 1/\bar 1 2\ldots m-1 2}f_{m/\bar 1 2\ldots m-1}\vee\\ &\vee f_1f_{m/1\bar 2\ldots \overline{m-1}}\vee f_{m/\bar 1 2\ldots \overline{m-1}}. \end{aligned} \tag{22a} \]

Analogous reasoning leads to the expansion in conjunctive form

\[ \begin{aligned} f_m={}&(f_1\vee f_{2;\bar 1}\vee \ldots \vee f_{m-1/\bar 1 2\ldots \overline{m-2}}\vee f_{m/\bar 1 2\ldots \overline{m-1}})\wedge\\ &\wedge(\bar f_1\vee f_{2;1}\vee \ldots \vee f_{m-1/12\ldots \overline{m-2}}\vee f_{m/12\ldots \overline{m-1}})\wedge\\ &\wedge(f_1\vee \bar f_{2;\bar 1}\vee \ldots \vee f_{m-1/\bar 1 2\ldots m-2}\vee f_{m/\bar 1 2\ldots m-1})\wedge\\ &\wedge(\bar f_1\vee \bar f_{2;1}\vee \ldots \vee \bar f_{m-1/12\ldots m-2}\vee f_{m/12\ldots m-1}). \end{aligned} \tag{23} \]

Further simplification can be obtained if connections not extending to neighboring elements are eliminated, for example \(a_{13}=0\), but \(a_{23}\ne 0\), etc. In this case, for \(m=3\), \(f_3=(f_1f_{2;1}\vee f_{2;\bar 1})f_{3;2}\vee f_{3;\bar 2}=f_2f_{3;2}\vee f_{3;\bar 2}\), i.e., the problem reduces to the search for, as it were, a two-threshold function, and the chain of searches terminates when a function with a smaller index having a threshold realization is obtained,

\[ f_m=f_{m-1}f_{m/m-1}\vee f_{m;\overline{m-1}} \]

\[ f_{m-1}=f_{m-2}f_{m-1/m-2}\vee f_{m-1;\overline{m-2}} \]

\[ \cdots \]

\[ f_2=f_1f_{2;1}\vee f_{2;\bar 1}. \tag{24} \]

For the further exposition of the synthesis of logic circuits on threshold elements, it is necessary to introduce the basic rules for carrying out the operation

over them [5], by means of which Boolean functions can be represented by threshold elements: a disjunction of \(m\)-Boolean threshold functions can be realized by no more than \(m\)-threshold logical elements, with
\(a_{(m-1)m}=T_m\) (where \(a_{(m-1)m}\) is the weight coefficient for the functional input from the neighboring threshold element).

A conjunction of \(m\)-Boolean threshold functions can be realized by no more than \(m-1\) threshold elements with

\[ a_{(m-1)m}>\sum_{i=1}^{n} a_{im} \quad\text{and}\quad T'_m=T_m+a_{(m-1)m}. \]

In accordance with (24) and the rules set forth above, the synthesis of threshold networks must be carried out according to a scheme that is somewhat simplified in comparison with [5].

1. Represent the Boolean function \(f_m\) in minimal disjunctive form (not necessarily irredundant).

2. Choose as the function \(f_{m;\overline{m-1}}\) one of the disjunctions covering the possibly minimal number of constituents, which will always be threshold.

3. From the remaining prime implicants, separate out the threshold function \(f_{m;m-1}\) and the isobaric function \(f_{m;\overline{m-1}}\), for which purpose the remaining function is represented in conjunctive form. At this stage the function \(f_{m-1}\) is also separated out.

4. The decomposition of the function \(f_{m-1}\) is carried out analogously. The chain of searches continues until the product of two threshold functions \(f_{2;1} f_1\) is obtained.

5. The weight coefficients are determined in the realization of the functions
   \(f_{m;m-1}, f_{m-1;m-2}, \ldots, f_{2;1}, f_1\), and then in the realization of the functions
   \(f_{m;\overline{m-1}}, f_{m-1;\overline{m-2}}, \ldots, f_{2;\overline{1}}\). The weights of the functional inputs are determined as

\[ a_{(m-1)m}=T_{m;\overline{m-1}}-T_{m;m-1}. \]

Example.

\[ \begin{aligned} f_m={}&x_1\bar{x}_2x_3\bar{x}_4x_5 \vee x_1\bar{x}_2\bar{x}_3x_4x_5 \vee x_1\bar{x}_2\bar{x}_3x_4\bar{x}_5 \vee{}\\ &\vee \bar{x}_1x_2\bar{x}_3\bar{x}_4x_5 \vee \bar{x}_1\bar{x}_2x_3x_4x_5 \vee \bar{x}_1x_2x_3x_4x_5 \vee{}\\ &\vee x_1x_2x_3x_4x_5 \vee x_1x_2\bar{x}_3x_4\bar{x}_5 \vee x_1x_2x_3\bar{x}_4x_5 \vee{}\\ &\vee x_1x_2x_3x_4x_5; \end{aligned} \]

\[ \begin{aligned} 1.\quad f_m(x_1,x_2,x_3,x_4,x_5)={}& \bar{x}_1x_2\bar{x}_3\bar{x}_4x_5 \vee x_1x_3\bar{x}_4x_5 \vee{}\\ &\vee x_1\bar{x}_3x_4x_5 \vee x_1x_3\bar{x}_4x_5 \vee \bar{x}_1x_3x_4x_5 \vee x_2x_3x_4x_5; \end{aligned} \]

\[ 2.\quad f_{m;\overline{m-1}}(x_1,x_2,x_3,x_4,x_5) = \bar{x}_1x_2\bar{x}_3\bar{x}_4x_5; \]

\[ \begin{aligned} 3.\quad f_{m;m-1}f_{m-1}={}& (x_1\vee x_3)(x_1\vee x_4)(x_1\vee x_5)(x_3\vee x_4\vee x_5)\wedge{}\\ &\wedge(\bar{x}_3\vee x_4\vee \bar{x}_5)(\bar{x}_3\vee \bar{x}_4\vee x_5) (\bar{x}_1\vee x_2\vee \bar{x}_3\vee \bar{x}_4)\\ &(\bar{x}_1\vee x_2\vee \bar{x}_4\vee \bar{x}_5) \wedge(\bar{x}_1\vee x_2\vee \bar{x}_3\vee \bar{x}_5); \end{aligned} \]

\[ \begin{aligned} f_{m;m-1}(\bar{x}_1,x_2,\bar{x}_3,\bar{x}_4,\bar{x}_5) ={}& (\bar{x}_1\vee x_2\vee \bar{x}_3\vee \bar{x}_4)\\ &(\bar{x}_1\vee x_2\vee \bar{x}_4\vee \bar{x}_5) \wedge(\bar{x}_1\vee x_2\vee \bar{x}_3\vee \bar{x}_5); \end{aligned} \]

\[ \begin{aligned} f_{m-1}(x_1,x_2,x_3,x_4,x_5) ={}&(x_1\vee x_3)(x_1\vee x_4)(x_1\vee x_5)\wedge{}\\ &\wedge(x_3\vee x_4\vee x_5)(x_3\vee \bar{x}_4\vee \bar{x}_5) (\bar{x}_3\vee x_4\vee \bar{x}_5)(\bar{x}_3\vee \bar{x}_4\vee x_5)\\ ={}&x_1\bar{x}_3x_4\bar{x}_5 \vee x_1\bar{x}_3\bar{x}_4x_5 \vee x_1x_3\bar{x}_4x_5 \vee x_3\vee x_5; \end{aligned} \]

\[ 4.\quad f_{m-1;\overline{m-2}}(x_1,\bar{x}_3,x_4,\bar{x}_5) = x_1\bar{x}_3x_4\bar{x}_5 \]

\[ \begin{aligned} f_{m-1,m-2} f_{m-2} f_{m-2} &= (x_1 \vee x_3)(x_1 \vee x_4)(x_1 \vee x_5)(x_3 \vee x_5)\ \wedge \\ &\quad \wedge\ (x_3 \vee \bar{x}_4)(\bar{x}_4 \vee x_5)(\bar{x}_3 \vee x_4 \vee \bar{x}_5); \end{aligned} \]

\[ f_{m-1\mid m-2}(x_1,\bar{x}_3,x_4,\bar{x}_5) = (\bar{x}_3 \vee x_4 \vee \bar{x}_5)x_1 \vee x_4) = (x_4 \vee x_1\bar{x}_3 \vee x_1\bar{x}_5); \]

\[ \begin{aligned} f_{m-2}(x_1,x_3,\bar{x}_4,x_5) &= (x_1 \vee x_3)(x_1 \vee x_5)(x_3 \vee x_5)(x_3 \vee \bar{x}_4)\ \wedge \\ &\quad \wedge\ (\bar{x}_4 \wedge x_5) = x_1x_3\bar{x}_4 \vee x_1\bar{x}_4x_5 \vee x_3x_5. \end{aligned} \]

1. \[ f_{m\mid m-1}=f_{3\mid 2}(\bar{x}_1,x_2,\bar{x}_3,\bar{x}_4,\bar{x}_5)\to[2,2,1,1,1;2]; \]

\[ f_{m\mid \overline{m-1}}=f_{3\mid \bar{2}}(\bar{x}_1,x_2,\bar{x}_3,\bar{x}_4,\bar{x}_5)\to[2,2,1,1,1;7]; \]

\[ T_{3\mid 2}=2;\quad T_{3\mid \bar{2}}=7;\quad a_{23}=T_{3\mid \bar{2}}-T_{3\mid 2}=7-2=5; \]

\[ f_{m-1\mid m-2}=f_{2\mid 1}(x_1,\bar{x}_3,x_4,\bar{x}_5)\to[1,1,2,1;2]; \]

\[ f_{m-1\mid \overline{m-2}}=f_{2\mid \bar{1}}(x_1,\bar{x}_3,x_4,\bar{x}_5)\to[1,1,2,1;5] \]

\[ T_{2\mid 1}=2;\quad T_{2\mid \bar{1}}=5;\quad a_{12}=3; \]

\[ f_{m-2}=f_1(x_1,x_3,\bar{x}_4,x_5)\to[1,2,1,2;4]\qquad T_1=4 \]

The realization of the given function is shown in Fig. 2.

Fig. 2.

In conclusion, it should be noted that the realization of Boolean functions by threshold networks according to the synthesis method described also makes it possible to significantly reduce the number of required elements in comparison with realization in a Boolean basis.

REFERENCES

1. E. A. Butakov. On the systematics of threshold functions. Seminar “Questions of the Theory of Mathematical Electronic Digital Machines.” Kiev, 1965.

2. J. Riordan. An Introduction to Combinatorial Analysis. Moscow, Foreign Literature Publishing House, 1963.

3. G. N. Povarov. On group invariance of Boolean functions. Collection: Applications of Logic in Science and Technology, Publishing House of the Academy of Sciences of the USSR, pp. 263–340, 1959.

4. A. K. Kurosh. Course of Higher Algebra. Fizmatgiz, 1963.

5. K. Shannon. Symbolic analysis of relay and switching circuits. In: Works on Information Theory and Cybernetics. Moscow, Foreign Literature Publishing House, 1963.