### Book chapter

## О строении одного замкнутого класса функций трехзначной логики

All closed classes from Muchnik's example of closed class with infinite bases are described.

### In book

The complexity of realization of *k*-valued logic functions by circuits in a special infinite basis is under study. This basis consists of Post negation (i.e. function *x*+1(mod *k*)) and all monotone functions. The complexity of the circuit is the total number of elements of this circuit. For an arbitrary function *f*, we find the lower and upper bounds of complexity, which differ from one another at most by 1. The complexity has the form 3log_3 (*d*(*f*)+1)+*O*(1), here *d*(*f*) is the maximum number of the value decrease of the value of *f* taken over all increasing chains of tuples of variable values. We find the exact value of the corresponding Shannon function which characterizes the complexity of the most complex function of a given number of variables.

Closed classes of functions of three-valued logic whose generating systems include nonmonotone symmetric functions taking values in the set {0,1} are studied. It is shown that in some cases the problems of existence of a basis and existence of a finite basis can be reduced to a similar problem for reduced generated systems.

Closed classes of multi-valued logic are observed. Families of closed classes generated by function with special properties are considered. Criteria for basis existence have been obtained for these classes.

Closed classes of functions of many-valued logic are studied. Problem on the basis existence is considered for some families of closed sets. Functions from generating systems are symmetric functions taking the values from the set {0,1} and equal to zero on the unit collection and collections containing at least one zero. Furthermore, closure of any subset of considered set of fuction intersected with initial function set equals to the unit of every function closure of the subset intersected with initial function set.

Jan Lukasiewicz (1878-1956) was one of the most important members of the Lwow-Warsaw school of logic. The thirteen translated articles in this volume demonstrate the protean form of Lukasiewiczs work, from his texts on Aristotle and the principle of non-contradiction and syllogistics to modal logic, intuitionism, and multivalent logics. The articles show in particular his preoccupations with logical precision and the problem of human liberty.

The collection represents proceedings of the 5th school-seminar "Syntax and Semantics of Logic Systems" (Ulan-Ude, 08.08.2017 - 12.08.2017). The conference subject area includes: theory of models and universal algebra; theory of boolean and finite-valued functions; formal languages and logic calculus; mathematical logic in education.

Closed classes of functions of three-valued logic whose generating systems include nonmonotone symmetric functions taking values in the set {0,1} and taking value 1 on restricted number of layers are studied. Cryteria of existence of basis and existence of finite basis has been obtained.