Noncommutative logic

Noncommutative logic is an extension of linear logic which combines the commutative connectives of linear logic with the noncommutative multiplicative connectives of the Lambek calculus (see External links below). Its sequent calculus relies on the structure of order varieties (a family of cyclic orders which may be viewed as a species of structure), and the correctness criterion for its proof nets is given in terms of partial permutations. It also has a denotational semantics in which formulas are interpreted by modules over some specific Hopf algebras.

Contents

Noncommutativity in logic

By extension, the term noncommutative logic is also used by a number of authors to refer to a family of substructural logics in which the exchange rule is inadmissible. The remainder of this article is devoted to a presentation of this acceptance of the term.

The oldest noncommutative logic is the Lambek calculus, which gave rise to the class of logics known as categorial grammars. Since the publication of Jean-Yves Girard's linear logic there have been several new noncommutative logics proposed, namely the cyclic linear logic of David Yetter, the pomset logic of Christian Retore, and the noncommutative logics BV and NEL studied in the calculus of structures.

Noncommutative logic is sometimes called ordered logic, since it is possible with most proposed noncommutative logics to impose a total or partial order on the formulae in sequents. However this is not fully general since some noncommutative logics do not support such an order, such as Yetter's cyclic linear logic. Note also that while most noncommutative logics do not allow weakening or contraction together with noncommutativity, this restriction is not necessary.

The Lambek calculus

Joachim Lambek proposed the first noncommutative logic in his 1958 paper Mathematics of Sentence Structure to model the combinatory possibilities of the syntax of natural languages. His calculus has thus become one of the fundamental formalisms of computational linguistics.

Cyclic linear logic

David Yetter proposed a weaker structural rule in place of the exchange rule of linear logic, yielding cyclic linear logic. Sequents of cyclic linear logic form a ring, and so are invariant under rotation, where multipremise rules glue their rings together at the formulae described in the rules. The calculus supports three structural modalities, a self-dual modality allowing exchange, but still linear, and the usual exponentials (? and !) of linear logic, allowing nonlinear structural rules to be used together with exchange.

Pomset logic

Pomset logic was proposed by Christian Retore in a semantic formalism with two dual sequential operators existing together with the usual tensor product and par operators of linear logic, the first logic proposed to have both commutative and noncommutative operators. A sequent calculus for the logic was given, but it lacked a cut-elimination theorem; instead the sense of the calculus was established through a denotational semantics.

BV and NEL

Alessio Guglielmi proposed a variation of Retore's calculus, BV, in which the two noncommutative operations are collapsed onto a single, self-dual, operator, and proposed a novel proof calculus, the calculus of structures to accommodate the calculus. The principal novelty of the calculus of structures was its pervasive use of deep inference, which it was argued is necessary for calculi combining commutative and noncommutative operators; this explanation concurs with the difficulty of designing sequent systems for pomset logic that have cut-elimination.

Lutz Strassburger devised a related system, NEL, also in the calculus of structures in which linear logic with the mix rule appears as a subsystem.

Structads

Structads are an approach to the semantics of logic that are based upon generalising the notion of sequent along the lines of Joyal's combinatorial species, allowing the treatment of more drastically nonstandard logics than those described above, where, for example, the ',' of the sequent calculus is not associative.

See also

Quantum logic

External links

  1. Non-commutative logic I: the multiplicative fragment by V. Michele Abrusci and Paul Ruet, Annals of Pure and Applied Logic 101(1), 2000.
  2. Logical aspects of computational linguistics (PS) by Patrick Blackburn, Marc Dymetman, Alain Lecomte, Aarne Ranta, Christian Retore and Eric Villemonte de la Clergerie.
  3. Papers on Commutative/Non-commutative Linear Logic in the calculus of structures: a research homepage from which the papers proposing BV and NEL are available.

Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Outline of logic — The following outline is provided as an overview of and topical guide to logic: Logic – formal science of using reason, considered a branch of both philosophy and mathematics. Logic investigates and classifies the structure of statements and… …   Wikipedia

  • List of mathematics articles (N) — NOTOC N N body problem N category N category number N connected space N dimensional sequential move puzzles N dimensional space N huge cardinal N jet N Mahlo cardinal N monoid N player game N set N skeleton N sphere N! conjecture Nabla symbol… …   Wikipedia

  • Kripke semantics — (also known as relational semantics or frame semantics, and often confused with possible world semantics) is a formal semantics for non classical logic systems created in the late 1950s and early 1960s by Saul Kripke. It was first made for modal… …   Wikipedia

  • Calculus of structures — The calculus of structures is a proof calculus with deep inference for studying the structural proof theory of noncommutative logic. The calculus has since been applied to study linear logic, classical logic, modal logic, and process calculi, and …   Wikipedia

  • Deep inference — names a general idea in structural proof theory that breaks with the classical sequent calculus by generalising the notion of structure to permit inference to occur in contexts of high structural complexity. The term deep inference is generally… …   Wikipedia

  • List of academic disciplines — An academic discipline, or field of study, is a branch of knowledge that is taught and researched at the college or university level. Disciplines are defined (in part), and recognized by the academic journals in which research is published, and… …   Wikipedia

  • Converse nonimplication — In logic, converse nonimplication is a logical connective which is the negation of the converse of implication. Contents 1 Definition 1.1 Truth table 1.2 Venn diagram …   Wikipedia

  • Graduate Texts in Mathematics — (GTM) is a series of graduate level textbooks in mathematics published by Springer Verlag. The books in this series, like the other Springer Verlag mathematics series, are small yellow books of a standard size. This particular series is easily… …   Wikipedia

  • Matrix (mathematics) — Specific elements of a matrix are often denoted by a variable with two subscripts. For instance, a2,1 represents the element at the second row and first column of a matrix A. In mathematics, a matrix (plural matrices, or less commonly matrixes)… …   Wikipedia

  • mathematics, foundations of — Scientific inquiry into the nature of mathematical theories and the scope of mathematical methods. It began with Euclid s Elements as an inquiry into the logical and philosophical basis of mathematics in essence, whether the axioms of any system… …   Universalium

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.