View source for Many-valued logic

A branch of [[Mathematical logic|mathematical logic]] studying mathematical models of [[Propositional calculus|propositional calculus]]. These models reflect the two fundamental features of the latter: the plurality of truth values of propositions, and the possibility of constructing new, more complicated, propositions from given ones using logical operations, which also allow the truth values of the compound propositions to be established with respect to the truth values of initial propositions. Examples of many-valued propositions are statements with a modal outcome ( "yes" ,  "no" ,  "may be" ) and statements of a probabilistic nature; examples of logical operations are logical connectives of the type  "and" ,  "or" ,  "if … then" . In general, models of many-valued logic are generalizations of the [[Algebra of logic|algebra of logic]]. It is important to note that in the algebra of logic, propositions take only two truth values ( "yes" ,  "no" ); thus, in general, they may not reflect the full variety of logical structures encountered in practice. In a fairly broad interpretation of many-valued logic, logical calculi (cf. [[Logical calculus|Logical calculus]]) are also sometimes included.

Historically, the first models of many-valued logics were the two-valued logic of G. Boole (mid 19th century), also called the algebra of logic, the three-valued logic of J. Łucasiewicz (1920) and the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m0622501.png" />-valued logic of E. Post (1921). The investigation of these models was an important stage in the development of the theory of many-valued logics.

==Basic models of many-valued logics.==
Many-valued logics have a specific distinguishing feature, which is the discussion of the problems and methods arising in the investigation of many-valued logics from the point of view of mathematical logic, mathematical cybernetics and algebra. Thus, from the point of view of mathematical cybernetics, models of many-valued logics are considered as languages describing the functioning of complex control systems the components of which may be in a certain number of different states, and from the point of view of algebra, models of many-valued logics are algebraic systems (cf. [[Algebraic system|Algebraic system]]) having both applied and theoretical interest.

The construction of models of many-valued logics is done by analogy with the construction of a two-valued logic. Thus the individual propositions of the logic, separated into classes with the same truth value, lead to the idea of a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m0622502.png" />, a constant of the model, which in fact identifies all individual propositions, replacing them by their corresponding truth values; variable propositions become variable quantities <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m0622503.png" /> which take values in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m0622504.png" />; the logical connectives become elements of a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m0622505.png" /> of elementary functions (operations) the arguments of which take values from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m0622506.png" />. Compound propositions, constructed from individual and variable propositions and also the logical connectives, become elements of the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m0622507.png" /> of formulas over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m0622508.png" />. The truth value from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m0622509.png" /> of a compound proposition is a function of the corresponding truth values of the propositions figuring in the given compound proposition. In the model this function is associated with a formula corresponding to the given compound proposition; the formula is also said to realise the function. Functions mapping a [[Tuple|tuple]] of elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225010.png" /> into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225011.png" /> are called functions of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225013.png" />-valued logic, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225014.png" /> denotes the cardinality of the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225015.png" />. The set of all functions of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225016.png" />-valued logic is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225017.png" />. The set of formulas <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225018.png" /> leads to a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225019.png" /> of functions realizing the formulas from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225020.png" /> called superpositions (or compositions) over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225021.png" />. The set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225022.png" /> is called the closure of the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225023.png" />. The specification of the concrete model of a many-valued logic <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225024.png" /> is to be regarded as equivalent to indicating the sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225025.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225026.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225027.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225028.png" />; the model is then said to be generated by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225029.png" />; if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225030.png" /> is finite, the model is called finitely generated. This model is called a formula model, and also an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225032.png" />-valued logic.

The distinctive approach of mathematical cybernetics to many-valued logics is to regard models of many-valued logics as control systems. The elementary functions here are the elements producing the operations, and formulas are interpreted as schemes constructed from the elements which also process input information into output. Control systems of this kind, known in cybernetics as diagrams of functional elements (without branching), are widely utilized in theoretical and practical questions of cybernetics.

At the same time there are a number of problems of logic and cybernetics connected with the study of relationships between the sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225033.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225034.png" /> in which the role of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225035.png" /> is somewhat in the background, regarded just as a means of defining the second set from the first. This situation leads to another model of a many-valued logic as an algebra whose elements are functions taking values and arguments from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225036.png" />. It is common to use as operations in this algebra a special set of operations equivalent in meaning to the relationship of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225037.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225038.png" /> to the set of formulas constructed from functions on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225039.png" />; that is, compound functions are obtained from single functions whose arguments are other functions. These algebras are called the algebras of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225041.png" />-valued logic. They may be arrived at concretely, for example, by the introduction of the following one-place operations: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225042.png" />, and a binary operation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225043.png" />. If one assumes that, taking into account fictitious variables, each function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225044.png" /> from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225045.png" /> depends on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225046.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225047.png" /> is determined by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225048.png" />, then these operations can be given as:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225049.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225050.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225051.png" /></td> </tr></table>

if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225052.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225053.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225054.png" />;

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225055.png" /></td> </tr></table>

and for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225056.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225057.png" />,

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225058.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225059.png" /></td> </tr></table>

The algebras <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225060.png" /> are sometimes called Post algebras.

==Problems in many-valued logic.==
Among the problems characteristic of formula models of many-valued logics is the problem of  "description" , that is, the question of giving all formulas of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225061.png" /> which realise functions from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225062.png" />, for a given set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225063.png" />. A particular case of this problem is the important question in mathematical logic of giving all formulas which realise a given constant; for example, in propositional calculus, this is equivalent to the construction of all identically-true propositions.

A question at the interface between mathematical logic and algebra, related to the problem of description, is the problem of identical transformations. Here for a given <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225064.png" /> it is required to select the simplest, in some sense, subset of pairs of equal (i.e. realizing the same function) formulas from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225065.png" /> (identities) which by substitution of one formula for the other allows one to obtain from any formula all formulas equal to it (a complete system of identities).

A similar place is occupied by the so-called completeness problem, which is to give all subsets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225066.png" /> of a given closed (i.e. equal to its closure) set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225067.png" /> for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225068.png" />; that is, the completeness property (or the functional completeness property) of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225069.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225070.png" /> holds. Close to this problem is the basis problem, which is to give each complete subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225071.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225072.png" /> no proper subset of which is complete in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225073.png" />; complete independent systems of functions are also called bases. There are two approaches to the solution of the completeness problem — the algorithmic and the algebraic. In the first case there is the question of the existence of an algorithm which establishes the completeness or incompleteness of a system of functions described in some language; in the second, one passes to the study of the properties of the lattice of subalgebras of a given algebra of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225074.png" />-valued logic and solves the completeness question using these properties. An important idea in the algebraic approach is that of a criterial system of subalgebras. A system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225075.png" /> of subalgebras of an algebra <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225076.png" /> is called criterial if the following property holds: A set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225077.png" /> is complete if and only if it is not a subset of any subalgebra in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225078.png" />. For example, the set of all proper subalgebras of the algebra <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225079.png" /> is criterial. In general, the latter criterial system is too large. Each criterial system contains all maximal subalgebras of the algebra <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225080.png" /> (all pre-complete classes), and this enables one to move to the consideration of more economical criterial systems which do not contain subalgebras of maximal subalgebras. Thus, in completeness problems one may confine oneself to the use of criterial systems of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225081.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225082.png" /> is the set of all maximal subalgebras and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225083.png" /> consists of some of those subalgebras that are not subalgebras of any maximal subalgebra. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225084.png" /> is empty, then the completeness problem reduces to the description of all maximal subalgebras of the algebra <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225085.png" />.

A global problem in many-valued logics is the description of the lattice of closed classes of a given model of a many-valued logic.

The characteristic question in the theory of complexity of control systems arises naturally in relation to the formulas and functions from a many-valued logic. Typical for this approach is the following problem on the complexity of realization. By some means a numerical measure (the complexity of a formula) is introduced on the set of all elementary formulas; it is then extended to the set of all formulas, for example, by summing the measures of all elementary formulas entering in a given formula. For a given function it is required to give the (simplest) formula which realizes the function with least complexity, and also to clarify how this complexity depends on the properties of the function considered. Various generalizations of the problem have been studied.

There is a wide circle of questions connected with the realization of functions by formulas with preassigned properties. Here one has the problem on the realization of functions of the algebra of logic by disjunctive normal forms (cf. [[Disjunctive normal form|Disjunctive normal form]]) and the related minimization problem; also there is the problem of the realization of functions by formulas which have bounded depth (that is, by formulas in which the chain of formulas substituted in each other has bounded length, this bound being connected with realizability and speed of calculation), the decomposition problem, that is, the realization of functions of variables using formulas constructed from elementary formulas which realize functions of fewer variables, and a number of other problems.

The solution of all the problems above depends essentially on the cardinalities of the sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225086.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225087.png" /> generating the given model of the many-valued logic.

==The most important examples of many-valued logics.==
The most important examples of many-valued logics are the finite-valued logics (that is, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225088.png" />-valued logics for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225089.png" /> is finite). For these it is common to assume that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225090.png" />, and the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225091.png" />-valued logic <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225092.png" /> is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225093.png" />. The case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225094.png" /> has been investigated most deeply; here the functions are also called Boolean functions (cf. [[Boolean function|Boolean function]]). The most important result is the complete description, by Post (see [[#References|[1]]]), of the lattice of closed classes. Their set turns out to be countable, and each class and the lattice of classes, ordered by inclusion, can be effectively constructed. These classes are called Post classes. Each closed class has a finite basis of cardinality not exceeding 4. These results lead to solutions of the problems on description, completeness and bases, and also of the problem on identical transformations. With respect to complete finite systems, for  "almost-all"  functions the behaviour of the measure of complexity of the simplest formulas realizing these functions has been given and corresponding algorithms for the synthesis of the formulas have been constructed (see [[#References|[2]]]). The problem of the construction of optimal formulas with respect to complexity, realizing functions reliably and sufficiently quickly, and also the question of the complexity of realization for a large number of special classes of functions and individual functions have been studied.

One of the intensively researched problems for two-valued logics is the minimization problem. Here a special language for the specification of the functions of a two-valued logic — the language of disjunctive normal forms — has been studied. The idea of the complexity of a disjunctive normal form, the number of letters in it, has been introduced, and the problems connected with the finding, construction and metric properties of the disjunctive normal form that is  "simplest"  in the sense of this measure and that realizes a given function have been investigated (see [[#References|[3]]]). The decomposition problem of Boolean functions is the clarification of conditions under which a given function of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225095.png" /> variables may be realized by a formula constructed from functions of fewer variables, where all functions substituted into each other during the construction of the formula do not depend on common variables. Such formulas are called non-iterative. It has been shown that there is no finite system of functions such that each function can be realized by a non-iterative formula over this system, and even that  "almost-all"  functions do not have a realization by non-iterative formulas. On the whole, two-valued logics, because of special properties, are the main objects in which the general formulation of problems is discussed.

For arbitrary finite-valued logics, which for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225096.png" /> are essentially different from two-valued logics, there are effective solutions of the problems on description for finite systems. It has been shown that for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225097.png" /> there are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225098.png" />-valued logics with a finite basis and which, at the same time, do not have a finite complete system of identities (see [[#References|[4]]]), whereas in two-valued logics each closed class has a finite complete system of identities (see [[#References|[5]]]). For finite-valued logics with a finite basis there is an effective solution of the completeness problem. It is obtained in the following way. One says that a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m06225099.png" /> preserves a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250100.png" /> if for any set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250101.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250102.png" />, one has <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250103.png" />. A set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250104.png" /> is called regular if the choice function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250105.png" /> is contained in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250106.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250107.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250108.png" />, and if each function from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250109.png" /> preserves <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250110.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250111.png" />, then in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250112.png" /> one selects all systems <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250113.png" /> with the following properties: the functions in them depend only on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250114.png" />; the addition to them of all choice functions makes these systems regular; they do not contain <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250115.png" /> as a subset. This procedure of selection of all regular sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250116.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250117.png" />, is effective. The system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250118.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250119.png" /> (the preservation class of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250120.png" />) consists of all functions from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250121.png" /> which preserve <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250122.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250123.png" />, is criterial. Inclusion of an arbitrary finite set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250124.png" /> in each of the classes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250125.png" /> can also be verified effectively. Each pre-complete class is a preservation class and the set of all pre-complete classes in this case forms a criterial system. It has been shown that for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250126.png" /> there is a continuum of closed classes in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250127.png" />, and that there exist closed classes with bases of given finite or infinite cardinality, and also classes which do not have bases; here the families of classes without a basis, or with a countable basis, have the cardinality of the continuum. Examples of classes without a basis or having a countable basis are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250128.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250129.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250130.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250131.png" /> and for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250132.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250133.png" /> is equal to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250134.png" /> on all collections except <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250135.png" />, at which it is equal to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250136.png" />; <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250137.png" /> is equal to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250138.png" /> on all collections except the collections of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250139.png" /> at which it is equal to 1 (see [[#References|[6]]]).

The completeness problem in the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250140.png" />-valued logic <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250141.png" /> is of particular interest. In <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250142.png" /> there are finite complete systems; this allows one to select a finite complete subsystem for each complete system and to reduce the problem to the study of finite complete systems. There also exist complete systems consisting of one function; such functions are called Sheffer functions. An example is the Wenn function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250143.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250144.png" />). Because of finite generation, the completeness problem in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250145.png" /> can be solved effectively.

In <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250146.png" /> all pre-complete classes, which are preservation classes for special predicates, have been effectively constructed. Giving these predicates forms the content of the completeness theorem in finite-valued logics (see [[#References|[7]]]). One says that a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250147.png" /> preserves a predicate <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250148.png" /> if the formula

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250149.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250150.png" /></td> </tr></table>

is identically equal to 1 for all values of the variables <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250151.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250152.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250153.png" />. The class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250154.png" /> of all functions preserving a predicate <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250155.png" /> is called the preservation class of the predicate <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250156.png" />. It has been shown that for each pre-complete class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250157.png" /> it is possible to choose a predicate <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250158.png" />, depending on at most <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250159.png" /> variables, and for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250160.png" /> on at most <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250161.png" /> variables, such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250162.png" />. These predicates may be partitioned into six families: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250163.png" />. The families <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250164.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250165.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250166.png" /> consist of all two-place predicates or order relations on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250167.png" /> having one maximal and one minimal element in the first case; giving permutations on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250168.png" /> which decompose into cycles of identical prime number length (without invariant elements) in the second case; and giving non-identity and non-universal equivalence relations on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250169.png" /> in the third case. The family <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250170.png" /> is not empty for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250171.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250172.png" /> a prime, and consists of all four-place predicates <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250173.png" /> for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250174.png" /> is equivalent to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250175.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250176.png" /> is an Abelian group in which each non-zero element has order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250177.png" />. The predicate <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250178.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250179.png" />, is reflexive if the fact that not all the numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250180.png" /> are distinct implies that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250181.png" />. It is symmetric if for any permutation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250182.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250183.png" /> one has <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250184.png" />; the set of elements <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250185.png" /> for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250186.png" /> for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250187.png" /> is called the centre of the symmetric predicate <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250188.png" />. A predicate <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250189.png" /> is central if it is reflexive, symmetric and has a centre <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250190.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250191.png" />. The family <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250192.png" /> consists of all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250193.png" />-place central predicates such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250194.png" />. For an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250195.png" /> from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250196.png" /> one puts <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250197.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250198.png" />. The family <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250199.png" /> consists of all predicates <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250200.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250201.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250202.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250203.png" />, such that for some surjection <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250204.png" /> the equality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250205.png" /> is equivalent to the collections <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250206.png" /> being the same for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250207.png" />. It has been established that predicates from different families give different pre-complete classes, and conditions have been given under which predicates from the same family give the same classes. It has been shown that the number of pre-complete classes is asymptotically equal to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250208.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250209.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250210.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250211.png" /> is even and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250212.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250213.png" /> is odd (that is, this number grows fairly rapidly), which is an indication of the small practical effectiveness of criterial systems (see [[#References|[8]]]). Various modifications of the completeness problem have been discussed, leading to the investigation of systems with certain a priori known properties; for example, systems containing the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250214.png" /> of all one-place functions, or the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250215.png" /> of all permutations. In the first case for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250216.png" />, and in the second for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250217.png" />, the system is complete if and only if it contains an essential function, that is, a function depending on more than one variable and taking all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250218.png" /> values (see [[#References|[9]]], [[#References|[10]]]). Related to this is the problem of giving all subsets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250219.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250220.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250221.png" />, each of which, together with any essential function, forms a complete system. It has been shown that the subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250222.png" /> of all one-place functions not taking at least one value is such a subset, while the subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250223.png" /> of all one-place functions not taking at least two values is, in general, already not one of these. For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250224.png" /> they are precisely the subsets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250225.png" /> which are: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250226.png" />-transitive for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250227.png" />; <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250228.png" />-transitive for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250229.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250230.png" /> prime, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250231.png" />; and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250232.png" />-transitive for the remaining <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250233.png" />. These conditions, with a natural generalization of transitivity, hold for arbitrary systems of functions which take all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250234.png" /> values (see [[#References|[11]]]).

For systems consisting of one function, the completeness criterion is the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250235.png" />-transitivity condition. For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250236.png" /> an arbitrary set of functions is complete if and only if it is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250237.png" />-transitive and if the degree of transitivity cannot be reduced.

From finite complete systems, by identification, it is possible to transfer to a simpler class of complete systems, called simple bases. By a simple basis is meant a finite complete system which loses the completeness property after identification of any pair of essential variables in any function of the system. There are only a finite number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250238.png" /> of simple bases and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250239.png" /> [[#References|[12]]]. The number of variables in functions from simple bases does not exceed <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250240.png" />, and there are functions in a simple basis which essentially depend on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250241.png" /> variables. Representations of the many-valued logic <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250242.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250243.png" />, that is, homomorphisms of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250244.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250245.png" />, have been given [[#References|[13]]]; some analogues of the minimization theory have also been constructed for arbitrary finite-valued logics.

The first example of finite-valued logics were the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250247.png" />-valued logic of Łucasiewicz generated by the functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250248.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250249.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250250.png" /> take the values <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250251.png" />, and the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250253.png" />-valued logic of Post generated by the functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250254.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250255.png" />), <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250256.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250257.png" /> take the values <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250258.png" />. Bordering on the subject of finite-valued logics is the topic of algebras of many-valued functions to which, to a significant extent, the problems and methods of research of finite-valued logics have been transferred.

Examples of other many-valued logics are countable-valued and continuum-valued logics (that is, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250259.png" />-valued logics whose cardinality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250260.png" /> is, respectively, countable or that of the continuum). These models play an important role in mathematical logic, model theory and mathematical analysis. For countable-valued logics it has been established that the set of pre-complete (and thus the set of all) closed classes has a cardinality higher than that of the continuum, and the solution of the completeness problem for systems containing the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250261.png" /> of all one-place functions has been found [[#References|[14]]]. In contrast to finite-valued logics <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250262.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250263.png" />, where there is only one pre-complete class containing all one-place functions, in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250264.png" /> there are two such pre-complete classes, and a given system of functions is complete if and only if it is not contained in these classes. If one generalizes the notion of an essential function to be a function which forms a complete system together with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250265.png" />, then, just as in finite-valued logics, there is the problem of describing all subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250266.png" /> that contain the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250267.png" /> of permutations from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250268.png" /> and that together with any essential function form a complete system. It has been shown that the intersection of all such closed subsets itself has the property mentioned. This intersection, which is different from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250269.png" />, has been effectively described in set-theoretical terms.

In countable-valued and continuum-valued logics a special role is played by various subclasses. Such are, in the first case, limit logics, and, in the second case, many-valued logics of continuous functions. Limit logics are countable closed classes of functions of the many-valued logic <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250270.png" /> which contain homomorphic inverse images of all finite-valued logics. There is a continuum of distinct, and even finitely-generated, pairwise non-isomorphic limit logics. It has been established that the completeness problem for limit logics, in general, is not equivalent to finding all pre-complete classes. The cardinality of the set of pre-complete classes in limit logics may be any natural number and also may be countable or of the cardinality of the continuum (see [[#References|[15]]]). For many-valued logics of continuous functions the completeness of all two-place functions has been proved, and an analogue of the theorem on the completeness of systems consisting of all one-place and many-place functions has been obtained. It has also been established that every continuous function can be represented as the sum of specially chosen continuous one-place functions. It has been shown that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250271.png" />-times differentiable functions of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250272.png" /> variables, in general, cannot be represented using superpositions of functions of the same smoothness but depending on fewer variables (see [[#References|[16]]]).

It is also possible to attribute to many-valued logics algebras of functions in which the collection of operations is somewhat different from those described above. Such are algebras of non-homogeneous finite-valued functions (their arguments take a finite number of values from their domains), recursive and partial recursive functions, algebras of automata mappings, and a number of others.

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  S.V. Yablonskii,   G.P. Gavrilov,   V.B. Kudryavtsev,   "Functions of the algebra of logic and Post classes" , Moscow  (1964)  (In Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  O.B. Lupanov,   "On an approach to synthesis of control systems—the local coding principle"  ''Probl. Kibernetiki'' , '''14'''  (1965)  pp. 31–110  (In Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  Yu.I. Zhuravlev,   "Set-theoretical methods in the algebra of logic"  ''Probl. Kibernetiki'' , '''8'''  (1962)  pp. 5–44  (In Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  R.K. Lyndon,   "Identities in two-valued calculi"  ''Kibernet. Sb.'' , '''1'''  (1960)  pp. 234–245  (In Russian)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  V.L. Murskii,   "The existence in the three-valued logic of a closed class with finite basis, not having a finite complete system of identities"  ''Soviet Math. Dokl.'' , '''6''' :  4  (1965)  pp. 1020–1024  ''Dokl. Akad. Nauk SSSR'' , '''163''' :  4  (1965)  pp. 815–818</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  Yu.I. Yanov,   A.A. Muchnik,   "On the existence of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250273.png" />-valued closed classes without finite basis"  ''Dokl. Akad. Nauk SSSR'' , '''127''' :  1  (1959)  pp. 44–46  (In Russian)</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top">  I. Rosenberg,   "Ueber die funktionale Vollständigkeit in den mehrwertigen Logiken" , Chechoslovak. Akad.  (1970)</TD></TR><TR><TD valign="top">[8]</TD> <TD valign="top">  E.Yu. Zakharova,   V.B. Kudryavtsev,   S.V. Yablonskii,   "Precomplete classes in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250274.png" />-valued logics"  ''Soviet Math. Dokl.'' , '''10''' :  3  (1969)  pp. 618–622  ''Dokl. Akad. Nauk SSSR'' , '''186''' :  3  (1969)  pp. 509–512</TD></TR><TR><TD valign="top">[9]</TD> <TD valign="top">  S.V. Yablonskii,   "Functional constructions in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250275.png" />-valued logic"  ''Trudy Mat. Inst. Steklov.'' , '''51'''  (1958)  pp. 5–142  (In Russian)</TD></TR><TR><TD valign="top">[10]</TD> <TD valign="top">  A. Salomaa,   "Some completeness criteria for sets of functions over a finite domain II"  ''Turun Yliopiston Julkaisuja'' , '''AI''' :  63  (1963)</TD></TR><TR><TD valign="top">[11]</TD> <TD valign="top">  V.B. Kudryavtsev,   "The properties of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250276.png" />-systems of functions of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250277.png" />-valued logic"  ''Elektron. Informationverarb. und Kybernetik (EIK)'' , '''9''' :  1–2  (1973)  pp. 81–105  (In Russian)  (English and German abstracts)</TD></TR><TR><TD valign="top">[12]</TD> <TD valign="top">  V.B. Alekseev,   "On the number of simple bases in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062250/m062250278.png" />-valued logic"  ''Diskretn. Anal.'' :  19  (1971)  pp. 3–10  (In Russian)</TD></TR><TR><TD valign="top">[13]</TD> <TD valign="top">  A.I. Mal'tsev,   "Iterative algebras and Post varieties"  ''Algebra i Logika'' , '''5''' :  2  (1966)  pp. 5–24  (In Russian)</TD></TR><TR><TD valign="top">[14]</TD> <TD valign="top">  G.P. Gavrilov,   "On functional completeness in countable-valued logic"  ''Probl. Kibernetiki'' , '''15'''  (1965)  pp. 5–64  (In Russian)</TD></TR><TR><TD valign="top">[15]</TD> <TD valign="top">  Ya. Demetrovich,   "On certain homomorphisms and relations for limit logics"  ''Probl. Kibernetiki'' , '''30'''  (1975)  pp. 5–42  (In Russian)</TD></TR><TR><TD valign="top">[16]</TD> <TD valign="top">  A.G. Vitushkin,   "On the possibility of representing a function by a superposition of functions of fewer variables" , ''Proc. International Congress Mathematicians Moscow, 1966'' , Moscow  (1968)  pp. 322–328  (In Russian)</TD></TR></table>



====Comments====


====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  A. Urquhart,   "Many-valued logic"  D. Gabbay (ed.)  F. Guenther (ed.) , ''Handbook of philosophical logic'' , '''III''' , Reidel  (1986)  pp. 71–116</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  N. Rescher,   "Many-valued logic" , McGraw-Hill  (1969)</TD></TR></table>