Multi-valued logic

Multi-valued logic is a generic term for all logical systems that use more than two truth values.

The starting point for the development of multi-valued logics was the epistemological question as to whether the principle of duality has extra-logical truth. For statements about the future, Aristotle asks this question by arguing that the truth of a statement such as "tomorrow a sea battle will take place" will only be established on the evening of tomorrow and that it will still be indefinite and therefore contingent up to this point in time must be considered possible .

The first multi-valued logic formalized in the modern sense is the three-valued logic L ₃ presented by Jan Łukasiewicz in 1920 . With reference to the example of Aristotle's sea battle, Łukasiewicz interprets its three truth values ​​as "true", "false" and - for future statements whose truth has not yet been established - "(contingently) possible".

More recently, multi-valued logics have gained great practical importance in the field of computer science . They make it possible to deal with the fact that databases can contain not only clearly definite, but also indefinite, missing or even contradicting information.

Basics of multi-valued logic

While multivalued logic with the principle of two-valued abandonment of one of the two basic principles of classical logic , it retains its other basic principle, the principle of extensionality : the truth value of every compound statement is still uniquely determined by the truth values ​​of its partial statements.

In contrast to classical logic, the interpretation of truth values ​​in multi-valued logics is less natural. Many different interpretations have been proposed. For this reason and because many interpretations that view more than two values ​​not as grades or types of truth and falsehood, but, for example, epistemically as a gradation of knowledge or certainty (for example with the three values ​​"known as true", "unknown" and “known to be wrong”), the values ​​of multi-valued logic are often not referred to as truth values, but as pseudo- truth values or as quasi- truth values . For reasons of compactness, this article uses the term “truth value” throughout.

In addition to the problem of interpreting truth values, there are numerous tasks of a technical nature when dealing with multi-valued logic and there are further problems of interpretation: Basic concepts such as those of tautology , that of contradiction or that of inference  must be redefined and interpreted.

Tautologies and designated truth values

In classical logic, tautologies are defined as statements that are always true (that is, regardless of how the atomic statements they contain are evaluated). In order to make the term “tautology” useful for the multi-valued logic, one or more of the pseudo-truth values ​​must be marked. The term “tautology” can then be adapted to the multi-valued logic by designating all those statements as tautologies which always, i.e. under each evaluation, assume one of the excellent truth values. These excellent truth values ​​are also called designated truth values .

Contradiction and negatively designated truth values

If you want to extend the term "contradiction" to multi-valued logic, you have two options: On the one hand, you can emphasize one or more of the truth values negatively and then designate all those statements as contradictions that always - that is, under each evaluation - one negative deliver a designated truth value. On the other hand, a statement can be called a contradiction, the negation of which is a tautology. It is assumed that a suitable negation is available and that it has been clarified which of the multi-valued negations is suitable for this purpose.

Inference

With the help of the concept of designated truth values, the concept of inference can easily be extended to multi-valued logic analogous to that of classical logic: An argument is therefore valid if, among all evaluations under which all premises of the argument assume designated truth values, also its conclusion assumes the designated truth value.

Multi-valued propositional logic systems

Kleene logic K ₃

The Kleene logic contains three truth values, namely 1 for “true”, 0 for “false” and , which is also referred to here as i and stands for “neither true nor false”. Kleene defines the negation , conjunction , disjunction and implication by the following truth value functions: ${\displaystyle K_{3}}$ ${\displaystyle {\tfrac {1}{2}}}$ ${\displaystyle f\neg }$ ${\displaystyle f\wedge }$ ${\displaystyle f\vee }$ ${\displaystyle f\rightarrow }$

${\displaystyle {\begin{array}{|c || c|}f\neg &\\\hline 1&0\\i&i\\0&1\\\end{array}}\quad {\begin{array}{|c || c|c|c|}f\wedge &1&i&0\\\hline 1&1&i&0\\i&i&i&0\\0&0&0&0\\\end{array}}\quad {\begin{array}{|c || c|c|c|}f\vee &1&i&0\\\hline 1&1&1&1\\i&1&i&i\\0&1&i&0\\\end{array}}\quad {\begin{array}{|c || c|c|c|}f\rightarrow &1&i&0\\\hline 1&1&i&0\\i&1&i&i\\0&1&1&1\\\end{array}}}$

Thus - as for example in Łukasiewicz's three-valued logic , see there - the disjunction forms the maximum and the conjunction the minimum of the connected truth values ​​and the negation of a statement with truth value v is calculated as 1- v . ${\displaystyle L_{3}}$

If one considers 1 as the only designated truth value, then there are no tautologies; If one considers both ¹ ⁄ ₂ and 1 as designated, then the set of tautologies in is identical to the set of classical , two-valued propositional logic. ${\displaystyle K_{3}}$ ${\displaystyle K_{3}}$

Gödel logics G _k and G _∞

In 1932 Gödel defined a family of multi-valued logics with a finite number of truth values , so that, for example, it includes the truth values and the truth values . Similarly, he defines a logic with an infinite number of truth values, in which the real numbers  in the interval from 0 to 1 are used as truth values . The designated truth value is 1 for each of these logics. ${\displaystyle G_{k}}$ ${\displaystyle 0,{\tfrac {1}{k-1}},{\tfrac {2}{k-1}},\ldots {\tfrac {k-2}{k-1}},1}$ ${\displaystyle G_{3}}$ ${\displaystyle 0,{\tfrac {1}{2}},1}$ ${\displaystyle G_{4}}$ ${\displaystyle 0,{\tfrac {1}{3}},{\tfrac {2}{3}},1}$ ${\displaystyle G_{\infty }}$

He defines the conjunction and the disjunction as the minimum or maximum of the formula truth values: ${\displaystyle \wedge }$ ${\displaystyle \vee }$

• ${\displaystyle u\wedge v:=\min\{u,v\}}$
• ${\displaystyle u\vee v:=\max\{u,v\}}$

The negation and implication are defined by the following truth value functions: ${\displaystyle \sim }$ ${\displaystyle \rightarrow _{G}}$

• ${\displaystyle \sim u={\begin{cases}1,&{\text{wenn }}u=0\\0,&{\text{wenn }}u>0\end{cases}}}$

• ${\displaystyle u\rightarrow _{G}v={\begin{cases}1,&{\text{wenn }}u\leq v\\v,&{\text{wenn }}u>v\end{cases}}}$

The Gödel systems are completely axiomatizable, i. H. Calculi can be set up in which all tautologies of the respective system can be derived.

Łukasiewicz Logics L _v

Jan Łukasiewicz defines the implication and the negation by the following truth value functions: ${\displaystyle \rightarrow _{L}}$ ${\displaystyle \neg }$

• ${\displaystyle \neg u:=1-u}$
• ${\displaystyle u\rightarrow _{L}v:=\min\{1,1-u+v\}}$

First Łukasiewicz developed his three-valued logic, the system , with the truth values and designated truth value 1 according to this scheme in 1920. His infinite logic followed in 1922 , in which he expanded the set of truth values ​​to the interval of real numbers from 0 to 1. The designated truth value is 1 in both cases. ${\displaystyle L_{3}}$ ${\displaystyle 0,{\tfrac {1}{2}},1}$ ${\displaystyle L_{\infty }}$

To generalize, Łukasiewicz's logics break down into finite-valued systems (set of truth values ​​as in Gödel ), into the one already mentioned, and into where the rational numbers (i.e. fractions) in the interval from 0 to 1 are used as truth values . The set of tautologies, that is, statements with a designated truth value, is identical for and . ${\displaystyle L_{v}}$ ${\displaystyle L_{n}}$ ${\displaystyle 0,{\tfrac {1}{n-1}},{\tfrac {2}{n-1}},\ldots ,{\tfrac {n-2}{n-1}},1}$ ${\displaystyle L_{\infty }}$ ${\displaystyle L_{\aleph _{0}}}$ ${\displaystyle L_{\infty }}$ ${\displaystyle L_{\aleph _{0}}}$

Product logic Π

The product logic contains a conjunction and an implication , which are defined as follows: ${\displaystyle \odot }$ ${\displaystyle \rightarrow _{\Pi }}$

• for : ${\displaystyle u,v\in [0,1]}$ ${\displaystyle u\odot v:=uv}$
• ${\displaystyle u\rightarrow _{\Pi }v:={\begin{cases}1,&{\text{wenn }}u\leq v\\{\frac {v}{u}},&{\text{wenn }}u>v\end{cases}}}$

In addition, the product logic contains a truth value constant that denotes the truth value "false". ${\displaystyle {\overline {0}}}$

Using the additional constants, a negation and a further conjunction can be defined as follows: ${\displaystyle \sim }$ ${\displaystyle \wedge }$

• ${\displaystyle \sim \varphi :=\varphi \rightarrow _{\Pi }{\overline {0}}}$
• ${\displaystyle \varphi \wedge \psi :=\varphi \odot (\varphi \rightarrow _{\Pi }\psi )}$

Post logics P _m

In 1921, Post defined a family of logics with (as in and ) the truth values . Post defines negation and disjunction as follows: ${\displaystyle P_{m}}$ ${\displaystyle L_{n}}$ ${\displaystyle G_{k}}$ ${\displaystyle 0,{\tfrac {1}{m-1}},{\tfrac {2}{m-1}},\ldots ,{\tfrac {m-2}{m-1}},1}$ ${\displaystyle \sim }$ ${\displaystyle \vee }$

• ${\displaystyle \sim u:={\begin{cases}1,&{\text{wenn }}u=0\\u-{\frac {1}{m-1}},&{\text{wenn }}u\not =0\end{cases}}}$

• ${\displaystyle u\vee v:=\max\{u,v\}}$

Four-valued logic by Belnap

Main article: Belnap's tetravalent logic

In 1977 Nuel Belnap developed his four-valued logic with the truth values t (true), f (false), u (unknown) and b (both, i.e. contradicting information).

Bočvar logic B ₃

This article or the following section is not adequately provided with supporting documents ( e.g. individual evidence ). Information without sufficient evidence could be removed soon. Please help Wikipedia by researching the information and including good evidence.

The Bočvar logic (by Dmitrij Anatoljewitsch Bočvar, also written Bochvar or Botschwar) contains two classes of joiners, namely the inner joiners on the one hand and the outer joiners on the other. The inner joiners negation , implication , disjunction , conjunction and bisubjunction correspond to those of classical logic. The outer joiners negation , implication , disjunction , conjunction and bisubjunction are metalinguistic in nature and are as follows: ${\displaystyle B_{3}}$ ${\displaystyle \neg }$ ${\displaystyle \rightarrow }$ ${\displaystyle \vee }$ ${\displaystyle \wedge }$ ${\displaystyle \leftrightarrow }$ ${\displaystyle \neg *}$ ${\displaystyle \rightarrow *}$ ${\displaystyle \vee *}$ ${\displaystyle \wedge *}$ ${\displaystyle \leftrightarrow *}$

• ${\displaystyle \neg *\varphi }$( is wrong) ${\displaystyle \varphi }$
• ${\displaystyle \varphi \rightarrow *\psi }$(is true, so too ) ${\displaystyle \varphi }$ ${\displaystyle \psi }$
• ${\displaystyle \varphi \vee *\psi }$( is true or is true) ${\displaystyle \varphi }$ ${\displaystyle \psi }$
• ${\displaystyle \varphi \wedge *\psi }$( is true and is true) ${\displaystyle \varphi }$ ${\displaystyle \psi }$
• ${\displaystyle \varphi \leftrightarrow *\psi }$( is true iff is true) ${\displaystyle \varphi }$ ${\displaystyle \psi }$

The truth value functions correspond to those of Kleene logic . ${\displaystyle K_{3}}$

For the definition of the outer joiners, another single-digit join is added, namely the external confirmation with the truth value function ${\displaystyle A_{*}}$

${\displaystyle {\begin{array}{|c || c|}A_{*}&\\\hline 1&0\\i&0\\0&1\\\end{array}}}$

The outer joiners can thus be defined as follows:

• ${\displaystyle \neg *\varphi :=\neg A_{*}\varphi }$
• ${\displaystyle \varphi \vee *\psi :=A_{*}\varphi \vee A_{*}\psi }$
• ${\displaystyle \varphi \rightarrow *\psi :=A_{*}\varphi \rightarrow A_{*}\psi }$
• ${\displaystyle \varphi \wedge *\psi :=A_{*}\varphi \wedge A_{*}\psi }$
• ${\displaystyle \varphi \leftrightarrow *\psi :=A_{*}\varphi \leftrightarrow A_{*}\psi }$

The logic of the outer joiners, which distinguishes between 0 and i, corresponds exactly to classical logic.

Bayesian logic

The Bayeslogik (also Bayesian logic or inductive Bayesian logic ) is an inductive-valued logic from the limit field of logic , epistemology and machine learning with applications in the fields of psychology and human-computer interaction .

Bayesian logic determines the rational subjective validity or probabilistic adequacy of logical predications (such as "ravens are black AND can fly") inductively according to the rules of probability theory . Your results can change again with further data (it is " non-monotonic "). Probability theory is applied at the level of alternative logical explanatory patterns (which can, however, overlap). Given certain assumptions, Bayesian logic can determine the rational degree of adequacy of logical explanatory patterns (logical joiners ) and, for example, determine the best explanation based on frequency data and previous expectations ( conclusion on the best explanation ). According to Bayes' theorem , P (connectivity i | data) = P (data | connectivity i ) * P (connectivity i ) / P (data). A likelihood function is assumed here, which does not always assign a probability of zero in the case of exceptions to a connective hypothesis if an exception parameter r > 0. In the case of exception parameter r = 0 and data that contradict a connective hypothesis, a falsificationist follows here too The norm of equivalency of hypothesis testing: A single contradicting evidence refutes a hypothesis. In the absence of refutation, as in falsificationism, the more specific (logically 'stronger') hypothesis based on a Bayesian version of Occam's razor is preferred. If r> 0, Bayesian logic also allows more specific hypotheses to be preferred, even if it allows more exceptions. In spite of the data-based (extensional aspects), it is also an intensive logic, which under some conditions also shows psychologically descriptively good results and possibly can offer a rational explanation of conjunctural errors (Conjunction Fallacy) that seem to contradict a direct application seem to stand in accordance with probability theory.

Fuzzy logic

In the fuzzy set theory, often also referred to as fuzzy logic , ambiguous statements are also dealt with. An example is the statement “the weather is very warm”. This statement will apply to varying degrees depending on the actual temperature: at 35 degrees with certainty, at 25 degrees to some extent, at 0 degrees by no means. The arbitrarily determined degrees of correctness are represented by a real number between 0 and 1.

The above multi-valued logics treat individual statements as atomic, so they do not even know their internal structure. In contrast to this, the fuzzy set theory only deals with statements with a very special internal structure: A basic set of possible observations (e.g. the temperatures that occur) are assigned degrees of correctness of a statement (“is very warm”). The term set in fuzzy set refers to the set of observations for which the degree of correctness of the statement is> 0; the term fuzzy indicates the variable degree of applicability.

The fuzzy set theory does not address the question of whether it is unknown or doubtful whether a statement is true. A statement as such is not assigned any truth value at all; the degrees of correctness are not truth values, but rather interpretations of an original measured value.

The fuzzy set theory also provides methods to determine the degree of correctness of statements in which several elementary statements are linked (“the weather is warm and dry”). The methods for combining degrees of correctness can in part also be applied to the combination of truth values ​​of the multi-valued logics.

Application of multi-valued logics

In the hardware development of logic circuits, multi-valued logics are used for simulation in order to represent different states and to model tri-state gates and buses . In the hardware description language VHDL , for example , the nine-valued logic defined in the IEEE standard with the number 1164 is often used, the standard logic 1164 . She has the values

1. U undefined
2. X unknown (strong driver)
3. 0 logical zero (strong driver)
4. 1 logical one (strong driver)
5. Z high resistance (high impedance Z )
6. W unknown (weak driver)
7. L logical zero low (weak driver)
8. H logical one high (weak driver)
9. - unimportant don't care

Standard Logic 1164, a nine-valued logic for hardware simulation

In a real circuit, only 1 , 0 and (for inputs / outputs) Z occur. In the simulation, the state U occurs with signals to which no other value has yet been assigned. The value - ( Don't-Care , is often represented with X outside of VHDL ) is only used for synthesis; it signals to the translation program that a certain state is not intended and therefore it does not matter how the synthesized circuit deals with this state.

The distinction between strong and weak drivers is used in the event of a conflict (when two outputs are connected to a single line and deliver different values) to decide which signal is assigned to the corresponding line. This conflict often occurs in bus systems where several bus users start sending data at the same time. If a 1 (strong) meets an L (weak), the strong signal prevails and the value 1 is assigned to the signal line . However, if signals of equal strength come together, the signal line goes into an undefined state. These states are X (if there is a conflict between 1 and 0 ) and W (if there is a conflict between H and L ).

Demarcation

Multi-valued logics are often discussed under metaphysical or epistemological questions. This includes B. the frequently asked question, which logical system is "correct", i. H. which logical system describes reality correctly (or better: best). Different philosophical currents give different answers to this question; some currents, e.g. B. Positivism , even reject the question itself as meaningless.

literature

• Lothar Kreiser, Siegfried Gottwald , Werner Stelzner (eds.): Non-classical logic. An introduction . 2nd Edition. Akademie-Verlag, Berlin 1990, ISBN 978-3-05-000274-3 .
• Alexander Alexandrowitsch Zinoviev : About multi-valued logic. A demolition . Deutscher Verlag der Wissenschaften, Berlin 1968. (Also Braunschweig: Vieweg and Basel: CF Winter. ISBN 978-3-528-08271-0 )
• Siegfried Gottwald: Multi-valued logic. An introduction to theory and application . Akademie-Verlag, Berlin 1989, 1995, ISBN 978-3-05-000765-6 .

Web links

• Siegfried Gottwald :  Many-Valued Logic. In: Edward N. Zalta (Ed.): Stanford Encyclopedia of Philosophy .
• Multiple-Valued Logic - An International Journal (MVL-IJ)
• Journal of Multiple-Valued Logic and Soft Computing
• Nuel Belnap: (Some) papers and publications ( Memento of January 3, 2009 in the Internet Archive )
• Quotes on Nuel Belnap: A Useful Four-valued Logic

Individual evidence

1. ^ Aristotle, De interpretatione c. 9., quoted from Ewald Richter : Logic, polyvalent . In: Historical Dictionary of Philosophy . Volume 5, p. 444
2. ↑ Source for this and the following paragraphs is Kreiser / Gottwald / Stelzner: Non-Classical Logic , Chapter 2.1 “Basic principles of multi-valued logic”, p. 19 f. (see literature list)
3. ↑ This and the following definitions follow in particular Kreiser / Gottwald / Stelzner: Non- Classical Logic , Chapter 2.3.3 "Excellent quasi-truth values, tautologies and conclusions", page 32ff. (see literature list)
4. ↑ cf. Kreiser / Gottwald / Stelzner: Non-Classical Logic , page 44 (see literature list)
5. ↑ Kurt Gödel: On the intuitionist calculus of statements . In: Anzeiger Academy of Sciences Vienna , mathematical-natural science class, 69, p. 65 f.
6. ↑ Source for this and the following information on the Łukasiewicz logics is Kreiser / Gottwald / Stelzner: Non-classical logic , page 41ff. and page 45ff (see literature list)
7. ↑ Petr Hajek: Fuzzy Logic . In: Edward N. Zalta: The Stanford Encyclopedia of Philosophy , Spring 2009. ( plato.stanford.edu )
8. ↑ Дмитрий Анатольевич Бочвар: Об одном трехзначном исчислении и его применении к анализу парадоксов классического расширенного функционального исчисления . Математический сборник 46 (1938) 4, pp. 287-308
9. ^ Siegfried Gottwald: Multi-valued logic. An introduction to theory and application . Akademie-Verlag, Berlin 1989, p. 165 ff.
10. ↑ Georg Gottlob: Multi-valued logic and computer science . In: Franz Pichler (Ed.): Europolis 6. Computer science for games and traffic. Extension of set theory . Universitätsverlag Trauner, Linz 2006, pp. 396–405.
11. ↑ von Sydow, M. (2016). Towards a Pattern-Based Logic of Probability Judgments and Logical Inclusion “Fallacies” . Thinking & Reasoning, 22 (3), 297-335. [doi: 10.1080 / 13546783.2016.1140678]
12. ↑ von Sydow, M. (2011). The Bayesian Logic of Frequency-Based Conjunction Fallacies. Journal of Mathematical Psychology, 55, 2, 119-139. [doi: 10.1016 / j.jmp.2010.12.001
13. ↑ von Sydow, M., & Fiedler, K. (2012). Bayesian Logic and Trial-by-Trial Learning. Proceedings of the Thirty-Fourth Annual Conference of the Cognitive Science Society (pp. 1090-1095). Austin, TX: Cognitive Science Society.
14. ↑ von Sydow, M. (2017). Rational Explanations of the Conjunction Fallacies - A Polycausal Proposal. Proceedings of the Thirty-Ninth Annual Conference of the Cognitive Science Society (pp. 3472-3477). Austin, TX: Cognitive Science Society.