In mathematics, Łukasiewicz logic (//; 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 variants, both propositional and first-order.^{[2]} It belongs to the classes of t-norm fuzzy logics^{[3]} and substructural logics.^{[4]}
This article presents the Łukasiewicz logic in its full generality, i.e. as an infinite-valued logic. For an elementary introduction to the three-valued instantiation Ł_{3}, see three-valued logic.
Language
The propositional connectives of Łukasiewicz logic are
implication $\backslash rightarrow$,
negation $\backslash neg$,
equivalence $\backslash leftrightarrow$,
weak conjunction $\backslash wedge$,
strong conjunction $\backslash otimes$,
weak disjunction $\backslash vee$,
strong disjunction $\backslash oplus$,
and propositional constants $\backslash overline\{0\}$ and $\backslash 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
The original system of axioms for propositional infinite-valued Łukasiewicz logic used implication and negation as the primitive connectives:
- $A\; \backslash rightarrow\; (B\; \backslash rightarrow\; A)$
- $(A\; \backslash rightarrow\; B)\; \backslash rightarrow\; ((B\; \backslash rightarrow\; C)\; \backslash rightarrow\; (A\; \backslash rightarrow\; C))$
- $((A\; \backslash rightarrow\; B)\; \backslash rightarrow\; B)\; \backslash rightarrow\; ((B\; \backslash rightarrow\; A)\; \backslash rightarrow\; A)$
- $(\backslash neg\; B\; \backslash rightarrow\; \backslash neg\; A)\; \backslash rightarrow\; (A\; \backslash 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\; \backslash wedge\; B)\; \backslash rightarrow\; (A\; \backslash otimes\; (A\; \backslash rightarrow\; B))$
- Double negation: $\backslash neg\backslash neg\; A\; \backslash 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(\backslash theta\; \backslash circ\; \backslash phi)=F\_\backslash circ(w(\backslash theta),w(\backslash phi))$ for a binary connective $\backslash circ,$
- $w(\backslash neg\backslash theta)=F\_\backslash neg(w(\backslash theta)),$
- $w(\backslash overline\{0\})=0$ and $w(\backslash overline\{1\})=1,$
and where the definitions of the operations hold as follows:
- Implication: $F\_\backslash rightarrow(x,y)\; =\; \backslash min\backslash \{1,\; 1\; -\; x\; +\; y\; \backslash \}$
- Equivalence: $F\_\backslash leftrightarrow(x,y)\; =\; 1\; -\; |x-y|$
- Negation: $F\_\backslash neg(x)\; =\; 1-x$
- Weak Conjunction: $F\_\backslash wedge(x,y)\; =\; \backslash min\backslash \{x,\; y\; \backslash \}$
- Weak Disjunction: $F\_\backslash vee(x,y)\; =\; \backslash max\backslash \{x,\; y\; \backslash \}$
- Strong Conjunction: $F\_\backslash otimes(x,y)\; =\; \backslash max\backslash \{0,\; x\; +\; y\; -1\; \backslash \}$
- Strong Disjunction: $F\_\backslash oplus(x,y)\; =\; \backslash min\backslash \{1,\; x\; +\; y\; \backslash \}.$
The truth function $F\_\backslash otimes$ of strong conjunction is the Łukasiewicz t-norm and the truth function $F\_\backslash oplus$ of strong disjunction is its dual t-conorm. The truth function $F\_\backslash 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:^{[3]}
- 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).
References
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.