Reports of the Academy of Sciences of the USSR
1966, Volume 167, No. 6

CYBERNETICS
AND CONTROL THEORY

UDC 519.95

R. V. FREIVALD

COMPLETENESS CRITERIA FOR PARTIAL FUNCTIONS OF ALGEBRA OF LOGIC AND MANY-VALUED LOGICS

(Presented by Academician P. S. Novikov on 27 VII 1965)

We shall consider the sets \(\widetilde P_k\) \((k=2,3,\ldots)\) of all functions \(F(x_1,\ldots,x_n)\) such that: a) the arguments take the values \(0,1,\ldots,k-1\); b) the values of the functions are also equal to \(0,1,\ldots,k-1\); c) the functions are not necessarily defined for all tuples of values of the arguments. Such functions will be called partial functions of \(k\)-valued logic, or simply partial \(k\)-valued functions.

In defining the superposition

\[ F(x_1,\ldots,x_n)= f\bigl(g_1(x_{11},\ldots,x_{1r_1}),\ g_2(x_{21},\ldots,x_{2r_2}),\ldots,\ g_m(x_{m1},\ldots,x_{mr_m})\bigr) \]

of partial functions \(g_1,g_2,\ldots,g_m\) into a function \(f\), it is natural to assume that, if for some tuple \((x_1,\ldots,x_n)\) at least one of the functions \(g_1,\ldots,g_m\) is not defined, then the function \(F(x_1,\ldots,x_n)\) is not defined on this tuple either.

In the present note we consider the completeness problem investigated for everywhere-defined functions in \((^{1,2})\).

1°. Completeness criterion for \(\widetilde P_2\). Define 8 classes \(\Phi_1,\Phi_2,\ldots,\Phi_8\) of functions from \(\widetilde P_2\):

\(\Phi_1\). Functions that are either everywhere defined or nowhere defined.

\(\Phi_2\). Functions that on the tuple \(000\ldots0\) either take the value 0 or are not defined.

\(\Phi_3\). Functions that on the tuple \(111\ldots1\) either take the value 1 or are not defined.

\(\Phi_4\). Functions that are either not defined on at least one of the tuples \(000\ldots0\) and \(111\ldots1\), or preserve both values.

\(\Phi_5\). Functions that can be extended to monotone functions.

\(\Phi_6\). Functions that can be extended to self-dual functions.

To define the classes \(\Phi_7\) and \(\Phi_8\), introduce 4-place everywhere-defined auxiliary functions \(\chi_7\) and \(\chi_8\): \(\chi_8(x_1,x_2,x_3,x_4)=x_1\oplus x_2\oplus x_3\oplus x_4\), while \(\chi_7\) differs from \(\chi_8\) only on the tuples \(0110\) and \(1001\), where \(\chi_7(0,1,1,0)=0\), \(\chi_7(1,0,0,1)=0\).

A function \(f\) (denote the number of its arguments by \(n\)) belongs to \(\Phi_7\) if and only if, for any ordered quadruple of tuples of zeros and ones

\[ (a_{11},a_{12},\ldots,a_{1n}),\quad (a_{21},a_{22},\ldots,a_{2n}),\quad (a_{31},a_{32},\ldots,a_{3n}),\quad (a_{41},a_{42},\ldots,a_{4n}) \]

(the tuples are not necessarily distinct) from

\[ \bigwedge_{i=1}^{n}\chi_7(a_{1i},a_{2i},a_{3i},a_{4i})=1 \]

it follows that

\[ \chi_7\bigl(f(a_{11},\ldots,a_{1n}),\ f(a_{21},\ldots,a_{2n}),\ f(a_{31},\ldots,a_{3n}),\ f(a_{41},\ldots,a_{4n})\bigr) \]

is either equal to 1 or is not defined.*

In the definition of the class \(\Phi_8\), \(\chi_8\) is used everywhere instead of \(\chi_7\).

Theorem 1. In order that a system of functions be functionally complete in \(\widetilde P_2\), it is necessary and sufficient that the system not be contained in any of the 8 indicated classes.

In other words, it is necessary and sufficient that for each class \(\Phi_i\) \((i=1,2,\ldots,8)\) the system contain at least one function not belonging to \(\Phi_i\).

* Since \(\chi_7\) is an everywhere-defined function, definedness of the superposition is equivalent to definedness of the function \(f\) on all four indicated tuples.

Corollary. Since none of the indicated classes is contained entirely in another class, Theorem 1 implies the precompleteness of all the classes mentioned.

2°. Further, it can be shown that the function

\[ \Pi(x_1,x_2,x_3)= \begin{cases} \overline{x_1 \& x_2}, & \text{if } x_2=x_3,\\ \text{undefined}, & \text{if } x_2\ne x_3, \end{cases} \]

alone constitutes a complete basis for \(\tilde P_2\), and that no such two-place functions exist.

Theorem 2. From any system of functions forming a complete basis for \(\tilde P_2\), one can extract a subsystem consisting of no more than 5 functions which also forms a complete basis.

Remark 1. Theorem 2 cannot be strengthened, since the following system of functions ceases to be a complete basis upon deletion of any one of its 5 functions:
\(h_1(x_1,x_2)=x_1 \& x_2\), \(h_2(x_1)=0\), \(h_3(x_1)=1\), \(h_4(x_1,x_2,x_3)=x_1\oplus x_2\oplus x_3\), and \(h_5(x_1)\): \(h_5(0)=0\), \(h_5(1)\) is undefined.

Remark 2. To each partial function of the algebra of logic one can naturally assign an everywhere-defined 3-valued function: on tuples where the partial function is undefined, the corresponding 3-valued function takes the value 2. This establishes a one-to-one correspondence between \(\tilde P_2\) and the class of all 3-valued functions for which, if at least one argument is equal to 2, then the function is equal to 2. Superposition of partial functions is thereby matched with superposition of the corresponding 3-valued functions. Therefore every theorem on completeness in \(\tilde P_2\) is also a theorem on the mentioned closed class of functions of 3-valued logic.

It is known \((^{1,2})\) that every closed class of functions of the algebra of logic has a finite basis. It is also known that there exist closed classes of functions of 3-valued logic without a finite basis. Theorem 3 shows that such classes also exist in \(\tilde P_2\) (and still more so in any \(\tilde P_k\), \(k=3,4,\ldots\)).

Theorem 3. The class of all functions not defined on tuples of the form \(000\ldots0\) is closed and has no finite basis.

3°. Completeness criteria for \(\tilde P_k\). Let us define some classes of functions from \(\tilde P_k\). Each class \(\Phi_\chi\) corresponds to a certain \(k^2\)-place \(k\)-valued everywhere-defined auxiliary function \(\chi\), taking only the values 0 and 1. We shall consider the classes corresponding to each such function, provided only that it: a) takes the value 1 on the tuples
\(0,1,\ldots,k-1,0,1,\ldots,k-1,\ldots,0,1,\ldots,k-1\) and \(0\ldots01\ldots1\ldots k-1\ldots k-1\) *; b) is not identically equal to one.

A function \(f\) (denote the number of its arguments by \(n\)) belongs to the class \(\Phi_\chi\) if and only if, for any ordered \(k^2\)-tuple of tuples of values \(0,1,\ldots,k-1\):
\((\alpha_{11},\alpha_{12},\ldots,\alpha_{1n})\),
\((\alpha_{21},\alpha_{22},\ldots,\alpha_{2n})\), \(\ldots\),
\((\alpha_{k^2 1},\alpha_{k^2 2},\ldots,\alpha_{k^2 n})\)
(the tuples need not be distinct), from

\[ \bigwedge_{i=1}^{n}\chi(\alpha_{1i},\alpha_{2i},\ldots,\alpha_{k^2 i})=1 \]

it follows that

\[ \chi\bigl(f(\alpha_{11},\ldots,\alpha_{1n}),\,f(\alpha_{21},\ldots,\alpha_{2n}),\,\ldots,\,f(\alpha_{k^2 1},\ldots,\alpha_{k^2 n})\bigr) \]

is either equal to 1 or is undefined. Let us define one more important class \(\Phi_0\): a function belongs to \(\Phi_0\) if it is either everywhere defined or nowhere defined.

Theorem 4. In order for a system of functions to be functionally complete in \(\tilde P_k\), it is necessary and sufficient that the system not be contained in any one of the classes indicated above.

The author expresses gratitude to Yu. I. Zhuravlev, B. A. Trakhtenbrot, and Ya. M. Barzdin for their attention to the present work.

Institute of Mathematics, Siberian Branch
Academy of Sciences of the USSR

Received
20 VII 1965

REFERENCES

\(^{1}\) E. L. Post, Am. J. Math., 43 (1921).
\(^{2}\) S. V. Yablonskii, Tr. Matem. inst. im. V. A. Steklova AN SSSR, 51 (1958).

* In this tuple each value \(0,1,\ldots,k-1\) occurs exactly \(k\) times.