many-valued logic

9:52 PM | BY ZeroDivide EDIT

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.

History[edit]

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.

Examples[edit]

Main articles: Three-valued logic and Four-valued logic

Kleene (strong) K₃ and Priest logic P₃[edit]

Kleene's "(strong) logic of indeterminacy" K₃ (sometimes

K_3^S

) 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]

¬
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 K₃ only T is a designated truth value, while in P₃ both T and I are (a logical formula is considered a tautology if it evaluates to a designated truth value). In Kleene's logic I can be interpreted as being "underdetermined", being neither true nor false, while in Priest's logic I can be interpreted as being "overdetermined", being both true and false. K₃ does not have any tautologies, while P₃ has the same tautologies as classical two-valued logic.^{[citation needed]}

Bochvar's internal three-valued logic (also known as Kleene's weak three-valued logic)[edit]

Another logic is Bochvar's "internal" three-valued logic (

B_3^I

) also called Kleene's weak three-valued logic. Except for negation and biconditional, its truth tables are all different from the above.^[3]

∧₊	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.^[4]

Belnap logic (B₄)[edit]

Belnap's logic B₄ combines K₃ and P₃. 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

Semantics[edit]

Matrix semantics (logical matrices)[edit]

Proof theory[edit]

Relation to classical logic[edit]

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 middledoesn't hold: a proposition that is not flawed is not necessarily justified; instead, it's only not proven that it's flawed. The key difference is the determinacy of the preserved property: One may prove that P is justified, that P is flawed, or be unable to prove either. A valid argument preserves justification across transformations, so a proposition derived from justified propositions is still justified. However, there are proofs in classical logic that depend upon the law of excluded middle; since that law is not usable under this scheme, there are propositions that cannot be proven that way.

Suszko's thesis[edit]

Applications[edit]

Applications of many-valued logic can be roughly classified into two groups.^[5] 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.

Research venues[edit]

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.^[6] There is also a Journal of Multiple-Valued Logic and Soft Computing.^[7]

Language[edit]

The propositional connectives of Łukasiewicz logic are implication

\rightarrow

, negation

\neg

, equivalence

\leftrightarrow

, weak conjunction

\wedge

, strong conjunction

\otimes

, weak disjunction

\vee

, strong disjunction

\oplus

, and propositional constants

\overline{0}

and

\overline{1}

. The presence of weak and strong conjunction and disjunction is a common feature of substructural logics without the rule of contraction, to which Łukasiewicz logic belongs.

Axioms[edit]

This section requires expansionwith: additional axioms for finite-valued logics. (August 2014)

The original system of axioms for propositional infinite-valued Łukasiewicz logic used implication and negation as the primitive connectives:

A \rightarrow (B \rightarrow A)

(A \rightarrow B) \rightarrow ((B \rightarrow C) \rightarrow (A \rightarrow C))

((A \rightarrow B) \rightarrow B) \rightarrow ((B \rightarrow A) \rightarrow A)

(\neg B \rightarrow \neg A) \rightarrow (A \rightarrow B).

Propositional infinite-valued Łukasiewicz logic can also be axiomatized by adding the following axioms to the axiomatic system of monoidal t-norm logic:

Divisibility: $(A \wedge B) \rightarrow (A \otimes (A \rightarrow B))$
Double negation: $\neg\neg A \rightarrow A.$

That is, infinite-valued Łukasiewicz logic arises by adding the axiom of double negation to basic t-norm logic BL, or by adding the axiom of divisibility to the logic IMTL.

Finite-valued Łukasiewicz logics require additional axioms.

Real-valued semantics[edit]

Infinite-valued Łukasiewicz logic is a real-valued logic in which sentences from sentential calculus may be assigned a truth value of not only zero or one but also any real number in between (e.g. 0.25). Valuations have a recursive definition where:

$w(\theta \circ \phi)=F_\circ(w(\theta),w(\phi))$ for a binary connective $\circ,$
$w(\neg\theta)=F_\neg(w(\theta)),$
$w(\overline{0})=0$ and $w(\overline{1})=1,$

and where the definitions of the operations hold as follows:

Implication: $F_\rightarrow(x,y) = \min\{1, 1 - x + y \}$
Equivalence: $F_\leftrightarrow(x,y) = 1 - |x-y|$
Negation: $F_\neg(x) = 1-x$
Weak Conjunction: $F_\wedge(x,y) = \min\{x, y \}$
Weak Disjunction: $F_\vee(x,y) = \max\{x, y \}$
Strong Conjunction: $F_\otimes(x,y) = \max\{0, x + y -1 \}$
Strong Disjunction: $F_\oplus(x,y) = \min\{1, x + y \}.$

The truth function

F_\otimes

of strong conjunction is the Łukasiewicz t-norm and the truth function

F_\oplus

of strong disjunction is its dual t-conorm. The truth function

F_\rightarrow

is the residuum of the Łukasiewicz t-norm. All truth functions of the basic connectives are continuous.

By definition, a formula is a tautology of infinite-valued Łukasiewicz logic if it evaluates to 1 under any valuation of propositional variables by real numbers in the interval [0, 1].

Finite-valued and countable-valued semantics[edit]

Using exactly the same valuation formulas as for real-valued semantics Łukasiewicz (1922) also defined (up to isomorphism) semantics over

any finite set of cardinality n ≥ 2 by choosing the domain as { 0, 1/(n − 1), 2/(n − 1), ..., 1 }
any countable set by choosing the domain as { p/q | 0 ≤ p ≤ q where p is a non-negative integer and q is a positive integer }.

General algebraic semantics[edit]

The standard real-valued semantics determined by the Łukasiewicz t-norm is not the only possible semantics of Łukasiewicz logic. General algebraic semantics of propositional infinite-valued Łukasiewicz logic is formed by the class of all MV-algebras. The standard real-valued semantics is a special MV-algebra, called the standard MV-algebra.

Like other t-norm fuzzy logics, propositional infinite-valued Łukasiewicz logic enjoys completeness with respect to the class of all algebras for which the logic is sound (that is, MV-algebras) as well as with respect to only linear ones. This is expressed by the general, linear, and standard completeness theorems:^[4]

The following conditions are equivalent:

$A$ is provable in propositional infinite-valued Łukasiewicz logic
$A$ is valid in all MV-algebras (general completeness)
$A$ is valid in all linearly ordered MV-algebras (linear completeness)
$A$ is valid in the standard MV-algebra (standard completeness).

Font, Rodriguez and Torrens introduced in 1984 the Wajsberg algebra as an alternative model for the infinite-valued Łukasiewicz logic.^[6]

A 1940s attempt by Grigore Moisil to provide algebraic semantics for the n-valued Łukasiewicz logic by means of his Łukasiewicz–Moisil (LM) algebra(which Moisil called Łukasiewicz algebras) turned out to be an incorrect model for n ≥ 5. This issue was made public by Alan Rose in 1956. Chang's MV-algebra, which is a model for the ℵ₀-valued (infinitely-many-valued) Łukasiewicz-Tarski logic, was published in 1958. For the axiomatically more complicated (finite) n-valued Łukasiewicz logics, suitable algebras were published in 1977 by Revaz Grigolia and called MV_n-algebras.^[7] MV_n-algebras are a subclass of LM_n-algebras, and the inclusion is strict for n ≥ 5.^[8] In 1982 Roberto Cignoli published some additional constraints that added to LM_n-algebras produce proper models for n-valued Łukasiewicz logic; Cignoli called his discovery proper Łukasiewicz algebras.^[9]

Web Journal