CYBERNETICS AND CONTROL THEORY

V. N. GREBENSHCHIKOV

COALITIONS OF SYSTEMS OF EQUATIONS OF BOOLEAN ALGEBRA AND THEIR SOLUTION

(Presented by Academician A. N. Kolmogorov, 19 VII 1961)

The literature describes methods for solving equations of Boolean algebra with single-valued coefficients and unknown functions ((¹); (²), p. 230). In the present note we study the solution of equations whose coefficients are multivalued and possess a partially ordered set of simultaneously given Boolean forms. Such equations have not previously been studied, but they are of interest, since they occur, for example, in the synthesis of contact circuits with multivalued contact conductances by the method (³).

Consider a set of Boolean functions \(A\) satisfying the inequality

\[ \min A \leqslant A \leqslant \max A, \tag{1} \]

where \(\min A\) and \(\max A\) are certain boundary functions. We shall call this set a segment and denote it by \(A^*\). Consider a set of segments \(A^*_\alpha\) \((\alpha = 1,\ldots,h)\). Construct the totality of distinct sets of functions containing one arbitrary function from each segment. We shall call this totality a coalition of sets of functions and denote it by \([A^*_1,\ldots,A^*_h]^*\). If the coalition contains the maximum possible number of mutually distinct sets, we shall call it complete.

As is known ((¹), pp. 26 and 32; (²), p. 230), any system of inequalities and equations of Boolean algebra can be reduced to a single equation of the form

\[ \sum_{\alpha=1}^{2^n} A_\alpha \prod_{\beta=1}^{n} Y_\beta^{s_{\alpha\beta}} = 0, \tag{2} \]

where \(A_\alpha\) \((\alpha = 1,\ldots,2^n)\) are certain Boolean functions of the variables \(a,b,\ldots,f\); \(Y_\beta\) \((\beta = 1,\ldots,n)\) are unknown functions of the same variables; \(Y_\beta^0 = \overline{Y}_\beta\), \(Y_\beta^1 = Y_\beta\), and \(s_{\alpha\beta}\) \((\alpha = 1,\ldots,2^n;\ \beta = 1,\ldots,n)\) is a set of binary constants whose matrix has the form

\[ \left\| s_{\alpha\beta} \right\| = \left\| \begin{array}{cccc} 0 & \ldots & 0 & 0\\ 0 & \ldots & 0 & 1\\ \ldots & \ldots & \ldots & \ldots\\ 1 & \ldots & 1 & 1 \end{array} \right\|. \tag{3} \]

Suppose that each coefficient \(A_\alpha\) of equation (2) possesses a set of simultaneously given Boolean forms constituting the segment \(A^*_\alpha\). Consider a coalition of sets of the form \([A^*_1, A^*_2,\ldots,A^*_{2^n}]^*\). Substitute each

a tuple that belongs to the coalition into equation 2). The resulting collection of formulas will be called a coalition of equations, and we shall consider that it defines an equation with multivalued coefficients. We shall write the collection of formulas of the coalition, in abbreviated form, as

\[ \sum_{\alpha=1}^{2^n} A_\alpha^{*}\prod_{\beta=1}^{n}Y_\beta^{s_{\alpha\beta}}=0. \tag{4} \]

We shall call a coalition of equations complete if the corresponding coalition of tuples is complete. We shall consider only complete coalitions of equations.

We shall call a particular solution of equation (2) any set of functions \(Y_\beta\) \((\beta=1,\ldots,n)\) satisfying it. The general solution of this equation will be the collection of all its particular solutions. We shall call an equation solvable if it has at least one particular solution. A particular solution of the coalition of equations (4) will be any particular solution of any equation contained in it. The general solution of a coalition of equations will be the collection of the general solutions of all solvable equations contained in it. We shall call a coalition of equations solvable if it contains at least one solvable equation. The general solution of a coalition of equations will be called coalitionary if all tuples of functions \(Y_\beta\) \((\beta=1,\ldots,n)\) belonging to the general solution form a coalition. A coalitionary solution will be called complete if it forms a complete coalition of tuples.

Some properties of the general and particular solutions of the coalition of equations (4) are determined by the following theorems.

Theorem 1. The general solution of the coalition of equations (4) is equivalent to the general solution of the equation

\[ \sum_{\alpha=1}^{2^n}\min A_\alpha\prod_{\beta=1}^{n}Y_\beta^{s_{\alpha\beta}}=0. \tag{5} \]

Theorem 2 (solvability criterion). The coalition of equations (4) is solvable if and only if the relation

\[ \prod_{\alpha=1}^{2^n}\min A_\alpha=0 \tag{6} \]

holds.

Theorem 3. The general solution of equation (5) is equivalent to the general solution of the system of inequalities

\[ \sum_{\alpha=\chi}^{2^{\,n-\gamma}}\prod_{\delta=1}^{\,2^{\,n-\gamma}}\min A_{\alpha+\delta-1}\prod_{\beta=1}^{\gamma-1}Y_\beta^{s_{\alpha\beta}} \leq Y_\gamma \leq \prod_{\alpha=\lambda}\left(\sum_{\delta=1}^{\,2^{\,n-\gamma}}\overline{\min A_{\alpha+\delta-1}}+\sum_{\beta=1}^{\gamma-1}\overline{Y_\beta^{s_{\alpha\beta}}}\right), \tag{7} \]

\[ \gamma=1,\ldots,n;\qquad \varepsilon=1,\ldots,2^{\gamma-1};\qquad \chi=2^{\,n-\gamma}(2\varepsilon-2)+1; \]

\[ \lambda=2^{\,n-\gamma}(2\varepsilon-1)+1. \]

Theorem 4. The general solution of the coalition of equations (4) is coalitionary; its boundary functions are determined by the relations

\[ \min Y_\gamma=\prod_{\alpha=\chi}\min A_\alpha,\qquad \max Y_\gamma=\sum_{\alpha=\lambda}\overline{\min A_\alpha}, \tag{8} \]

\[ \gamma=1,\ldots,n;\qquad \varepsilon=1,\ldots,2^{\gamma-1};\qquad \eta=1,\ldots,2^{\,n-\gamma}; \]

\[ \chi=2^{\,n-\gamma}(2\varepsilon-2)+\eta;\qquad \lambda=2^{\,n-\gamma}(2\varepsilon-1)+\eta. \]

Theorem 5 (completeness criterion). The general solution of the coalition of equations (4) is complete if and only if the relations

\[ \min A_\rho \leqslant \sum_{\gamma=1}^{n}\prod_{\alpha=\chi}\min A_\alpha, \tag{9} \]

\[ \rho=1,\ldots,2^n;\qquad \varepsilon=1,\ldots,2^{\gamma-1};\qquad \eta=1,\ldots,2^{n-\gamma}; \]

\[ \chi=2^{\,n-\gamma}(2\varepsilon-1-S_{\rho\gamma})+\eta . \]

Theorem 6 (partial-completeness criterion). The general solution of the coalition of equations (4) contains a complete coalition of sets with boundary functions

\[ \min Y_\gamma=\sum_{\alpha=\chi}\min A_\alpha,\qquad \max Y_\gamma=\prod_{\alpha=\lambda}\overline{\min A_\alpha}, \tag{10} \]

\[ \gamma=1,\ldots,n;\qquad \varepsilon=1,\ldots,2^{\gamma-1};\qquad \eta=1,\ldots,2^{n-\gamma}; \]

\[ \chi=2^{\,n-\gamma}(2\varepsilon-2)+\eta;\qquad \lambda=2^{\,n-\gamma}(2\varepsilon-1)+\eta, \]

if and only if the relations

\[ \sum_{\alpha=\chi}\min A_\alpha \leqslant \prod_{\alpha=\lambda}\overline{\min A_\alpha}, \tag{11} \]

\[ \gamma=1,\ldots,n;\qquad \varepsilon=1,\ldots,2^{\gamma-1};\qquad \eta=1,\ldots,2^{n-\gamma}; \]

\[ \chi=2^{\,n-\gamma}(2\varepsilon-2)+\eta;\qquad \lambda=2^{\,n-\gamma}(2\varepsilon-1)+\eta . \]

If the coalition of equations (4) is solvable (the relations (6) are satisfied), then any of its partial solutions is obtained by means of formulas (7). These same formulas determine the general solution. Relations (8), (9), (10), (11) determine the basic properties of the general solution of the coalition.

Received
4 V 1961

REFERENCES

¹ L. Couturat, Algebra of Logic, Odessa, 1909.
² G. Birkhoff, Theory of Structures, Moscow, 1952.
³ V. N. Grebenshchikov. DAN, 119, No. 2, 278 (1958).