$S$-classification of functions of many-valued logic

S. S. Marchenkov

Diskretnaya Matematika, Tome 9 (1997) no. 3, pp. 125-152

Résumé

The set of functions of many-valued logic is proposed to be classified with respect to two operations: superposition and transition to dual functions (the $S$-classification). The contensive description of all $S$-closed classes, which was begun by the author in 1979–82, was completed by Nguen Van Hoa. If $k\ge5$, then the set of functions of $k$-valued logic has only two $S$-precomplete classes: the class $I_k$ of idempotent functions and the Słupecki class $SLP_k$. In this paper the key properties determining the $S$-closed classes are found and formalized in the form of the so-called basic relations. Using the Galois theory for Post algebras, it is shown that every $S$-closed class of functions, which is not contained in $SLP_k$, can be described by the basic relations. In the set of all systems of the basic relations all independent systems are determined which correspond to all $S$-closed classes not contained in $SLP_k$. An exact formula for the number of $S$-closed classes contained in $I_k$ is obtained which is a cubic polynomial in $k$. This research was supported by the Russian Foundation for Basic Research, grant 95–01–01625.