• Many-valued logic 1 From Wikipedia, the free encyclopedia
  • Contents 1 Four-valued logic 1 1.1 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1.1 Electronics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1.2 Software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2 Many-valued logic 4 2.1 History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2.1 Kleene (strong) K3 and Priest logic P3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2.2 Bochvar’s internal three-valued logic (also known as Kleene’s weak three-valued logic) . . . 5 2.2.3 Belnap logic (B4) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2.4 Gödel logics Gk and G∞ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2.5 Łukasiewicz logics Lv and L∞ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2.6 Product logic Π . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2.7 Post logics Pm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.3 Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.3.1 Matrix semantics (logical matrices) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.4 Proof theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.5 Relation to classical logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.5.1 Suszko’s thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.6 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.7 Research venues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.8 See also . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.9 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.10 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.11 Further reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.12 External links . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3 Problem of future contingents 10 3.1 Aristotle’s solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.2 Leibniz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.3 20th century . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 i
  • ii CONTENTS 3.4 See also . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.5 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.6 Further reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.7 External links . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 4 Three-valued logic 14 4.1 Representation of values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 4.2 Logics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 4.2.1 Kleene and Priest logics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 4.2.2 Łukasiewicz logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 4.2.3 Bochvar logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.2.4 ternary Post logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.2.5 Modular algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.3 Application in SQL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.4 See also . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.5 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 4.6 Further reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 4.7 External links . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 4.8 Text and image sources, contributors, and licenses . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4.8.1 Text . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4.8.2 Images . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4.8.3 Content license . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
  • Chapter 1 Four-valued logic In logic, a four-valued logic is used to model signal values in digital circuits: the four values are Z, X and the boolean values 1 and 0. Z stands for high impedance or open circuit, while X stands for “unknown”. There is also a 9-valued logic standard by the IEEE called IEEE 1164. There are other types of four value logic, such as Belnap’s four-valued relevance logic: the possible values are 1) true, 2) false, 3) both true and false, and 4) neither true nor false. Belnap’s logic is designed to cope with multiple information sources such that if only true is found then true is assigned, if only false is found then false is assigned, if some sources say true and others say false then both is assigned, and if no information is given by any information source then neither is assigned. 1.1 Applications 1.1.1 Electronics Among the distinct logic values supported by digital electronics theory (as defined in VHDL's std_logic) are such diverse elements as: � 1 or High, usually representing TRUE. � 0 or Low, usually representing FALSE. � X representing a “Conflict”. � U representing “Unassigned” or “Unknown”. � - representing "Don't Care". � Z representing "high impedance", undriven line. � H, L andW are other high-impedance values, the weak pull to “High”, “Low” and “Don't Know” correspond- ingly. The “U” value does not exist in real-world circuits, it is merely a placeholder used in simulators and for design purposes. Some simulators support representation of the “Z” value, others do not. The “Z” value does exist in real-world circuits but only as an output state. Use of “U” value in simulation Many hardware description language (HDL) simulation tools, such as Verilog and VHDL, support an unknown value like that shown above during simulation of digital electronics. The unknown value may be the result of a design error, which the designer can correct before synthesis into an actual circuit. The unknown also represents uninitialised memory values and circuit inputs before the simulation has asserted what the real input value should be. HDL synthesis tools usually produce circuits that operate only on binary logic. 1
  • 2 CHAPTER 1. FOUR-VALUED LOGIC Use of “X” value in digital design When designing a digital circuit, some conditions may be outside the scope of the purpose that the circuit will perform. Thus, the designer does not care what happens under those conditions. In addition, the situation occurs that inputs to a circuit are masked by other signals so the value of that input has no effect on circuit behaviour. In these situations, it is traditional to use “X” as a placeholder to indicate "Don't Care" when building truth tables. This is especially common in state machine design and Karnaugh map simplification. The “X” values provide additional degrees of freedom to the final circuit design, generally resulting in a simplified and smaller circuit.[1] Once the circuit design is complete and a real circuit is constructed, the “X” values will no longer exist. They will become some tangible “0” or “1” value but could be either depending on the final design optimisation. Use of “Z” value for high impedance Main article: three-state Some digital devices support a form of three-state logic on their outputs only. The three states are “0”, “1”, and “Z”. Commonly referred to as tristate [2] logic (a trademark of National Semiconductor), it comprises the usual true and false states, with a third transparent high impedance state (or 'off-state') which effectively disconnects the logic output. This provides an effective way to connect several logic outputs to a single input, where all but one are put into the high impedance state, allowing the remaining output to operate in the normal binary sense. This is commonly used to connect banks of computer memory and other similar devices to a common data bus; a large number of devices can communicate over the same channel simply by ensuring only one is enabled at a time. It is important to note that while outputs can have one of three states, inputs can only recognise two. Hence the kind of relations shown in the table above do not occur. Although it could be argued that the high-impedance state is effectively an “unknown”, there is absolutely no provision in the vast majority of normal electronics to interpret a high-impedance state as a state in itself. Inputs can only detect “0” and “1”. When a digital input is left disconnected (i.e., when it is given a high impedance signal), the digital value interpreted by the input depends on the type of technology used. TTL technology will reliably default to a “1” state. On the other hand CMOS technology will temporarily hold the previous state seen on that input (due to the capacitance of the gate input). Over time, leakage current causes the CMOS input to drift in a random direction, possibly causing the input state to flip. Disconnected inputs on CMOS devices can pick up noise, they can cause oscillation, the supply current may dramatically increase (crowbar power) or the device may completely destroy itself. Exotic ternary-logic devices True three-valued logic can be implemented in electronics, although the complexity of design has thus far made it uneconomical to pursue commercially and interest has been primarily confined to research (see Setun); 'Normal' binary logic is simply cheaper to implement and in most cases can easily be configured to emulate ternary systems. There are, however, useful applications in fuzzy logic and error correction, and several true ternary logic devices have been manufactured. 1.1.2 Software Vehicle technology In the SAE J1939 standard, used for CAN data transmission in heavy road vehicles, there are four logical (boolean) values, False, True, Error Condition, and Not installed (represented by values 0-3). Error Condition means there is a technical problem obstacling data acquisition. The logics for that is for example True and Error Condition=Error Condition. Not installed is used for a feature which does not exist in this vehicle, and should be disregarded for logical calculation. On CAN, usually fixed data messages are sent containing many signal values each, so a signal representing a not-installed feature will be sent anyway.
  • 1.2. NOTES 3 1.2 Notes [1] Wakerly, John F (2001). Digital Design Principles & Practices. Prentice Hall. ISBN 0-13-090772-3. [2] National Semiconductor (1993), LS TTL Data Book, National Semiconductor Corporation
  • Chapter 2 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. 2.1 History The first known classical logician who didn't 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”[1]). 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. 2.2 Examples Main articles: Three-valued logic and Four-valued logic 2.2.1 Kleene (strong) K3 and Priest logic P3 Kleene's "(strong) logic of indeterminacy”K3 (sometimesKS3 ) and Priest’s “logic of paradox” add a third “undefined” or “indeterminate” truth value I. The truth functions for negation (¬), conjunction (∧), disjunction (∨), implication (→K), and biconditional (↔K) are given by:[2] 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 (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. K3 does not have any tautologies, while P3 has the same tautologies as classical two-valued logic. 4
  • 2.2. EXAMPLES 5 2.2.2 Bochvar’s internal three-valued logic (also known as Kleene’s weak three-valued logic) Another logic is Bochvar’s “internal” three-valued logic ( BI3 ) also called Kleene’s weak three-valued logic. Except for negation and biconditional, its truth tables are all different from the above.[3] 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.[4] 2.2.3 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. 2.2.4 Gödel logics Gk and G∞ In 1932 Gödel defined[5] a familyGk of many-valued logics, with finitely many truth values 0; 1k�1 ; 2k�1 ; : : : k�2k�1 ; 1 , for exampleG3 has the truth values 0; 12 ; 1 andG4 has 0; 13 ; 23 ; 1 . In a similar manner he defined a logic with infinitely many truth values,G1 , in which the truth values are all the real numbers in the interval [0; 1] . The designated truth value in these logics is 1. The conjunction ^ and the disjunction _ are defined respectively as the maximum and minimum of the operands: � u ^ v := minfu; vg � u _ v := maxfu; vg Negation :G and implication!G are defined as follows: � :Gu = ( 1; ifu = 0 0; ifu > 0 u!G v = ( 1; ifu � v 0; ifu > v Gödel logics are completely axiomatisable, that is to say it is possible to define a logical calculus in which all tautologies are provable. 2.2.5 Łukasiewicz logics Lv and L∞ Implication!L and negation :L were defined by Jan Łukasiewicz through the following functions: � :Lu := 1� u � u!L v := minf1; 1� u+ vg At first Łukasiewicz used these definition in 1920 for his three-valued logic L3 , with truth values 0; 12 ; 1 . In 1922 he developed a logic with infinitely many values L1 , in which the truth values spanned the real numbers in the interval [0; 1] . In both cases the designated truth walue was 1.[6] By adopting truth values defined in the same way as for Gödel logics 0; 1v�1 ; 2v�1 ; : : : ; v�2v�1 ; 1 , it is possible to create a finitely-valued family of logics Lv , the abovementioned L1 and the logic L@0 , in which the truth values are given by the rational numbers in the interval [0; 1] . The set of tautologies in L1 and L@0 is identical.
  • 6 CHAPTER 2. MANY-VALUED LOGIC 2.2.6 Product logic Π In product logic we have truth values in the interval [0; 1] , a conjunction � and an implication !� , defined as follows[7] � u� v := uv � u!� v := ( 1; ifu � v v u ; ifu > v Additionally there is a negative designated value 0 that denotes the concept of false. Through this value it is possible to define a negation :� and an additional conjunction ^� as follows: � :�u := u!� 0 � u ^� v := u� (u!� v) 2.2.7 Post logics Pm In 1921 Post defined a family of logics Pm with (as in Lv and Gk ) the truth values 0; 1m�1 ; 2m�1 ; : : : ; m�2m�1 ; 1 . Negation :P and disjunction _P are defined as follows: � :Pu := ( 1; ifu = 0 u� 1m�1 ; ifu 6= 0 � u _P v := maxfu; vg 2.3 Semantics 2.3.1 Matrix semantics (logical matrices) 2.4 Proof theory 2.5 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.
  • 2.6. APPLICATIONS 7 2.5.1 Suszko’s thesis See also: Principle of bivalence § Suszko’s thesis 2.6 Applications Known applications of many-valued logic can be roughly classified into two groups.[8] 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. 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, Field Programmable Gate Arrays (FPGA) etc. 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. 2.7 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.[9] There is also a Journal of Multiple-Valued Logic and Soft Computing.[10] 2.8 See also Mathematical logic � Degrees of truth � Fuzzy logic � Gödel logic � Kleene logic � Kleene algebra (with involution) � Łukasiewicz logic � MV-algebra � Post logic � Principle of bivalence � A. N. Prior � Relevance logic Philosophical logic
  • 8 CHAPTER 2. MANY-VALUED LOGIC � False dilemma � Mu Digital logic � MVCML, multiple-valued current-mode logic � IEEE 1164 a nine-valued standard for VHDL � IEEE 1364 a four-valued standard for Verilog � Noise-based logic 2.9 Notes 2.10 References [1] Hurley, Patrick. A Concise Introduction to Logic, 9th edition. (2006). [2] (Gottwald 2005, p. 19) [3] (Bergmann 2008, p. 80) [4] (Bergmann 2008, p. 80) [5] Gödel, Kurt (1932). “Zum intuitionistischen Aussagenkalkül”. Anzeiger Akademie der Wissenschaften Wien (69): 65f. [6] Kreiser, Lothar; Gottwald, Siegfried; Stelzner, Werner (1990). Nichtklassische Logik. Eine Einführung. Berlin: Akademie- Verlag. pp. 41ff –– 45ff. ISBN 978-3-05-000274-3. [7] Hajek, Petr: Fuzzy Logic. In: Edward N. Zalta: The Stanford Encyclopedia of Philosophy, Spring 2009. () [8] Dubrova, Elena (2002). Multiple-Valued Logic Synthesis and Optimization, in Hassoun S. and Sasao T., editors, Logic Synthesis and Verification, Kluwer Academic Publishers, pp. 89-114 [9] http://www.informatik.uni-trier.de/~{}ley/db/conf/ismvl/index.html [10] http://www.oldcitypublishing.com/MVLSC/MVLSC.html 2.11 Further reading General � Béziau J.-Y. (1997), What is many-valued logic ? Proceedings of the 27th International Symposium onMultiple- 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. � Bergmann, Merrie (2008), An introduction to many-valued and fuzzy logic: semantics, algebras, and derivation systems, Cambridge University Press, ISBN 978-0-521-88128-9 � Cignoli, R. L. O., D'Ottaviano, I, M. L., Mundici, D., (2000). Algebraic Foundations of Many-valued Reason- ing. Kluwer. � Malinowski, Grzegorz (1993). Many-valued logics. Clarendon Press. ISBN 978-0-19-853787-8. � S. Gottwald, A Treatise on Many-Valued Logics. Studies in Logic and Computation, vol. 9, Research Studies Press: Baldock, Hertfordshire, England, 2001. � Gottwald, Siegfried (2005). “Many-Valued Logics” (PDF).
  • 2.12. EXTERNAL LINKS 9 � Miller, D. Michael; Thornton, Mitchell A. (2008). Multiple valued logic: concepts and representations. Syn- thesis lectures on digital circuits and systems 12. Morgan & Claypool Publishers. ISBN 978-1-59829-190-2. � Hájek P., (1998), Metamathematics of fuzzy logic. Kluwer. (Fuzzy logic understood as many-valued logic sui generis.) 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 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: Many-valued 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 978-1-4020-9408-8. Covers proof theory of many-valued logics as well, in the tradition of Hájek. � Hähnle, Reiner (1993). Automated deduction in multiple-valued logics. Clarendon Press. ISBN 978-0-19- 853989-6. � Azevedo, Francisco (2003). Constraint solving over multi-valued logics: application to digital circuits. IOS Press. ISBN 978-1-58603-304-0. � Bolc, Leonard; Borowik, Piotr (2003). Many-valued Logics 2: Automated reasoning and practical applications. Springer. ISBN 978-3-540-64507-8. � Stanković, Radomir S.; Astola, Jaakko T.; Moraga, Claudio (2012). Representation of Multiple-Valued Logic Functions. Morgan & Claypool Publishers. doi:10.2200/S00420ED1V01Y201205DCS037. ISBN 978-1- 60845-942-1. 2.12 External links � Gottwald, Siegfried (2009). “Many-Valued Logic”. Stanford Encyclopedia of Philosophy. � Stanford Encyclopedia of Philosophy: "Truth Values"—by Yaroslav Shramko and Heinrich Wansing. � IEEE Computer Society's Technical Committee on Multiple-Valued Logic � Resources for Many-Valued Logic by Reiner Hähnle, Chalmers University � Many-valued Logics W3 Server (archived) � Yaroslav Shramko and Heinrich Wansing (2014). “Suszko’s Thesis”. Stanford Encyclopedia of Philosophy. � Carlos Caleiro, Walter Carnielli, Marcelo E. Coniglio and João Marcos, Two’s company: “The humbug of many logical values” in Jean-Yves Beziau, ed. (2007). Logica Universalis: Towards a General Theory of Logic (2nd ed.). Springer Science & Business Media. pp. 174–194. ISBN 978-3-7643-8354-1.
  • Chapter 3 Problem of future contingents Aristotle: if a sea-battle will not be fought tomorrow, then it was also true yesterday that it will not be fought. But all past truths are necessary truths. Therefore it is not possible that the battle will be fought Future contingent propositions (or simply, future contingents) are statements about states of affairs in the future that are neither necessarily true nor necessarily false. The problem of future contingents seems to have been first discussed by Aristotle in chapter 9 of his On Inter- pretation (De Interpretatione), using the famous sea-battle example.[1] Roughly a generation later, Diodorus Cronus from the Megarian school of philosophy stated a version of the problem in his notorious Master Argument.[2] The problem was later discussed by Leibniz. The problem can be expressed as follows. Suppose that a sea-battle will not be fought tomorrow. Then it was also true yesterday (and the week before, and last year) that it will not be fought, since any true statement about what will be the case was also true in the past. But all past truths are now necessary truths; therefore it is now necessarily true that the battle will not be fought, and thus the statement that it will be fought is necessarily false. Therefore it is not possible that the battle will be fought. In general, if something will not be the case, it is not possible for it to be the case. “For a man may predict an event ten thousand years beforehand, and another may predict the reverse; that which was truly predicted at the moment in the past will of necessity take place in the fullness of time” (18 b35). This conflicts with the idea that of our own free choice: that we have the power to determine or control the course of 10
  • 3.1. ARISTOTLE’S SOLUTION 11 events in the future, which seems impossible if what happens, or does not happen, is necessarily going to happen, or not happen. As Aristotle says, if so there would be no need “to deliberate or to take trouble, on the supposition that if we should adopt a certain course, a certain result would follow, while, if we did not, the result would not follow”. 3.1 Aristotle’s solution Aristotle solved the problem by asserting that the principle of bivalence found its exception in this paradox of the sea battles: in this specific case, what is impossible is that both alternatives can be possible at the same time: either there will be a battle, or there won't. Both options can't be simultaneously taken. Today, they are neither true nor false; but if one is true, then the other becomes false. According to Aristotle, it is impossible to say today if the proposition is correct: we must wait for the contingent realization (or not) of the battle, logic realizes itself afterwards: One of the two propositions in such instances must be true and the other false, but we cannot say determi- nately that this or that is false, but must leave the alternative undecided. One may indeed be more likely to be true than the other, but it cannot be either actually true or actually false. It is therefore plain that it is not necessary that of an affirmation and a denial, one should be true and the other false. For in the case of that which exists potentially, but not actually, the rule which applies to that which exists actually does not hold good. (§9) For Diodorus, the future battle was either impossible or necessary. Aristotle added a third term, contingency, which saves logic while in the same time leaving place for indetermination in reality. What is necessary is not that there will or that there won't be a battle tomorrow, but the dichotomy itself is necessary: A sea-fight must either take place tomorrow or not, but it is not necessary that it should take place tomorrow, neither is it necessary that it should not take place, yet it is necessary that it either should or should not take place tomorrow. (De Interpretatione, 9, 19 a 30.) Thus, the event always comes in the form of the future, undetermined event; logic always comes afterwards. Hegel would say the same thing by claiming that wisdom came at dusk. For Aristotle, this is also a practical, ethical question: to pretend that the future is determined would have unacceptable consequences for man. 3.2 Leibniz Leibniz gave another response to the paradox in §6 ofDiscourse on Metaphysics: “That God does nothing which is not orderly, and that it is not even possible to conceive of events which are not regular.” Thus, even a miracle, the Event by excellence, does not break the regular order of things. What is seen as irregular is only a default of perspective, but does not appear so in relation to universal order. Possibility exceeds human logics. Leibniz encounters this paradox because according to him: Thus the quality of king, which belonged to Alexander the Great, an abstraction from the subject, is not sufficiently determined to constitute an individual, and does not contain the other qualities of the same subject, nor everything which the idea of this prince includes. God, however, seeing the individual concept, or haecceity, of Alexander, sees there at the same time the basis and the reason of all the predicates which can be truly uttered regarding him; for instance that he will conquer Darius and Porus, even to the point of knowing a priori (and not by experience) whether he died a natural death or by poison,- facts which we can learn only through history. When we carefully consider the connection of things we see also the possibility of saying that there was always in the soul of Alexander marks of all that had happened to him and evidences of all that would happen to him and traces even of everything which occurs in the universe, although God alone could recognize them all. (§8) If everything which happens to Alexander derives from the haecceity of Alexander, then fatalism threatens Leibniz’s construction: We have said that the concept of an individual substance includes once for all everything which can ever happen to it and that in considering this concept one will be able to see everything which can truly be said
  • 12 CHAPTER 3. PROBLEM OF FUTURE CONTINGENTS concerning the individual, just as we are able to see in the nature of a circle all the properties which can be derived from it. But does it not seem that in this way the difference between contingent and necessary truths will be destroyed, that there will be no place for human liberty, and that an absolute fatality will rule as well over all our actions as over all the rest of the events of the world? To this I reply that a distinction must be made between that which is certain and that which is necessary. (§13) Against Aristotle’s separation between the subject and the predicate, Leibniz states: “Thus the content of the subject must always include that of the predicate in such a way that if one understands perfectly the concept of the subject, he will know that the predicate appertains to it also.” (§8) The predicate (what happens to Alexander) must be completely included in the subject (Alexander) “if one un- derstands perfectly the concept of the subject”. Leibniz henceforth distinguishes two types of necessity: necessary necessity and contingent necessity, or universal necessity vs singular necessity. Universal necessity concerns universal truths, while singular necessity concerns something necessary which could not be (it is thus a “contingent necessity”). Leibniz hereby uses the concept of compossible worlds. According to Leibniz, contingent acts such as “Caesar cross- ing the Rubicon” or “Adam eating the apple” are necessary: that is, they are singular necessities, contingents and accidentals, but which concerns the principle of sufficient reason. Furthermore, this leads Leibniz to conceive of the subject not as a universal, but as a singular: it is true that “Caesar crosses the Rubicon”, but it is true only of this Caesar at this time, not of any dictator nor of Caesar at any time (§8, 9, 13). Thus Leibniz conceives of substance as plural: there is a plurality of singular substances, which he calls monads. Leibniz hence creates a concept of the individual as such, and attributes to it events. There is a universal necessity, which is universally applicable, and a singular necessity, which applies to each singular substance, or event. There is one proper noun for each singular event: Leibniz creates a logic of singularity, which Aristotle thought impossible (he considered that there could only be knowledge of generality). 3.3 20th century One of the early motivations for the study of many-valued logics has been precisely this issue. In the early 20th century, the Polish formal logician Jan Łukasiewicz proposed three truth-values: the true, the false and the as-yet- undetermined. This approach was later developed by Arend Heyting and L. E. J. Brouwer;[3] see Łukasiewicz logic. Issues such as this have also been addressed in various temporal logics, where one can assert that "Eventually, either there will be a sea battle tomorrow, or there won't be.” (Which is true if “tomorrow” eventually occurs.) The Modal Fallacy The error in the argument underlying the alleged “Problem of Future Contingents” lies in the assumption that “X is the case” implies that “necessarily, X is the case”. In logic, this is known as the Modal Fallacy.[4] By asserting “A sea-fight must either take place tomorrow or not, but it is not necessary that it should take place tomorrow, neither is it necessary that it should not take place, yet it is necessary that it either should or should not take place tomorrow.” Aristotle is simply claiming “necessarily (a or not-a)”, which is correct. However, the next step in Aristotle’s reasoning seems to be: “If a is the case, then necessarily, a is the case”, which is a logical fallacy. Expressed in another way: (i) If a proposition is true, then it cannot be false. (ii) If a proposition cannot be false, then it is necessarily true. (iii) Therefore if a proposition is true, it is necessarily true. That is, there are no contingent propositions. Every proposition is either necessarily true or necessarily false. The fallacy arises in the ambiguity of the first premise. If we interpret it close to the English, we get: (iv) P entails it is not possible that not-P (v) It is not possible that not-P entails it is necessary that P (vi) Therefore, P entails it is necessary that P However, if we recognize that the original English expression (i) is potentially misleading, that it assigns a necessity to what is simply nothing more than a necessary condition, then we get instead as our premises: (vii) It is not possible that (P and not P) (viii) (It is not possible that not P) entails (it is necessary that P) From these latter two premises, one cannot validly infer the conclusion:
  • 3.4. SEE ALSO 13 (ix) P entails it is necessary that P 3.4 See also � Logical determinism � Free will � Principle of distributivity � Principle of plenitude � Truth-value link � In Borges' The Garden of Forking Paths, both alternatives happen, thus leading to what Deleuze calls “incom- possible worlds” 3.5 Notes [1] Dorothea Frede, The sea-battle reconsidered, Oxford Studies in Ancient Philosophy 1985, pp. 31-87. [2] Dialectical School entry by Susanne Bobzien in the Stanford Encyclopedia of Philosophy [3] Paul Tomassi (1999). Logic. Routledge. p. 124. ISBN 978-0-415-16696-6. [4] Norman Swartz, The Modal Fallacy 3.6 Further reading � Dorothea Frede (1985), The Sea-Battle Reconsidered, Oxford Studies in Ancient Philosophy 3, 31-87. � Peter Øhrstrøm; Per F. V. Hasle (1995). Temporal logic: from ancient ideas to artificial intelligence. Springer. ISBN 978-0-7923-3586-3. � Richard Gaskin (1995). The sea battle and the master argument: Aristotle and Diodorus Cronus on the meta- physics of the future. Walter de Gruyter. ISBN 978-3-11-014430-7. � Melvin Fitting; Richard L. Mendelsohn (1998). First-order modal logic. Springer. pp. 35–40. ISBN 978-0- 7923-5335-5. attempts to reconstruct both Aristotle’s and Diodorus’ arguments in propositional modal logic � John MacFarlane (2003), Sea Battles, Futures Contingents, and Relative Truth and Future Contingent and Relative Truth, The Philosophical Quarterly 53, 321-36 � Jules Vuillemin, Le chapitre IX du De Interpretatione d'Aristote - Vers une réhabilitation de l'opinion comme connaissance probable des choses contingentes, in Philosophiques, vol. X, n°1, April 1983 (French) 3.7 External links � Future Contingents entry by Peter Øhrstrøm and Per Hasle in the Stanford Encyclopedia of Philosophy � Medieval Theories of Future Contingents entry by Simo Knuuttila in the Stanford Encyclopedia of Philosophy � The Master Argument: The Sea Battle in De Intepretatione 9, Diodorus Cronus, Philo the Dialectician with a bibliography on Diodorus and the problem of future contingents
  • Chapter 4 Three-valued logic In logic, a three-valued logic (also trinary logic, trivalent, ternary, or trilean, sometimes abbreviated 3VL) is any of several many-valued logic systems in which there are three truth values indicating true, false and some indeter- minate third value. This is contrasted with the more commonly known bivalent logics (such as classical sentential or Boolean logic) which provide only for true and false. Conceptual form and basic ideas were initially created by Jan Łukasiewicz and C. I. Lewis. These were then re-formulated by Grigore Moisil in an axiomatic algebraic form, and also extended to n-valued logics in 1945. 4.1 Representation of values As with bivalent logic, truth values in ternary logic may be represented numerically using various representations of the ternary numeral system. A few of the more common examples are: � in balanced ternary, each digit has one of 3 values: −1, 0, or +1; these values may also be simplified to −, 0, +, respectively.[1] � in the redundant binary representation, each digit can have a value of �1, 0, 0, or 1 (the value 0 has two different representations) � in the ternary numeral system, each digit is a trit (trinary digit) having a value of: 0, 1, or 2 � in the skew binary number system, only most-significant non-zero digit has a value 2, and the remaining digits have a value of 0 or 1 � 1 for true, 2 for false, and 0 for unknown, unknowable/undecidable, irrelevant, or both.[2] � 0 for false, 1 for true, and a third non-integer “maybe” symbol such as ?, #, ½,[3] or xy. Inside a ternary computer, ternary values are represented by ternary signals. This article mainly illustrates a system of ternary propositional logic using the truth values {false, unknown, and true}, and extends conventional Boolean connectives to a trivalent context. Ternary predicate logics exist as well; these may have readings of the quantifier different from classical (binary) predicate logic, and may include alternative quantifiers as well. 4.2 Logics Where Boolean Logic has 4 monadic operators, the addition of a third value in ternary logic leads to a total of 27 distinct operators on a single input value. Similarly, where Boolean logic has 16 distinct diadic operators (operators with 2 inputs), ternary logic has 19,683 such operators. Where we can easily name a significant fraction of the Boolean operators (not, and, or, nand, nor, exclusive or), it is unreasonable to attempt to name all but a small fraction of the possible ternary operators.[4] 14
  • 4.2. LOGICS 15 4.2.1 Kleene and Priest logics See also: Kleene algebra (with involution) Below is a set of truth tables showing the logic operations for Kleene's “strong logic of indeterminacy” and Priest’s “logic of paradox”. In these truth tables, the unknown state can be thought of as neither true nor false in Kleene logic, or thought of as both true and false in Priest logic. The difference lies in the definition of tautologies. Where Kleene logic’s only designated truth value is T, Priest logic’s designated truth values are both T and U. In Kleene logic, the knowledge of whether any particular unknown state secretly represents true or false at any moment in time is not available. However, certain logical operations can yield an unambiguous result, even if they involve at least one unknown operand. For example, since true OR true equals true, and true OR false also equals true, one can infer that true OR unknown equals true, as well. In this example, since either bivalent state could be underlying the unknown state, but either state also yields the same result, a definitive true results in all three cases. If numeric values, e.g. balanced ternary values, are assigned to false, unknown and true such that false is less than unknown and unknown is less than true, then A AND B AND C... = MIN(A, B, C ...) and A OR B OR C ... = MAX(A, B, C...). Material implication for Kleene logic can be defined as: A! B def= NOT(A) OR B , and its truth table is which differs from that for Łukasiewicz logic (described below). Kleene logic has no tautologies (valid formulas) because whenever all of the atomic components of a well-formed formula are assigned the value Unknown, the formula itself must also have the value Unknown. (And the only designated truth value for Kleene logic is True.) However, the lack of valid formulas does not mean that it lacks valid arguments and/or inference rules. An argument is semantically valid in Kleene logic if, whenever (for any interpretation/model) all of its premises are True, the conclusion must also be True. (Note that the Logic of Paradox (LP) has the same truth tables as Kleene logic, but it has two designated truth values instead of one; these are: True and Both (the analogue of Unknown), so that LP does have tautologies but it has fewer valid inference rules.)[5] 4.2.2 Łukasiewicz logic Further information: Łukasiewicz logic The Łukasiewicz Ł3 has the same tables for AND, OR, and NOT as the Kleene logic given above, but differs in its definition of implication. This section follows the presentation from Malinowski’s chapter of the Handbook of the History of Logic, vol 8.[6] In fact, using Łukasiewicz’s implication and negation, the other usual connectives may be derived as: � A ∨ B = (A→ B) → B � A ∧ B = ¬(¬A ∨ ¬ B) � A↔ B = (A→ B) ∧ (B→ A) It’s also possible to derive a few other useful unary operators (first derived by Tarski in 1921): � MA = ¬A→ A � LA = ¬M¬A � IA =MA ∧ ¬LA They have the following truth tables: M is read as “it is not false that...” or in the (unsuccessful) Tarski–Łukasiewicz attempt to axiomatize modal logic using a three-valued logic, “it is possible that...” L is read “it is true that...” or “it is necessary that...” Finally I is read “it is unknown that...” or “it is contingent that...”
  • 16 CHAPTER 4. THREE-VALUED LOGIC In Łukasiewicz’s Ł3 the designated value is True, meaning that only a proposition having this value everywhere is considered a tautology. For example A → A and A ↔ A are tautologies in Ł3 and also in classical logic. Not all tautologies of classical logic lift to Ł3 “as is”. For example, the law of excluded middle, A ∨ ¬A, and the law of non-contradiction, ¬(A ∧ ¬A) are not tautologies in Ł3. However, using the operator I defined above, it is possible to state tautologies that are their analogues: � A ∨ IA ∨ ¬A [law of excluded fourth] � ¬(A ∧ ¬IA ∧ ¬A) [extended contradiction principle]. 4.2.3 Bochvar logic Main article: Many-valued_logic § Bochvar.27s_internal_three-valued_logic_.28also_known_as_Kleene.27s_weak_three- valued_logic.29 4.2.4 ternary Post logic 4.2.5 Modular algebras Some 3VL modular algebras have been introduced more recently, motivated by circuit problems rather than philo- sophical issues:[7] � Cohn algebra � Pradhan algebra � Dubrova and Muzio algebra 4.3 Application in SQL Main article: Null (SQL) The database structural query language SQL implements ternary logic as a means of handling comparisons with NULL field content. The original intent of NULL in SQL was to represent missing data in a database, i.e. the assumption that an actual value exists, but that the value is not currently recorded in the database. SQL uses a common fragment of the Kleene K3 logic, restricted to AND, OR, and NOT tables. In SQL, the intermediate value is intended to be interpreted as UNKNOWN. Explicit comparisons with NULL, including that of another NULL yields UNKNOWN. However this choice of semantics is abandoned for some set operations, e.g. UNION or INTERSECT, where NULLs are treated as equal with each other. Critics assert that this inconsistency deprives SQL of intuitive semantics in its treatment of NULLs.[8] The SQL standard defines an optional feature called F571, which adds some unary operators, among which IS UNKNOWN corresponding to the Łukasiewicz I in this article. The addition of IS UNKNOWN to the other operators of SQL’s three-valued logic makes the SQL three-valued logic functionally complete,[9] meaning its logical operators can express (in combination) any conceivable three-valued logical function. 4.4 See also � Aymara language – a Bolivian language famous for using ternary rather than binary logic[10] � Binary logic (disambiguation) � Boolean algebra (structure) � Boolean function
  • 4.5. REFERENCES 17 � Digital circuit � Four-valued logic � Setun - an experimental Russian computer which was based on ternary logic � Ternary numeral system (and Balanced ternary) � Three-state logic 4.5 References [1] Knuth, Donald E. (1981). The Art of Computer Programming Vol. 2. Reading, Mass.: Addison-Wesley Publishing Com- pany. p. 190. [2] Hayes, Brian (November–December 2001). “Third Base”. American Scientist (Sigma Xi, the Scientific Research Society) 89 (6): 490–494. doi:10.1511/2001.6.490. [3] The Penguin Dictionary of Mathematics. 2nd Edition. London, England: Penguin Books. 1998. p. 417. [4] Douglas W. Jones, Standard Ternary Logic, Feb. 11, 2013 [5] http://www.uky.edu/~{}look/Phi520-Lecture7.pdf [6] Grzegorz Malinowski, “Many-valued Logic and its Philosophy” in Dov M. Gabbay, John Woods (eds.) Handbook of the History of Logic Volume 8. The Many Valued and Nonmonotonic Turn in Logic, Elsevier, 2009 [7] Miller, D. Michael; Thornton, Mitchell A. (2008). Multiple valued logic: concepts and representations. Synthesis lectures on digital circuits and systems 12. Morgan & Claypool Publishers. pp. 41–42. ISBN 978-1-59829-190-2. [8] Ron van der Meyden, "Logical approaches to incomplete information: a survey" in Chomicki, Jan; Saake, Gunter (Eds.) Logics for Databases and Information Systems, Kluwer Academic Publishers ISBN 978-0-7923-8129-7, p. 344; PS preprint (note: page numbering differs in preprint from the published version) [9] C. J. Date, Relational database writings, 1991-1994, Addison-Wesley, 1995, p. 371 [10] “El idioma de los aymaras” (in Spanish). Aymara Uta. Retrieved 2013-08-20. 4.6 Further reading � Bergmann, Merrie (2008). An Introduction to Many-Valued and Fuzzy Logic: Semantics, Algebras, and Deriva- tion Systems. Cambridge University Press. ISBN 978-0-521-88128-9. Retrieved 24 August 2013., chapters 5-9 � Mundici, D. The C*-Algebras of Three-Valued Logic. Logic Colloquium ’88, Proceedings of the Colloquium held in Padova 61–77 (1989). doi:10.1016/s0049-237x(08)70262-3 4.7 External links � Introduction to Many-Valued Logics by Bertram Fronhöfer. Handout from a Technische Universität Dresden 2011 summer class. (Despite the title, this is almost entirely about three-valued logics.)
  • 18 CHAPTER 4. THREE-VALUED LOGIC 4.8 Text and image sources, contributors, and licenses 4.8.1 Text � Four-valued logic Source: https://en.wikipedia.org/wiki/Four-valued_logic?oldid=630213717 Contributors: Hyacinth, Jason Quinn, Cje~enwiki, Ruud Koot, Fresheneesz, Mikeblas, SmackBot, Oli Filth, BIL, “alyosha”, CRGreathouse, Amalas, Cydebot, Em3ryguy, R'n'B, Xenogene, Dekart, Paraconsistent, Paradoxe allemand, AnomieBOT, Erik9bot, AvicAWB, Tijfo098, Helpful Pixie Bot, Kahtar and Anonymous: 3 � Many-valued logic Source: https://en.wikipedia.org/wiki/Many-valued_logic?oldid=670673489Contributors: Dan~enwiki, BryanDerk- sen, Tarquin, Taw, B4hand, Michael Hardy, JakeVortex, MartinHarper, Justin Johnson, Eric119, Snoyes, Cyan, DesertSteve, Rzach, Reddi, Hyacinth, Hadal, Wikibot, Wile E. Heresiarch, Filemon, Snobot, Giftlite, Kim Bruning, Dissident, Muke, Jason Quinn, Gub- bubu, Lucidish, Mindspillage, Rich Farmbrough, Leibniz, EmilJ, Nortexoid, PWilkinson, Lysdexia, Oleg Alexandrov, Woohookitty, Mindmatrix, Kzollman, Ruud Koot, BD2412, Rjwilmsi, MWAK, David H Braun (1964), CiaPan, Urocyon, SmackBot, Mhss, Pwjb, Vina-iwbot~enwiki, MagnaMopus, Bjankuloski06en~enwiki, Makyen, Courcelles, JRSpriggs, Lahiru k, CRGreathouse, Giorgiomug- naini, Gregbard, ParmenidesII, Peterdjones, Quibik, Letranova, Escarbot, PChalmer, .anacondabot, STBot, Caregiver, Gurchzilla, Hey- itspeter, TXiKiBoT, Don4of4, LBehounek, Linguist1, Soler97, Cobalttempest, Francvs, Mild Bill Hiccup, Timberframe, Gerhard- valentin, Pgallert, Addbot, Rdanneskjold, SpBot, ChartreuseCat, Luckas-bot, Yobot, Legobot II, AnomieBOT, JackieBot, TheAMmol- lusc, Gilo1969, Oursipan, Argumzio, LittleWink, Trappist the monk, ZéroBot, Reasonable Excuse, Tijfo098, RockMagnetist, G8yingri, Helpful Pixie Bot, Repep, Sebrider, Jochen Burghardt, LvdT88, JMP EAX, Tecolotl 91, Phormicola and Anonymous: 50 � Problem of future contingents Source: https://en.wikipedia.org/wiki/Problem_of_future_contingents?oldid=667681351 Contributors: Vadmium, Chalst, Miss Madeline, Koavf, Mercury McKinnon, SmackBot, Srnec, Monagz, Santa Sangre, O0pyromancer0o, CBM, Sdor- rance, Gregbard, Miguel de Servet, Barticus88, D. Webb, Arno Matthias, Stijn Vermeeren, R'n'B, Dionysiaca, Adavidb, Belovedfreak, Westfalr3, Ontoraul, Eletheia, Singinglemon~enwiki, CohesionBot, -Midorihana-, Spirals31, SchreiberBike, Qwfp, Addbot, Renamed user 5, Peter Damian (old), Yobot, AnomieBOT, Peter Damian, RjwilmsiBot, WikitanvirBot, Donner60, Tijfo098, Jack Greenmaven, Rezabot, Helpful Pixie Bot, Flosfa, CMDarling and Anonymous: 26 � Three-valued logic Source: https://en.wikipedia.org/wiki/Three-valued_logic?oldid=666966799 Contributors: Ray Van De Walker, Booyabazooka, Shellreef, Cyp, AugPi, Dcoetzee, Furrykef, Hyacinth, AnonMoos, Saforrest, Ancheta Wis, Giftlite, Gwalla, DavidCary, Monedula, Jason Quinn, Jds, Nayuki, WhiteDragon, B.d.mills, Kate, Gazpacho, Guppyfinsoup, Mindspillage, Foolip, Ben Standeven, Kwamikagami, Nickj, EmilJ, Mairi, Spoon!, Telamon~enwiki, RJFJR, Alai, Klparrot, Forderud, Jörg Knappen~enwiki, Ruud Koot, Ash- moo, BD2412, Qwertyus, Rjwilmsi, Salix alba, MaximRazin, Kakurady, YurikBot, Hillman, Trovatore, PrologFan, Vicarious, SmackBot, Tumbleman, Mhss, Bluebot, A Geek Tragedy, Cybercobra, Byelf2007, Bjankuloski06en~enwiki, Beard0, Norm mit, Judgesurreal777, Jason.grossman, Skapur, Ianji, SqlPac, ShelfSkewed, Shandris, Gregbard, Thijs!bot, Em3ryguy, Albmont, Loqi, Ssybesma, Nikpapag, Try0yrt, Ignat99, Peskydan, SparsityProblem, Robertgreer, Barraki, Dozen, Maghnus, Anonymous Dissident, Ruleof3, SieBot, Soler97, Svofski, Auntof6, Northernhenge, HumphreyW, Dekart, Addbot, DOI bot, Wireless friend, Luckas-bot, Yobot, AnomieBOT, Bci2, Fkereki, Omnipaedista, Douglas W. Jones, Fortdj33, LucienBOT, Oashi, Gire 3pich2005, Diannaa, MrSlasherX, EmausBot, Cogiati, Ti- jfo098, Matthiaspaul, G8yingri, BG19bot, BattyBot, DialaceStarvy, Leoesb1032, Caesuralyx, Erinius, میهاربا۲۰۱۲, Immanuel Thought- maker, JMP EAX and Anonymous: 80 4.8.2 Images � File:Brain.png Source: https://upload.wikimedia.org/wikipedia/commons/7/73/Nicolas_P._Rougier%27s_rendering_of_the_human_ brain.png License: GPL Contributors: http://www.loria.fr/~{}rougier Original artist: Nicolas Rougier � File:Gnome-searchtool.svg Source: https://upload.wikimedia.org/wikipedia/commons/1/1e/Gnome-searchtool.svgLicense: LGPLCon- tributors: http://ftp.gnome.org/pub/GNOME/sources/gnome-themes-extras/0.9/gnome-themes-extras-0.9.0.tar.gz Original artist: David Vignoni � File:Logic_portal.svg Source: https://upload.wikimedia.org/wikipedia/commons/7/7c/Logic_portal.svg License: CC BY-SA 3.0 Con- tributors: Own work Original artist: Watchduck (a.k.a. Tilman Piesk) � File:NaveGreca.jpg Source: https://upload.wikimedia.org/wikipedia/commons/1/12/NaveGreca.jpg License: Public domain Contribu- tors: scansion by original document Original artist: Poecus � File:Question_book-new.svg Source: https://upload.wikimedia.org/wikipedia/en/9/99/Question_book-new.svg License: Cc-by-sa-3.0 Contributors: Created from scratch in Adobe Illustrator. Based on Image:Question book.png created by User:Equazcion Original artist: Tkgd2007 � File:Translation_to_english_arrow.svg Source: https://upload.wikimedia.org/wikipedia/commons/8/8a/Translation_to_english_arrow. svgLicense: CC-BY-SA-3.0Contributors: Transferred from en.wikipedia; transferred to Commons byUser:Faigl.ladislav usingCommonsHelper. Original artist: tkgd2007. Original uploader was Tkgd2007 at en.wikipedia � File:Wiki_letter_w.svg Source: https://upload.wikimedia.org/wikipedia/en/6/6c/Wiki_letter_w.svg License: Cc-by-sa-3.0 Contributors: ? Original artist: ? � File:Wiki_letter_w_cropped.svg Source: https://upload.wikimedia.org/wikipedia/commons/1/1c/Wiki_letter_w_cropped.svg License: CC-BY-SA-3.0 Contributors: � Wiki_letter_w.svg Original artist: Wiki_letter_w.svg: Jarkko Piiroinen 4.8.3 Content license � Creative Commons Attribution-Share Alike 3.0 Four-valued logic Applications Electronics Software Notes Many-valued logic History Examples Kleene (strong) K3 and Priest logic P3 Bochvar’s internal three-valued logic (also known as Kleene’s weak three-valued logic) Belnap logic (B4) Gödel logics Gk and G∞ Łukasiewicz logics Lv and L∞ Product logic Π Post logics Pm Semantics Matrix semantics (logical matrices) Proof theory Relation to classical logic Suszko’s thesis Applications Research venues See also Notes References Further reading External links Problem of future contingents Aristotle’s solution Leibniz 20th century See also Notes Further reading External links Three-valued logic Representation of values Logics Kleene and Priest logics Łukasiewicz logic Bochvar logic ternary Post logic Modular algebras Application in SQL See also References Further reading External links Text and image sources, contributors, and licenses Text Images Content license
Please download to view
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
...

Many-Valued Logic 1

by man

on

Report

Category:

Documents

Download: 0

Comment: 0

212

views

Comments

Description

1. From Wikipedia, the free encyclopedia
2. Lexicographical order
Download Many-Valued Logic 1

Transcript

  • Many-valued logic 1 From Wikipedia, the free encyclopedia
  • Contents 1 Four-valued logic 1 1.1 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1.1 Electronics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1.2 Software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2 Many-valued logic 4 2.1 History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2.1 Kleene (strong) K3 and Priest logic P3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2.2 Bochvar’s internal three-valued logic (also known as Kleene’s weak three-valued logic) . . . 5 2.2.3 Belnap logic (B4) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2.4 Gödel logics Gk and G∞ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2.5 Łukasiewicz logics Lv and L∞ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2.6 Product logic Π . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2.7 Post logics Pm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.3 Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.3.1 Matrix semantics (logical matrices) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.4 Proof theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.5 Relation to classical logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.5.1 Suszko’s thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.6 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.7 Research venues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.8 See also . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.9 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.10 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.11 Further reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.12 External links . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3 Problem of future contingents 10 3.1 Aristotle’s solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.2 Leibniz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.3 20th century . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 i
  • ii CONTENTS 3.4 See also . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.5 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.6 Further reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.7 External links . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 4 Three-valued logic 14 4.1 Representation of values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 4.2 Logics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 4.2.1 Kleene and Priest logics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 4.2.2 Łukasiewicz logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 4.2.3 Bochvar logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.2.4 ternary Post logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.2.5 Modular algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.3 Application in SQL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.4 See also . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.5 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 4.6 Further reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 4.7 External links . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 4.8 Text and image sources, contributors, and licenses . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4.8.1 Text . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4.8.2 Images . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4.8.3 Content license . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
  • Chapter 1 Four-valued logic In logic, a four-valued logic is used to model signal values in digital circuits: the four values are Z, X and the boolean values 1 and 0. Z stands for high impedance or open circuit, while X stands for “unknown”. There is also a 9-valued logic standard by the IEEE called IEEE 1164. There are other types of four value logic, such as Belnap’s four-valued relevance logic: the possible values are 1) true, 2) false, 3) both true and false, and 4) neither true nor false. Belnap’s logic is designed to cope with multiple information sources such that if only true is found then true is assigned, if only false is found then false is assigned, if some sources say true and others say false then both is assigned, and if no information is given by any information source then neither is assigned. 1.1 Applications 1.1.1 Electronics Among the distinct logic values supported by digital electronics theory (as defined in VHDL's std_logic) are such diverse elements as: � 1 or High, usually representing TRUE. � 0 or Low, usually representing FALSE. � X representing a “Conflict”. � U representing “Unassigned” or “Unknown”. � - representing "Don't Care". � Z representing "high impedance", undriven line. � H, L andW are other high-impedance values, the weak pull to “High”, “Low” and “Don't Know” correspond- ingly. The “U” value does not exist in real-world circuits, it is merely a placeholder used in simulators and for design purposes. Some simulators support representation of the “Z” value, others do not. The “Z” value does exist in real-world circuits but only as an output state. Use of “U” value in simulation Many hardware description language (HDL) simulation tools, such as Verilog and VHDL, support an unknown value like that shown above during simulation of digital electronics. The unknown value may be the result of a design error, which the designer can correct before synthesis into an actual circuit. The unknown also represents uninitialised memory values and circuit inputs before the simulation has asserted what the real input value should be. HDL synthesis tools usually produce circuits that operate only on binary logic. 1
  • 2 CHAPTER 1. FOUR-VALUED LOGIC Use of “X” value in digital design When designing a digital circuit, some conditions may be outside the scope of the purpose that the circuit will perform. Thus, the designer does not care what happens under those conditions. In addition, the situation occurs that inputs to a circuit are masked by other signals so the value of that input has no effect on circuit behaviour. In these situations, it is traditional to use “X” as a placeholder to indicate "Don't Care" when building truth tables. This is especially common in state machine design and Karnaugh map simplification. The “X” values provide additional degrees of freedom to the final circuit design, generally resulting in a simplified and smaller circuit.[1] Once the circuit design is complete and a real circuit is constructed, the “X” values will no longer exist. They will become some tangible “0” or “1” value but could be either depending on the final design optimisation. Use of “Z” value for high impedance Main article: three-state Some digital devices support a form of three-state logic on their outputs only. The three states are “0”, “1”, and “Z”. Commonly referred to as tristate [2] logic (a trademark of National Semiconductor), it comprises the usual true and false states, with a third transparent high impedance state (or 'off-state') which effectively disconnects the logic output. This provides an effective way to connect several logic outputs to a single input, where all but one are put into the high impedance state, allowing the remaining output to operate in the normal binary sense. This is commonly used to connect banks of computer memory and other similar devices to a common data bus; a large number of devices can communicate over the same channel simply by ensuring only one is enabled at a time. It is important to note that while outputs can have one of three states, inputs can only recognise two. Hence the kind of relations shown in the table above do not occur. Although it could be argued that the high-impedance state is effectively an “unknown”, there is absolutely no provision in the vast majority of normal electronics to interpret a high-impedance state as a state in itself. Inputs can only detect “0” and “1”. When a digital input is left disconnected (i.e., when it is given a high impedance signal), the digital value interpreted by the input depends on the type of technology used. TTL technology will reliably default to a “1” state. On the other hand CMOS technology will temporarily hold the previous state seen on that input (due to the capacitance of the gate input). Over time, leakage current causes the CMOS input to drift in a random direction, possibly causing the input state to flip. Disconnected inputs on CMOS devices can pick up noise, they can cause oscillation, the supply current may dramatically increase (crowbar power) or the device may completely destroy itself. Exotic ternary-logic devices True three-valued logic can be implemented in electronics, although the complexity of design has thus far made it uneconomical to pursue commercially and interest has been primarily confined to research (see Setun); 'Normal' binary logic is simply cheaper to implement and in most cases can easily be configured to emulate ternary systems. There are, however, useful applications in fuzzy logic and error correction, and several true ternary logic devices have been manufactured. 1.1.2 Software Vehicle technology In the SAE J1939 standard, used for CAN data transmission in heavy road vehicles, there are four logical (boolean) values, False, True, Error Condition, and Not installed (represented by values 0-3). Error Condition means there is a technical problem obstacling data acquisition. The logics for that is for example True and Error Condition=Error Condition. Not installed is used for a feature which does not exist in this vehicle, and should be disregarded for logical calculation. On CAN, usually fixed data messages are sent containing many signal values each, so a signal representing a not-installed feature will be sent anyway.
  • 1.2. NOTES 3 1.2 Notes [1] Wakerly, John F (2001). Digital Design Principles & Practices. Prentice Hall. ISBN 0-13-090772-3. [2] National Semiconductor (1993), LS TTL Data Book, National Semiconductor Corporation
  • Chapter 2 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. 2.1 History The first known classical logician who didn't 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”[1]). 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. 2.2 Examples Main articles: Three-valued logic and Four-valued logic 2.2.1 Kleene (strong) K3 and Priest logic P3 Kleene's "(strong) logic of indeterminacy”K3 (sometimesKS3 ) and Priest’s “logic of paradox” add a third “undefined” or “indeterminate” truth value I. The truth functions for negation (¬), conjunction (∧), disjunction (∨), implication (→K), and biconditional (↔K) are given by:[2] 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 (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. K3 does not have any tautologies, while P3 has the same tautologies as classical two-valued logic. 4
  • 2.2. EXAMPLES 5 2.2.2 Bochvar’s internal three-valued logic (also known as Kleene’s weak three-valued logic) Another logic is Bochvar’s “internal” three-valued logic ( BI3 ) also called Kleene’s weak three-valued logic. Except for negation and biconditional, its truth tables are all different from the above.[3] 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.[4] 2.2.3 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. 2.2.4 Gödel logics Gk and G∞ In 1932 Gödel defined[5] a familyGk of many-valued logics, with finitely many truth values 0; 1k�1 ; 2k�1 ; : : : k�2k�1 ; 1 , for exampleG3 has the truth values 0; 12 ; 1 andG4 has 0; 13 ; 23 ; 1 . In a similar manner he defined a logic with infinitely many truth values,G1 , in which the truth values are all the real numbers in the interval [0; 1] . The designated truth value in these logics is 1. The conjunction ^ and the disjunction _ are defined respectively as the maximum and minimum of the operands: � u ^ v := minfu; vg � u _ v := maxfu; vg Negation :G and implication!G are defined as follows: � :Gu = ( 1; ifu = 0 0; ifu > 0 u!G v = ( 1; ifu � v 0; ifu > v Gödel logics are completely axiomatisable, that is to say it is possible to define a logical calculus in which all tautologies are provable. 2.2.5 Łukasiewicz logics Lv and L∞ Implication!L and negation :L were defined by Jan Łukasiewicz through the following functions: � :Lu := 1� u � u!L v := minf1; 1� u+ vg At first Łukasiewicz used these definition in 1920 for his three-valued logic L3 , with truth values 0; 12 ; 1 . In 1922 he developed a logic with infinitely many values L1 , in which the truth values spanned the real numbers in the interval [0; 1] . In both cases the designated truth walue was 1.[6] By adopting truth values defined in the same way as for Gödel logics 0; 1v�1 ; 2v�1 ; : : : ; v�2v�1 ; 1 , it is possible to create a finitely-valued family of logics Lv , the abovementioned L1 and the logic L@0 , in which the truth values are given by the rational numbers in the interval [0; 1] . The set of tautologies in L1 and L@0 is identical.
  • 6 CHAPTER 2. MANY-VALUED LOGIC 2.2.6 Product logic Π In product logic we have truth values in the interval [0; 1] , a conjunction � and an implication !� , defined as follows[7] � u� v := uv � u!� v := ( 1; ifu � v v u ; ifu > v Additionally there is a negative designated value 0 that denotes the concept of false. Through this value it is possible to define a negation :� and an additional conjunction ^� as follows: � :�u := u!� 0 � u ^� v := u� (u!� v) 2.2.7 Post logics Pm In 1921 Post defined a family of logics Pm with (as in Lv and Gk ) the truth values 0; 1m�1 ; 2m�1 ; : : : ; m�2m�1 ; 1 . Negation :P and disjunction _P are defined as follows: � :Pu := ( 1; ifu = 0 u� 1m�1 ; ifu 6= 0 � u _P v := maxfu; vg 2.3 Semantics 2.3.1 Matrix semantics (logical matrices) 2.4 Proof theory 2.5 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.
  • 2.6. APPLICATIONS 7 2.5.1 Suszko’s thesis See also: Principle of bivalence § Suszko’s thesis 2.6 Applications Known applications of many-valued logic can be roughly classified into two groups.[8] 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. 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, Field Programmable Gate Arrays (FPGA) etc. 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. 2.7 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.[9] There is also a Journal of Multiple-Valued Logic and Soft Computing.[10] 2.8 See also Mathematical logic � Degrees of truth � Fuzzy logic � Gödel logic � Kleene logic � Kleene algebra (with involution) � Łukasiewicz logic � MV-algebra � Post logic � Principle of bivalence � A. N. Prior � Relevance logic Philosophical logic
  • 8 CHAPTER 2. MANY-VALUED LOGIC � False dilemma � Mu Digital logic � MVCML, multiple-valued current-mode logic � IEEE 1164 a nine-valued standard for VHDL � IEEE 1364 a four-valued standard for Verilog � Noise-based logic 2.9 Notes 2.10 References [1] Hurley, Patrick. A Concise Introduction to Logic, 9th edition. (2006). [2] (Gottwald 2005, p. 19) [3] (Bergmann 2008, p. 80) [4] (Bergmann 2008, p. 80) [5] Gödel, Kurt (1932). “Zum intuitionistischen Aussagenkalkül”. Anzeiger Akademie der Wissenschaften Wien (69): 65f. [6] Kreiser, Lothar; Gottwald, Siegfried; Stelzner, Werner (1990). Nichtklassische Logik. Eine Einführung. Berlin: Akademie- Verlag. pp. 41ff –– 45ff. ISBN 978-3-05-000274-3. [7] Hajek, Petr: Fuzzy Logic. In: Edward N. Zalta: The Stanford Encyclopedia of Philosophy, Spring 2009. () [8] Dubrova, Elena (2002). Multiple-Valued Logic Synthesis and Optimization, in Hassoun S. and Sasao T., editors, Logic Synthesis and Verification, Kluwer Academic Publishers, pp. 89-114 [9] http://www.informatik.uni-trier.de/~{}ley/db/conf/ismvl/index.html [10] http://www.oldcitypublishing.com/MVLSC/MVLSC.html 2.11 Further reading General � Béziau J.-Y. (1997), What is many-valued logic ? Proceedings of the 27th International Symposium onMultiple- 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. � Bergmann, Merrie (2008), An introduction to many-valued and fuzzy logic: semantics, algebras, and derivation systems, Cambridge University Press, ISBN 978-0-521-88128-9 � Cignoli, R. L. O., D'Ottaviano, I, M. L., Mundici, D., (2000). Algebraic Foundations of Many-valued Reason- ing. Kluwer. � Malinowski, Grzegorz (1993). Many-valued logics. Clarendon Press. ISBN 978-0-19-853787-8. � S. Gottwald, A Treatise on Many-Valued Logics. Studies in Logic and Computation, vol. 9, Research Studies Press: Baldock, Hertfordshire, England, 2001. � Gottwald, Siegfried (2005). “Many-Valued Logics” (PDF).
  • 2.12. EXTERNAL LINKS 9 � Miller, D. Michael; Thornton, Mitchell A. (2008). Multiple valued logic: concepts and representations. Syn- thesis lectures on digital circuits and systems 12. Morgan & Claypool Publishers. ISBN 978-1-59829-190-2. � Hájek P., (1998), Metamathematics of fuzzy logic. Kluwer. (Fuzzy logic understood as many-valued logic sui generis.) 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 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: Many-valued 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 978-1-4020-9408-8. Covers proof theory of many-valued logics as well, in the tradition of Hájek. � Hähnle, Reiner (1993). Automated deduction in multiple-valued logics. Clarendon Press. ISBN 978-0-19- 853989-6. � Azevedo, Francisco (2003). Constraint solving over multi-valued logics: application to digital circuits. IOS Press. ISBN 978-1-58603-304-0. � Bolc, Leonard; Borowik, Piotr (2003). Many-valued Logics 2: Automated reasoning and practical applications. Springer. ISBN 978-3-540-64507-8. � Stanković, Radomir S.; Astola, Jaakko T.; Moraga, Claudio (2012). Representation of Multiple-Valued Logic Functions. Morgan & Claypool Publishers. doi:10.2200/S00420ED1V01Y201205DCS037. ISBN 978-1- 60845-942-1. 2.12 External links � Gottwald, Siegfried (2009). “Many-Valued Logic”. Stanford Encyclopedia of Philosophy. � Stanford Encyclopedia of Philosophy: "Truth Values"—by Yaroslav Shramko and Heinrich Wansing. � IEEE Computer Society's Technical Committee on Multiple-Valued Logic � Resources for Many-Valued Logic by Reiner Hähnle, Chalmers University � Many-valued Logics W3 Server (archived) � Yaroslav Shramko and Heinrich Wansing (2014). “Suszko’s Thesis”. Stanford Encyclopedia of Philosophy. � Carlos Caleiro, Walter Carnielli, Marcelo E. Coniglio and João Marcos, Two’s company: “The humbug of many logical values” in Jean-Yves Beziau, ed. (2007). Logica Universalis: Towards a General Theory of Logic (2nd ed.). Springer Science & Business Media. pp. 174–194. ISBN 978-3-7643-8354-1.
  • Chapter 3 Problem of future contingents Aristotle: if a sea-battle will not be fought tomorrow, then it was also true yesterday that it will not be fought. But all past truths are necessary truths. Therefore it is not possible that the battle will be fought Future contingent propositions (or simply, future contingents) are statements about states of affairs in the future that are neither necessarily true nor necessarily false. The problem of future contingents seems to have been first discussed by Aristotle in chapter 9 of his On Inter- pretation (De Interpretatione), using the famous sea-battle example.[1] Roughly a generation later, Diodorus Cronus from the Megarian school of philosophy stated a version of the problem in his notorious Master Argument.[2] The problem was later discussed by Leibniz. The problem can be expressed as follows. Suppose that a sea-battle will not be fought tomorrow. Then it was also true yesterday (and the week before, and last year) that it will not be fought, since any true statement about what will be the case was also true in the past. But all past truths are now necessary truths; therefore it is now necessarily true that the battle will not be fought, and thus the statement that it will be fought is necessarily false. Therefore it is not possible that the battle will be fought. In general, if something will not be the case, it is not possible for it to be the case. “For a man may predict an event ten thousand years beforehand, and another may predict the reverse; that which was truly predicted at the moment in the past will of necessity take place in the fullness of time” (18 b35). This conflicts with the idea that of our own free choice: that we have the power to determine or control the course of 10
  • 3.1. ARISTOTLE’S SOLUTION 11 events in the future, which seems impossible if what happens, or does not happen, is necessarily going to happen, or not happen. As Aristotle says, if so there would be no need “to deliberate or to take trouble, on the supposition that if we should adopt a certain course, a certain result would follow, while, if we did not, the result would not follow”. 3.1 Aristotle’s solution Aristotle solved the problem by asserting that the principle of bivalence found its exception in this paradox of the sea battles: in this specific case, what is impossible is that both alternatives can be possible at the same time: either there will be a battle, or there won't. Both options can't be simultaneously taken. Today, they are neither true nor false; but if one is true, then the other becomes false. According to Aristotle, it is impossible to say today if the proposition is correct: we must wait for the contingent realization (or not) of the battle, logic realizes itself afterwards: One of the two propositions in such instances must be true and the other false, but we cannot say determi- nately that this or that is false, but must leave the alternative undecided. One may indeed be more likely to be true than the other, but it cannot be either actually true or actually false. It is therefore plain that it is not necessary that of an affirmation and a denial, one should be true and the other false. For in the case of that which exists potentially, but not actually, the rule which applies to that which exists actually does not hold good. (§9) For Diodorus, the future battle was either impossible or necessary. Aristotle added a third term, contingency, which saves logic while in the same time leaving place for indetermination in reality. What is necessary is not that there will or that there won't be a battle tomorrow, but the dichotomy itself is necessary: A sea-fight must either take place tomorrow or not, but it is not necessary that it should take place tomorrow, neither is it necessary that it should not take place, yet it is necessary that it either should or should not take place tomorrow. (De Interpretatione, 9, 19 a 30.) Thus, the event always comes in the form of the future, undetermined event; logic always comes afterwards. Hegel would say the same thing by claiming that wisdom came at dusk. For Aristotle, this is also a practical, ethical question: to pretend that the future is determined would have unacceptable consequences for man. 3.2 Leibniz Leibniz gave another response to the paradox in §6 ofDiscourse on Metaphysics: “That God does nothing which is not orderly, and that it is not even possible to conceive of events which are not regular.” Thus, even a miracle, the Event by excellence, does not break the regular order of things. What is seen as irregular is only a default of perspective, but does not appear so in relation to universal order. Possibility exceeds human logics. Leibniz encounters this paradox because according to him: Thus the quality of king, which belonged to Alexander the Great, an abstraction from the subject, is not sufficiently determined to constitute an individual, and does not contain the other qualities of the same subject, nor everything which the idea of this prince includes. God, however, seeing the individual concept, or haecceity, of Alexander, sees there at the same time the basis and the reason of all the predicates which can be truly uttered regarding him; for instance that he will conquer Darius and Porus, even to the point of knowing a priori (and not by experience) whether he died a natural death or by poison,- facts which we can learn only through history. When we carefully consider the connection of things we see also the possibility of saying that there was always in the soul of Alexander marks of all that had happened to him and evidences of all that would happen to him and traces even of everything which occurs in the universe, although God alone could recognize them all. (§8) If everything which happens to Alexander derives from the haecceity of Alexander, then fatalism threatens Leibniz’s construction: We have said that the concept of an individual substance includes once for all everything which can ever happen to it and that in considering this concept one will be able to see everything which can truly be said
  • 12 CHAPTER 3. PROBLEM OF FUTURE CONTINGENTS concerning the individual, just as we are able to see in the nature of a circle all the properties which can be derived from it. But does it not seem that in this way the difference between contingent and necessary truths will be destroyed, that there will be no place for human liberty, and that an absolute fatality will rule as well over all our actions as over all the rest of the events of the world? To this I reply that a distinction must be made between that which is certain and that which is necessary. (§13) Against Aristotle’s separation between the subject and the predicate, Leibniz states: “Thus the content of the subject must always include that of the predicate in such a way that if one understands perfectly the concept of the subject, he will know that the predicate appertains to it also.” (§8) The predicate (what happens to Alexander) must be completely included in the subject (Alexander) “if one un- derstands perfectly the concept of the subject”. Leibniz henceforth distinguishes two types of necessity: necessary necessity and contingent necessity, or universal necessity vs singular necessity. Universal necessity concerns universal truths, while singular necessity concerns something necessary which could not be (it is thus a “contingent necessity”). Leibniz hereby uses the concept of compossible worlds. According to Leibniz, contingent acts such as “Caesar cross- ing the Rubicon” or “Adam eating the apple” are necessary: that is, they are singular necessities, contingents and accidentals, but which concerns the principle of sufficient reason. Furthermore, this leads Leibniz to conceive of the subject not as a universal, but as a singular: it is true that “Caesar crosses the Rubicon”, but it is true only of this Caesar at this time, not of any dictator nor of Caesar at any time (§8, 9, 13). Thus Leibniz conceives of substance as plural: there is a plurality of singular substances, which he calls monads. Leibniz hence creates a concept of the individual as such, and attributes to it events. There is a universal necessity, which is universally applicable, and a singular necessity, which applies to each singular substance, or event. There is one proper noun for each singular event: Leibniz creates a logic of singularity, which Aristotle thought impossible (he considered that there could only be knowledge of generality). 3.3 20th century One of the early motivations for the study of many-valued logics has been precisely this issue. In the early 20th century, the Polish formal logician Jan Łukasiewicz proposed three truth-values: the true, the false and the as-yet- undetermined. This approach was later developed by Arend Heyting and L. E. J. Brouwer;[3] see Łukasiewicz logic. Issues such as this have also been addressed in various temporal logics, where one can assert that "Eventually, either there will be a sea battle tomorrow, or there won't be.” (Which is true if “tomorrow” eventually occurs.) The Modal Fallacy The error in the argument underlying the alleged “Problem of Future Contingents” lies in the assumption that “X is the case” implies that “necessarily, X is the case”. In logic, this is known as the Modal Fallacy.[4] By asserting “A sea-fight must either take place tomorrow or not, but it is not necessary that it should take place tomorrow, neither is it necessary that it should not take place, yet it is necessary that it either should or should not take place tomorrow.” Aristotle is simply claiming “necessarily (a or not-a)”, which is correct. However, the next step in Aristotle’s reasoning seems to be: “If a is the case, then necessarily, a is the case”, which is a logical fallacy. Expressed in another way: (i) If a proposition is true, then it cannot be false. (ii) If a proposition cannot be false, then it is necessarily true. (iii) Therefore if a proposition is true, it is necessarily true. That is, there are no contingent propositions. Every proposition is either necessarily true or necessarily false. The fallacy arises in the ambiguity of the first premise. If we interpret it close to the English, we get: (iv) P entails it is not possible that not-P (v) It is not possible that not-P entails it is necessary that P (vi) Therefore, P entails it is necessary that P However, if we recognize that the original English expression (i) is potentially misleading, that it assigns a necessity to what is simply nothing more than a necessary condition, then we get instead as our premises: (vii) It is not possible that (P and not P) (viii) (It is not possible that not P) entails (it is necessary that P) From these latter two premises, one cannot validly infer the conclusion:
  • 3.4. SEE ALSO 13 (ix) P entails it is necessary that P 3.4 See also � Logical determinism � Free will � Principle of distributivity � Principle of plenitude � Truth-value link � In Borges' The Garden of Forking Paths, both alternatives happen, thus leading to what Deleuze calls “incom- possible worlds” 3.5 Notes [1] Dorothea Frede, The sea-battle reconsidered, Oxford Studies in Ancient Philosophy 1985, pp. 31-87. [2] Dialectical School entry by Susanne Bobzien in the Stanford Encyclopedia of Philosophy [3] Paul Tomassi (1999). Logic. Routledge. p. 124. ISBN 978-0-415-16696-6. [4] Norman Swartz, The Modal Fallacy 3.6 Further reading � Dorothea Frede (1985), The Sea-Battle Reconsidered, Oxford Studies in Ancient Philosophy 3, 31-87. � Peter Øhrstrøm; Per F. V. Hasle (1995). Temporal logic: from ancient ideas to artificial intelligence. Springer. ISBN 978-0-7923-3586-3. � Richard Gaskin (1995). The sea battle and the master argument: Aristotle and Diodorus Cronus on the meta- physics of the future. Walter de Gruyter. ISBN 978-3-11-014430-7. � Melvin Fitting; Richard L. Mendelsohn (1998). First-order modal logic. Springer. pp. 35–40. ISBN 978-0- 7923-5335-5. attempts to reconstruct both Aristotle’s and Diodorus’ arguments in propositional modal logic � John MacFarlane (2003), Sea Battles, Futures Contingents, and Relative Truth and Future Contingent and Relative Truth, The Philosophical Quarterly 53, 321-36 � Jules Vuillemin, Le chapitre IX du De Interpretatione d'Aristote - Vers une réhabilitation de l'opinion comme connaissance probable des choses contingentes, in Philosophiques, vol. X, n°1, April 1983 (French) 3.7 External links � Future Contingents entry by Peter Øhrstrøm and Per Hasle in the Stanford Encyclopedia of Philosophy � Medieval Theories of Future Contingents entry by Simo Knuuttila in the Stanford Encyclopedia of Philosophy � The Master Argument: The Sea Battle in De Intepretatione 9, Diodorus Cronus, Philo the Dialectician with a bibliography on Diodorus and the problem of future contingents
  • Chapter 4 Three-valued logic In logic, a three-valued logic (also trinary logic, trivalent, ternary, or trilean, sometimes abbreviated 3VL) is any of several many-valued logic systems in which there are three truth values indicating true, false and some indeter- minate third value. This is contrasted with the more commonly known bivalent logics (such as classical sentential or Boolean logic) which provide only for true and false. Conceptual form and basic ideas were initially created by Jan Łukasiewicz and C. I. Lewis. These were then re-formulated by Grigore Moisil in an axiomatic algebraic form, and also extended to n-valued logics in 1945. 4.1 Representation of values As with bivalent logic, truth values in ternary logic may be represented numerically using various representations of the ternary numeral system. A few of the more common examples are: � in balanced ternary, each digit has one of 3 values: −1, 0, or +1; these values may also be simplified to −, 0, +, respectively.[1] � in the redundant binary representation, each digit can have a value of �1, 0, 0, or 1 (the value 0 has two different representations) � in the ternary numeral system, each digit is a trit (trinary digit) having a value of: 0, 1, or 2 � in the skew binary number system, only most-significant non-zero digit has a value 2, and the remaining digits have a value of 0 or 1 � 1 for true, 2 for false, and 0 for unknown, unknowable/undecidable, irrelevant, or both.[2] � 0 for false, 1 for true, and a third non-integer “maybe” symbol such as ?, #, ½,[3] or xy. Inside a ternary computer, ternary values are represented by ternary signals. This article mainly illustrates a system of ternary propositional logic using the truth values {false, unknown, and true}, and extends conventional Boolean connectives to a trivalent context. Ternary predicate logics exist as well; these may have readings of the quantifier different from classical (binary) predicate logic, and may include alternative quantifiers as well. 4.2 Logics Where Boolean Logic has 4 monadic operators, the addition of a third value in ternary logic leads to a total of 27 distinct operators on a single input value. Similarly, where Boolean logic has 16 distinct diadic operators (operators with 2 inputs), ternary logic has 19,683 such operators. Where we can easily name a significant fraction of the Boolean operators (not, and, or, nand, nor, exclusive or), it is unreasonable to attempt to name all but a small fraction of the possible ternary operators.[4] 14
  • 4.2. LOGICS 15 4.2.1 Kleene and Priest logics See also: Kleene algebra (with involution) Below is a set of truth tables showing the logic operations for Kleene's “strong logic of indeterminacy” and Priest’s “logic of paradox”. In these truth tables, the unknown state can be thought of as neither true nor false in Kleene logic, or thought of as both true and false in Priest logic. The difference lies in the definition of tautologies. Where Kleene logic’s only designated truth value is T, Priest logic’s designated truth values are both T and U. In Kleene logic, the knowledge of whether any particular unknown state secretly represents true or false at any moment in time is not available. However, certain logical operations can yield an unambiguous result, even if they involve at least one unknown operand. For example, since true OR true equals true, and true OR false also equals true, one can infer that true OR unknown equals true, as well. In this example, since either bivalent state could be underlying the unknown state, but either state also yields the same result, a definitive true results in all three cases. If numeric values, e.g. balanced ternary values, are assigned to false, unknown and true such that false is less than unknown and unknown is less than true, then A AND B AND C... = MIN(A, B, C ...) and A OR B OR C ... = MAX(A, B, C...). Material implication for Kleene logic can be defined as: A! B def= NOT(A) OR B , and its truth table is which differs from that for Łukasiewicz logic (described below). Kleene logic has no tautologies (valid formulas) because whenever all of the atomic components of a well-formed formula are assigned the value Unknown, the formula itself must also have the value Unknown. (And the only designated truth value for Kleene logic is True.) However, the lack of valid formulas does not mean that it lacks valid arguments and/or inference rules. An argument is semantically valid in Kleene logic if, whenever (for any interpretation/model) all of its premises are True, the conclusion must also be True. (Note that the Logic of Paradox (LP) has the same truth tables as Kleene logic, but it has two designated truth values instead of one; these are: True and Both (the analogue of Unknown), so that LP does have tautologies but it has fewer valid inference rules.)[5] 4.2.2 Łukasiewicz logic Further information: Łukasiewicz logic The Łukasiewicz Ł3 has the same tables for AND, OR, and NOT as the Kleene logic given above, but differs in its definition of implication. This section follows the presentation from Malinowski’s chapter of the Handbook of the History of Logic, vol 8.[6] In fact, using Łukasiewicz’s implication and negation, the other usual connectives may be derived as: � A ∨ B = (A→ B) → B � A ∧ B = ¬(¬A ∨ ¬ B) � A↔ B = (A→ B) ∧ (B→ A) It’s also possible to derive a few other useful unary operators (first derived by Tarski in 1921): � MA = ¬A→ A � LA = ¬M¬A � IA =MA ∧ ¬LA They have the following truth tables: M is read as “it is not false that...” or in the (unsuccessful) Tarski–Łukasiewicz attempt to axiomatize modal logic using a three-valued logic, “it is possible that...” L is read “it is true that...” or “it is necessary that...” Finally I is read “it is unknown that...” or “it is contingent that...”
  • 16 CHAPTER 4. THREE-VALUED LOGIC In Łukasiewicz’s Ł3 the designated value is True, meaning that only a proposition having this value everywhere is considered a tautology. For example A → A and A ↔ A are tautologies in Ł3 and also in classical logic. Not all tautologies of classical logic lift to Ł3 “as is”. For example, the law of excluded middle, A ∨ ¬A, and the law of non-contradiction, ¬(A ∧ ¬A) are not tautologies in Ł3. However, using the operator I defined above, it is possible to state tautologies that are their analogues: � A ∨ IA ∨ ¬A [law of excluded fourth] � ¬(A ∧ ¬IA ∧ ¬A) [extended contradiction principle]. 4.2.3 Bochvar logic Main article: Many-valued_logic § Bochvar.27s_internal_three-valued_logic_.28also_known_as_Kleene.27s_weak_three- valued_logic.29 4.2.4 ternary Post logic 4.2.5 Modular algebras Some 3VL modular algebras have been introduced more recently, motivated by circuit problems rather than philo- sophical issues:[7] � Cohn algebra � Pradhan algebra � Dubrova and Muzio algebra 4.3 Application in SQL Main article: Null (SQL) The database structural query language SQL implements ternary logic as a means of handling comparisons with NULL field content. The original intent of NULL in SQL was to represent missing data in a database, i.e. the assumption that an actual value exists, but that the value is not currently recorded in the database. SQL uses a common fragment of the Kleene K3 logic, restricted to AND, OR, and NOT tables. In SQL, the intermediate value is intended to be interpreted as UNKNOWN. Explicit comparisons with NULL, including that of another NULL yields UNKNOWN. However this choice of semantics is abandoned for some set operations, e.g. UNION or INTERSECT, where NULLs are treated as equal with each other. Critics assert that this inconsistency deprives SQL of intuitive semantics in its treatment of NULLs.[8] The SQL standard defines an optional feature called F571, which adds some unary operators, among which IS UNKNOWN corresponding to the Łukasiewicz I in this article. The addition of IS UNKNOWN to the other operators of SQL’s three-valued logic makes the SQL three-valued logic functionally complete,[9] meaning its logical operators can express (in combination) any conceivable three-valued logical function. 4.4 See also � Aymara language – a Bolivian language famous for using ternary rather than binary logic[10] � Binary logic (disambiguation) � Boolean algebra (structure) � Boolean function
  • 4.5. REFERENCES 17 � Digital circuit � Four-valued logic � Setun - an experimental Russian computer which was based on ternary logic � Ternary numeral system (and Balanced ternary) � Three-state logic 4.5 References [1] Knuth, Donald E. (1981). The Art of Computer Programming Vol. 2. Reading, Mass.: Addison-Wesley Publishing Com- pany. p. 190. [2] Hayes, Brian (November–December 2001). “Third Base”. American Scientist (Sigma Xi, the Scientific Research Society) 89 (6): 490–494. doi:10.1511/2001.6.490. [3] The Penguin Dictionary of Mathematics. 2nd Edition. London, England: Penguin Books. 1998. p. 417. [4] Douglas W. Jones, Standard Ternary Logic, Feb. 11, 2013 [5] http://www.uky.edu/~{}look/Phi520-Lecture7.pdf [6] Grzegorz Malinowski, “Many-valued Logic and its Philosophy” in Dov M. Gabbay, John Woods (eds.) Handbook of the History of Logic Volume 8. The Many Valued and Nonmonotonic Turn in Logic, Elsevier, 2009 [7] Miller, D. Michael; Thornton, Mitchell A. (2008). Multiple valued logic: concepts and representations. Synthesis lectures on digital circuits and systems 12. Morgan & Claypool Publishers. pp. 41–42. ISBN 978-1-59829-190-2. [8] Ron van der Meyden, "Logical approaches to incomplete information: a survey" in Chomicki, Jan; Saake, Gunter (Eds.) Logics for Databases and Information Systems, Kluwer Academic Publishers ISBN 978-0-7923-8129-7, p. 344; PS preprint (note: page numbering differs in preprint from the published version) [9] C. J. Date, Relational database writings, 1991-1994, Addison-Wesley, 1995, p. 371 [10] “El idioma de los aymaras” (in Spanish). Aymara Uta. Retrieved 2013-08-20. 4.6 Further reading � Bergmann, Merrie (2008). An Introduction to Many-Valued and Fuzzy Logic: Semantics, Algebras, and Deriva- tion Systems. Cambridge University Press. ISBN 978-0-521-88128-9. Retrieved 24 August 2013., chapters 5-9 � Mundici, D. The C*-Algebras of Three-Valued Logic. Logic Colloquium ’88, Proceedings of the Colloquium held in Padova 61–77 (1989). doi:10.1016/s0049-237x(08)70262-3 4.7 External links � Introduction to Many-Valued Logics by Bertram Fronhöfer. Handout from a Technische Universität Dresden 2011 summer class. (Despite the title, this is almost entirely about three-valued logics.)
  • 18 CHAPTER 4. THREE-VALUED LOGIC 4.8 Text and image sources, contributors, and licenses 4.8.1 Text � Four-valued logic Source: https://en.wikipedia.org/wiki/Four-valued_logic?oldid=630213717 Contributors: Hyacinth, Jason Quinn, Cje~enwiki, Ruud Koot, Fresheneesz, Mikeblas, SmackBot, Oli Filth, BIL, “alyosha”, CRGreathouse, Amalas, Cydebot, Em3ryguy, R'n'B, Xenogene, Dekart, Paraconsistent, Paradoxe allemand, AnomieBOT, Erik9bot, AvicAWB, Tijfo098, Helpful Pixie Bot, Kahtar and Anonymous: 3 � Many-valued logic Source: https://en.wikipedia.org/wiki/Many-valued_logic?oldid=670673489Contributors: Dan~enwiki, BryanDerk- sen, Tarquin, Taw, B4hand, Michael Hardy, JakeVortex, MartinHarper, Justin Johnson, Eric119, Snoyes, Cyan, DesertSteve, Rzach, Reddi, Hyacinth, Hadal, Wikibot, Wile E. Heresiarch, Filemon, Snobot, Giftlite, Kim Bruning, Dissident, Muke, Jason Quinn, Gub- bubu, Lucidish, Mindspillage, Rich Farmbrough, Leibniz, EmilJ, Nortexoid, PWilkinson, Lysdexia, Oleg Alexandrov, Woohookitty, Mindmatrix, Kzollman, Ruud Koot, BD2412, Rjwilmsi, MWAK, David H Braun (1964), CiaPan, Urocyon, SmackBot, Mhss, Pwjb, Vina-iwbot~enwiki, MagnaMopus, Bjankuloski06en~enwiki, Makyen, Courcelles, JRSpriggs, Lahiru k, CRGreathouse, Giorgiomug- naini, Gregbard, ParmenidesII, Peterdjones, Quibik, Letranova, Escarbot, PChalmer, .anacondabot, STBot, Caregiver, Gurchzilla, Hey- itspeter, TXiKiBoT, Don4of4, LBehounek, Linguist1, Soler97, Cobalttempest, Francvs, Mild Bill Hiccup, Timberframe, Gerhard- valentin, Pgallert, Addbot, Rdanneskjold, SpBot, ChartreuseCat, Luckas-bot, Yobot, Legobot II, AnomieBOT, JackieBot, TheAMmol- lusc, Gilo1969, Oursipan, Argumzio, LittleWink, Trappist the monk, ZéroBot, Reasonable Excuse, Tijfo098, RockMagnetist, G8yingri, Helpful Pixie Bot, Repep, Sebrider, Jochen Burghardt, LvdT88, JMP EAX, Tecolotl 91, Phormicola and Anonymous: 50 � Problem of future contingents Source: https://en.wikipedia.org/wiki/Problem_of_future_contingents?oldid=667681351 Contributors: Vadmium, Chalst, Miss Madeline, Koavf, Mercury McKinnon, SmackBot, Srnec, Monagz, Santa Sangre, O0pyromancer0o, CBM, Sdor- rance, Gregbard, Miguel de Servet, Barticus88, D. Webb, Arno Matthias, Stijn Vermeeren, R'n'B, Dionysiaca, Adavidb, Belovedfreak, Westfalr3, Ontoraul, Eletheia, Singinglemon~enwiki, CohesionBot, -Midorihana-, Spirals31, SchreiberBike, Qwfp, Addbot, Renamed user 5, Peter Damian (old), Yobot, AnomieBOT, Peter Damian, RjwilmsiBot, WikitanvirBot, Donner60, Tijfo098, Jack Greenmaven, Rezabot, Helpful Pixie Bot, Flosfa, CMDarling and Anonymous: 26 � Three-valued logic Source: https://en.wikipedia.org/wiki/Three-valued_logic?oldid=666966799 Contributors: Ray Van De Walker, Booyabazooka, Shellreef, Cyp, AugPi, Dcoetzee, Furrykef, Hyacinth, AnonMoos, Saforrest, Ancheta Wis, Giftlite, Gwalla, DavidCary, Monedula, Jason Quinn, Jds, Nayuki, WhiteDragon, B.d.mills, Kate, Gazpacho, Guppyfinsoup, Mindspillage, Foolip, Ben Standeven, Kwamikagami, Nickj, EmilJ, Mairi, Spoon!, Telamon~enwiki, RJFJR, Alai, Klparrot, Forderud, Jörg Knappen~enwiki, Ruud Koot, Ash- moo, BD2412, Qwertyus, Rjwilmsi, Salix alba, MaximRazin, Kakurady, YurikBot, Hillman, Trovatore, PrologFan, Vicarious, SmackBot, Tumbleman, Mhss, Bluebot, A Geek Tragedy, Cybercobra, Byelf2007, Bjankuloski06en~enwiki, Beard0, Norm mit, Judgesurreal777, Jason.grossman, Skapur, Ianji, SqlPac, ShelfSkewed, Shandris, Gregbard, Thijs!bot, Em3ryguy, Albmont, Loqi, Ssybesma, Nikpapag, Try0yrt, Ignat99, Peskydan, SparsityProblem, Robertgreer, Barraki, Dozen, Maghnus, Anonymous Dissident, Ruleof3, SieBot, Soler97, Svofski, Auntof6, Northernhenge, HumphreyW, Dekart, Addbot, DOI bot, Wireless friend, Luckas-bot, Yobot, AnomieBOT, Bci2, Fkereki, Omnipaedista, Douglas W. Jones, Fortdj33, LucienBOT, Oashi, Gire 3pich2005, Diannaa, MrSlasherX, EmausBot, Cogiati, Ti- jfo098, Matthiaspaul, G8yingri, BG19bot, BattyBot, DialaceStarvy, Leoesb1032, Caesuralyx, Erinius, میهاربا۲۰۱۲, Immanuel Thought- maker, JMP EAX and Anonymous: 80 4.8.2 Images � File:Brain.png Source: https://upload.wikimedia.org/wikipedia/commons/7/73/Nicolas_P._Rougier%27s_rendering_of_the_human_ brain.png License: GPL Contributors: http://www.loria.fr/~{}rougier Original artist: Nicolas Rougier � File:Gnome-searchtool.svg Source: https://upload.wikimedia.org/wikipedia/commons/1/1e/Gnome-searchtool.svgLicense: LGPLCon- tributors: http://ftp.gnome.org/pub/GNOME/sources/gnome-themes-extras/0.9/gnome-themes-extras-0.9.0.tar.gz Original artist: David Vignoni � File:Logic_portal.svg Source: https://upload.wikimedia.org/wikipedia/commons/7/7c/Logic_portal.svg License: CC BY-SA 3.0 Con- tributors: Own work Original artist: Watchduck (a.k.a. Tilman Piesk) � File:NaveGreca.jpg Source: https://upload.wikimedia.org/wikipedia/commons/1/12/NaveGreca.jpg License: Public domain Contribu- tors: scansion by original document Original artist: Poecus � File:Question_book-new.svg Source: https://upload.wikimedia.org/wikipedia/en/9/99/Question_book-new.svg License: Cc-by-sa-3.0 Contributors: Created from scratch in Adobe Illustrator. Based on Image:Question book.png created by User:Equazcion Original artist: Tkgd2007 � File:Translation_to_english_arrow.svg Source: https://upload.wikimedia.org/wikipedia/commons/8/8a/Translation_to_english_arrow. svgLicense: CC-BY-SA-3.0Contributors: Transferred from en.wikipedia; transferred to Commons byUser:Faigl.ladislav usingCommonsHelper. Original artist: tkgd2007. Original uploader was Tkgd2007 at en.wikipedia � File:Wiki_letter_w.svg Source: https://upload.wikimedia.org/wikipedia/en/6/6c/Wiki_letter_w.svg License: Cc-by-sa-3.0 Contributors: ? Original artist: ? � File:Wiki_letter_w_cropped.svg Source: https://upload.wikimedia.org/wikipedia/commons/1/1c/Wiki_letter_w_cropped.svg License: CC-BY-SA-3.0 Contributors: � Wiki_letter_w.svg Original artist: Wiki_letter_w.svg: Jarkko Piiroinen 4.8.3 Content license � Creative Commons Attribution-Share Alike 3.0 Four-valued logic Applications Electronics Software Notes Many-valued logic History Examples Kleene (strong) K3 and Priest logic P3 Bochvar’s internal three-valued logic (also known as Kleene’s weak three-valued logic) Belnap logic (B4) Gödel logics Gk and G∞ Łukasiewicz logics Lv and L∞ Product logic Π Post logics Pm Semantics Matrix semantics (logical matrices) Proof theory Relation to classical logic Suszko’s thesis Applications Research venues See also Notes References Further reading External links Problem of future contingents Aristotle’s solution Leibniz 20th century See also Notes Further reading External links Three-valued logic Representation of values Logics Kleene and Priest logics Łukasiewicz logic Bochvar logic ternary Post logic Modular algebras Application in SQL See also References Further reading External links Text and image sources, contributors, and licenses Text Images Content license
Fly UP