Łukasiewicz logic

From Wikipedia, the free encyclopedia

In mathematics, Łukasiewicz logic is a non-classical, many valued logic. It was originally defined 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]

Contents

[edit] 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 weak and strong conjunction and disjunction is a common feature of susbtructural logics without the rule of contraction, among which Łukasiewicz logic belongs.

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

[edit] Real-valued semantics

Infinite-valued Łukasiewicz logic is a real-valued logic in which sentences from sentential calculus are assigned a truth value of arbitrary precision between 0 and 1. Valuations have a recursive definition, with

  • 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,

where

  • F_\rightarrow(x,y) = \min\{1, 1 - x + y \}
  • F_\leftrightarrow(x,y) = 1 - |x-y|
  • F_\neg(x) = 1-x
  • F_\wedge(x,y) = \min\{x, y \}
  • F_\vee(x,y) = \max\{x, y \}
  • F_\otimes(x,y) = \max\{0, x + y -1 \}
  • 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].

[edit] 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:

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)

[edit] 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 0720422523
  2. ^ Hay, L.S., 1963, Axiomatization of the infinite-valued predicate calculus. Journal of Symbolic Logic 28:77–86.
  3. ^ Hájek P., 1998, Metamathematics of Fuzzy Logic. Dordrecht: Kluwer.
  4. ^ 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.
Languages