Many-valued logic

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. Classical two-valued logic may be extended to "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 (finitely-many valued) with more than three values, and the infinite-valued (infinitely-many-valued), such as fuzzy logic and probability logic.
History.
The first known classical logician who did not fully accept the law of excluded middle 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"→∞. 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.
Examples.
Kleene (strong) and Priest logic.
Kleene's "(strong) logic of indeterminacy" (sometimes formula_1) and Priest's "logic of paradox" add a third "undefined" or "indeterminate" truth value . The truth functions for negation (¬), conjunction (∧), disjunction (∨), implication (), and biconditional () are given by:
The difference between the two logics lies in how tautologies are defined. In only is a "designated truth value", while in both and are (a logical formula is considered a tautology if it evaluates to a designated truth value). In Kleene's logic can be interpreted as being "underdetermined", being neither true nor false, while in Priest's logic can be interpreted as being "overdetermined", being both true and false. does not have any tautologies, while has the same tautologies as classical two-valued logic.
Bochvar's internal three-valued logic.
Another logic is Bochvar's "internal" three-valued logic formula_2, also called Kleene's weak three-valued logic. Except for negation and biconditional, its truth tables are all different from the above.
The intermediate truth value in Bochvar's "internal" logic can be described as "contagious" because it propagates in a formula regardless of the value of any other variable.
Belnap logic ().
Belnap's logic combines and . The overdetermined truth value is here denoted as "B" and the underdetermined truth value as "N".
Gödel logics "Gk" and "G"∞.
In 1932 Gödel defined a family formula_3 of many-valued logics, with finitely many truth values formula_4, for example formula_5 has the truth values formula_6 and formula_7 has formula_8. In a similar manner he defined a logic with infinitely many truth values, formula_9, in which the truth values are all the real numbers in the interval formula_10. The designated truth value in these logics is 1.
The conjunction formula_11 and the disjunction formula_12 are defined respectively as the minimum and maximum of the operands:
Negation formula_14 and implication formula_15 are defined as follows:
Gödel logics are completely axiomatisable, that is to say it is possible to define a logical calculus in which all tautologies are provable.
Łukasiewicz logics and.
Implication formula_17 and negation formula_18 were defined by Jan Łukasiewicz through the following functions:
At first Łukasiewicz used these definition in 1920 for his three-valued logic formula_20, with truth values formula_6. In 1922 he developed a logic with infinitely many values formula_22, in which the truth values spanned the real numbers in the interval formula_10. In both cases the designated truth value was 1.
By adopting truth values defined in the same way as for Gödel logics formula_24, it is possible to create a finitely-valued family of logics formula_25, the abovementioned formula_22 and the logic formula_27, in which the truth values are given by the rational numbers in the interval formula_10. The set of tautologies in formula_22 and formula_27 is identical.
Product logic.
In product logic we have truth values in the interval formula_10, a conjunction formula_32 and an implication formula_33, defined as follows
Additionally there is a negative designated value formula_35 that denotes the concept of "false". Through this value it is possible to define a negation formula_36 and an additional conjunction formula_37 as follows:
Post logics "Pm".
In 1921 Post defined a family of logics formula_39 with (as in formula_25 and formula_3) the truth values formula_42. Negation formula_43 and conjunction formula_44 and disjunction formula_45 are defined as follows:
Rose logics.
In 1951, Alan Rose defined another family of logics for systems whose truth-values form lattices. ("Systems of logic whose truth-values form lattices", Math. Annalen, vol. 123, December 1951, pp. 152–165; source).
Semantics.
Matrix semantics (logical matrices).
See Logical matrix
Relation to classical logic.
Logics are usually systems intended to codify rules for preserving some semantic property of propositions across transformations. In classical logic, 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.
Functional completeness of many-valued logics.
Functional completeness is a term used to describe a special property of finite logics and algebras. A logic's set of connectives is said to be "functionally complete" or "adequate" if and only if its set of connectives can be used to construct a formula corresponding to every possible truth function. An adequate algebra is one in which every finite mapping of variables can be expressed by some composition of its operations.
Classical logic: CL = ({0,1}, ¬, →, ∨, ∧, ↔) is functionally complete, whereas no Łukasiewicz logic or infinitely many-valued logics has this property.
We can define a finitely many-valued logic as being L"n" ({1, 2, ..., "n"} ƒ1, ..., ƒ"m") where "n" ≥ 2 is a given natural number. Post (1921) proves that assuming a logic is able to produce a function of any "m"th order model, there is some corresponding combination of connectives in an adequate logic L"n" which can produce a model of order "m+1".
Applications.
Known applications of many-valued logic can be roughly classified into two groups. The first group uses many-valued logic domain to solve binary problems more efficiently. For example, a well-known approach to represent a multiple-output Boolean function is to treat its output part as a single many-valued variable and convert it to a single-output characteristic function (specifically, the indicator function). Other applications of many-valued logic include design of programmable logic arrays (PLAs) with input decoders, optimization of finite state machines, testing, and verification.
The second group targets the design of electronic circuits which employ more than two discrete levels of signals, such as many-valued memories, arithmetic circuits, and field programmable gate arrays (FPGAs). Many-valued circuits have a number of theoretical advantages over standard binary circuits. For example, the interconnect on and off chip can be reduced if signals in the circuit assume four or more levels rather than only two. In memory design, storing two instead of one bit of information per memory cell doubles the density of the memory in the same die size. Applications using arithmetic circuits often benefit from using alternatives to binary number systems. For example, residue and redundant number systems can reduce or eliminate the ripple-through carries which are involved in normal binary addition or subtraction, resulting in high-speed arithmetic operations. These number systems have a natural implementation using many-valued circuits. However, the practicality of these potential advantages heavily depends on the availability of circuit realizations, which must be compatible or competitive with present-day standard technologies. In addition to aiding in the design of electronic circuits, many-valued logic is used extensively to test circuits for faults and defects. Basically all known automatic test pattern generation (ATG) algorithms used for digital circuit testing require a simulator that can resolve 5-valued logic (0, 1, x, D, D'). The additional values—x, D, and D' -- represent (1) unknown/uninitialized, (2) a 0 instead of a 1, and (3) a 1 instead of a 0.
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. There is also a "Journal of Multiple-Valued Logic and Soft Computing".
Further reading.
General
Specific