On the expressibility of functions of many-valued logic in some logical-functional classes

S. S. Marchenkov

Diskretnaya Matematika, Tome 11 (1999) no. 4, pp. 110-126.

Résumé

For each $k$, $k\ge2$, three logical-functional languages are introduced for the set of functions of $k$-valued logic: the positive expressibility language $\operatorname{Pos}_k$, the first-order language $1\operatorname{L}_k$, and the second-order language $2\operatorname{L}_k$. On the basis of the notion of expressibility in a language, the corresponding closure operators are defined. It is proved that the operators of $1\operatorname{L}_k$-closure and $2\operatorname{L}_k$-closure coincide. The $1\operatorname{L}_k$-closed and $\operatorname{Pos}_k$-closed classes are described with the help of symmetric groups and symmetric semigroups. The expressibility in the languages $1\operatorname{L}_k$ and $\operatorname{Pos}_k$ is compared with the parametric expressibility and the expressibility by terms.The research was supported by the Russian Foundation for Basic Research, grant 97–01–00989.