Manyvalued logic
source link: https://www.tuicool.com/articles/ErmUZvA
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
This article may be expanded with text translated from the corresponding article in German . (January 2011) Click [show] for important translation instructions.
 View a machinetranslated version of the German article.
 Machine translation like Deepl or Google Translate is a useful starting point for translations, but translators must revise errors as necessary and confirm that the translation is accurate, rather than simply copypasting machinetranslated text into the English Wikipedia.
 Do not translate text that appears unreliable or lowquality. If possible, verify the text with references provided in the foreignlanguage article.
 You must provide copyright attribution in theedit summary accompanying your translation by providing aninterlanguage link to the source of your translation. A model attribution edit summary (using German):
Content in this edit is translated from the existing German Wikipedia article at [[:de:Exact name of German article]]; see its history for attribution.
 You should also add the template
{{TranslateddeMehrwertige Logik}}
to thetalk page.  For more guidance, see Wikipedia:Translation .
Inlogic, a manyvalued logic (also multi or multiplevalued logic ) is a propositional calculus in which there are more than twotruth values. Traditionally, inAristotle'slogical calculus, there were only two possible values (i.e., "true" and "false") for anyproposition. Classicaltwovalued logic may be extended to n valued logic for n greater than 2. Those most popular in the literature arethreevalued (e.g.,Łukasiewicz's andKleene's, which accept the values "true", "false", and "unknown"), thefinitevalued (finitelymany valued) with more than three values, and theinfinitevalued ( infinitelymany valued ), such asfuzzy logic andprobability logic.
Contents

 2.1 Kleene (strong) K 3 and Priest logic P 3
 2.2 Bochvar's internal threevalued logic
 2.3 Belnap logic ( B 4 )
 2.4 Gödel logics G k and G ∞
 2.5 Łukasiewicz logics L v and L ∞

 3.1 Matrix semantics (logical matrices)
 4 Relation to classical logic
History [ edit ]
The first known classical logician who did not fully accept the law of excluded middle wasAristotle (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 multivalued logic to explain this isolated remark. Until the coming of the 20th century, later logicians followedAristotelian logic, which includes or assumes the law of the excluded middle .
The 20th century brought back the idea of multivalued logic. The Polish logician and philosopherJan Łukasiewicz began to create systems of manyvalued 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 andAlfred 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 thatintuitionistic logic is not a finitelymany valued logic , and defined a system ofGödel logics intermediate betweenclassical and intuitionistic logic; such logics are known asintermediate logics.
Examples [ edit ]
Kleene (strong) K 3 and Priest logic P 3 [ edit ]
Kleene's "(strong) logic of indeterminacy" K 3 (sometimes ) and Priest's "logic of paradox" add a third "undefined" or "indeterminate" truth value I . The truth functions fornegation (¬),conjunction (∧),disjunction (∨),implication (), andbiconditional () are given by:
¬ T F I I F T ∧ T I F T T I F I I I F F F F F ∨ T I F T T T T I T I I F T I F T I F T T I F I T I I F T T T T I F T T I F I I I I F F I TThe difference between the two logics lies in howtautologies are defined. In K 3 only T is a designated truth value , while in P 3 both T and I are (a logical formula is considered a tautology if it evaluates to a designated truth value). In Kleene's logic I can be interpreted as being "underdetermined", being neither true nor false, while in Priest's logic I can be interpreted as being "overdetermined", being both true and false. K 3 does not have any tautologies, while P 3 has the same tautologies as classical twovalued logic.
[ citation needed ]
Bochvar's internal threevalued logic [ edit ]
Another logic is Bochvar's "internal" threevalued logic , also called Kleene's weak threevalued logic. Except for negation and biconditional, its truth tables are all different from the above.
T I F T T I F I I I I F F I F T I F T T I T I I I I F T I F T I F T T I F I I I I F T I TThe 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 ( B 4 ) [ edit ]
Belnap's logic B 4 combines K 3 and P 3 . The overdetermined truth value is here denoted as B and the underdetermined truth value as N .
f ¬ T F B B N N F T f ∧ T B N F T T B N F B B B F F N N F N F F F F F F f ∨ T B N F T T T T T B T B T B N T T N N F T B N FGödel logics G k and G ∞ [ edit ]
In 1932Gödel defineda family of manyvalued logics, with finitely many truth values , for example has the truth values and has . In a similar manner he defined a logic with infinitely many truth values, , in which the truth values are all thereal numbers in the interval . The designated truth value in these logics is 1.
The conjunction and the disjunction are defined respectively as theminimum andmaximum of the operands:
Negation and implication 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 L v and L ∞ [ edit ]
Implication and negation were defined byJan Łukasiewicz through the following functions:
At first Łukasiewicz used these definition in 1920 for his threevalued logic , with truth values . In 1922 he developed a logic with infinitely many values , in which the truth values spanned the real numbers in the interval . In both cases the designated truth value was 1.
By adopting truth values defined in the same way as for Gödel logics , it is possible to create a finitelyvalued family of logics , the abovementioned and the logic , in which the truth values are given by therational numbers in the interval . The set of tautologies in and is identical.
Product logic Π [ edit ]
In product logic we have truth values in the interval , a conjunction and an implication , defined as follows
Additionally there is a negative designated value that denotes the concept of false . Through this value it is possible to define a negation and an additional conjunction as follows:
Post logics P m [ edit ]
In 1921Post defined a family of logics with (as in and ) the truth values . Negation and conjunction and disjunction are defined as follows:
Rose logics [ edit ]
In 1951,Alan Rose defined another family of logics for systems whose truthvalues form lattices. (" Systems of logic whose truthvalues form lattices ", Math. Annalen, vol. 123, December 1951, pp. 152165; source ).
Semantics [ edit ]
Matrix semantics (logical matrices) [ edit ]
SeeLogical matrix
Relation to classical logic [ edit ]
Logics are usually systems intended to codify rules for preserving somesemantic property of propositions across transformations. In classicallogic, 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.
Multivalued 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 threevalued logic, sometimes the two greatest truthvalues (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 ofintuitionistic 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.
Suszko's thesis [ edit ]
Applications [ edit ]
Known applications of manyvalued logic can be roughly classified into two groups.The first group uses manyvalued logic domain to solve binary problems more efficiently. For example, a wellknown approach to represent a multipleoutput Boolean function is to treat its output part as a single manyvalued variable and convert it to a singleoutput characteristic function (specifically, theindicator function). Other applications of manyvalued 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 manyvalued memories, arithmetic circuits, and field programmable gate arrays (FPGAs). Manyvalued 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 ripplethrough carries which are involved in normal binary addition or subtraction, resulting in highspeed arithmetic operations. These number systems have a natural implementation using manyvalued circuits. However, the practicality of these potential advantages heavily depends on the availability of circuit realizations, which must be compatible or competitive with presentday standard technologies. In addition to aiding in the design of electronic circuits, manyvalued 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 5valued 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 [ edit ]
AnIEEE International Symposium on MultipleValued Logic (ISMVL) has been held annually since 1970. It mostly caters to applications in digital design and verification.There is also a Journal of MultipleValued Logic and Soft Computing .
See also [ edit ]
Mathematical logic Degrees of truth
 Fuzzy logic
 Gödel logic
 Jaina sevenvalued logic
 Kleene logic
 Kleene algebra (with involution)
 Łukasiewicz logic
 MValgebra
 Post logic
 Principle of bivalence
 A. N. Prior
 Relevance logic
 MVCML, multiplevalued currentmode logic
 IEEE 1164 a ninevalued standard forVHDL
 IEEE 1364 a fourvalued standard forVerilog
 Threestate logic
 Noisebased logic
Notes [ edit ]
References [ edit ]
 Hurley, Patrick. A Concise Introduction to Logic , 9th edition. (2006).
 Gödel, Kurt (1932). "Zum intuitionistischen Aussagenkalkül". Anzeiger der Akademie der Wissenschaften in Wien (69): 65f.
 Kreiser, Lothar; Gottwald, Siegfried; Stelzner, Werner (1990). Nichtklassische Logik. Eine Einführung . Berlin: AkademieVerlag. pp. 41ff–45ff.ISBN 9783050002743 .
 Hajek, Petr: Fuzzy Logic . In: Edward N. Zalta: The Stanford Encyclopedia of Philosophy , Spring 2009. ( [1] )
 Dubrova, Elena (2002). MultipleValued Logic Synthesis and Optimization , in Hassoun S. and Sasao T., editors, Logic Synthesis and Verification , Kluwer Academic Publishers, pp. 89114
 Meher, Pramod Kumar; Valls, Javier; Juang, TsoBing; Sridharan, K.; Maharatna, Koushik (20080822). "50 Years of CORDIC: Algorithms, Architectures and Applications" (PDF) . IEEE Transactions on Circuits & SystemsI: Regular Papers (published 20090909). 56 (9): 1893–1907.doi: 10.1109/TCSI.2009.2025803 . Retrieved 20160103 .
 Abramovici, Miron; Breuer, Melvin A.; Friedman, Arthur D. (1994). Digital Systems Testing and Testable Design . New York: Computer Science Press. p. 183.ISBN 9780780310629 .
 http://www.informatik.unitrier.de/~ley/db/conf/ismvl/index.html
 http://www.oldcitypublishing.com/MVLSC/MVLSC.html
Further reading [ edit ]
General
 Augusto, Luis M. (2017). Manyvalued logics: A mathematical and computational introduction. London: College Publications. 340 pages.ISBN 9781848902503 . Webpage
 Béziau J.Y. (1997), What is manyvalued logic ? Proceedings of the 27th International Symposium on MultipleValued Logic , IEEE Computer Society, Los Alamitos, pp. 117–121.
 Malinowski, Gregorz, (2001), ManyValued Logics, in Goble, Lou, ed., The Blackwell Guide to Philosophical Logic . Blackwell.
 Bergmann, Merrie (2008), An introduction to manyvalued and fuzzy logic: semantics, algebras, and derivation systems , Cambridge University Press,ISBN 9780521881289
 Cignoli, R. L. O., D'Ottaviano, I, M. L., Mundici, D., (2000). Algebraic Foundations of Manyvalued Reasoning . Kluwer.
 Malinowski, Grzegorz (1993). Manyvalued logics . Clarendon Press.ISBN 9780198537878 .
 S. Gottwald , A Treatise on ManyValued Logics. Studies in Logic and Computation, vol. 9, Research Studies Press: Baldock, Hertfordshire, England, 2001.
 Gottwald, Siegfried (2005). "ManyValued Logics" (PDF) . Archived from the original on 20160303. CS1 maint: BOT: originalurl status unknown (link)
 Miller, D. Michael; Thornton, Mitchell A. (2008). Multiple valued logic: concepts and representations . Synthesis lectures on digital circuits and systems. 12 . Morgan & Claypool Publishers.ISBN 9781598291902 .
 Hájek P., (1998), Metamathematics of fuzzy logic . Kluwer. (Fuzzy logic understood as manyvalued logicsui generis.)
Specific
 Alexandre Zinoviev , Philosophical Problems of ManyValued Logic , D. Reidel Publishing Company, 169p., 1963.
 Prior A. 1957, Time and Modality. Oxford University Press , based on his 1956John Locke 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: Manyvalued rules of inference , Zeitschr. f. math. Logik und Grundlagen d. Math., 25, 45–52.
 Metcalfe, George; Olivetti, Nicola; Dov M. Gabbay (2008). Proof Theory for Fuzzy Logics . Springer.ISBN 9781402094088 . Covers proof theory of manyvalued logics as well, in the tradition of Hájek.
 Hähnle, Reiner (1993). Automated deduction in multiplevalued logics . Clarendon Press.ISBN 9780198539896 .
 Azevedo, Francisco (2003). Constraint solving over multivalued logics: application to digital circuits . IOS Press.ISBN 9781586033040 .
 Bolc, Leonard; Borowik, Piotr (2003). Manyvalued Logics 2: Automated reasoning and practical applications . Springer.ISBN 9783540645078 .
 Stanković, Radomir S.; Astola, Jaakko T.; Moraga, Claudio (2012). Representation of MultipleValued Logic Functions . Morgan & Claypool Publishers.doi: 10.2200/S00420ED1V01Y201205DCS037 . ISBN 9781608459421 .
 Abramovici, Miron; Breuer, Melvin A.; Friedman, Arthur D. (1994). Digital Systems Testing and Testable Design . New York: Computer Science Press.ISBN 9780780310629 .
External links [ edit ]
 Gottwald, Siegfried (2009). "ManyValued Logic" . Stanford Encyclopedia of Philosophy . Metaphysics Research Lab, Stanford University.
 Stanford Encyclopedia of Philosophy : " Truth Values "—by Yaroslav Shramko and Heinrich Wansing.
 IEEE Computer Society 's Technical Committee on MultipleValued Logic
 Resources for ManyValued Logic by Reiner Hähnle,Chalmers University
 Manyvalued Logics W3 Server (archived)
 Yaroslav Shramko and Heinrich Wansing (2014). "Suszko's Thesis" . Stanford Encyclopedia of Philosophy . CS1 maint: Uses authors parameter (link)
 Carlos Caleiro, Walter Carnielli, Marcelo E. Coniglio and João Marcos, Two's company: "The humbug of many logical values" in JeanYves Beziau, ed. (2007). Logica Universalis: Towards a General Theory of Logic (2nd ed.). Springer Science & Business Media. pp. 174–194.ISBN 9783764383541 .
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK