zbMATH — the first resource for mathematics

A new version of the proof of completeness criterion for $$k$$-valued logic functions. (English. Russian original) Zbl 0863.03009
Discrete Math. Appl. 6, No. 5, 505-530 (1996); translation from Diskretn. Mat. 8, No. 4, 11-36 (1996).
Summary: We suggest a new version of the proof of the completeness criterion in terms of precomplete classes of $$k$$-valued logic functions. As before, the basis of the proof is the idea of preserving relations (predicates) by these functions, which was suggested by Post and developed by Yablonskij, Kuznetsov, Rosenberg, Lo Chu Kai, Kudryavtsev, Zakharova, etc. The essence of our reasoning consists in a rather different approach to the process of finding relations such that the classes preserving them coincide with precomplete ones. This approach arose while studying the $$r$$-completeness problem in the class of determinate functions. It allows us to shorten the well-known proof due to Rosenberg.

MSC:
 03B50 Many-valued logic
Full Text: