Łukasiewicz logic

In mathematics and philosophy, Łukasiewicz logic (/ˌluːkəˈʃɛvɪtʃ/ LOO-kə-SHEV-itch, Polish: [wukaˈɕɛvitʂ]) is a non-classical, many-valued logic. It was originally defined in the early 20th century by Jan Łukasiewicz as a three-valued logic;[1] it was later generalized to n-valued (for all finite n) as well as infinitely-many-valued (ℵ₀-valued) variants, both propositional and first-order.[2] The ℵ₀-valued version was published in 1930 by Łukasiewicz and Alfred Tarski; consequently it is sometimes called the Łukasiewicz–Tarski logic.[3] It belongs to the classes of t-norm fuzzy logics[4] and substructural logics.[5]

This article is about a system of logic. For the similarly named Łukasiewicz notation, see Polish notation.

This article presents the Łukasiewicz[-Tarski] logic in its full generality, i.e. as an infinite-valued logic. For an elementary introduction to the three-valued instantiation Ł₃, see three-valued logic.

Language

The propositional connectives of Łukasiewicz logic are implication ${\displaystyle \rightarrow }$, negation ${\displaystyle \neg }$, equivalence ${\displaystyle \leftrightarrow }$, weak conjunction ${\displaystyle \wedge }$, strong conjunction ${\displaystyle \otimes }$, weak disjunction ${\displaystyle \vee }$, strong disjunction ${\displaystyle \oplus }$, and propositional constants ${\displaystyle {\overline {0}}}$ and ${\displaystyle {\overline {1}}}$. The presence of conjunction and disjunction is a common feature of substructural logics without the rule of contraction, to which Łukasiewicz logic belongs.

Axioms

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

${\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 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

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:

• ${\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 any valuation of propositional variables by real numbers in the interval [0, 1].

Finite-valued and countable-valued semantics

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

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

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

References

1. Łukasiewicz J., 1920, O logice trójwartościowej (in Polish). Ruch filozoficzny 5:170–171. English translation: On three-valued logic, in L. Borkowski (ed.), Selected works by Jan Łukasiewicz, North–Holland, Amsterdam, 1970, pp. 87–88. ISBN 0-7204-2252-3
2. Hay, L.S., 1963, Axiomatization of the infinite-valued predicate calculus. Journal of Symbolic Logic 28:77–86.
3. Lavinia Corina Ciungu (2013). Non-commutative Multiple-Valued Logic Algebras. Springer. p. vii. ISBN 978-3-319-01589-7. citing Łukasiewicz, J., Tarski, A.: Untersuchungen über den Aussagenkalkül. Comp. Rend. Soc. Sci. et Lettres Varsovie Cl. III 23, 30–50 (1930).
4. Hájek P., 1998, Metamathematics of Fuzzy Logic. Dordrecht: Kluwer.
5. Ono, H., 2003, "Substructural logics and residuated lattices — an introduction". In F.V. Hendricks, J. Malinowski (eds.): Trends in Logic: 50 Years of Studia Logica, Trends in Logic 20: 177–212.
6. http://journal.univagora.ro/download/pdf/28.pdf citing J. M. Font, A. J. Rodriguez, A. Torrens, Wajsberg Algebras, Stochastica, VIII, 1, 5-31, 1984
7. Lavinia Corina Ciungu (2013). Non-commutative Multiple-Valued Logic Algebras. Springer. pp. vii–viii. ISBN 978-3-319-01589-7. citing Grigolia, R.S.: "Algebraic analysis of Lukasiewicz-Tarski’s n-valued logical systems". In: Wójcicki, R., Malinkowski, G. (eds.) Selected Papers on Lukasiewicz Sentential Calculi, pp. 81–92. Polish Academy of Sciences, Wroclav (1977)
8. Iorgulescu, A.: Connections between MV_n-algebras and n-valued Łukasiewicz–Moisil algebras—I. Discrete Math. 181, 155–177 (1998) doi:10.1016/S0012-365X(97)00052-6
9. R. Cignoli, Proper n-Valued Łukasiewicz Algebras as S-Algebras of Łukasiewicz n-Valued Propositional Calculi, Studia Logica, 41, 1982, 3-16, doi:10.1007/BF00373490

Further reading

• 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