A textbook on modal logic, intended for readers already acquainted with the elements of formal logic, containing nearly 500 exercises. Brian F. Chellas provides a systematic introduction to the principal ideas and results in contemporary treatments of modality, including theorems on completeness and decidability. Illustrative chapters focus on deontic logic and conditionality. Modality is a rapidly expanding branch of logic, and familiarity with the subject is now regarded as a necessary part of every philosopher's technical equipment. Chellas here offers an (...) up-to-date and reliable guide essential for the student. (shrink)

This book introduces an important group of logics that have come to be known under the umbrella term 'susbstructural'. Substructural logics have independently led to significant developments in philosophy, computing and linguistics. _An Introduction to Substrucural Logics_ is the first book to systematically survey the new results and the significant impact that this class of logics has had on a wide range of fields.The following topics are covered: * Proof Theory * Propositional Structures * Frames * Decidability * Coda Both (...) students and professors of philosophy, computing, linguistics, and mathematics will find this to be an important addition to their reading. (shrink)

We provide a finite axiomatization of the consequence , i.e. of the set of common sequential rules for and . Moreover, we show that has no proper non-trivial strengthenings other than and . A similar result is true for , but not, e.g., for +.

We recapitulate (Section 1) some basic details of the system of implicative BCSK logic, which has two primitive binary implicational connectives, and which can be viewed as a certain fragment of the modal logic S5. From this modal perspective we review (Section 2) some results according to which the pure sublogic in either of these connectives (i.e., each considered without the other) is an exact replica of the material implication fragment of classical propositional logic. In Sections 3 and 5 we (...) show that for the pure logic of one of these implicational connectives two-in general distinct-consequence relations (global and local) definable in the Kripke semantics for modal logic turn out to coincide, though this is not so for the pure logic of the other connective, and that there is an intimate relation between formulas constructed by means of the former connective and the local consequence relation. (Corollary 5.8. This, as we show in an Appendix, is connected to the fact that the 'propositional operations' associated with both of our implicational connectives are close to being what R. Quackenbush has called pattern functions.) Between these discussions Section 4 examines some of the replacement-of-equivalents properties of the two connectives, relative to these consequence relations, and Section 6 closes with some observations about the metaphor of identical twins as applied to such pairs of connectives. (shrink)

Linear logic is a new logic which was recently developed by Girard in order to provide a logical basis for the study of parallelism. It is described and investigated in Gi]. Girard's presentation of his logic is not so standard. In this paper we shall provide more standard proof systems and semantics. We shall also extend part of Girard's results by investigating the consequence relations associated with Linear Logic and by proving corresponding str ong completeness theorems. Finally, we shall investigate (...) the relation between Linear Logic and previously known systems, especially Relevance logics. (shrink)

We present a Kripke model for Girard's Linear Logic (without exponentials) in a conservative fashion where the logical functors beyond the basic lattice operations may be added one by one without recourse to such things as negation. You can either have some logical functors or not as you choose. Commutatively and associatively are isolated in such a way that the base Kripke model is a model for noncommutative, nonassociative Linear Logic. We also extend the logic by adding a coimplication operator, (...) similar to Curry's subtraction operator, which is resituated with Linear Logic's contensor product. And we can add contraction to get nondistributive Relevance Logic. The model rests heavily on Urquhart's representation of nondistributive lattices and also on Dunn's Gaggle Theory. Indeed, the paper may be viewed as an investigation into nondistributive Gaggle Theory restricted to binary operations. The valuations on the Kripke model are three valued: true, false, and indifferent. The lattice representation theorem of Urquhart has the nice feature of yielding Priestley's representation theorem for distributive lattices if the original lattice happens to be distributive. Hence the representation is consistent with Stone's representation of distributive and Boolean lattices, and our semantics is consistent with the Lemmon-Scott representation of modal algebras and the Routley-Meyer semantics for Relevance Logic. (shrink)

We recapitulate (Section 1) some basic details of the system of implicative BCSK logic, which has two primitive binary implicational connectives, and which can be viewed as a certain fragment of the modal logic S5. From this modal perspective we review (Section 2) some results according to which the pure sublogic in either of these connectives (i.e., each considered without the other) is an exact replica of the material implication fragment of classical propositional logic. In Sections 3 and 5 we (...) show that for the pure logic of one of these implicational connectives two – in general distinct – consequence relations (global and local) definable in the Kripke semantics for modal logic turn out to coincide, though this is not so for the pure logic of the other connective, and that there is an intimate relation between formulas constructed by means of the former connective and the local consequence relation. (Corollary 5.8. This, as we show in an Appendix, is connected to the fact that the ‘propositional operations’ associated with both of our implicational connectives are close to being what R. Quackenbush has called pattern functions.) Between these discussions Section 4 examines some of the replacement-of-equivalents properties of the two connectives, relative to these consequence relations, and Section 6 closes with some observations about the metaphor of identical twins as applied to such pairs of connectives. (shrink)

Modal logic is the study of modalities - expressions that qualify assertions about the truth of statements - like the ordinary language phrases necessarily, possibly, it is known/believed/ought to be, etc., and computationally or mathematically motivated expressions like provably, at the next state, or after the computation terminates. The study of modalities dates from antiquity, but has been most actively pursued in the last three decades, since the introduction of the methods of Kripke semantics, and now impacts on a wide (...) range of disciplines, including the philosophy of language and linguistics ('possible words' semantics for natural language), constructive mathematics (intuitionistic logic), theoretical computer science (dynamic logic, temporal and other logics for concurrency), and category theory (sheaf semantics). This volume collects together a number of the author's papers on modal logic, beginning with his work on the duality between algebraic and set-theoretic modals, and including two new articles, one on infinitary rules of inference, and the other about recent results on the relationship between modal logic and first-order logic. Another paper on the 'Henkin method' in completeness proofs has been substantially extended to give new applications. Additional articles are concerned with quantum logic, provability logic, the temporal logic of relativistic spacetime, modalities in topos theory, and the logic of programs. (shrink)

Sections 1, 2 and 3 contain the main result, the strong finite axiomatizability of all 2-valued matrices. Since non-strongly finitely axiomatizable 3-element matrices are easily constructed the result reveals once again the gap between 2-valued and multiple-valued logic. Sec. 2 deals with the basic cases which include the important F i from Post's classification. The procedure in Sec. 3 reduces the general problem to these cases. Sec. 4 is a study of basic algebraic properties of 2-element algebras. In particular, we (...) show that equational completeness is equivalent to the Stone-property and that each 2-element algebra generates a minimal quasivariety. The results of Sec. 4 will be applied in Sec. 5 to maximality questions and to a matrix free characterization of 2-valued consequences in the lattice of structural consequences in any language. Sec. 6 takes a look at related axiomatization. problems for finite algebras and matrices. We study the notion of a propositional consequence with equality and, among other things, present explicit axiomatizations of 2-valued consequences with equality. (shrink)

We establish the “contraction-elimination theorem” which means that if a sequent Γ A is provable in the implicational fragment of the Gentzen's sequent calculus LK and if it satisfies a certain condition on the number of the occurrences of propositional variables, then it is provable without the right contraction rule. By this theorem, we get the following.1. If an implicational formula A is a theorem of classical logic and is not a theorem of intuitionistic logic, then there is a propositional (...) variable which occurs at least once positively and at least twice negatively in A → a) → a).2. If an implicational formula A is a theorem of intuitionistic logic and is not a theorem of BCK-logic, then there is a propositional variable which occurs at least twice positively and at least once negatively in A → a → b).We prove the contraction-elimination theorem by a fully syntactical method, which has some analogy with Gentzen's cut-elimination. (shrink)

Multiple -conclusion logic extends formal logic by allowing arguments to have a set of conclusions instead of a single one, the truth lying somewhere among the conclusions if all the premises are true. The extension opens up interesting possibilities based on the symmetry between premises and conclusions, and can also be used to throw fresh light on the conventional logic and its limitations. This is a sustained study of the subject and is certain to stimulate further research. Part I reworks (...) the fundamental ideas of logic to take account of multiple conclusions, and investigates the connections between multiple - and single - conclusion calculi. Part II draws on graph theory to discuss the form and validity of arguments independently of particular logical systems. Part III contrasts the multiple - and the single - conclusion treatment of one and the same subject, using many-valued logic as the example; and Part IV shows how the methods of 'natural deduction' can be matched by direct proofs using multiple conclusions. (shrink)

The purpose of this paper is to connect the proof theory and the model theory of a family of prepositional logics weaker than Heyting's. This family includes systems analogous to the Lambek calculus of syntactic categories, systems of relevant logic, systems related to BCK algebras, and, finally, Johansson's and Heyting's logic. First, sequent-systems are given for these logics, and cut-elimination results are proved. In these sequent-systems the rules for the logical operations are never changed: all changes are made in the (...) structural rules. Next, Hilbert-style formulations are given for these logics, and algebraic completeness results are demonstrated with respect to residuated lattice-ordered groupoids. Finally, model structures related to relevant model structures (of Urquhart, Fine, Routley, Meyer, and Maksimova) are given for our logics. These model structures are based on groupoids parallel to the sequent-systems. This paper lays the ground for a kind of correspondence theory for axioms of logics with implication weaker than Heyting's, a correspondence theory analogous to the correspondence theory for modal axioms of normal modal logics.Below is the sequel to the first part of the paper, which appeared in the previous issue of this journal (vol. 47 (1988), pp. 353–386). The first part contained sections on sequent-systems and Hilbert-formulations, and here is the third section on groupoid models. This second part is meant to be read in conjunction with the first part. (shrink)

The aim of the present book is to give a comprehensive account of the ‘state of the art’ of substructural logics, focusing both on their proof theory and on their semantics (both algebraic and relational. It is for graduate students in either philosophy, mathematics, theoretical computer science or theoretical linguistics as well as specialists and researchers.

Our object is to study the interaction between mereology and David Lewis’ theory of subject-matters, elaborating his observation that not every subject matter is of the form: how things stand with such-and-such a part of the world. After an informal introduction to this point in Section 1, we turn to a formal treatment of the partial orderings arising in the two areas – the part-whole relation, on the one hand, and the relation of refinement amongst partitions of the set of (...) worlds, on the other. We emphasize a certain duality, formulated in and in Section 2, between the corresponding lattice operations – mereological joins with partition-lattice meets, mereological meets with partition-lattice joins. Section 3 presents some issues that are raised by consideration of the informally familiar idea of logical subtraction. These include, in particular, a problem about the need for a notion of independence different from the usual logical notion going by that name. The apparatus of Section 2 promises to throw some light on this problem, as we indicate in Section 4. Section 5 ties up some loose ends and suggests an area in which further work would be desirable. (shrink)

The totality of extensional 1-ary connectives distinguishable in a logical framework allowing sequents with multiple or empty (alongside singleton) succedents form a lattice under a natural partial ordering relating one connective to another if all the inferential properties of the former are possessed by the latter. Here we give a complete description of that lattice; its Hasse diagram appears as Figure 1 in §2. Simple syntactic descriptions of the lattice elements are provided in §3; §§4 and 5 give some additional (...) remarks on matrix methods and on alternative terminology. Background: The size of this lattice was underestimated in [3]; some missing cases were noted in [4] in the course of correcting an example from [3] purporting to show the non-distributivity of the lattice. All the 'missing cases' (as well as those originally noted) are covered here. (The present discussion is self-contained.). (shrink)

The initial sections of this text deal with syntactical matters such as logical formalism, cut-elimination, and the embedding of intuitionistic logic in classical linear logic. Concluding chapters focus on proofnets for the multiplicative fragment and the algorithmic interpretation of cut-elimination in proofnets.

The present paper is concerned with the cut eliminability for some sequent systems of noncommutative substructural logics, i.e. substructural logics without exchange rule. Sequent systems of several extensions of noncommutative logics FL and LBB'I, which is sometimes called $\tw$, will be introduced. Then, the cut elimination theorem and the decision problem for them will be discussed in comparison with their commutative extensions.

We provide a finite axiomatization of the consequence $\vdash ^{\wedge}\cap \vdash ^{\vee}$ , i.e. of the set of common sequential rules for $\wedge $ and $\vee $ . Moreover, we show that $\vdash ^{\wedge}\cap \vdash ^{\vee}$ has no proper non-trivial strengthenings other than $\vdash ^{\wedge}$ and $\vdash ^{\vee}$ . A similar result is true for $\vdash ^{\leftrightarrow}\cap \vdash ^{\rightarrow}$ , but not, e.g., for $\vdash ^{\leftrightarrow}\cap \vdash ^{+}$.

This short note considers the formulation of Full Intuitionistic Linear Logic given by Hyland and de Paiva . Unfortunately the formulation is not closed under the process of cut elimination. This note proposes an alternative formulation based on the notion of patterns.