Łukasiewicz logic

{{Short description|System of logic in mathematics and philosophy}} {{About|a system of logic|the similarly named Łukasiewicz notation|Polish notation}} In [[mathematics]] and [[philosophy]], '''Łukasiewicz logic''' ({{IPAc-en|ˌ|w|ʊ|k|ə|ˈ|ʃ|ɛ|v|ɪ|tʃ}} {{respell|WUUK|ə|SHEV|itch}}, {{IPA|pl|wukaˈɕɛvitʂ|lang}}) is a [[non-classical logic|non-classical]], [[many-valued logic]]. It was originally defined in the early 20th century by [[Jan Łukasiewicz]] as a [[three-valued logic|three-valued]] [[modal logic]];<ref name="Luk1920">Ł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}}</ref> it was later generalized to ''n''-valued (for all finite integers ''n'') as well as [[infinite-valued logic|infinitely-many-valued]] ([[ℵ0|ℵ₀]]-valued) variants, both [[propositional logic|propositional]] and [[first-order logic|first order]].<ref name="Hay1963">Hay, L.S., 1963, [https://www.jstor.org/stable/2271339 Axiomatization of the infinite-valued predicate calculus]. ''[[Journal of Symbolic Logic]]'' '''28''':77–86.</ref> The ℵ₀-valued version was published in 1930 by Łukasiewicz and [[Alfred Tarski]]; consequently it is sometimes called the '''Łukasiewicz{{ndash}}Tarski logic'''.<ref name="Ciungu2013">{{cite book|author=Lavinia Corina Ciungu|title=Non-commutative Multiple-Valued Logic Algebras|year=2013|publisher=Springer|isbn=978-3-319-01589-7|page=vii}} citing Łukasiewicz, J., Tarski, A.: [http://chc60.fgcu.edu/images/articles/lukasiewicztarski.pdf Untersuchungen über den Aussagenkalkül]. Comp. Rend. Soc. Sci. et Lettres Varsovie Cl. III 23, 30–50 (1930).</ref> It belongs to the classes of [[t-norm fuzzy logics]]<ref name="Hájek1998">[[Petr Hájek|Hájek P.]], 1998, ''Metamathematics of Fuzzy Logic''. Dordrecht: Kluwer.</ref> and [[substructural logic]]s.<ref name="Ono2003">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.</ref>

Łukasiewicz logic was motivated by [[Aristotle]]'s suggestion that [[bivalent logic]] was not applicable to future contingents, e.g. the statement "There will be a sea battle tomorrow". In other words, statements about the future were neither true nor false, but an intermediate value could be assigned to them, to represent their possibility of becoming true in the future.

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 <math>\rightarrow</math> ("implication"), and the constant <math>\bot</math> ("false"). Additional connectives can be defined in terms of these:

<math> \begin{align} \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) \\ \top & =_{def} \bot \rightarrow \bot \end{align} </math>

The <math>\vee</math> and <math>\wedge</math> 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 (order)|lattice]] min/max connectives.

In terms of [[substructural logics]], there are also ''strong'' or ''multiplicative'' disjunction and conjunction connectives{{Citation needed|date=May 2026}}, although these are not part of Łukasiewicz's original presentation:

<math>\begin{align} A \oplus B &=_{def} \neg A \rightarrow B \\ A \otimes B &=_{def} \neg (A \rightarrow \neg B) \end{align} </math>

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

<math>\begin{align} \Diamond A &=_{def} \neg A \rightarrow A \\ \Box A &=_{def} \neg \Diamond \neg A \end{align} </math>

== Axioms == {{expand section|additional axioms for finite-valued logics|date=August 2014}} The original{{Citation needed|date=May 2026}} system of axioms for propositional infinite-valued Łukasiewicz logic used implication and negation as the primitive connectives, along with [[modus ponens]]:

<math>\begin{align} 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{align}</math>

Propositional infinite-valued Łukasiewicz logic can also be axiomatized by adding the following axioms to the axiomatic system of [[monoidal t-norm logic]]: ; Divisibility: <math>(A \wedge B) \rightarrow (A \otimes (A \rightarrow B))</math> ; Double negation: <math>\neg\neg A \rightarrow A.</math>

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 involutive monoidal t-norm based logic (IMTL)<ref>{{Cite journal |last=Wang |first=J. T. |last2=Xin |first2=X. L. |date=2022-06-01 |title=Monadic algebras of an involutive monoidal t-norm based logic |url=https://ijfs.usb.ac.ir/article_6951.html |journal=Iranian Journal of Fuzzy Systems |language=en |volume=19 |issue=3 |pages=187–202 |doi=10.22111/ijfs.2022.6951 |issn=1735-0654}}</ref>.

Finite-valued Łukasiewicz logics require additional axioms.

== Proof Theory == {{expand section|discussion of sequent calculi and natural deduction systems needed|date=June 2022}}

A [[hypersequent]] calculus for three-valued Łukasiewicz logic was introduced by [[Arnon Avron]] in 1991.<ref>A. Avron, "Natural 3-valued Logics– Characterization and Proof Theory", Journal of Symbolic Logic 56(1), doi:10.2307/2274919</ref>

[[Sequent calculus|Sequent calculi]] for finite and infinite-valued Łukasiewicz logics as an extension of [[linear logic]] were introduced by A. Prijatelj in 1994.<ref>A. Prijateli, "Bounded contraction and Gentzen-style formulation of Łukasiewicz logics", ''[[Studia Logica]]'' 57: 437-456, 1996</ref> However, these are not [[Cut-elimination theorem|cut-free]] systems.

Hypersequent calculi for Łukasiewicz logics were introduced by [[Agata Ciabattoni|A. Ciabattoni]] et al in 1999.<ref>A. Ciabattoni, D.M. Gabbay, N. Olivetti, "Cut-free proof systems for logics of weak excluded middle" Soft Computing 2 (1999) 147—156</ref> However, these are not cut-free for <math>n > 3</math> finite-valued logics.

A labelled [[analytic tableau|tableaux system]] was introduced by Nicola Olivetti in 2003.<ref>N. Olivetti, "Tableaux for Łukasiewicz Infinite-valued Logic", Studia Logica volume 73, pages 81–111 (2003)</ref>

A hypersequent calculus for infinite-valued Łukasiewicz logic was introduced by George Metcalfe in 2004.<ref>D. Gabbay and G. Metcalfe and N. Olivetti, "Hypersequents and Fuzzy Logic", Revista de la Real Academia de Ciencias 98 (1), pages 113-126 (2004).</ref>

== Semantics ==

=== Real-valued semantics === Infinite-valued Łukasiewicz logic is a [[infinite-valued logic|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 [[recursion|recursive]] definition where: * <math>w(\theta \circ \phi) = F_\circ(w(\theta), w(\phi))</math> for a binary connective <math>\circ,</math> * <math>w(\neg\theta) = F_\neg(w(\theta)),</math> * <math>w\left(\overline{0}\right) = 0</math> and <math>w\left(\overline{1}\right) = 1,</math>

and where the definitions of the operations hold as follows: * '''Implication:''' <math>F_\rightarrow(x,y) = \min\{1, 1-x+y\}</math> * '''Equivalence:''' <math>F_\leftrightarrow(x, y) = 1-|x-y|</math> * '''Negation:''' <math>F_\neg(x) = 1-x</math> * '''Weak conjunction:''' <math>F_\wedge(x, y) = \min\{x, y\}</math> * '''Weak disjunction:''' <math>F_\vee(x, y) = \max\{x, y\}</math> * '''Strong conjunction:''' <math>F_\otimes(x, y) = \max\{0, x+y-1\}</math> * '''Strong disjunction:''' <math>F_\oplus(x, y) = \min\{1, x+y\}.</math> * '''Modal functions''': <math>F_\Diamond(x) = \min\{1,2x\}, F_\Box(x) = \max\{0, 2x-1\}</math>

The truth function <math>F_\otimes</math> of strong conjunction is the Łukasiewicz [[t-norm]] and the truth function <math>F_\oplus</math> of strong disjunction is its dual [[t-norm#T-conorms|t-conorm]]. Obviously, <math>F_\otimes(.5,.5) = 0</math> and <math>F_\oplus(.5,.5)=1</math>, so if <math>T(p)=.5</math>, then <math>T(p\wedge p)=T(\neg p \wedge \neg p) = 0</math> while the respective logically-equivalent propositions have <math>T(p\vee p)= T(\neg p\vee \neg p) = 1</math>.

The truth function <math>F_\rightarrow</math> is the [[t-norm#Residuum|residuum]] of the Łukasiewicz t-norm. All truth functions of the basic connectives are continuous.

By definition, a formula is a [[tautology (logic)|tautology]] of infinite-valued Łukasiewicz logic if it evaluates to 1 under each valuation of [[propositional variable]]s by real numbers in the interval [0,&nbsp;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-valued logic|finite set]] of cardinality ''n'' ≥ 2 by choosing the domain as {{nowrap|{ 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 (mathematical logic)|algebraic semantics]] of propositional infinite-valued Łukasiewicz logic is formed by the class of all [[MV-algebra]]s. 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:<ref name="Hájek1998"/> :The following conditions are equivalent: :* <math>A</math> is provable in propositional infinite-valued Łukasiewicz logic :* <math>A</math> is valid in all MV-algebras (''general completeness'') :* <math>A</math> is valid in all [[total order|linearly ordered]] MV-algebras (''linear completeness'') :* <math>A</math> 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.<ref>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</ref>

A 1940s attempt by [[Grigore Moisil]] to provide algebraic semantics for the ''n''-valued Łukasiewicz logic by means of his [[Łukasiewicz–Moisil algebra|Łukasiewicz–Moisil (LM) algebra]] (which Moisil called ''Łukasiewicz algebras'') turned out to be an incorrect [[model (mathematical logic)|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.<ref name="Ciungu2013bis">{{cite book|author=Lavinia Corina Ciungu|title=Non-commutative Multiple-Valued Logic Algebras|year=2013|publisher=Springer|isbn=978-3-319-01589-7|pages=vii-viii}} 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)</ref> MV_''n''-algebras are a subclass of LM_''n''-algebras, and the inclusion is strict for ''n'' ≥ 5.<ref>Iorgulescu, A.: Connections between MV_''n''-algebras and ''n''-valued Łukasiewicz–Moisil algebras Part I. ''[[Discrete Mathematics (journal)|Discrete Mathematics]]'' 181, 155–177 (1998) {{doi|10.1016/S0012-365X(97)00052-6}}</ref> 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''.<ref>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}}</ref>

== Complexity ==

Łukasiewicz logics are [[Co-NP-complete|co-NP complete]].<ref>A. Ciabattoni, M. Bongini and F. Montagna, Proof Search and Co-NP Completeness for Many-Valued Logics. ''[[Fuzzy Sets and Systems]]''.</ref>

== Modal Logic ==

Łukasiewicz logics can be seen as [[Modal logic|modal logics]], a type of logic that addresses possibility,<ref>{{Cite web |title=Modal Logic: Contemporary View {{!}} Internet Encyclopedia of Philosophy |url=https://iep.utm.edu/modal-lo/ |access-date=2024-05-03 |language=en-US}}</ref> using the defined operators,

<math>\begin{align}

\Diamond A &=_{def} \neg A \rightarrow A \\ \Box A &=_{def} \neg \Diamond \neg A \\ \end{align} </math>

A third ''doubtful'' operator has been proposed, <math>\odot A =_{def} A \leftrightarrow \neg A </math>.<ref>Clarence Irving Lewis and Cooper Harold Langford. Symbolic Logic. Dover, New York, second edition, 1959.</ref>

From these we can prove the following theorems, which are common axioms in many [[modal logic]]s:

<math>\begin{align} 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{align} </math>

We can also prove distribution theorems on the strong connectives:

<math>\begin{align} \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{align} </math>

However, the following distribution theorems also hold:

<math>\begin{align} \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{align} </math>

In other words, if <math>\Diamond A \wedge \Diamond \neg A</math>, then <math>\Diamond (A \wedge \neg A)</math>, which is counter-intuitive.<ref>Robert Bull and Krister Segerberg. Basic modal logic. In Dov M. Gabbay and Franz Guenthner, editors, Handbook of Philosophical Logic, volume 2. D. Reidel Publishing Company, Lancaster, 1986</ref><ref>[[Alasdair Urquhart]]. An interpretation of many-valued logic. Zeitschr. f. math. Logik und Grundlagen d. Math., 19:111–114, 1973.</ref> However, these controversial theorems have been defended as a modal logic about future contingents by [[A. N. Prior]].<ref>A.N. Prior. Three-valued logic and future contingents. 3(13):317–26, October 1953.</ref> Notably, <math>\Diamond A \wedge \Diamond \neg A \leftrightarrow \odot A</math>.

== References == {{Reflist}}

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

{{Non-classical logic}} {{Authority control}}

{{DEFAULTSORT:Lukasiewicz logic}} [[Category:Many-valued logic]] [[Category:Fuzzy logic]]