Łukasiewicz logic

Language

The propositional connectives of Łukasiewicz logic are implication → , negation ¬ , equivalence ↔ , weak conjunction ∧ , strong conjunction ⊗ , weak disjunction ∨ , strong disjunction ⊕ , and propositional constants 0 ¯ and 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 → ( B → A ) ( A → B ) → ( ( B → C ) → ( A → C ) ) ( ( A → B ) → B ) → ( ( B → A ) → A ) ( ¬ B → ¬ A ) → ( A → 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 ∧ B ) → ( A ⊗ ( A → B ) )

Double negation: ¬ ¬ A → 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 ( θ ∘ ϕ ) = F ∘ ( w ( θ ) , w ( ϕ ) ) for a binary connective ∘ ,

w ( ¬ θ ) = F ¬ ( w ( θ ) ) ,

w ( 0 ¯ ) = 0 and w ( 1 ¯ ) = 1 ,

and where the definitions of the operations hold as follows:

Implication: F → ( x , y ) = min { 1 , 1 − x + y }

Equivalence: F ↔ ( x , y ) = 1 − | x − y |

Negation: F ¬ ( x ) = 1 − x

Weak Conjunction: F ∧ ( x , y ) = min { x , y }

Weak Disjunction: F ∨ ( x , y ) = max { x , y }

Strong Conjunction: F ⊗ ( x , y ) = max { 0 , x + y − 1 }

Strong Disjunction: F ⊕ ( x , y ) = min { 1 , x + y } .

The truth function F ⊗ of strong conjunction is the Łukasiewicz t-norm and the truth function F ⊕ of strong disjunction is its dual t-conorm. The truth function F → 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:

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.

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. MV_n-algebras are a subclass of LM_n-algebras, and the inclusion is strict for n ≥ 5. 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.