Mathematics

On the enumeration of maximal infinitely-generated classes of 01-functions in three-valued logic

S. S. Marchenkov

Lomonosov Moscow State University, Moscow, Russia

Abstract: Background. The superposition operation is the main operation in the study of multivalued logic functions. On the basis of this operation, classifications of multivalued logic functions are defined, which allow to solve important problems of expressiveness and completeness. However, if these problems have long been solved for Boolean functions (functions of two-valued logic), then, for example, for functions of $k$-valued logic (for $k\geqslant3$), the problem of describing all closed classes seems to have no satisfactory solution - in this case, the number of closed classes is continuous. In this connection, research on closed (with respect to the superposition operation) classes of functions of $k$-valued logic develops in the direction of describing various fragments of the lattice of closed classes: maximum and minimum classes, upper and lower cones, finite and countable intervals defined by meaningful classes, etc. One of the tasks of this direction, set by S. V. Yablonsky in the early 1980s, is to describe all maximal infinitely generated classes of a lattice of closed classes. In 1986, E. A. Mikheeva and G. Tardosh found examples of such maximal classes: E.A. Mikheeva for any $k\geqslant3$, G. Tardosh for $k=8$. The ideas of Tardosh were further developed by O.S. Dudakova. However, for fixed $k$, it has not yet been possible to determine the series of maximal infinitely-generated classes. In 2019, the author published an article where $4$ maximal infinitely-generated classes $\Pi_1-\Pi_4$ are defined in three-valued logic, which consist of functions that take only the values $0$ and $1$ (the same classes can be defined for functions that take the values $0,2$ and $1,2$). Thus, a series of $12$ maximal infinitely-generated classes appeared. There is every reason to believe that the classes $\Pi_1-\Pi_4$ exhaust all maximal infinitely-generated classes of 01-functions. This fact can be proved by the following scheme. First, for each class $\Pi_i$, you should define all the “simplest” functions from two or three variables that are obtained by superpositions from an arbitrary function that does not belong to the class $\Pi_i$. Then it is necessary to iterate through all possible fours of the “simplest” functions and, using known sufficient conditions of finite generatability, to establish the finite generatability of closed classes containing the selected fours of functions. Materials and methods. The constructions and proofs use the methods of the functional systems theory. Results and conclusions. We consider a class of functions of three-digit logic that accept only the values $0$ and $1$. In the classroom there are $4$ infinitely-generated classes $\Pi_1-\Pi_4$ that have the maximality property: every closed class of that contains any of the classes $\Pi_1-\Pi_4$ in its own way is finitely-generated. For each class $\Pi_i$ and an arbitrary function $f$ that does not belong to $П_i$ and essentially depends on at least two variables, all “simplest” functions of two or three variables that are obtained by superpositions of the function $f$ and that are not included in the class $\Pi_i$ are defined. In the future, all these functions are supposed to be used to prove that in the class all maximal infinitely-generated classes are exhausted by the classes $\Pi_1-\Pi_4$. Such proof should roughly consist in the analysis of several thousand fours, consisting of the obtained “simplest” function.

Keywords: infinite-generated classes, 01-functions in ternary logic, theory of functional systems.

UDC: 519.716

DOI: 10.21685/2072-3040-2021-3-1