The S-classification of three-valued logic functions. (Q2782030)

The classification of sets of logic functions is a non-trivial problem that goes back to E. Post. This problem is solved by defining a closure operator which brings any set of functions into correspondence with a closure set defined by means of functions from the given set. A lot of brilliant results were obtained in this field by Yu. I. Yanov, A. A. Muchnik, S. V. Yablonskij and many others. In this book the author pursues an alternative approach to the classification. This approach is different from the traditional one by the ground notion of closure. The new closure operator results from the traditional operator by adding to it a new operation of substitution relative to a fixed group of substitutions. This new operator is called S-closure operator. With S-closure, S-closed sets are defined as sets containing all superpositions and all functions that are dual to these superpositions relative to a group of substitutions. NEWLINENEWLINENEWLINEThe first important result is the definition of a criterion for S-completeness: a system of functions of 3-valued logic is S-complete in the class \(P_3\) if and only if it is not properly contained in any of the following four classes: (1) the class of idempotent functions, (2) the class of functions that are self-dual relative to any even substitution, (3) the class of functions representable by linear polynomials over the Galois field GF(3) (i.e. by linear Zhegalkin polynomials), (4) the class of functions essentially dependent on not more than one variable or taking not more than two values (so-called Slupecki class). The author describes 48 S-closed classes of 3-valued functions and gives examples of S-bases for them. The main theorem of the book states that any S-closed class of functions of 3-valued logic that contains all selector functions coincides with one of those 48 classes. Also the author gives predicate definitions for all S-closed classes. The set of predicates defines a class of functions in the following sense: one should add to these predicates all predicates that are dual to them with respect to any substitution on the set of values and then the given class would coincide with the set of all functions which preserve the resulted finite set of predicates. NEWLINENEWLINENEWLINEWe should note that S-classification is today the only complete and effective classification of many-valued logic functions. To illustrate its effectiveness, it is sufficient to recall that in the traditional classification there is a continuum of closed classes of functions already in the case of 3-valued logic, and some of these classes are generated by countably infinite sets of functions. At the same time, the number of all S-closed sets is finite and all of them are finitely S-generated.