This is a file in the archives of the Stanford Encyclopedia of Philosophy. 
version history

Stanford Encyclopedia of PhilosophyA  B  C  D  E  F  G  H  I  J  K  L  M  N  O  P  Q  R  S  T  U  V  W  X  Y  Z

last substantive content change

Manyvalued logics are nonclassical logics. They are similar to classical logic because they accept the principle of truthfunctionality, namely, that the truth of a compound sentence is determined by the truth values of its component sentences (and so remains unaffected when one of its component sentences is replaced by another sentence with the same truth value). But they differ from classical logic by the fundamental fact that they do not restrict the number of truth values to only two: they allow for a larger set W of truth degrees.
Just as the notion of ‘possible worlds’ in the semantics of modal logic can be reinterpreted (e.g., as ‘moments of time’ in the semantics of tense logic or as ‘states’ in the semantics of dynamic logic), there does not exist a standard interpretation of the truth degrees. How they are to be understood depends on the actual field of application. It is general usage, however, to assume that there are two particular truth degrees, usually denoted by "0" and "1", respectively, which act like the traditional truth values "falsum" and "verum".
The formalized languages for systems of manyvalued logic (MVL) follow the two standard patterns for propositional and predicate logic, respectively:
As usual in logic, these languages are the basis for semantically as well as syntactically founded systems of logic.
There are two kinds of semantics for systems of manyvalued logic.
We discuss these in turn.
The most suitable way of defining a system S of manyvalued logic is to fix the characteristic logical matrix for its language, i.e. to fix:
and additionally,
A wellformed formula A of a propositional language counts as valid under some valuation α (which maps the set of propositional variables into the set of truth degrees) iff it has a designated truth degree under α. And A is logically valid or a tautology iff it is valid under all valuations.
In the case of a firstorder language, such a wellformed formula A counts as valid under an interpretation α of the language iff it has a designated truth degree under this interpretation and all assignments of objects from the universe of discourse of this interpretation to the object variables. A counts as logically valid iff it is valid under all interpretations.
Like in classical logic, such an interpretation has to provide
A model of some set Σ of wellformed formulas is a valuation α or an interpretation α such that all A ∈ Σ are valid under α . That Σ entails A means that each model of Σ is also a model of A.
There is a second type of semantics for systems S of manyvalued logic which is based on a whole characteristic class K of (similar) algebraic structures. Each such algebraic structure has to provide all the data which have to be provided by a characteristic logical matrix for the language of S.
The notion of validity of a formula A with respect to an algebraic structure from K is defined as if this structure would form a logical matrix. And logical validity here means validity for all structures from the class K.
The type of algebraic structures which may form such a characteristic class K for some system S of MVL is usually determined by the (syntactical or semantical) Lindenbaum algebra of S, and often plays also a crucial role within an algebraic completeness proof. The algebraic structures in K have a similar role for S as the Boolean algebras do for classical logic.
For particular systems of MVL one has e.g. the following characteristic classes of algebraic structures:
From a philosophical point of view, it would be preferable to have a semantic foundation for a system of MVL which uses a characteristic logical matrix. However, from a formal point of view, both approaches are equally important, and the algebraic semantics turns out to be the more general approach.
The main types of logical calculi are all available for systems of MVL:
However, some of the above are available only for finitely valued systems.
For finitely valued systems, particularly mvalued ones, there are also sequent calculi which work with generalized sequents. In the mvalued case, these are sequences of length m of sets of formulas.
Tableau calculi with signed formulas are usually restricted to finitevalued systems of MVL, so that they can be dealt with in an effective way.
The main systems of MVL often come as families which comprise uniformly defined finitevalued as well as infinitevalued systems. Here is a list:
The systems L_{m} and L_{∞} are defined by the logical matrix which has either some finite set
W_{m} = {k/m−1  0 ≤ k ≤ m−1}
of rationals within the real unit interval, or the whole unit interval
W_{∞} = [0,1] = {x ∈ R  0 ≤ x ≤ 1}
as the truth degree set. The degree 1 is the only designated truth degree.
The main connectives of these systems are a strong and a weak conjunction, & and , respectively, given by the truth degree functions
u & v = max {0, u + v−1},
u v = min {u, v},
a negation connective ¬ determined by
¬u = 1−u,
and an implication connective → with truth degree function
u → v = min {1, 1−u + v}.
Often, two disjunction connectives are also used. These are defined in terms of & and , respectively, via the usual de Morgan laws using ¬. For the firstorder Łukasiewicz systems one adds two quantifiers ∀, ∃in such a way that the truth degree of ∀xH(x) is the infimum of all the relevant truth degrees of H(x), and that the truth degree of ∃xH(x) is the supremum of all the relevant truth degrees of H(x).
The systems G_{m} and G_{∞} are defined by the logical matrix which has either some finite set
W_{m} = {k/m−1  0 ≤ k ≤ m−1}
of rationals within the real unit interval, or the whole unit interval
W_{∞} = [0,1] = {x ∈ R  0 ≤ x ≤ 1}
as the truth degree set. The degree 1 is the only designated truth degree.
The main connectives of these systems are a conjunction and a disjunction determined by the truth degree functions
u v = min {u, v},
u v = max {u, v},
an implication connective → with truth degree function
u→v u≤v 1 u>v v
and a negation connective ~ with truth degree function
~u u=0 1 u≠0 0
For the firstorder Gödel systems one adds two quantifiers ∀, ∃in such a way that the truth degree of ∀xH(x) is the infimum of all the relevant truth degrees of H(x), and that the truth degree of ∃xH(x) is the supremum of all the relevant truth degrees of H(x).
For infinite valued systems with truth degree set
W_{∞} = [0,1] = {x ∈ R  0 ≤ x ≤ 1}
the influence of fuzzy set theory quite recently initiated the study of a whole class of such systems of MVL.
These systems are basically determined by a (possibly nonidempotent) strong conjunction connective &_{T} which has as corresponding truth degree function a tnorm T, i.e. a binary operation T in the unit interval which is associative, commutative, nondecreasing, and has the degree 1 as a neutral element:
For all those tnorms which have the suppreservation property
T(u, sup_{i} v_{i}) = sup_{i} T(u,v_{i}),
there is a standard way to introduce a related implication connective →_{T} with the truth degree function
u →_{T} v = sup {z  T(u,z) ≤ v}.
This implication connective is connected with the tnorm T by the crucial adjointness condition
T(u,v) ≤ w u ≤ (v →_{T} w),
which determines →_{T} uniquely for each T with suppreservation property.
The language is further enriched with a negation connective, − _{T}, determined by the truth degree function
− _{T} u = u →_{T} 0.
This forces the language to have also a truth degree constant 0 to denote the truth degree 0 because then − _{T} becomes a definable connective.
Usually one adds as two further connectives a (weak) conjunction and a disjunction with truth degree functions.
u v = min {u, v},
u v = max {u, v}.
For tnorms which are continuous functions (in the standard sense of continuity for real functions of two variables) these additional connectives become even definable. Suitable definitions are
min {u,v} = T(u, (u →_{T} v)) ,
max {u,v} = min { ((u →_{T} v) →_{T} v) , ((v →_{T} u) →_{T} u) } .
Particular cases of such tnorm related systems are the infinite valued Łukasiewicz and Gödel systems L_{∞}, G_{∞}, and also the product logic which has the usual arithmetic product as its basic tnorm.
The class of all tnorms is very large, and up to now not really well understood. Even for those tnorms which have the suppreservation property (and which are also called “left continuous tnorms”) the structural understanding is far from complete, but much better as for the general case: a discussion of the recent state of the art is given by Jenei (2004). Sufficiently well understood is only the further subclass of continuous tnorms: they are nicely composed out of isomorphic copies of the Łukasiewicz tnorm, the product tnorm, and the Gödel tnorm, i.e. the minoperation, as explained e.g. in Gottwald (2001).
Actually one is able to axiomatize tnorm based systems for some particular classes of tnorms. As a fundamental result, Hájek (1998) has given an axiomatization of the logic which has, as conjectured by Hajek and proved in Cignoli/Esteva/Godo/Torrens (2000), as its algebraic semantics the class of all tnorm based structures whose tnorm is a continuous function. Based upon this work, Esteva and Godo (2001) conjectured an axiomatization for the logic of all tnorms which have the suppreservation property, and Jenei/Montagna (2002) proved that this really is an adequate axiomatization.
The axiomatization of further tnorm based systems, as well as the question for tnorm based quantifiers, are recent research problems. The main focus is given by the following two aspects which concern modifications of the expressive power of these tnorm based systems: (i) strengthenings of this expressibility by forming systems with additional negation operators or with multiple tnorm based conjunction operations; (ii) modifications of this expressibility e.g. by deleting the truth degree constant 0 from the language, but adding an implication connective to the basic vocabulary, and (iii) generalizations which modify the basic tnorms into noncommutative “pseudotnorms” and thus lead to logics with noncommutative conjunction connectives. A survey for those developments, restricted to the case of propositional systems, is given by Gottwald/Hájek (200x).
3valued systems seem to be particularly simple cases which offer intuitive interpretations of the truth degrees; these systems include only one additional degree besides the classical truth values.
The mathematician and logician Kleene used a third truth degree for "undefined" in the context of partial recursive functions. His connectives were the negation, the weak conjunction, and the weak disjunction of the 3valued Łukasiewicz system together with a conjunction _{+} and an implication →_{+} determined by truth degree functions with the following function tables:
_{+} 0 ½ 1 0 0 ½ 0 ½ ½ ½ ½ 1 0 ½ 1
→_{+} 0 ½ 1 0 1 1 1 ½ ½ ½ ½ 1 0 ½ 1
Here ½ is the third truth degree "undefined". In this Kleene system, the degree 1 is the only designated truth degree.
Blau (1978) used a different system as an inherent logic of natural language. In Blau's system, both degrees 1 and ½ are designated. Other interpretations of the third truth degree ½, for example as "senseless", "undetermined", or "paradoxical", motivated the study of other 3valued systems.
This particularly interesting system of MVL was the result of research on relevance logic, but it also has significance for computer science applications. Its truth degree set may be taken as
W* = {Ø, {⊥}, {}, {⊥, }},
and the truth degrees interpreted as indicating (e.g. with respect to a database query for some particular state of affairs) that there is
This set of truth degrees has two natural (lattice) orderings:
Given the inf and the sup under the truth ordering, there are truth degree functions for a conjunction and a disjunction connective. A negation is, in a natural way, determined by a truth degree function which exchanges the degrees {⊥ } and {}, and which leaves the degrees {⊥ , } and Ø fixed.
Actually, there is no standard candidate for a implication connective, and the choice of the designated truth degrees depends on the intended applications:
The choice of suitable entailment relations is still an open research topic.
The general problem of finding an intuitive understanding of the truth degrees occasionally has a nice solution: one can consider them as comprising different aspects of the evaluation of sentences. In such a case of, say, k different aspects the truth degrees may be chosen as ktuples of values which evaluate the single aspects. (And these, e.g., may be standard truth values.)
The truth degree functions over such ktuples additionally can be defined "componentwise" from truth degree (or: truth value) functions for the values of the single components. In this manner, k logical systems may be combined into one manyvalued product system.
In this way, the truth degrees of Dunn/Belnap's 4valued system can be considered as evaluating two aspects of a state of affairs (SOA) related to a database:
Both aspects can use standard truth values for this evaluation.
In this case, the conjunction, disjunction, and negation of Dunn/Belnap's 4valued system are componentwise definable by conjunction, disjunction, or negation, respectively, of classical logic, i.e. this 4valued system is a product of two copies of classical twovalued logic.
Manyvalued logic was motivated in part by philosophical goals which were never achieved, and in part by formal considerations concerning functional completeness. In the earlier years of development, this caused some doubts about the usefulness of MVL. In the meantime, however, interesting applications were found in diverse fields. Some of these shall now be mentioned.
It is not a simple task to understand the propositional treatment of such sentences, e.g. to give criteria for forming their negation, or understanding the truth conditions of implications.
One type of solution for these problems refers to the use of many truth degrees, e.g. to product systems with ordered pairs as truth degrees: meaning that their components evaluate in parallel whether the presupposition is met, and whether the sentence is true or false. But 3valued approaches have also been discussed.
A second type of application to logic is the merging of different types of logical systems, e.g. the formulation of systems with graded modalities. Melvin Fitting (1991/92) considers systems that define such modalities by merging modal and manyvalued logic, with intended applications to problems of Artificial Intelligence.
A third type of application to logic is the modeling of partial predicates and truth value gaps. However, this is possible only in so far as these truth value gaps behave "truth functionally", i.e. in so far as the behavior of the truth value gaps in compound sentences can be described by suitable truth functions. (This is not always the case, e.g. it is not the case in formulations which use supervaluations.)
Based upon this idea, a reasonable theory of such languages which contain truth predicates was developed in the mid1930s by A. Tarski. One of the results was that such a language L_{T}, which contains its own truth predicate T and has a certain richness in expressive power, is necessarily inconsistent.
Another approach toward such languages L_{T} which contain their own truth predicate T was offered by S. Kripke (1975) and is essentially based upon the idea of considering T as a partial predicate, i.e. as a predicate which has "truth value gaps". In a case Kripke (1975) considers, these truth value gaps behave "truth functionally" and so can be treated like a third truth degree. Their propagation in compound sentences then becomes describable by suitable truth degree functions of threevalued systems. In Kripke's (1975) approach this reference was to threevalued systems which S. C. Kleene (1938) had considered in the (mathematical) context of partial functions and predicates in recursion theory.
A second application of MVL inside philosophy is to the old paradoxes like the Sorites (heap) or the falakros (bald man). (See the entry Sorites paradox.) In the case of the Sorites, the paradox is as follows:
(i) One grain of sand is not a heap of sand. And (ii) adding one grain of sand to something which is not a heap does not turn it into a heap. Hence (iii) a single grain of sand can never turn into a heap of sand, no matter how many grains of sand are added to it.
Thus the true premise (i) gives a false conclusion (iii) via a sequence of inferences using (ii). A rather natural solution inside an extension of MVL with a graded notion of inference, often called fuzzy logic, is to take the notion of heap as a vague one, i.e. as a notion which may hold true of given objects only to some (truth) degree. Additionally it is suitable to consider premise (ii) as only partially true, however to a degree which is quite near to the maximal degree 1. Then each single inference step is of the form:
However, this inference has to involve truth degrees for the premises (a) and (ii), and has to provide a truth degree for the conclusion (b). The crucial idea for the modeling of this type of reasoning inside MVL is to make sure that the truth degree for (b) is smaller than the truth degree for (a) in case the truth degree for (ii) is smaller than the maximal one. In effect, then, the sentence n grains of sand do not make a heap tends toward being false for an increasing number n of grains.
A first area of application concerns vague notions and commonsense reasoning, e.g. in expert systems. Both topics are modeled via fuzzy sets and fuzzy logic, and these refer to suitable systems of MVL. Also, in databases and in knowledgebased systems one likes to store vague information.
A second area of application is strongly tied with this first one: the automatization of data and knowledge mining. Here clustering methods come into consideration; these refer via unsharp clusters to fuzzy sets and MVL. In this context one is also interested in automated theorem proving techniques for systems of MVL, as well as in methods of logic programming for systems of MVL.
Manyvalued logic as a separate subject was created by the Polish logician and philosopher Łukasiewicz (1920), and developed first in Poland. His first intention was to use a third, additional truth value for "possible", and to model in this way the modalities "it is necessary that" and "it is possible that". This intended application to modal logic did not materialize. The outcome of these investigations are, however, the Łukasiewicz systems, and a series of theoretical results concerning these systems.
Essentially parallel to the Łukasiewicz approach, the American mathematician Post (1921) introduced the basic idea of additional truth degrees, and applied it to problems of the representability of functions.
Later on, Gödel (1932) tried to understand intuitionistic logic in terms of many truth degrees. The outcome was the family of Gödel systems, and a result, namely, that intuitionistic logic does not have a characteristic logical matrix with only finitely many truth degrees. A few years later, Jaskowski (1936) constructed an infinite valued characteristic matrix for intuitionistic logic. It seems, however, that the truth degrees of this matrix do not have a nice and simple intuitive interpretation.
A philosophical application of 3valued logic to the discussion of paradoxes was proposed by the Russian logician Bochvar (1938), and a mathematical one to partial function and relations by the American logician Kleene (1938). Much later Kleene's connectives also became philosophically interesting as a technical tool to determine fixed points in the revision theory of truth initiated by Kripke (1975).
The 1950s saw (i) an analytical characterization of the class of truth degree functions definable in the infinite valued propositional Łukasiewicz system by McNaughton (1951), (ii) a completeness proof for the same system by Chang (1958, 1959) introducing the notion of MValgebra and a more traditional one by Rose/Rosser (1958), as well as (iii) a completeness proof for the infinite valued propositional Gödel system by Dummett (1959). The 1950s also saw an approach of Skolem (1957) toward proving the consistency of set theory in the realm of infinite valued logic.
In the 1960s, Scarpellini (1962) made clear that the firstorder infinite valued Łukasiewicz system is not (recursively) axiomatizable. Hay (1963) as well as Belluce/Chang (1963) proved that the addition of one infinitary inference rule leads to an axiomatization of L_{∞}. And Horn (1969) presented a completeness proof for firstorder infinite valued Gödel logic. Besides these developments inside pure manyvalued logic, Zadeh (1965) started an (application oriented) approach toward the formalization of vague notions by generalized set theoretic means, which soon was related by Goguen (1968/69) to philosophical applications, and which later on inspired also a lot of theoretical considerations inside MVL.
The 1970s mark a period of restricted activity in pure manyvalued logic. There was, however, a lot of work in the closely related area of (computer science) applications of vague notions formalized as fuzzy sets, initiated e.g. by Zadeh (1975, 1979). And there was an important extension of MVL by a graded notion of inference and entailment in Pavelka (1979).
In the 1980s, fuzzy sets and their applications remained a hot topic that called for theoretical foundations by methods of manyvalued logic. In addition, there were the first complexity results e.g. concerning the set of logically valid formulas in firstorder infinite valued Łukasiewicz logic, by Ragaz (1983). Mundici (1986) started a deeper study of MValgebras.
These trends have continued since the 1980s. Research has included applications of MVL to fuzzy set theory and their applications, detailed investigations of algebraic structures related to systems of MVL, the study of graded notions of entailment, and investigations into complexity issues for different problems in systems of MVL. This research was complemented by interesting work on proof theory, on automated theorem proving, by different applications in artificial intelligence matters, and by a detailed study of infinite valued systems based on tnorms – which now often are called (mathematical) fuzzy logics.
Siegfried Gottwald gottwald@rz.unileipzig.de 
A  B  C  D  E  F  G  H  I  J  K  L  M  N  O  P  Q  R  S  T  U  V  W  X  Y  Z