Finite-valued logic

Last updated

In logic, a finite-valued logic (also finitely many-valued logic) is a propositional calculus in which truth values are discrete. Traditionally, in Aristotle's logic, the bivalent logic, also known as binary logic was the norm, as the law of the excluded middle precluded more than two possible values (i.e., "true" and "false") for any proposition. [1] Modern three-valued logic (ternary logic) allows for an additional possible truth value (i.e. "undecided"). [2]

Contents

The term finitely many-valued logic is typically used to describe many-valued logic having three or more, but not infinite, truth values. The term finite-valued logic encompasses both finitely many-valued logic and bivalent logic. [3] [4] Fuzzy logics, which allow for degrees of values between "true" and "false", are typically not considered forms of finite-valued logic. [5] However, finite-valued logic can be applied in Boolean-valued modeling, [6] [7] description logics, [8] and defuzzification [9] [10] of fuzzy logic. A finite-valued logic is decidable (sure to determine outcomes of the logic when it is applied to propositions) if and only if it has a computational semantics. [11]

History

Aristotle's collected works regarding logic, known as the Organon , describe bivalent logic primarily, though Aristotle's views may have allowed for propositions that are not actually true or false. The Organon influenced philosophers and mathematicians throughout the Enlightenment. [12] [13] George Boole developed an algebraic structure and an algorithmic probability theory based on bivalent logic in the 19th century. [14]

Jan Łukasiewicz developed a system of three-valued logic in 1920. Emil Leon Post introduced further truth degrees in 1921. [15]

Stephen Cole Kleene and Ulrich Blau expanded the three-valued logic system of Łukasiewicz, for computer applications and for natural language analyses, respectively. Nuel Belnap and J. Michael Dunn developed a four-valued logic for computer applications in 1977. [16] Since the mid-1970s, various procedures for providing arbitrary finite-valued logics have been developed. [17]

Examples

In linguistics, finite-valued logic is used to treat presuppositions as product systems with ordered pairs of truth degrees, or truth tables. This enables assumptions built into verbal or written statements to be associated with varying degrees of truth values in the course of natural-language processing. [18]

In the study of formal languages, finite-valued logic has shown that encapsulating a truth predicate in a language can render the language inconsistent. Saul Kripke has built on work pioneered by Alfred Tarski [19] to demonstrate that such a truth predicate can be modeled using three-valued logic. [20]

Philosophical questions, including the Sorites paradox, have been considered based on a finite-valued logic known as fuzzy plurivaluationism. [21] The Sorites paradox suggests that if adding a grain of sand to something that is not a heap cannot create a heap, then a heap of sand cannot be created. A logical model of a heap in which there are as many truth degrees as grains of sand tends to refute that suggestion. [22]

In electronics design, a logical model of the stable states of a circuit, in which there are as many truth degrees as there are states, serves as a model for finite-valued switching. [23] Three-valued operators can be realized in integrated circuits. [24]

In fuzzy logic, typically applied for approximate reasoning, a finitely-valued logic can represent propositions that may acquire values within a finite set. [25]

In mathematics, logical matrices having multiple truth degrees are used to model systems of axioms. [26]

Biophysical indications suggest that in the brain, synaptic charge injections occur in finite steps, [27] and that neuron arrangements can be modeled based on the probability distribution of a finitely valued random variable. [28]

In the study of logic itself, finite-valued logic has served as an aid to understand the nature and existence of infinite-valued logic. Kurt Gödel attempted to comprehend the human ability for logical intuition in terms of finite-valued logic before concluding that the ability is based on infinite-valued logic. [29]

See also

Related Research Articles

<span class="mw-page-title-main">Logical disjunction</span> Logical connective OR

In logic, disjunction, also known as logical disjunction or logical or or logical addition or inclusive disjunction, is a logical connective typically notated as and read aloud as "or". For instance, the English language sentence "it is sunny or it is warm" can be represented in logic using the disjunctive formula , assuming that abbreviates "it is sunny" and abbreviates "it is warm".

The propositional calculus is a branch of logic. It is also called propositional logic, statement logic, sentential calculus, sentential logic, or sometimes zeroth-order logic. It deals with propositions and relations between propositions, including the construction of arguments based on them. Compound propositions are formed by connecting propositions by logical connectives representing the truth functions of conjunction, disjunction, implication, biconditional, and negation. Some sources include other connectives, as in the table below.

In logic, the semantic principleof bivalence states that every declarative sentence expressing a proposition has exactly one truth value, either true or false. A logic satisfying this principle is called a two-valued logic or bivalent logic.

<span class="mw-page-title-main">Sheffer stroke</span> Logical operation

In Boolean functions and propositional calculus, the Sheffer stroke denotes a logical operation that is equivalent to the negation of the conjunction operation, expressed in ordinary language as "not both". It is also called non-conjunction, or alternative denial, or NAND. In digital electronics, it corresponds to the NAND gate. It is named after Henry Maurice Sheffer and written as or as or as or as in Polish notation by Łukasiewicz.

Many-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 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, four-valued, nine-valued, the finite-valued with more than three values, and the infinite-valued (infinitely-many-valued), such as fuzzy logic and probability logic.

Fuzzy logic is a form of many-valued logic in which the truth value of variables may be any real number between 0 and 1. It is employed to handle the concept of partial truth, where the truth value may range between completely true and completely false. By contrast, in Boolean logic, the truth values of variables may only be the integer values 0 or 1.

Classical logic or Frege–Russell logic is the intensively studied and most widely used class of deductive logic. Classical logic has had much influence on analytic philosophy.

In logic and mathematics, a truth value, sometimes called a logical value, is a value indicating the relation of a proposition to truth, which in classical logic has only two possible values.

In mathematics and logic, an axiomatic system is any set of primitive notions and axioms to logically derive theorems. A theory is a consistent, relatively-self-contained body of knowledge which usually contains an axiomatic system and all its derived theorems. An axiomatic system that is completely described is a special kind of formal system. A formal theory is an axiomatic system that describes a set of sentences that is closed under logical implication. A formal proof is a complete rendition of a mathematical proof within a formal system.

<span class="mw-page-title-main">Sorites paradox</span> Logical paradox from vague predicates

The sorites paradox is a paradox that results from vague predicates. A typical formulation involves a heap of sand, from which grains are removed individually. With the assumption that removing a single grain does not cause a heap to not be considered a heap anymore, the paradox is to consider what happens when the process is repeated enough times that only one grain remains: is it still a heap? If not, when did it change from a heap to a non-heap?

In logic, a three-valued logic is any of several many-valued logic systems in which there are three truth values indicating true, false, and some third value. This is contrasted with the more commonly known bivalent logics which provide only for true and false.

In abstract algebra, a branch of pure mathematics, an MV-algebra is an algebraic structure with a binary operation , a unary operation , and the constant , satisfying certain axioms. MV-algebras are the algebraic semantics of Łukasiewicz logic; the letters MV refer to the many-valued logic of Łukasiewicz. MV-algebras coincide with the class of bounded commutative BCK algebras.

Non-classical logics are formal systems that differ in a significant way from standard logical systems such as propositional and predicate logic. There are several ways in which this is commonly the case, including by way of extensions, deviations, and variations. The aim of these departures is to make it possible to construct different models of logical consequence and logical truth.

Logic is the formal science of using reason and is considered a branch of both philosophy and mathematics and to a lesser extent computer science. Logic investigates and classifies the structure of statements and arguments, both through the study of formal systems of inference and the study of arguments in natural language. The scope of logic can therefore be very large, ranging from core topics such as the study of fallacies and paradoxes, to specialized analyses of reasoning such as probability, correct reasoning, and arguments involving causality. One of the aims of logic is to identify the correct and incorrect inferences. Logicians study the criteria for the evaluation of arguments.

In mathematics and philosophy, Łukasiewicz logic is a non-classical, many-valued logic. It was originally defined in the early 20th century by Jan Łukasiewicz as a three-valued modal logic; it was later generalized to n-valued as well as infinitely-many-valued (ℵ0-valued) variants, both propositional and first order. The ℵ0-valued version was published in 1930 by Łukasiewicz and Alfred Tarski; consequently it is sometimes called the Łukasiewicz–Tarski logic. It belongs to the classes of t-norm fuzzy logics and substructural logics.

T-norm fuzzy logics are a family of non-classical logics, informally delimited by having a semantics that takes the real unit interval [0, 1] for the system of truth values and functions called t-norms for permissible interpretations of conjunction. They are mainly used in applied fuzzy logic and fuzzy set theory as a theoretical basis for approximate reasoning.

Łukasiewicz–Moisil algebras were introduced in the 1940s by Grigore Moisil in the hope of giving algebraic semantics for the n-valued Łukasiewicz logic. However, in 1956 Alan Rose discovered that for n ≥ 5, the Łukasiewicz–Moisil algebra does not model the Łukasiewicz logic. A faithful model for the ℵ0-valued (infinitely-many-valued) Łukasiewicz–Tarski logic was provided by C. C. Chang's MV-algebra, introduced in 1958. For the axiomatically more complicated (finite) n-valued Łukasiewicz logics, suitable algebras were published in 1977 by Revaz Grigolia and called MVn-algebras. MVn-algebras are a subclass of LMn-algebras, and the inclusion is strict for n ≥ 5. In 1982 Roberto Cignoli published some additional constraints that added to LMn-algebras produce proper models for n-valued Łukasiewicz logic; Cignoli called his discovery proper Łukasiewicz algebras.

In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values true and false, usually denoted 1 and 0, whereas in elementary algebra the values of the variables are numbers. Second, Boolean algebra uses logical operators such as conjunction (and) denoted as ∧, disjunction (or) denoted as ∨, and negation (not) denoted as ¬. Elementary algebra, on the other hand, uses arithmetic operators such as addition, multiplication, subtraction, and division. Boolean algebra is therefore a formal way of describing logical operations in the same way that elementary algebra describes numerical operations.

In logic, an infinite-valued logic is a many-valued logic in which truth values comprise a continuous range. Traditionally, in Aristotle's logic, logic other than bivalent logic was abnormal, as the law of the excluded middle precluded more than two possible values for any proposition. Modern three-valued logic allows for an additional possible truth value and is an example of finite-valued logic in which truth values are discrete, rather than continuous. Infinite-valued logic comprises continuous fuzzy logic, though fuzzy logic in some of its forms can further encompass finite-valued logic. For example, finite-valued logic can be applied in Boolean-valued modeling, description logics, and defuzzification of fuzzy logic.

References

  1. ↑ Weisstein, Eric (2018). "Law of the Excluded Middle". MathWorld--A Wolfram Web Resource.
  2. ↑ Weisstein, Eric (2018). "Three-Valued Logic". MathWorld--A Wolfram Web Resource.
  3. ↑ Kretzmann, Norman (1968). "IV, section 2. 'Infinitely Many' and 'Finitely Many'". William of Sherwood's Treatise on Syncategorematic Words. University of Minnesota Press. ISBN   9780816658053.
  4. ↑ Smith, Nicholas J.J. (2010). "Article 2.6" (PDF). Many-Valued Logics. Routledge. Archived from the original (PDF) on 2018-04-08. Retrieved 2018-05-16.
  5. ↑ Weisstein, Eric (2018). "Fuzzy Logic". MathWorld--A Wolfram Web Resource.
  6. ↑ Klawltter, Warren A. (1976). Boolean values for fuzzy sets. Theses and Dissertations, paper 2025 (Thesis). Lehigh Preserve.
  7. ↑ Perović, Aleksandar (2006). "Fuzzy Sets – a Boolean Valued Approach" (PDF). 4th Serbian-Hungarian Joint Symposium on Intelligent Systems. Conferences and Symposia @ Óbuda University.
  8. ↑ Cerami, Marco; García-Cerdaña, Àngel; Esteva, Frances (2014). "On finitely-valued Fuzzy Description Logics". International Journal of Approximate Reasoning. 55 (9): 1890–1916. doi: 10.1016/j.ijar.2013.09.021 . hdl:10261/131932.
  9. ↑ Schockaert, Steven; Janssen, Jeroen; Vermeir, Dirk (2012). "Satisfiability Checking in Łukasiewicz Logic as Finite Constraint Satisfaction". Journal of Automated Reasoning. 49 (4): 493–550. doi:10.1007/s10817-011-9227-0. S2CID   17959156.
  10. ↑ "1.4.4 Defuzzification" (PDF). Fuzzy Logic. Swiss Federal Institute of Technology Zurich. 2014. p. 4. Archived from the original (PDF) on 2009-07-09. Retrieved 2018-05-16.
  11. ↑ Stachniak, Zbigniew (1989). "Many-valued computational logics". Journal of Philosophical Logic. 18 (3): 257–274. doi:10.1007/BF00274067. S2CID   27383449.
  12. ↑ Folse, Henry. "The Aristotelian Theory of Knowledge". Department of Philosophy, College of Arts and Sciences, Loyola University.
  13. ↑ Rescher, Nicholas (1968). "Many-Valued Logic". Topics in Philosophical Logic. Humanities Press Synthese Library volume 17. pp. 54–125. doi:10.1007/978-94-017-3546-9_6. ISBN   978-90-481-8331-9.
  14. ↑ Kuphaldt, Tony. "7". Introduction to Boolean Algebra. Vol. 4.{{cite book}}: |work= ignored (help)
  15. ↑ Gottwald, Siegfried (2015). "Many-Valued Logic". 5. History of Many-Valued Logic. Stanford Encyclopedia of Philosophy.
  16. ↑ Gottwald, Siegfried (2015). "Many-Valued Logic". 3. Systems of Many-Valued Logic. Stanford Encyclopedia of Philosophy.
  17. ↑ Caleiro, Carlos; Marcos, João (2009). "Background". Classic-Like Analytic Tableaux for Finite-Valued Logics (PDF). Springer. pp. 268–280.{{cite book}}: |work= ignored (help)
  18. ↑ Dubois, Didier (2011). "Uncertainty Theories, Degrees of Truth and Epistemic States" (PDF). International Conference on Agents and Artificial Intelligence. Archived from the original (PDF) on 2017-08-29. Retrieved 2018-05-16.
  19. ↑ Rucker, Rudy. Infinity and the Mind. Princeton University Press., section 655 "What is Truth?"
  20. ↑ Kripke, Saul (1975). "Outline of a Theory of Truth" (PDF). The Journal of Philosophy. 72 (19): 690–716. doi:10.2307/2024634. JSTOR   2024634. S2CID   16684236.
  21. ↑ Behounek, Libor (2011). "In Which Sense Is Fuzzy Logic a Logic for Vagueness?" (PDF). CEUR Workshop Proceedings.
  22. ↑ Fisher, Peter (2000). "Sorites Paradox and Vague Geographies". Fuzzy Sets and Systems. 113: 7–18. CiteSeerX   10.1.1.409.905 . doi:10.1016/S0165-0114(99)00009-3.
  23. ↑ Krupinski, Joseph (1962). "Logic Design for Tristable Devices" (PDF). Defense Technical Information Center. Archived from the original (PDF) on February 18, 2017.
  24. ↑ Mouftah, H.T. (1976). "A study on the implementation of three-valued logic". MVL '76 Proceedings of the Sixth International Symposium on Multiple-valued Logic. MVL '76: 123–126.
  25. ↑ Behounek, Libor; Cintula, Pitr (2006). "Fuzzy logics as the logics of chains" (PDF). Fuzzy Sets and Systems. 157 (5): 608. doi:10.1016/j.fss.2005.10.005.[ permanent dead link ]
  26. ↑ Gottwald, Siegfried (2015). "Many-Valued Logic". 4. Applications of Many-Valued Logic. Stanford Encyclopedia of Philosophy.
  27. ↑ Levy, William; Berger, Toby; Sungka, Mustafa (2016). "Neural computation from first principles: Using the maximum entropy method to obtain an optimal bits-per-joule neuron". IEEE Transactions on Molecular, Biological and Multi-Scale Communications. 2 (2): 154–165. arXiv: 1606.03063 . Bibcode:2016arXiv160603063L. doi:10.1109/TMBMC.2017.2655021. S2CID   6537386.
  28. ↑ Choudhury, Kingshuk; Deacon, Pearl; Barrett, Rob; McDermott, Kieran (2010). "Hypothesis testing for neural cell growth experiments using a hybrid branching process model". Biostatistics. 11 (4): 631–643. doi: 10.1093/biostatistics/kxq038 . PMID   20525698.
  29. ↑ Burgess, John. "Intuitions of Three Kinds in Gödel's Views on the Continuum" (PDF).
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.