This introduction to the basic ideas of structural proof theory contains a thorough discussion and comparison of various types of formalization of first-order logic. Examples are given of several areas of application, namely: the metamathematics of pure first-order logic (intuitionistic as well as classical); the theory of logic programming; category theory; modal logic; linear logic; first-order arithmetic and second-order logic. In each case the aim is to illustrate the methods in relatively simple situations and then apply them elsewhere in much (...) more complex settings. There are numerous exercises throughout the text. In general, the only prerequisite is a standard course in first-order logic, making the book ideal for graduate students and beginning researchers in mathematical logic, theoretical computer science and artificial intelligence. For the new edition, many sections have been rewritten to improve clarity, new sections have been added on cut elimination, and solutions to selected exercises have been included. (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)

This book espouses a theory of scientific realism in which due weight is given to mathematics and logic. The authors argue that mathematics can be understood realistically if it is seen to be the study of universals, of properties and relations, of patterns and structures, the kinds of things which can be in several places at once. Taking this kind of scientific platonism as their point of departure, they show how the theory of universals can account for probability, laws of (...) nature, causation and explanation, and explore the consequences in all these fields. This will be an important book for all philosophers of science, logicians and metaphysicians, and their graduate students. The readership will also include those outside philosophy interested in the interrelationship of philosophy and science. (shrink)

This book is both suitable for logically and algebraically minded graduate and advanced graduate students of mathematics, computer science and philosophy, and ...

This paper is a reaction to the following remark by grzegorczyk: "the compound sentences are not a product of experiment. they arise from reasoning. this concerns also negations; we see that the lemon is yellow, we do not see that it is not blue." generally, in science the truth is ascertained as indirectly as falsehood. an example: a litmus-paper is used to verify the sentence "the solution is acid." this approach gives rise to a (very intuitionistic indeed) conservative extension of (...) the heyting logic satisfying natural duality laws. (shrink)

The class of equivalential logics comprises all implicative logics in the sense of Rasiowa [9], Suszko's logic SCI and many others. Roughly speaking, a logic is equivalential iff the greatest strict congruences in its matrices are determined by polynomials. The present paper is the first part of the survey in which systematic investigations into this class of logics are undertaken. Using results given in [3] and general theorems from the theory of quasi-varieties of models [5] we give a characterization of (...) all simple C-matrices for any equivalential logic C. In corollaries we give necessary and sufficient conditions for the class of all simple models for a given equivalential logic to be closed under free products. (shrink)

§0. A familiar if obscure idea: an indicative conditional presents its consequent as holding in the actual world on the supposition that its antecedent so holds, whereas a subjunctive conditional merely presents its consequent as holding in a world, typically counterfactual, in which its antecedent holds. Consider this pair.

ukasiewicz''s four-valued modal logic is surveyed and analyzed, together with ukasiewicz''s motivations to develop it. A faithful interpretation of it in classical (non-modal) two-valued logic is presented, and some consequences are drawn concerning its classification and its algebraic behaviour. Some counter-intuitive aspects of this logic are discussed in the light of the presented results, ukasiewicz''s own texts, and related literature.

We consider the class of pointed varieties of algebras having a lattice term reduct and we show that each such variety gives rise in a natural way, and according to a regular pattern, to at least three interesting logics. Although the mentioned class includes several logically and algebraically significant examples (e.g. Boolean algebras, MV algebras, Boolean algebras with operators, residuated lattices and their subvarieties, algebras from quantum logic or from depth relevant logic), we consider here in greater detail Abelian ℓ-groups, (...) where such logics respectively correspond to: i) Meyer and Slaney’s Abelian logic [31]; ii) Galli et al.’s logic of equilibrium [21]; iii) a new logic of “preservation of truth degrees”. (shrink)

Draws attention to some unexpected consequences of using a zero-ary connective in modal propositional logic.

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 +.

It is known that indicative and subjunctive conditionals interact differently with a rigidifying "actually" operator. The paper studies this difference in an abstract setting. It does not assume the framework of possible world semantics, characterizing "actually" instead by the type of logically valid formulas to which it gives rise. It is proved that in a language with such features all sentential contexts that are congruential (in the sense that they preserve logical equivalence) are extensional (in the sense that they preserve (...) material equivalence). For a subjunctive conditional, the natural conclusion to draw is that it is non-congruential. It is much harder to defend the claim that an indicative conditional is non-congruential. The pressure to treat the indicative conditional as truth-functional is correspondingly greater. The implications of these results for attempts to interpret the indicative conditional as an epistemic or doxastic operator are assessed. (shrink)

A sentence mentioning an object can be regarded as saying any one of several things about that object, without thereby being ambiguous. Some of the (logical) repercussions of this commonplace observation are recorded, and some critical discussion is provided of views which would appear to go against it.

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 ^{+}$.

The following logics are the most noteworthy from the perspective of the calculus of combinators: the Hilbert’s positive implicational logic , the Church’s weak theory of implication , the BCK-logic, and the BCI-logic. Their significance is due to a certain correspondence between combinators and implicational formulas . The first three logics mentioned have been immensely investigated but it was not so in case of the remaining one. The BCI-logics was mentioned by A. N. Prior in the second edition of his (...) Formal Logic of 1962 where it was credited to C. A. Meredith and dated in 1956 . A. (shrink)

Exegesis, analysis and discussion of an argument deployed by Dana Scott in his 1973 paper ‘Background to Formalization’, rovide an ideal setting for getting clear about some subtleties in the apparently simple idea of conservative extension. There, Scott claimed in respect of two fundamental principles concerning implication that any generalized consequence relation respecting these principles is always extended conservatively by some similarly fundamental principles concerning conjunction and disjunction. This claim appears on the face of it to conflict with cases in (...) the literature in which adding principles governing conjunction or disjunction or both provides a non-conservative extension of the logic to which they are added, even if that logic does satisfy the intuitionistic conditions on implication. We explore the extent to which such cases can be transformed into counterexamples to Scott’s claim. Once one part of this claim is suitably disambiguated, we find no conflict after all, though we also find that Scott occasionally understates what the argument he provides in support of this claim actually establishes. The main goal, apart from getting straight about Scott’s argument, is to give an airing to various issues and distinctions in the general area of conservativity of extensions; as a side benefit, some semantic light will be thrown on a fragmentary intermediate logic of R. A. Bull, which A. N. Prior showed to be extended non-conservatively by the addition of conjunction, governed by the usual axioms. We will see exactly why, despite appearances, this is not a counterexample to Scott’s claim. (shrink)

In the present note we continue the investigations undertaken in [2]. A full version of the paper has been submitted to Studia Logica. x1 Our goal is to give a characterization of the so called factorial matrices for a logic. A matrix M = is factorial i the greatest congruence M of M coincides with the diagonal of A. Recall that is a congruence of a matrix M = i is a congruence of the algebra A and for any a; (...) b 2 A, if ab then a 2 D i b 2 D. (shrink)

In Section 1 we show that the De Morgan type rules (= sequential rules in L(, ) which remain correct if and are interchanged) are finitely based. Section 2 contains a similar result for L(). These results are essentially based on special properties of some equational theories.

Section 1 contains a Kripke-style completeness theorem for arbitrary intermediate consequences. In Section 2 we apply weak Kripke semantics to splittings in order to obtain generalized axiomatization criteria of the Jankov-type. Section 3 presents new and short proofs of recent results on implicationless intermediate consequences. In Section 4 we prove that these consequences admit no deduction theorem. In Section 5 all maximal logics in the 3 rd counterslice are determined. On these results we reported at the 1980 meeting on Mathematical (...) Logic at Oberwolfach. This paper concerns propositional logic only. (shrink)

We study a multiple-succedent sequent calculus with both of the structural rules Left Weakening and Left Contraction but neither of their counterparts on the right, for possible application to the treatment of multiplicative disjunction against the background of intuitionistic logic. We find that, as Hirokawa dramatically showed in a 1996 paper with respect to the rules for implication, the rules for this connective render derivable some new structural rules, even though, unlike the rules for implication, these rules are what we (...) call ipsilateral: applying such a rule does not make any formula change sides—from the left to the right of the sequent separator or vice versa. Some possibilities for a semantic characterization of the resulting logic are also explored. The paper concludes with three open questions. (shrink)

After some motivating remarks in Section 1, in Section 2 we show how to replace an axiomatic basis for any one of a broad range of sentential logics having finitely many axiom schemes and Modus Ponens as the sole proper rule, by a basis with the same axiom schemes and finitely many one-premiss rules. Section 3 mentions some questions arising from this replacement procedure , explores another such procedure, and discusses some aspects of the consequence relations associated with the different (...) axiomatizations in play. Several open problems are mentioned. An appendix briefly treats the issue of a similar ‘at most one-premiss rules’ reformulation of proof systems with sequent-to-sequent rules. (shrink)

Humberstone asks whether every theorem of BCI provably implies $\phi\to\phi$ for some formula $\phi$. Meyer conjectures that the axiom $\mathbf{B}$ does not imply any such "self-implication." We prove a slightly stronger result, thereby confirming Meyer's conjecture.

Die vorliegenden Untersuchungen haben sich aus solchen entwickelt, die ich an andrer Stelle früher veröffentlichte. Die Kenntnis dieser früheren Arbeit wird in keiner Weise hier vorausgesetzt und ist für das folgende unwesentlich. Es sei mir jedoch gestattet, für den Kenner der früheren Arbeit einige Bemerkungen voraufzuschicken. In der genannten Arbeit hatte ich, angeregt ursprünglich durch Gedankengänge von Herrn Behmann, ein typenfreies System der Logik aufgebaut, das allein auf dem Gedanken fußte, daß der Definitionsbereich der Prädikate im allgemeinen beschränkt ist, sodaß (...) nur bestimmte Zusammenstellungen von Prädikaten und Dingen sinnvolle, d.h. wahre oder falsche Aussagen ergeben, und das diesen Gesichtspunkt meiner Meinung nach konsequent durchführte. Eine anschließende Arbeit sollte dann die Widerspruchsfreiheit des Systems untersuchen. Diese Untersuchung ist inzwischen geschehen. Es zeigte sich, daß sich die Widerspruchsfreiheit des Systems nur dann beweisen ließ, falls die in ihm enthaltene Vollständigkeit von → die sich durch das Bestehen eines Deduktionstheorems zeigte, fallen gelassen wurde. Die Grundformeln (13) und (14) mußten wegbleiben. Die Widerspruchsfreiheit des restlichen Systems ließ sich dann durch eine dem System eigentümliche Methode der Beweistransformation zeigen.Diese anschließienden Untersuchungen, die ihrer Zeit nicht mehr veröffentlicht werden konnten, sind inzwischen durch die vorliegenden überholt. Es war das Unbefriedigende bei dem genannten Aufbau, daß hinterher doch wieder eine Einschränkung gemacht werden mußte, die sich nicht aus den zugrunde gelegten Prinzipien ergab, sondern von ihnen aus unvorhergesehen war. Diese Einschränkung bewirkte übrigens, daß keine volle Zahlentheorie in dem System zu gewinnen war. (shrink)

Die vorliegenden Untersuchungen haben sich aus solchen entwickelt, die ich an andrer Stelle früher veröffentlichte. Die Kenntnis dieser früheren Arbeit wird in keiner Weise hier vorausgesetzt und ist für das folgende unwesentlich. Es sei mir jedoch gestattet, für den Kenner der früheren Arbeit einige Bemerkungen voraufzuschicken. In der genannten Arbeit hatte ich, angeregt ursprünglich durch Gedankengänge von Herrn Behmann, ein typenfreies System der Logik aufgebaut, das allein auf dem Gedanken fußte, daß der Definitionsbereich der Prädikate im allgemeinen beschränkt ist, sodaß (...) nur bestimmte Zusammenstellungen von Prädikaten und Dingen sinnvolle, d.h. wahre oder falsche Aussagen ergeben, und das diesen Gesichtspunkt meiner Meinung nach konsequent durchführte. Eine anschließende Arbeit sollte dann die Widerspruchsfreiheit des Systems untersuchen. Diese Untersuchung ist inzwischen geschehen. Es zeigte sich, daß sich die Widerspruchsfreiheit des Systems nur dann beweisen ließ, falls die in ihm enthaltene Vollständigkeit von → die sich durch das Bestehen eines Deduktionstheorems zeigte, fallen gelassen wurde. Die Grundformeln (13) und (14) mußten wegbleiben. Die Widerspruchsfreiheit des restlichen Systems ließ sich dann durch eine dem System eigentümliche Methode der Beweistransformation zeigen.Diese anschließienden Untersuchungen, die ihrer Zeit nicht mehr veröffentlicht werden konnten, sind inzwischen durch die vorliegenden überholt. Es war das Unbefriedigende bei dem genannten Aufbau, daß hinterher doch wieder eine Einschränkung gemacht werden mußte, die sich nicht aus den zugrunde gelegten Prinzipien ergab, sondern von ihnen aus unvorhergesehen war. Diese Einschränkung bewirkte übrigens, daß keine volle Zahlentheorie in dem System zu gewinnen war. (shrink)

Section 1 recalls a point noted by A. N. Prior forty years ago: that a certain formula in the language of a purely implicational intermediate logic investigated by R. A. Bull is unprovable in that logic but provable in the extension of the logic by the usual axioms for conjunction, once this connective is added to the language. Section 2 reminds us that every formula is interdeducible with (i.e. added to intuitionistic logic, yields the same intermediate logic as) some conjunction-free (...) formula. Thus it would seem that any detour going via formulas with conjunction can be avoided, which raises a puzzle: how is this consistent with the point from Section 1? Sections 3 and 4 raise and discuss this puzzle. In fact, the puzzle turns out on closer inspection not to be so puzzling after all, but it does serve as a convenient centrepiece around which to organize a discussion of the phenomenon illustrated by the Bull–Prior example. Section 5 notes that Prior's observation can be extended to the case of the result of adding disjunction to Bull's logic, while Section 6 includes some further remarks aimed at diagnosing one source of possible residual puzzlement. A subtext of our discussion—spanning several of the notes—is that this work by Bull and Prior has been overlooked, their results having to be rediscovered, by many algebraists and logicians in more recent years. (shrink)