Łukasiewicz logic

The propositional connectives of Łukasiewicz logic are ${\displaystyle \rightarrow }$ ("implication"), and the constant ${\displaystyle \bot }$ ("false"). Additional connectives can be defined in terms of these:

${\displaystyle {\begin{aligned}\neg A&=_{def}A\rightarrow \bot \\A\vee B&=_{def}(A\rightarrow B)\rightarrow B\\A\wedge B&=_{def}\neg (\neg A\vee \neg B)\\A\leftrightarrow B&=_{def}(A\rightarrow B)\wedge (B\rightarrow A)\end{aligned}}}$

The ${\displaystyle \vee }$ and ${\displaystyle \wedge }$ connectives are called weak disjunction and conjunction, because they are non-classical, as the law of excluded middle does not hold for them. In the context of substructural logics, they are called additive connectives. They also correspond to lattice min/max connectives.

In terms of substructural logics, there are also strong or multiplicative disjunction and conjunction connectives, although these are not part of Łukasiewicz's original presentation:

${\displaystyle {\begin{aligned}A\oplus B&=_{def}\neg A\rightarrow B\\A\otimes B&=_{def}\neg (A\rightarrow \neg B)\end{aligned}}}$

There are also defined modal operators, using the Tarskian Möglichkeit:

${\displaystyle {\begin{aligned}\Diamond A&=_{def}\neg A\rightarrow A\\\Box A&=_{def}\neg \Diamond \neg A\end{aligned}}}$

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

${\displaystyle {\begin{aligned}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).\end{aligned}}}$

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

Divisibility

${\displaystyle (A\wedge B)\rightarrow (A\otimes (A\rightarrow B))}$

Double negation

${\displaystyle \neg \neg A\rightarrow A.}$

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

Finite-valued Łukasiewicz logics require additional axioms.

A hypersequent calculus for three-valued Łukasiewicz logic was introduced by Arnon Avron in 1991.[6]

Sequent calculi for finite and infinite-valued Łukasiewicz logics as an extension of linear logic were introduced by A. Prijatelj in 1994.[7] However, these are not cut-free systems.

Hypersequent calculi for Łukasiewicz logics were introduced by A. Ciabattoni et al in 1999.[8] However, these are not cut-free for ${\displaystyle n>3}$ finite-valued logics.

A labelled tableaux system was introduced by Nicola Olivetti in 2003.[9]

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

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

and where the definitions of the operations hold as follows:

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

The truth function ${\displaystyle F_{\otimes }}$ of strong conjunction is the Łukasiewicz t-norm and the truth function ${\displaystyle F_{\oplus }}$ of strong disjunction is its dual t-conorm. Obviously, ${\displaystyle F_{\otimes }(.5,.5)=0}$ and ${\displaystyle F_{\oplus }(.5,.5)=1}$, so if ${\displaystyle T(p)=.5}$, then ${\displaystyle T(p\wedge p)=T(\neg p\wedge \neg p)=0}$ while the respective logically-equivalent propositions have ${\displaystyle T(p\vee p)=T(\neg p\vee \neg p)=1}$.

The truth function ${\displaystyle 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 each valuation of propositional variables by real numbers in the interval [0, 1].

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 }.

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:

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

Here valid means necessarily evaluates to 1.

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

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. C. C. 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.[11] MV_n-algebras are a subclass of LM_n-algebras, and the inclusion is strict for n ≥ 5.[12] 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.[13]

Łukasiewicz logics are co-NP complete.[14]

Łukasiewicz logics can be seen as modal logics using the defined operators,

${\displaystyle {\begin{aligned}\Diamond A&=_{def}\neg A\rightarrow A\\\Box A&=_{def}\neg \Diamond \neg A\\\end{aligned}}}$

A third doubtful operator has been proposed, ${\displaystyle \odot A=_{def}A\leftrightarrow \neg A}$.[15]

From these we can prove the following theorems, which are common axioms in many modal logics:

${\displaystyle {\begin{aligned}A&\rightarrow \Diamond A\\\Box A&\rightarrow A\\A&\rightarrow (A\rightarrow \Box A)\\\Box (A\rightarrow B)&\rightarrow (\Box A\rightarrow \Box B)\\\Box (A\rightarrow B)&\rightarrow (\Diamond A\rightarrow \Diamond B)\\\end{aligned}}}$

We can also prove distribution theorems on the strong connectives:

${\displaystyle {\begin{aligned}\Box (A\otimes B)&\leftrightarrow \Box A\otimes \Box B\\\Diamond (A\oplus B)&\leftrightarrow \Diamond A\oplus \Diamond B\\\Diamond (A\otimes B)&\rightarrow \Diamond A\otimes \Diamond B\\\Box A\oplus \Box B&\rightarrow \Box (A\oplus B)\end{aligned}}}$

However, the following distribution theorems also hold:

${\displaystyle {\begin{aligned}\Box A\vee \Box B&\leftrightarrow \Box (A\vee B)\\\Box A\wedge \Box B&\leftrightarrow \Box (A\wedge B)\\\Diamond A\vee \Diamond B&\leftrightarrow \Diamond (A\vee B)\\\Diamond A\wedge \Diamond B&\leftrightarrow \Diamond (A\wedge B)\end{aligned}}}$

In other words, if ${\displaystyle \Diamond A\wedge \Diamond \neg A}$, then ${\displaystyle \Diamond (A\wedge \neg A)}$, which is counter-intuitive.[16] [17] However, these controversial theorems have been defended as a modal logic about future contingents by A. N. Prior.[18] Notably, ${\displaystyle \Diamond A\wedge \Diamond \neg A\leftrightarrow \odot A}$.

• Rose, A.: 1956, Formalisation du Calcul Propositionnel Implicatif ℵ₀ Valeurs de Łukasiewicz, C. R. Acad. Sci. Paris 243, 1183–1185.
• Rose, A.: 1978, Formalisations of Further ℵ₀-Valued Łukasiewicz Propositional Calculi, Journal of Symbolic Logic 43(2), 207–210. doi:10.2307/2272818
• Cignoli, R., “The algebras of Lukasiewicz many-valued logic - A historical overview,” in S. Aguzzoli et al.(Eds.), Algebraic and Proof-theoretic Aspects of Non-classical Logics, LNAI 4460, Springer, 2007, 69-83. doi:10.1007/978-3-540-75939-3_5