Logic in Computer Science (LICS 1999)

Paper: On Bunched Predicate Logic (at LICS 1999)

Authors: David J. Pym

Abstract

We present the logic of bunched implications, BI,in which a multiplicative (or linear) and an additive (or intuitionistic) implication live side-by-side. The propositional version of BI arises from an analysis of the proof-theoretic relationship between conjunction and implication, and may be viewed as a merging of intuitionistic logic and multiplicative, intuitionistic linear logic. The predicate version of BI includes, in addition to usual additive quantifiers, multiplicative (or intensional) quantifiers 8new and 9new ,which arise from observing restrictions on structural rules on the level of terms as well as propositions. Moreover, these restrictions naturally allow the distinction between additive predication and multiplicative predication for each propositional connective. We provide a natural deduction system, a sequent calculus, a Kripke semantics and a BHK semantics for BI. We mention computational interpretations, based on locality and sharing, at both the propositional and predicate levels. We explain BI's relationship with intuitionistic logic, linear logic and other relevant logics.

BibTeX

  @InProceedings{Pym-OnBunchedPredicateL,
    author = 	 {David J. Pym},
    title = 	 {On Bunched Predicate Logic},
    booktitle =  {Proceedings of the Fourteenth Annual IEEE Symp. on Logic in Computer Science, {LICS} 1999},
    year =	 1999,
    editor =	 {Giuseppe Longo},
    month =	 {July}, 
    pages =      {183--192},
    location =   {Trento, Italy}, 
    publisher =	 {IEEE Computer Society Press}
  }