Łukasiewicz logic

In mathematics, Łukasiewicz logic (/luːkəˈʃɛvɪtʃ/; Polish pronunciation: [wukaˈɕɛvʲitʂ]) 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 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 $\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 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:

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

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

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:

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

^ Ł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
^ Hay, L.S., 1963, Axiomatization of the infinite-valued predicate calculus. Journal of Symbolic Logic 28:77–86.
^ 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).
^ ^a ^b Hájek P., 1998, Metamathematics of Fuzzy Logic. Dordrecht: Kluwer.
^ 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.
^ 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
^ 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)
^ 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
^ 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

v t e Non-classical logic
Intuitionistic	Intuitionistic logic Constructive analysis Heyting arithmetic Intuitionistic type theory Constructive set theory
Fuzzy	Degree of truth Fuzzy rule Fuzzy set Fuzzy finite element Fuzzy set operations
Substructural	Structural rule Relevance logic Linear logic
Paraconsistent	Dialetheism
Description	Ontology (computer science) Ontology language
Many-valued	Three-valued Four-valued Łukasiewicz
Digital logic	Three-state logic Tri-state buffer Four-valued Verilog IEEE 1164 VHDL
Others	Dynamic semantics Inquisitive logic Intermediate logic Non-monotonic logic