Łukasiewicz Logic
   HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
and
philosophy Philosophy (from , ) is the systematized study of general and fundamental questions, such as those about existence, reason, knowledge, values, mind, and language. Such questions are often posed as problems to be studied or resolved. Some ...
, Łukasiewicz logic ( , ) is a non-classical,
many-valued logic Many-valued logic (also multi- or multiple-valued logic) refers to a propositional calculus in which there are more than two truth values. Traditionally, in Aristotle's logical calculus, there were only two possible values (i.e., "true" and "false" ...
. It was originally defined in the early 20th century by
Jan Łukasiewicz Jan Łukasiewicz (; 21 December 1878 – 13 February 1956) was a Polish logician and philosopher who is best known for Polish notation and Łukasiewicz logic His work centred on philosophical logic, mathematical logic and history of logic. He ...
as a
three-valued logic In logic, a three-valued logic (also trinary logic, trivalent, ternary, or trilean, sometimes abbreviated 3VL) is any of several many-valued logic systems in which there are three truth values indicating ''true'', ''false'' and some indeterminate ...
;Ł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. it was later generalized to ''n''-valued (for all finite ''n'') as well as infinitely-many-valued ( 0-valued) variants, both propositional and first-order.Hay, L.S., 1963
Axiomatization of the infinite-valued predicate calculus
''
Journal of Symbolic Logic The '' Journal of Symbolic Logic'' is a peer-reviewed mathematics journal published quarterly by Association for Symbolic Logic. It was established in 1936 and covers mathematical logic. The journal is indexed by '' Mathematical Reviews'', Zentra ...
'' 28:77–86.
The ℵ0-valued version was published in 1930 by Łukasiewicz and
Alfred Tarski Alfred Tarski (, born Alfred Teitelbaum;School of Mathematics and Statistics, University of St Andrews ''School of Mathematics and Statistics, University of St Andrews''. January 14, 1901 – October 26, 1983) was a Polish-American logician a ...
; consequently it is sometimes called the ŁukasiewiczTarski logic. citing Łukasiewicz, J., Tarski, A.
Untersuchungen über den Aussagenkalkül
Comp. Rend. Soc. Sci. et Lettres Varsovie Cl. III 23, 30–50 (1930).
It belongs to the classes of t-norm fuzzy logics Hájek P., 1998, ''Metamathematics of Fuzzy Logic''. Dordrecht: Kluwer. and
substructural logic In logic, a substructural logic is a logic lacking one of the usual structural rules (e.g. of classical and intuitionistic logic), such as weakening, contraction, exchange or associativity. Two of the more significant substructural logics are ...
s.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. 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 Ł3, see
three-valued logic In logic, a three-valued logic (also trinary logic, trivalent, ternary, or trilean, sometimes abbreviated 3VL) is any of several many-valued logic systems in which there are three truth values indicating ''true'', ''false'' and some indeterminate ...
.


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 and \overline. 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: : \begin 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 Propositional infinite-valued Łukasiewicz logic can also be axiomatized by adding the following axioms to the axiomatic system of
monoidal t-norm logic In mathematical logic, monoidal t-norm based logic (or shortly MTL), the logic of left-continuous t-norms, is one of the t-norm fuzzy logics. It belongs to the broader class of substructural logics, or logics of residuated lattices;Ono (2003). it e ...
: ; 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 Propositional calculus is a branch of logic Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science ...
may be assigned a
truth value In logic and mathematics, a truth value, sometimes called a logical value, is a value indicating the relation of a proposition to truth, which in classical logic has only two possible values (''true'' or '' false''). Computing In some progr ...
of not only zero or one but also any
real number In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every real ...
in between (e.g. 0.25). Valuations have a
recursive Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics ...
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\left(\overline\right) = 0 and w\left(\overline\right) = 1, and where the definitions of the operations hold as follows: * Implication: F_\rightarrow(x,y) = \min\ * Equivalence: F_\leftrightarrow(x, y) = 1 - , x - y, * Negation: F_\neg(x) = 1 - x * Weak conjunction: F_\wedge(x, y) = \min\ * Weak disjunction: F_\vee(x, y) = \max\ * Strong conjunction: F_\otimes(x, y) = \max\ * Strong disjunction: F_\oplus(x, y) = \min\. The truth function F_\otimes of strong conjunction is the Łukasiewicz
t-norm In mathematics, a t-norm (also T-norm or, unabbreviated, triangular norm) is a kind of binary operation used in the framework of probabilistic metric spaces and in multi-valued logic, specifically in fuzzy logic. A t-norm generalizes intersectio ...
and the truth function F_\oplus of strong disjunction is its dual
t-conorm In mathematics, a t-norm (also T-norm or, unabbreviated, triangular norm) is a kind of binary operation used in the framework of probabilistic metric spaces and in multi-valued logic, specifically in fuzzy logic. A t-norm generalizes intersection i ...
. Obviously, F_\otimes(.5,.5) = 0 and F_\oplus(.5,.5)=1, so if T(p)=.5, then T(p\wedge p)=T(\neg p \wedge \neg p) = 0 while the respective logically-equivalent propositions have T(p\vee p)= T(\neg p\vee \neg p) = 1. 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 each valuation of
propositional variable In mathematical logic, a propositional variable (also called a sentential variable or sentential letter) is an input variable (that can either be true or false) of a truth function. Propositional variables are the basic building-blocks of propositi ...
s by real numbers in the interval , 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 In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example, :\ is a finite set with five elements. Th ...
of cardinality ''n'' ≥ 2 by choosing the domain as * any
countable set In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numbers; ...
by choosing the domain as .


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-algebra In abstract algebra, a branch of pure mathematics, an MV-algebra is an algebraic structure with a binary operation \oplus, a unary operation \neg, and the constant 0, satisfying certain axioms. MV-algebras are the algebraic semantics of Łukasie ...
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: :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 In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X: # a \leq a ( reflexive) ...
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 Grigore Constantin Moisil (; 10 January 1906 – 21 May 1973) was a Romanian mathematician, computer pioneer, and list of members of the Romanian Academy, titular member of the Romanian Academy. His research was mainly in the fields of mathematic ...
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 A model is an informative representation of an object, person or system. The term originally denoted the Plan_(drawing), plans of a building in late 16th-century English, and derived via French and Italian ultimately from Latin ''modulus'', a mea ...
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 ℵ0-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. 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) 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''.R. Cignoli, Proper n-Valued Łukasiewicz Algebras as S-Algebras of Łukasiewicz n-Valued Propositional Calculi, Studia Logica, 41, 1982, 3-16,


References


Further reading

* Rose, A.: 1956, Formalisation du Calcul Propositionnel Implicatif ℵ0 Valeurs de Łukasiewicz, C. R. Acad. Sci. Paris 243, 1183–1185. * Rose, A.: 1978, Formalisations of Further ℵ0-Valued Łukasiewicz Propositional Calculi, Journal of Symbolic Logic 43(2), 207–210. * 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. {{DEFAULTSORT:Lukasiewicz logic Many-valued logic Fuzzy logic