This article is cited in
19 papers
$S$-classification of functions of many-valued logic
S. S. Marchenkov
Abstract:
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.
UDC:
519.716 Received: 23.03.1994
Revised: 23.09.1996
DOI:
10.4213/dm488
Fulltext:
PDF file (3024 kB)