Many-valued logic

Source: Wikipedia, the free encyclopedia.

Many-valued logic (also multi- or multiple-valued logic) is a

nine-valued, the finite-valued (finitely-many valued) with more than three values, and the infinite-valued (infinitely-many-valued), such as fuzzy logic and probability logic
.

History

It is wrong that the first known classical logician who did not fully accept the

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

intermediate logics
.

Examples

Kleene (strong) K3 and Priest logic P3

Kleene's "(strong) logic of indeterminacy" K3 (sometimes ) and

biconditional (K) are given by:[3]

¬  
T F
I I
F T
T I F
T T I F
I I I F
F F F F
T I F
T T T T
I T I I
F T I F
K T I F
T T I F
I T I I
F T T T
K T I F
T T I F
I I I I
F F I T

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]

Bochvar's internal three-valued logic

Another logic is Dmitry Bochvar's "internal" three-valued logic , also called Kleene's weak three-valued logic. Except for negation and biconditional, its truth tables are all different from the above.[5]

+ T I F
T T I F
I I I I
F F I F
+ T I F
T T I T
I I I I
F T I F
+ T I F
T T I F
I I I I
F T I T

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.[5]

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.

f¬  
T F
B B
N N
F T
f T B N F
T T B N F
B B B F F
N N F N F
F F F F F
f T B N F
T T T T T
B T B T B
N T T N N
F T B N F

Gödel logics Gk and G

In 1932 Gödel defined[6] a family of many-valued logics, with finitely many truth values , for example has the truth values and has . In a similar manner he defined a logic with infinitely many truth values, , in which the truth values are all the real numbers in the interval . The designated truth value in these logics is 1.

The conjunction and the disjunction are defined respectively as the

maximum
of the operands:

Negation and implication are defined as follows:

Gödel logics are completely axiomatisable, that is to say it is possible to define a logical calculus in which all tautologies are provable. The implication above is the unique

Heyting implication defined by the fact that the suprema and minima operations form a complete lattice with an infinite distributive law, which defines a unique complete Heyting algebra
structure on the lattice.

Łukasiewicz logics Lv and L

Implication and negation were defined by Jan Łukasiewicz through the following functions:

At first Łukasiewicz used these definitions in 1920 for his three-valued logic , with truth values . In 1922 he developed a logic with infinitely many values , in which the truth values spanned the real numbers in the interval . In both cases the designated truth value was 1.[7]

By adopting truth values defined in the same way as for Gödel logics , it is possible to create a finitely-valued family of logics , the abovementioned and the logic , in which the truth values are given by the rational numbers in the interval . The set of tautologies in and is identical.

Product logic Π

In product logic we have truth values in the interval , a conjunction and an implication , defined as follows[8]

Additionally there is a negative designated value that denotes the concept of false. Through this value it is possible to define a negation and an additional conjunction as follows:

and then .

Post logics Pm

In 1921 Post defined a family of logics with (as in and ) the truth values . Negation and conjunction and disjunction are defined as follows:

Rose logics

In 1951, Alan Rose defined another family of logics for systems whose truth-values form

lattices.[9]

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.

Suszko's thesis

Functional completeness of many-valued logics

Functional completeness is a term used to describe a special property of finite logics and algebras. A logic's set of connectives is said to be functionally complete or adequate if and only if its set of connectives can be used to construct a formula corresponding to every possible truth function.[10] An adequate algebra is one in which every finite mapping of variables can be expressed by some composition of its operations.[11]

Classical logic: CL = ({0,1}, ¬, →, ∨, ∧, ↔) is functionally complete, whereas no Łukasiewicz logic or infinitely many-valued logics has this property.[11][12]

We can define a finitely many-valued logic as being Ln ({1, 2, ..., n} ƒ1, ..., ƒm) where n ≥ 2 is a given natural number. Post (1921) proves that assuming a logic is able to produce a function of any mth order model, there is some corresponding combination of connectives in an adequate logic Ln that can produce a model of order m+1.[13]

Applications

Known applications of many-valued logic can be roughly classified into two groups.

finite state machines
, testing, and verification.

The second group targets the design of electronic circuits that employ more than two discrete levels of signals, such as many-valued memories, arithmetic circuits, and

ripple-through carries that are involved in normal binary addition or subtraction, resulting in high-speed arithmetic operations. These number systems have a natural implementation using many-valued circuits. However, the practicality of these potential advantages heavily depends on the availability of circuit realizations, which must be compatible or competitive with present-day standard technologies. In addition to aiding in the design of electronic circuits, many-valued logic is used extensively to test circuits for faults and defects. Basically all known automatic test pattern generation (ATG) algorithms used for digital circuit testing require a simulator that can resolve 5-valued logic (0, 1, x, D, D').[16]
The additional values—x, D, and D'—represent (1) unknown/uninitialized, (2) a 0 instead of a 1, and (3) a 1 instead of a 0.

Research venues

An

IEEE International Symposium on Multiple-Valued Logic (ISMVL) has been held annually since 1970. It mostly caters to applications in digital design and verification.[17] There is also a Journal of Multiple-Valued Logic and Soft Computing.[18]

See also

Mathematical logic
Philosophical logic
Digital logic

References

  1. ^ Hurley, Patrick. A Concise Introduction to Logic, 9th edition. (2006).
  2. ^ Jules Vuillemin, Necessity or Contingency, CSLI Lecture Notes, N°56, Stanford, 1996, pp. 133-167
  3. ^ (Gottwald 2005, p. 19)
  4. .
  5. ^ a b (Bergmann 2008, p. 80)
  6. ^ Gödel, Kurt (1932). "Zum intuitionistischen Aussagenkalkül". Anzeiger der Akademie der Wissenschaften in Wien (69): 65f.
  7. .
  8. ^ Hajek, Petr: Fuzzy Logic. In: Edward N. Zalta: The Stanford Encyclopedia of Philosophy, Spring 2009. ([1])
  9. S2CID 119735870
    .
  10. ^ Smith, Nicholas (2012). Logic: The Laws of Truth. Princeton University Press. p. 124.
  11. ^ a b Malinowski, Grzegorz (1993). Many-Valued Logics. Clarendon Press. pp. 26–27.
  12. .
  13. .
  14. ^ 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
  15. (PDF) from the original on October 9, 2022. Retrieved January 3, 2016.
  16. .
  17. ^ "IEEE International Symposium on Multiple-Valued Logic (ISMVL)". www.informatik.uni-trier.de/~ley.
  18. ^ "MVLSC home". Archived from the original on March 15, 2014. Retrieved August 12, 2011.

Further reading

General

Specific