CYBERNETICS AND THE THEORY OF CONTROL

A. D. TALANTSEV

ON THE ALGEBRA OF POTENTIAL-PULSE OBJECTS

(Presented by Academician V. A. Trapeznikov, 12 IV 1961)

1. In the logical investigation of various kinds of objects, one is usually interested in a discrete set of states characteristic of them. We shall confine ourselves here to considering objects for each of which no more than two states are distinguished (usually denoted by 1 and 0). We shall assume that information about the behavior of such objects in time is expressed in the form of quantized signals, a typical example of which is shown in Fig. 1a. The positive ordinate of the graph represents state 1, the negative ordinate state 0. This figure presents all the characteristic features of the behavior of an object in the small, i.e., in a neighborhood of an arbitrary instant of time. The behavior of an object similar to its behavior at the instant of time $t_1$ and denoted by $1_1$ will be called a positive potential. The behavior of an object similar to its behavior at the instant of time $t_2$ and denoted by $0_1$ will be called a negative impulse. The behavior of an object similar to its behavior at the instant of time $t_3$ and denoted by $\Delta_1$ will be called a positive transition. The behavior of an object similar to its behavior at the instant of time $t_4$ and denoted by $0_0$ will be called a negative potential. The behavior of an object similar to its behavior at the instant of time $t_5$ and denoted by $1_0$ will be called a positive impulse. The behavior of an object similar to its behavior at the instant of time $t_6$ and denoted by $\Delta_0$ will be called a negative transition. Impulses and transitions will be called events of the object. We shall consider potentials and events to be values of a certain logical variable, which it assumes as time passes. There are six values, forming the alphabet $\{1_1\; 0_0\; 1_0\; 0_1\; \Delta_1\; \Delta_0\}$. A variable taking values from this alphabet will be called a potential-pulse logical variable. Objects described by variables of this kind will be called potential-pulse objects.

Fig. 1

We assume that potentials and events postulate the following rules of behavior of a potential-pulse object in the small.

1.1. If at the instant of time $t$ the object is in potential $1_1$, then on a time interval containing the instant $t$ and not smaller than some fixed interval $q$, the object is also in potential $1_1$.

1.2. If at the instant of time $t$ the object is in potential $0_0$, then on an interval containing the instant $t$ and not smaller than $q$, the object is also in potential $0_0$.

1.3. If at time \(t\) the event \(1_0\) occurred, then on the intervals \((t-q,t)\) and \((t,t+q)\) the object is in the potential \(0_0\).

1.4. If at time \(t\) the event \(0_1\) occurred, then on the intervals \((t-q,t)\) and \((t,t+q)\) the object is in the potential \(1_1\).

1.5. If at time \(t\) the event \(\Delta_1\) occurred, then on the interval \((t-q,t)\) the object is in the potential \(1_1\), and on the interval \((t,t+q)\)—in the potential \(0_0\).

1.6. If at time \(t\) the event \(\Delta_0\) occurred, then on the interval \((t-q,t)\) the object is in the potential \(0_0\), and on the interval \((t,t+q)\)—in the potential \(1_1\).

It follows from the rules of behavior in the small that the time interval between any two events cannot be less than the fixed interval \(q\). To describe potential-pulse objects it is expedient to introduce a quantized time scale. We assume that events can occur only at instants of time corresponding to integers. In this case the initial and terminal points of the interval on which the behavior of the object is considered are excluded for events. In this case, on a time interval \(m\cdot q\) (\(m\) an integer, \(q\) the unit of time) a potential-pulse variable is completely determined by its values at the instants of time \(1,2,\ldots,\ldots,m-1\).

We shall denote individual representatives of the set of potential-pulse variables by \(Z_1, Z_2, \ldots, Z_n\) (variables of type \(Z\)). Two variables \(Z_i\) and \(Z_k\) are equal (\(Z_i=Z_k\)) if for every instant of time their values coincide. From the set of potential-pulse variables we single out the constants \(\mathbf{1}\) and \(\mathbf{0}\). The first is equal to \(1_1\) at all instants of time, the second to \(0_0\). A potential-pulse variable that has no pulses will be called a potential logical variable (a variable of type \(X\)). A potential-pulse variable that lacks the potential \(1_1\) will be called a positive-pulse logical variable (a variable of type \(Y^1\)). On an interval \(m\cdot q\) there is realized a maximum of \(2\cdot 3^{\,n-1}\) variables of type \(Z\), a maximum of \(2^m\) variables of type \(X\), and a maximum of \(2^{m-1}\) variables of type \(Y^1\).

1. We shall investigate functions of potential-pulse variables. A function of potential-pulse variables is itself a potential-pulse variable. We shall confine ourselves to consideration of the class of functions whose definition follows below.

Definition. A function of potential-pulse variables is stationary if, for any instants of time, the values of the function corresponding to the same sets of values of the arguments coincide.

As is evident, for stationary functions the assignment table does not depend on time. We note that the property of stationarity and the rules of behavior in the small eliminate arbitrariness in assigning the values of a function for different sets of argument values. For stationary functions the following processing rules are observed:

2a) sets of values of the arguments from the alphabet \(\{1_1\ 0_0\}\) can pass into function values only from the alphabet \(\{1_1\ 0_0\}\);

2b) sets of values of the arguments from the alphabet \(\{1_1 0_0\ 1_0 0_1\}\) can pass into function values only from the alphabet \(\{1_1\ 0_0\ 1_0\ 0_1\}\);

2c) sets of values of the arguments containing at least one of the values \(\Delta_1,\ \Delta_0\) can pass into values from the full alphabet \(\{1_1,0_0,\ 1_0\ 0_1\ \Delta_1\ \Delta_0\}\).

Operators realizing stationary functions will be called filters. Corresponding to the number of arguments \(1,2,\ldots,n\), filters will be called single-input (with one input), two-input (with two inputs), \(\ldots\), \(n\)-input (with \(n\) inputs). Since the greatest restriction is imposed on the processing of potentials, the specification of a filter should begin with those sets into which only potentials enter.

Four important one-input filters are defined by Table 1.

Table 1

The filter \(p\) “cleanses” a potential-pulse variable of pulses (Fig. 1б). It transforms a variable of type \(Z\) into a variable of type \(X\). We shall call it a potentiality filter. The filter \(d\) marks, by pulses \(1_0\), the transitions \(\Delta_1\) of a variable of type \(Z\) (Fig. 1в). We shall call it a filter of positive transition. The filter \(i\) marks, by pulses \(1_0\), the pulses \(1_0\) of a variable of type \(Z\) (Fig. 1г). We shall call it a filter of positive pulseness. The filters \(d\) and \(i\) transform variables of type \(Z\) into variables of type \(Y^1\). The filter \(N\) “inverts” a potential-pulse variable. We shall call it a filter of logical negation.

In what follows we shall use the following notation: by \(\gamma\) we denote any symbol of the alphabet \(\{1_1\ 0_0\ 1_0\ 0_1\ \Delta_1\ \Delta_0\}\); by \(\beta\), any symbol of the alphabet \(\{1_0\ 0_1\ \Delta_1\ \Delta_0\}\); by \(\alpha\), any symbol of the alphabet \(\{1_1\ 0_0\}\).

Table 2

\[ \beta \ne 1_0,\quad i=1,0, \]
\[ \gamma_1 \& \gamma_2=\gamma_2 \& \gamma_1 \ldots (T_2) \]

Table 3

\[ \beta \ne 0_1,\quad i=1,0, \]
\[ \gamma_1 \vee \gamma_2=\gamma_2 \vee \gamma_1 \ldots (T_3) \]

Table 2 and relation \((T_2)\) define a two-input filter \(\&\), which we shall call universal conjunction. Table 3 and relation \((T_3)\) define a two-input filter \(\vee\), which we shall call universal disjunction.

The set of potential-pulse variables with the operations \(p, d, i, N, \&\), and \(\vee\) forms a certain algebraic system, which we shall call the algebra of potential-pulse objects. The question naturally arises as to the functional completeness of the system of filters \(p, d, i, N, \&\), and \(\vee\). The following assertion is true.

Theorem. Any filter with \(n\) inputs can be represented by means of a formula using the filters \(p, d, i, N, \&\), and \(\vee\).

Let \(\Phi(Z_1,\ldots,Z_n)\) be an arbitrary filter with \(n\) inputs. Below, instead of the symbol \(N\) we shall use the symbol \(\bar{\ }\), instead of the symbol \(\&\)—the sym-

... by the symbol \(\cdot\). We shall further assume that

\[ Z^{1_1}=pZ,\qquad Z^{0_0}=p\bar Z,\qquad Z^{1_0}=iZ,\qquad Z^{0_1}=i\bar Z,\qquad Z^{\Delta_1}=dZ,\qquad Z^{\Delta_0}=d\bar Z. \]

The following relation holds:

\[ \begin{aligned} \Phi(Z_1,\ldots,Z_n)=&\\ =&\left(\sum_{1_1} Z_1^{\alpha_1}\cdots Z_n^{\alpha_n}\right)\cdot \left(\sum_{0_1} Z_{i_1}^{\alpha_{i_1}}\cdots Z_{i_{k-1}}^{\alpha_{i_{k-1}}}\cdot Z_{i_k}^{\beta_{i_k}}\cdots Z_{i_n}^{\beta_{i_n}}\right)\vee\\ &\vee \sum_{1_0} Z_{i_1}^{\alpha_{i_1}}\cdots Z_{i_{k-1}}^{\alpha_{i_{k-1}}}\cdot Z_{i_k}^{\alpha_{i_k}}\cdots Z_{i_n}^{\beta_{i_n}} . \end{aligned} \tag{1} \]

Here \(\sum_{1_1}\) denotes the universal disjunction over those sets \(\alpha_1,\ldots,\alpha_n\) for which \(\Phi(\alpha_1,\ldots,\alpha_n)=1_1\); \(\sum_{0_1}\) denotes the universal disjunction over those sets \(\alpha_{i_1},\ldots,\alpha_{i_{k-1}},\ \beta_{i_k},\ldots,\beta_{i_n}\) for which
\(\Phi(\alpha_{i_1},\ldots,\alpha_{i_{k-1}},\beta_{i_k},\ldots,\beta_{i_n})=0_1\); \(\sum_{1_0}\) denotes the universal disjunction over those sets \(\alpha_{i_1},\ldots,\alpha_{i_{k-1}},\beta_{i_k},\ldots,\beta_{i_n}\) for which
\(\Phi(\alpha_{i_1},\ldots,\alpha_{i_{k-1}},\beta_{i_k},\ldots,\beta_{i_n})=1_0\). For \(\sum_{0_1}\) and \(\sum_{1_0}\): \(i_j=1,\ldots,n\), where \(j=1,\ldots,k,\ldots,n\) and \(k=1,\ldots,n\). The right-hand side of (1) will be called the perfect normal form for an \(n\)-input filter.

It is interesting to note that for filters transforming variables of type \(X\) into variables of type \(X\) (filters of type \(X—X\)), the disjunctions \(\sum_{0_1}\) and \(\sum_{1_0}\) are equal to \(0\), and the right-hand side of (1) becomes the perfect disjunctive normal form for functions of Boolean algebra. Thus, Boolean algebra is a subalgebra of the algebra of potential-pulse objects. The number of filters with \(n\) inputs grows extremely rapidly as \(n\) increases. There are exactly 40 one-input filters. The number \(M\) of filters with \(n\) inputs is estimated by the inequalities:

\[ 2^{4^n}<M<2^{6^n}. \tag{2} \]

1. If potential-pulse variables are modeled by electrical quantities of a definite type, then the filters \(p,d,i\) are realized by electrical filters. The filter \(p\) corresponds to a low-pass filter, the filter \(d\) to a medium-frequency filter (“band-pass filter”), and the filter \(i\) to a high-pass filter. The system of filters \(p,d,i\) possesses, as is evident, “physical completeness,” i.e., the ability to process the full frequency spectrum. In papers \((^1,^2)\), technical applications of the so-called homogeneous potential-pulse circuits (filters of type \(X—Y\)) were considered. The present note generalizes the results of those papers.

The author expresses deep gratitude to S. V. Yablonskii for his interest in the work and for valuable comments.

Institute of Automation and Telemechanics
Academy of Sciences of the USSR

Received
11 IV 1961

REFERENCES

1. A. D. Talantsev, DAN, 127, No. 2 (1959).
2. A. D. Talantsev, Automation and Telemechanics, 20, No. 7 (1959).