Logic, Many-Valued

the branch of mathematical logic that studies mathematical models of the propositional calculus. The models reflect two basic characteristics of the propositional calculus, namely, the multiplicity of truth values of propositions and the possibility of constructing new, more complex propositions from given propositions by means of logical operations. Logical operations also make it possible to determine the truth value of a complex proposition by the analysis of the truth values of the initial propositions. Propositions with a modal content (“yes,” “no,” “perhaps”) and probabilistic propositions are examples of many-valued propositions. Examples of logical operations are logical connectives of the type “and,” “or,” and “if …, then.… “In the general case, the models of many-valued logic are generalizations of the algebra of logic. It is important to note that propositions in the algebra of logic have only two truth values (“yes,” “no”), so that in the general case the algebra of logic is unable to reflect the wide variety of logical constructions that are encountered in actual practice. Logical calculi are sometimes classed as part of many-valued logic, when the latter is broadly interpreted.

The two-valued logic of G. Boole (also called an algebra of logic), the three-valued logic of J. Lukasiewicz (1920), and the in-valued logic of E. Post (1921) were the first examples of many-valued logic. Study of them was of great importance for the development of many-valued logic. The major characteristic of many-valued logic is that it examines the problems and methods of approach from the standpoint of mathematical logic, theoretical cybernetics, and algebra. From the standpoint of theoretical cybernetics, models of many-valued logic are regarded as languages that describe the functioning of complex control systems whose components may be in a number of states. From the viewpoint of algebra, models of many-valued logic are algebraic systems of purely theoretical, as well as applied, interest.

Models of many-valued logic are constructed by analogy with the construction of two-valued logic. Thus, individual logical propositions are separated into classes, each with the same truth value and each equated with the set E or set of model constants, that in fact identify all individual propositions with their corresponding truth values. The propositional variables become the variables x₁, x², . . ., whose values range over the set E. Logical connectives constitute the set M of elementary functions (operations) that, like their arguments, take their values from e. Complex propositions constructed from individual and propositional variables, as well as from logical connectives, become set 〈M〉 of formulas over M. The truth value of a complex proposition from E is a function of the corresponding truth values of the propositions that make up the given complex proposition. In the model, this function is assigned to the formula that corresponds to the given complex proposition. It is also said that the formula satisfies this function. The set of formulas 〈M〉 becomes a set [M] of functions that are satisfied by formulas in (M) and are said to be superpositions over M. Set [M] is called the closure of set M. The specification of an actual model of many-valued logic is considered equivalent to the indication of sets E, M, 〈M〉 , and [M]; in this case, it is said that the model is generated by set M. This model is called a formula model and also an m- valued logic, where m denotes a cardinality of E.

The specific character of the approach of mathematical cybernetics to many-valued logic lies in its treatment of models of many-valued logic as control systems. In this approach, elementary functions are elements that perform definite operations. Formulas are interpreted as schemata constructed from elements; formulas also transform input information into output information. Control systems of this type, known in cybernetics as schemata of functional elements, are widely used to solve theoretical and practical problems in cybernetics. There are also a number of problems in logic and cybernetics that involve the study of the correspondences between sets M and [M] and in which the role of set (M) is somewhat obscured, being reduced to a method of generating [M] from M. In this case, another model of many-valued logic is necessary—that is, an algebra whose elements are functions that, like their arguments, take as their values elements from E. A special group of operations equivalent, in terms of the correspondences between M and [M], to the set of formulas constructed from functions in M —that is, to the derivation of complex functions from given functions by substituting particular functions for the arguments of other functions—is usually used in this algebra as the operations.

One of the problems characteristic of the formula model of many-valued logic is the description problem, that is, the problem of indicating for a given set M² ⊆ [M²] all formulas in 〈M₁〉 that satisfy functions in M₂. A special case of this problem is the important question in mathematical logic of indicating all formulas that satisfy a given constant, which in the propositional calculus is equivalent to the construction of all identically true propositions. The problem of transformations that preserve truth value, which is related to the description problem, is common to mathematical logic and algebra. In this case it is necessary to distinguish for a given set M, the simplest subset, in some sense, of pairs of equal formulas (that is, formulas that satisfy the same function) in 〈M〉; this subset makes it possible to obtain all formulas equal to a given formula by substituting one of the selected equal formulas for another. One of the most important problems for many-valued logic, also common to both mathematical logic and algebra, is the completeness problem, which consists in indicating all subsets M₁ of a given closed set M (that is, a set that coincides with its closure), for which [M₁] = M (that is, M₁ is complete in M). The description of the structure of closed classes of a given model of many-valued logic is a universal (or “pervasive”) problem in many-valued logic.

The problem of the complexity of systems, a problem characteristic of the theory of control systems, naturally arises in regard to formulas and functions from many-valued logic. A typical problem in this approach is that of the complexity of a realization [of a function]. A numerical measure (the complexity of formulas) is introduced in some way on the set of all elementary formulas and is then extended to the set of all formulas (for example, by summing the numbers of all elementary formulas that are used in the construction of a given formula). For a specified function, it is necessary to indicate the simplest formula that satisfies this function and has the least complexity; it is also necessary to explain how this complexity depends on certain properties of the given function. Various generalizations of this problem are being investigated.

A broad set of questions is associated with the satisfaction of functions by formulas with properties stipulated in advance. The problem of satisfying functions in the algebra of logic by disjunctive normal forms and the related problem of minimization are also important in this connection. Another problem involves the satisfaction of functions by formulas that are in some sense limited in depth, that is, by formulas in which the chain of substitutable formulas is limited in length, such a limitation being determined by the reliability and speed of calculations.

The solutions of all these problems essentially depend on the cardinality of the sets E and M that generate the given model of many-valued logic.

Among the most important examples of many-valued logic are finite-valued logics (that is, m-valued logics, where m is finite). The most thoroughly investigated case has been m = 2. A complete description of the structure of closed classes and the acquisition of important information on the problem of complexity problem realization is the most important result of work on the m = 2 problem. It has been established that when m > 2, there arise in finite-valued logics a number of features that substantially distinguish them from the two-valued case. These include the fact that the set of closed classes has the power of the continuum (when m = 2, they are infinite), features in the solution of the problem of the complexity of a realization, and a number of other problems. Finite-valued logics have produced an effective solution for the completeness problem for closed classes containing all functions with values in E. Work on the solution of the other problems in finite-valued logics has advanced to various degrees. The importance of finite-valued logics lies in their ability to describe the operation of the most varied actual computers and automata.

Other examples of many-valued logics include countably [infinite]-valued logics and power-of-the-continuum-valued logics (that is, m-valued logics whose cardinality m is countably infinite or has the power of the continuum, respectively). These models play an important role in mathematical logic, in the theory of models, and in mathematical analysis. Those algebras of functions, whose range of operations differs somewhat from the indicated range, are also sometimes classed as many-valued logics. As a rule, this is achieved by narrowing this range or by introducing certain [range of the] functions of a given many-valued logic into the operations.