Article collection "Mathematical Problems of Cybernetics" №18, Moscow, 2013

Authors:Mihajlovich A.V.

Closed Classes of Multi-Valued Logics Generated by Symmetric Functions

Abstract:

Problem of basis existence for some families of closed classes of multi-valued logic functions is considered. Generating systems for classes from these examples consist of symmetric functions taking values from the set {0,1} and equal zero on the unit tuples and tuples containing at least one zero. Basis existence and finite basis existence criteria are obtained for one-layer symmetric functions and monotone symmetric functions. It is shown that closure of the set of all one-layer symmetric functions with respect to superposition and addition of dummy arguments and closure of the same set with respect to identification, relabling arguments and addition of dummy arguments are the same. Necessary and sufficient conditions of basis existence for closes classes with generating systems of special type are proved. Examples of sets of function of such type are given.