Multi-valued logic
Encyclopedia
In logic
, a many-valued logic (also multi- or multiple-valued logic) is a propositional calculus
in which there are more than two truth values. Traditionally, in Aristotle
's logical calculus
, there were only two possible values (i.e., "true" and "false") for any proposition
. An obvious extension to classical two-valued logic is an n-valued logic for n greater than 2. Those most popular in the literature are three-valued (e.g., Łukasiewicz's and Kleene's
, which accept the values "true", "false", and "unknown"), the finite-valued with more than three values, and the infinite-valued, such as fuzzy logic
and probability logic
.
was Aristotle
(who, ironically, is also generally considered to be the first classical logician and the "father of logic"). Aristotle admitted that his laws did not all apply to future events (De Interpretatione, ch. IX), but he didn't create a system of multi-valued logic to explain this isolated remark. Until the coming of the 20th century, later logicians followed Aristotelian logic, which includes or assumes the law of the excluded middle.
The 20th century brought back the idea of multi-valued logic. The Polish logician and philosopher, Jan Łukasiewicz, began to create systems of many-valued logic in 1920, using a third value, "possible", to deal with Aristotle's paradox of the sea battle. Meanwhile, the American mathematician, Emil L. Post (1921), also introduced the formulation of additional truth degrees with n ≥ 2, where n are the truth values. Later, Jan Łukasiewicz and Alfred Tarski
together formulated a logic on n truth values where n ≥ 2. In 1932 Hans Reichenbach
formulated a logic of many truth values where n→infinity. Kurt Gödel
in 1932 showed that intuitionistic logic
is not a finitely-many valued logic, and defined a system of Gödel logics intermediate between classical
and intuitionistic logic; such logics are known as intermediate logics.
(¬), conjunction
(∧), disjunction (∨), implication (→K), and biconditional (↔K) are given by:
The difference between the two logics lies in how tautologies
are defined. In K3 only T is a designated truth value, while in P3 both T and I are. In Kleene's logic I can be interpreted as being "underdetermined", being neither true not false, while in Priest's logic I can be interpreted as being "overdetermined", being both true and false. K3 does not have any tautologies, while P3 has the same tautologies as classical two-valued logic.
K3 has additional connectives for conjunction (∧+), disjunction (∨+) and implication (→+):
, this property is "truth." In a valid argument, the truth of the derived proposition is guaranteed if the premises are jointly true, because the application of valid steps preserves the property. However, that property doesn't have to be that of "truth"; instead, it can be some other concept.
Multi-valued logics are intended to preserve the property of designationhood (or being designated). Since there are more than two truth values, rules of inference may be intended to preserve more than just whichever corresponds (in the relevant sense) to truth. For example, in a three-valued logic, sometimes the two greatest truth-values (when they are represented as e.g. positive integers) are designated and the rules of inference preserve these values. Precisely, a valid argument will be such that the value of the premises taken jointly will always be less than or equal to the conclusion.
For example, the preserved property could be justification, the foundational concept of intuitionistic logic
. Thus, a proposition is not true or false; instead, it is justified or flawed. A key difference between justification and truth, in this case, is that the law of excluded middle
doesn't hold: a proposition that is not flawed is not necessarily justified; instead, it's only not proven that it's flawed. The key difference is the determinacy of the preserved property: One may prove that P is justified, that P is flawed, or be unable to prove either. A valid argument preserves justification across transformations, so a proposition derived from justified propositions is still justified. However, there are proofs in classical logic that depend upon the law of excluded middle; since that law is not usable under this scheme, there are propositions that cannot be proven that way.
theory and fuzzy logic
. The notion of fuzzy subset was introduced by Lotfi Zadeh as a formalization of vagueness
; i.e., the phenomenon that a predicate may apply to an object not absolutely, but to a certain degree, and that there may be borderline cases. Indeed, as in multi-valued logic, fuzzy logic admits truth values different from "true" and "false". As an example, usually the set of possible truth values is the whole interval [0,1]. Nevertheless, the main difference between fuzzy logic and multi-valued logic is in the aims. In fact, in spite of its philosophical interest (it can be used to deal with the Sorites paradox
), fuzzy logic is devoted mainly to the applications. More precisely, there are two approaches to fuzzy logic. The first one is very closely linked with multi-valued logic tradition (Hajek school). So a set of designed values is fixed and this enables us to define an entailment
relation. The deduction apparatus is defined by a suitable set of logical axioms and suitable inference rules. Another approach (Goguen
, Pavelka and others) is devoted to defining a deduction apparatus in which approximate reasonings are admitted. Such an apparatus is defined by a suitable fuzzy subset of logical axioms and by a suitable set of fuzzy inference rules. In the first case the logical consequence operator gives the set of logical consequence of a given set of axioms. In the latter the logical consequence operator gives the fuzzy subset of logical consequence of a given fuzzy subset of hypotheses.
Philosophical logic
Digital logic
Specific
Logic
In philosophy, Logic is the formal systematic study of the principles of valid inference and correct reasoning. Logic is used in most intellectual activities, but is studied primarily in the disciplines of philosophy, mathematics, semantics, and computer science...
, a many-valued logic (also multi- or multiple-valued logic) is a propositional calculus
Propositional calculus
In mathematical logic, a propositional calculus or logic is a formal system in which formulas of a formal language may be interpreted as representing propositions. A system of inference rules and axioms allows certain formulas to be derived, called theorems; which may be interpreted as true...
in which there are more than two truth values. Traditionally, in Aristotle
Aristotle
Aristotle was a Greek philosopher and polymath, a student of Plato and teacher of Alexander the Great. His writings cover many subjects, including physics, metaphysics, poetry, theater, music, logic, rhetoric, linguistics, politics, government, ethics, biology, and zoology...
's logical calculus
Term logic
In philosophy, term logic, also known as traditional logic or aristotelian logic, is a loose name for the way of doing logic that began with Aristotle and that was dominant until the advent of modern predicate logic in the late nineteenth century...
, there were only two possible values (i.e., "true" and "false") for any proposition
Proposition
In logic and philosophy, the term proposition refers to either the "content" or "meaning" of a meaningful declarative sentence or the pattern of symbols, marks, or sounds that make up a meaningful declarative sentence...
. An obvious extension to classical two-valued logic is an n-valued logic for n greater than 2. Those most popular in the literature are three-valued (e.g., Łukasiewicz's and Kleene's
Stephen Cole Kleene
Stephen Cole Kleene was an American mathematician who helped lay the foundations for theoretical computer science...
, which accept the values "true", "false", and "unknown"), the finite-valued with more than three values, and the infinite-valued, such as fuzzy logic
Fuzzy logic
Fuzzy logic is a form of many-valued logic; it deals with reasoning that is approximate rather than fixed and exact. In contrast with traditional logic theory, where binary sets have two-valued logic: true or false, fuzzy logic variables may have a truth value that ranges in degree between 0 and 1...
and probability logic
Probabilistic logic
The aim of a probabilistic logic is to combine the capacity of probability theory to handle uncertainty with the capacity of deductive logic to exploit structure. The result is a richer and more expressive formalism with a broad range of possible application areas...
.
History
The first known classical logician who didn't fully accept the law of excluded middleLaw of excluded middle
In logic, the law of excluded middle is the third of the so-called three classic laws of thought. It states that for any proposition, either that proposition is true, or its negation is....
was Aristotle
Aristotle
Aristotle was a Greek philosopher and polymath, a student of Plato and teacher of Alexander the Great. His writings cover many subjects, including physics, metaphysics, poetry, theater, music, logic, rhetoric, linguistics, politics, government, ethics, biology, and zoology...
(who, ironically, is also generally considered to be the first classical logician and the "father of logic"). Aristotle admitted that his laws did not all apply to future events (De Interpretatione, ch. IX), but he didn't create a system of multi-valued logic to explain this isolated remark. Until the coming of the 20th century, later logicians followed Aristotelian logic, which includes or assumes the law of the excluded middle.
The 20th century brought back the idea of multi-valued logic. The Polish logician and philosopher, Jan Łukasiewicz, began to create systems of many-valued logic in 1920, using a third value, "possible", to deal with Aristotle's paradox of the sea battle. Meanwhile, the American mathematician, Emil L. Post (1921), also introduced the formulation of additional truth degrees with n ≥ 2, where n are the truth values. Later, Jan Łukasiewicz and Alfred Tarski
Alfred Tarski
Alfred Tarski was a Polish logician and mathematician. Educated at the University of Warsaw and a member of the Lwow-Warsaw School of Logic and the Warsaw School of Mathematics and philosophy, he emigrated to the USA in 1939, and taught and carried out research in mathematics at the University of...
together formulated a logic on n truth values where n ≥ 2. In 1932 Hans Reichenbach
Hans Reichenbach
Hans Reichenbach was a leading philosopher of science, educator and proponent of logical empiricism...
formulated a logic of many truth values where n→infinity. Kurt Gödel
Kurt Gödel
Kurt Friedrich Gödel was an Austrian logician, mathematician and philosopher. Later in his life he emigrated to the United States to escape the effects of World War II. One of the most significant logicians of all time, Gödel made an immense impact upon scientific and philosophical thinking in the...
in 1932 showed that intuitionistic logic
Intuitionistic logic
Intuitionistic logic, or constructive logic, is a symbolic logic system differing from classical logic in its definition of the meaning of a statement being true. In classical logic, all well-formed statements are assumed to be either true or false, even if we do not have a proof of either...
is not a finitely-many valued logic, and defined a system of Gödel logics intermediate between classical
Classical logic
Classical logic identifies a class of formal logics that have been most intensively studied and most widely used. The class is sometimes called standard logic as well...
and intuitionistic logic; such logics are known as intermediate logics.
Kleene (K3) and Priest logic (P3)
Kleene's "(strong) logic of indeterminacy" K3 and Priest's "logic of paradox" add a third "undefined" or "indeterminate" truth value I. The truth functions for negationNegation
In logic and mathematics, negation, also called logical complement, is an operation on propositions, truth values, or semantic values more generally. Intuitively, the negation of a proposition is true when that proposition is false, and vice versa. In classical logic negation is normally identified...
(¬), conjunction
Conjunction
Conjunction can refer to:* Conjunction , an astronomical phenomenon* Astrological aspect, an aspect in horoscopic astrology* Conjunction , a part of speech** Conjunctive mood , same as subjunctive mood...
(∧), disjunction (∨), implication (→K), and biconditional (↔K) are given by:
|
|
|
|
|
The difference between the two logics lies in how tautologies
Tautology
Tautology may refer to:*Tautology , using different words to say the same thing even if the repetition does not provide clarity. Tautology also means a series of self-reinforcing statements that cannot be disproved because the statements depend on the assumption that they are already...
are defined. In K3 only T is a designated truth value, while in P3 both T and I are. In Kleene's logic I can be interpreted as being "underdetermined", being neither true not false, while in Priest's logic I can be interpreted as being "overdetermined", being both true and false. K3 does not have any tautologies, while P3 has the same tautologies as classical two-valued logic.
K3 has additional connectives for conjunction (∧+), disjunction (∨+) and implication (→+):
|
|
Belnap logic (B4)
Belnap's logic B4 combines K3 and P3. The overdetermined truth value is here denoted as B and the underdetermined truth value as N.
|
|
|
||
Relation to classical logic
Logics are usually systems intended to codify rules for preserving some semantic property of propositions across transformations. In classical logicLogic
In philosophy, Logic is the formal systematic study of the principles of valid inference and correct reasoning. Logic is used in most intellectual activities, but is studied primarily in the disciplines of philosophy, mathematics, semantics, and computer science...
, this property is "truth." In a valid argument, the truth of the derived proposition is guaranteed if the premises are jointly true, because the application of valid steps preserves the property. However, that property doesn't have to be that of "truth"; instead, it can be some other concept.
Multi-valued logics are intended to preserve the property of designationhood (or being designated). Since there are more than two truth values, rules of inference may be intended to preserve more than just whichever corresponds (in the relevant sense) to truth. For example, in a three-valued logic, sometimes the two greatest truth-values (when they are represented as e.g. positive integers) are designated and the rules of inference preserve these values. Precisely, a valid argument will be such that the value of the premises taken jointly will always be less than or equal to the conclusion.
For example, the preserved property could be justification, the foundational concept of intuitionistic logic
Intuitionistic logic
Intuitionistic logic, or constructive logic, is a symbolic logic system differing from classical logic in its definition of the meaning of a statement being true. In classical logic, all well-formed statements are assumed to be either true or false, even if we do not have a proof of either...
. Thus, a proposition is not true or false; instead, it is justified or flawed. A key difference between justification and truth, in this case, is that the law of excluded middle
Law of excluded middle
In logic, the law of excluded middle is the third of the so-called three classic laws of thought. It states that for any proposition, either that proposition is true, or its negation is....
doesn't hold: a proposition that is not flawed is not necessarily justified; instead, it's only not proven that it's flawed. The key difference is the determinacy of the preserved property: One may prove that P is justified, that P is flawed, or be unable to prove either. A valid argument preserves justification across transformations, so a proposition derived from justified propositions is still justified. However, there are proofs in classical logic that depend upon the law of excluded middle; since that law is not usable under this scheme, there are propositions that cannot be proven that way.
Relation to fuzzy logic
Multi-valued logic is closely related to fuzzy setFuzzy set
Fuzzy sets are sets whose elements have degrees of membership. Fuzzy sets were introduced simultaneously by Lotfi A. Zadeh and Dieter Klaua in 1965 as an extension of the classical notion of set. In classical set theory, the membership of elements in a set is assessed in binary terms according to...
theory and fuzzy logic
Fuzzy logic
Fuzzy logic is a form of many-valued logic; it deals with reasoning that is approximate rather than fixed and exact. In contrast with traditional logic theory, where binary sets have two-valued logic: true or false, fuzzy logic variables may have a truth value that ranges in degree between 0 and 1...
. The notion of fuzzy subset was introduced by Lotfi Zadeh as a formalization of vagueness
Vagueness
The term vagueness denotes a property of concepts . A concept is vague:* if the concept's extension is unclear;* if there are objects which one cannot say with certainty whether belong to a group of objects which are identified with this concept or which exhibit characteristics that have this...
; i.e., the phenomenon that a predicate may apply to an object not absolutely, but to a certain degree, and that there may be borderline cases. Indeed, as in multi-valued logic, fuzzy logic admits truth values different from "true" and "false". As an example, usually the set of possible truth values is the whole interval [0,1]. Nevertheless, the main difference between fuzzy logic and multi-valued logic is in the aims. In fact, in spite of its philosophical interest (it can be used to deal with the Sorites paradox
Sorites paradox
The sorites paradox is a paradox that arises from vague predicates. The paradox of the heap is an example of this paradox which arises when one considers a heap of sand, from which grains are individually removed...
), fuzzy logic is devoted mainly to the applications. More precisely, there are two approaches to fuzzy logic. The first one is very closely linked with multi-valued logic tradition (Hajek school). So a set of designed values is fixed and this enables us to define an entailment
Entailment
In logic, entailment is a relation between a set of sentences and a sentence. Let Γ be a set of one or more sentences; let S1 be the conjunction of the elements of Γ, and let S2 be a sentence: then, Γ entails S2 if and only if S1 and not-S2 are logically inconsistent...
relation. The deduction apparatus is defined by a suitable set of logical axioms and suitable inference rules. Another approach (Goguen
Joseph Goguen
Joseph Amadee Goguen was a computer science professor in the Department of Computer Science and Engineering at the University of California, San Diego, USA, who helped develop the OBJ family of programming languages. He was author of A Categorical Manifesto and founder and Editor-in-Chief of the...
, Pavelka and others) is devoted to defining a deduction apparatus in which approximate reasonings are admitted. Such an apparatus is defined by a suitable fuzzy subset of logical axioms and by a suitable set of fuzzy inference rules. In the first case the logical consequence operator gives the set of logical consequence of a given set of axioms. In the latter the logical consequence operator gives the fuzzy subset of logical consequence of a given fuzzy subset of hypotheses.
Research venues
An IEEE International Symposium on Multiple-Valued Logic (ISMVL) has been held annually since 1970. It mostly caters to applications in digital design and verification. The exists the Journal of Multiple-Valued Logic and Soft Computing.See also
Mathematical logic- Fuzzy logicFuzzy logicFuzzy logic is a form of many-valued logic; it deals with reasoning that is approximate rather than fixed and exact. In contrast with traditional logic theory, where binary sets have two-valued logic: true or false, fuzzy logic variables may have a truth value that ranges in degree between 0 and 1...
- Gödel logics
- Kleene logic (Kleene algebraKleene algebraIn mathematics, a Kleene algebra is either of two different things:* A bounded distributive lattice with an involution satisfying De Morgan's laws , additionally satisfying the inequality x∧−x ≤ y∨−y. Kleene algebras are subclasses of Ockham algebras...
) - Łukasiewicz logic (MV-algebraMV-algebraIn abstract algebra, a branch of pure mathematics, an MV-algebra is an algebraic structure with a binary operation \oplus, a unary operation \neg, and the constant 0, satisfying certain axioms...
) - Post logic
- Relevance logicRelevance logicRelevance logic, also called relevant logic, is a kind of non-classical logic requiring the antecedent and consequent of implications be relevantly related. They may be viewed as a family of substructural or modal logics...
- Degrees of truth
- Principle of bivalencePrinciple of bivalenceIn logic, the semantic principle of bivalence states that every declarative sentence expressing a proposition has exactly one truth value, either true or false...
Philosophical logic
- False dilemmaFalse dilemmaA false dilemma is a type of logical fallacy that involves a situation in which only two alternatives are considered, when in fact there are additional options...
- MuMu (negative)or Wu , is a word which has been translated variously as "not", "nothing", "without", "nothingness", "non existent", "non being", or evocatively simply as "no thing"...
Digital logic
- IEEE 1164IEEE 1164The IEEE 1164 standard defines a package design unit that contains declarations that support a uniform representation of a logic value in a VHDL hardware description....
a nine-valued standard for VHDL - IEEE 1364 a four-valued standard for VerilogVerilogIn the semiconductor and electronic design industry, Verilog is a hardware description language used to model electronic systems. Verilog HDL, not to be confused with VHDL , is most commonly used in the design, verification, and implementation of digital logic chips at the register-transfer level...
- Noise-based logicNoise-based logicNoise-based logic is a new class of multivalued deterministic logic schemes where the logic values and bits are represented by different realizations of a stochastic process...
Further reading
General- Béziau J.-Y. 1997 What is many-valued logic ? Proceedings of the 27th International Symposium on Multiple-Valued Logic, IEEE Computer Society, Los Alamitos, pp. 117–121.
- Malinowski, Gregorz, 2001, Many-Valued Logics, in Goble, Lou, ed., The Blackwell Guide to Philosophical Logic. Blackwell.
- Cignoli, R. L. O., D'Ottaviano, I, M. L., Mundici, D., 2000. Algebraic Foundations of Many-valued Reasoning. Kluwer.
- S. GottwaldSiegfried GottwaldSiegfried Johannes Gottwald is a German mathematician, logician and historian of science.- Life and work :...
, A Treatise on Many-Valued Logics. Studies in Logic and Computation, vol. 9, Research Studies Press: Baldock, Hertfordshire, England, 2001.|volume=12}} - Hájek P.Petr HájekPetr Hájek is a Czech scientist in the area of mathematical logic and a professor of mathematics. He works at the Institute of Computer Science at the Academy of Sciences of the Czech Republic and worked as a lecturer at the Faculty of Mathematics and Physics at the Charles University in Prague...
, 1998, Metamathematics of fuzzy logic. Kluwer. (Fuzzy logic understood as many-valued logic sui generisSui generisSui generis is a Latin expression, literally meaning of its own kind/genus or unique in its characteristics. The expression is often used in analytic philosophy to indicate an idea, an entity, or a reality which cannot be included in a wider concept....
.)
Specific
- Alexandre Zinoviev, Philosophical Problems of Many-Valued Logic, D. Reidel Publishing Company, 169p., 1963.
- Prior A. 1957, Time and Modality. Oxford University Press, based on his 1956 John LockeJohn LockeJohn Locke FRS , widely known as the Father of Liberalism, was an English philosopher and physician regarded as one of the most influential of Enlightenment thinkers. Considered one of the first of the British empiricists, following the tradition of Francis Bacon, he is equally important to social...
lectures - Goguen J.A. 1968/69, The logic of inexact concepts, Synthese, 19, 325–373.
- Chang C.C. and Keisler H. J. 1966. Continuous Model Theory, Princeton, Princeton University Press.
- Gerla G. 2001, Fuzzy logic: Mathematical Tools for Approximate Reasoning, Kluwer Academic Publishers, Dordrecht.
- Pavelka J. 1979, On fuzzy logic I: Many-valued rules of inference, Zeitschr. f. math. Logik und Grundlagen d. Math., 25, 45–52. Covers proof theory of many-valued logics as well, in the tradition of Hájek.
External links
- Stanford Encyclopedia of PhilosophyStanford Encyclopedia of PhilosophyThe Stanford Encyclopedia of Philosophy is a freely-accessible online encyclopedia of philosophy maintained by Stanford University. Each entry is written and maintained by an expert in the field, including professors from over 65 academic institutions worldwide...
: "Truth Values" -- by Yaroslav Shramko and Heinrich Wansing. - IEEE Computer SocietyIEEE Computer SocietyThe IEEE Computer Society is a professional society of IEEE. Its purpose and scope is “to advance the theory, practice, and application of computer and information processing science and technology” and the “professional standing of its members.” The CS is the largest of 38 technical societies...
's Technical Committee on Multiple-Valued Logic - Resources for Many-Valued Logic by Reiner Hähnle, Chalmers University
- Many-valued Logics W3 Server (archived)