In this paper we provide a detailed proof-theoretical analysis of a natural deduction system for classical propositional logic that (i) represents classical proofs in a more natural way than standard Gentzen-style natural deduction, (ii) admits of a simple normalization procedure such that normal proofs enjoy the Weak Subformula Property, (iii) provides the means to prove a Non-contamination Property of normal proofs that is not satisfied by normal proofs in the Gentzen tradition and is useful for applications, especially in formal argumentation, (...) (iv) naturally leads to defining a notion of depth of a proof, to the effect that, for every fixed natural k, normal k-depth deducibility is a tractable problem and converges to classical deducibility as k tends to infinity. (shrink)

Although much technical and philosophical attention has been given to relevance logics, the notion of relevance itself is generally left at an intuitive level. It is difficult to find in the literature an explicit account of relevance in formal reasoning. In this article I offer a formal explication of the notion of relevance in deductive logic and argue that this notion has an interesting place in the study of classical logic. The main idea is that a premise is relevant to (...) an argument when it contributes to the validity of that argument. I then argue that the sequents which best embody this ideal of relevance are the so-called perfect sequents—that is, sequents which are valid but have no proper subsequents that are valid. Church’s theorem entails that there is no recursively axiomatizable proof-system that proves all and only the perfect sequents, so the project that emerges from studying perfection in classical logic is not one of finding a perfect subsystem of classical logic, but is rather a comparative study of classifying subsystems of classical logic according to how well they approximate the ideal of perfection. (shrink)

The concept of _substructural logic_ was originally introduced in relation to limitations of Gentzen’s structural rules of Contraction, Weakening and Exchange. Recent years have witnessed the development of substructural logics also challenging the Tarskian properties of Reflexivity and Transitivity of logical consequence. In this introduction we explain this recent development and two aspects in which it leads to a reassessment of the bounds of classical logic. On the one hand, standard ways of defining the notion of logical consequence in classical (...) logic naturally induce substructural logics when admitting more than two truth values; on the other hand, these substructural logics give rise to hierarchies of _metainferences_ that can be used to approximate classical logic at different levels. (shrink)

In this paper we present a logic that determines when implications in a classical logic context express a relevant connection between antecedent and consequent. In contrast with logics in the relevance logic literature, we leave classical negation intact—in the sense that the law of non-contradiction can be used to obtain relevant implications, as long as there is a connection between antecedent and consequent. On the other hand, we give up the requirement that our theory of relevance should be able to (...) define a new standard of deduction. We present and argue for a list of requirements such a logical theory of classical relevance needs to meet and go on to formulate a system that respects each of these requirements. The presented system is a Tarski logic that extends the relevance logic R with a new relevant implication which allows for Disjunctive Syllogism and similar rules. This is achieved by interpreting the logical symbols in the antecedents in a stronger way than the logical symbols in consequents. A proof theory and an algebraic semantics are formulated and interesting metatheorems are proven. Finally we give a philosophical motivation for our non-standard relevant implication and the asymmetric interpretation of antecedents and consequents. (shrink)

In this paper we first develop a logic independent account of relevant implication. We propose a stipulative denition of what it means for a multiset of premises to relevantly L-imply a multiset of conclusions, where L is a Tarskian consequence relation: the premises relevantly imply the conclusions iff there is an abstraction of the pair such that the abstracted premises L-imply the abstracted conclusions and none of the abstracted premises or the abstracted conclusions can be omitted while still maintaining valid (...) L-consequence. Subsequently we apply this denition to the classical logic consequence relation to obtain NTR-consequence, i.e. the relevant CL-consequence relation in our sense, and develop a sequent calculus that is sound and complete with regard to relevant CL-consequence. We present a sound and complete sequent calculus for NTR. In a next step we add rules for an object language relevant implication to the sequent calculus. The object language implication reflects exactly the NTR-consequence relation. One can see the resulting logic NTR-> as a relevant logic in the traditional sense of the word. By means of a translation to the relevant logic R, we show that the presented logic NTR is very close to relevance logics in the Anderson-Belnap-Dunn-Routley-Meyer tradition. However, unlike usual relevant logics, NTR is decidable for the full language, Disjunctive Syllogism and Adjunction are valid, and neither Modus Ponens nor the Cut rule are admissible. (shrink)

In a recent paper on Truth, Knowability and Neutrality Timothy Kenyon sets out to defend the coherence of a putative anti-realist truth-predicate, superassertibility, due to Wright (1992, 1999), against a number of Wright’s critics. By his own admission, the success of Kenyon’s defensive strategies turns out to hinge upon a realist conception of absolute warrant which conflicts with the anti-realist character of the original proposal, based, as it was, on a notion of defeasible warrant. Kenyon’s potential success in resisting Wright’s (...) critics brings a pyrrhic victory: either way, realism wins. Here I argue that the link between superassertibility and defeasible warrant can be restored in a way which clarifies the consistency of the pair, provided that the notion of inference to superassertibility is properly understood in logical terms. As one might expect, the requisite notion is not classical in character. As one might not expect, the notion cannot be properly construed in intuitionist terms either. Hence, I propose an alternative logical framework which, I believe, is at least formally adequate to the representation of superassertibility on the basis of defeasible warrant. The price to be paid for rejecting the ‘third way’ proposed here in favour of either of the two more traditional logical options is precisely that indicated by Kenyon’s discussion. (shrink)

The system of natural deduction that originated with Gentzen , and for which Prawitz proved a normalization theorem, is re-cast so that all elimination rules are in parallel form. This enables one to prove a very exigent normalization theorem. The normal forms that it provides have all disjunction-eliminations as low as possible, and have no major premisses for eliminations standing as conclusions of any rules. Normal natural deductions are isomorphic to cut-free, weakening-free sequent proofs. This form of normalization theorem renders (...) unnecessary Gentzen's resort to sequent calculi in order to establish the desired metalogical properties of his logical system.Ultimate normal forms are well-adapted to the needs of the computational logician, affording valuable constraints on proof-search. They also provide an analysis of deductive relevance. There is a deep isomorphism between natural deductions and sequent proofs in the relevantized system. (shrink)

We define a system IR of first-order intuitionistic relevant logic. We show that intuitionistic mathematics (on the assumption that it is consistent) can be relevantized, by virtue of the following metatheorem: any intuitionistic proof of A from a setX of premisses can be converted into a proof in IR of eitherA or absurdity from some subset ofX. Thus IR establishes the same inconsistencies and theorems as intuitionistic logic, and allows one to prove every intuitionistic consequence of any consistent set of (...) premisses. (shrink)

The Theory of theory change has contraction and revision as its central notions. Of these, contraction is the more fundamental. The best-known theory, due to Alchourrón, Gärdenfors, and Makinson, is based on a few central postulates. The most fundamental of these is the principle of recovery: if one contracts a theory with respect to a sentence, and then adds that sentence back again, one recovers the whole theory. Recovery is demonstrably false. This paper shows why, and investigates how one can (...) nevertheless characterize contraction in a theoretically fruitful way. The theory proposed lends itself to implementation, which in turn could yield new theoretical insights. The Main proposal is a ‘staining algorithm’ which identifies which sentences to reject when contracting a theory. The algorithm requires one to be clear about the structure of reasons one has for including sentences within one's theory. (shrink)

I use the Corcoran–Smiley interpretation of Aristotle's syllogistic as my starting point for an examination of the syllogistic from the vantage point of modern proof theory. I aim to show that fresh logical insights are afforded by a proof-theoretically more systematic account of all four figures. First I regiment the syllogisms in the Gentzen–Prawitz system of natural deduction, using the universal and existential quantifiers of standard first-order logic, and the usual formalizations of Aristotle's sentence-forms. I explain how the syllogistic is (...) a fragment of my system of Core Logic. Then I introduce my main innovation: the use of binary quantifiers, governed by introduction and elimination rules. The syllogisms in all four figures are re-proved in the binary system, and are thereby revealed as all on a par with each other. I conclude with some comments and results about grammatical generativity, ecthesis, perfect validity, skeletal validity and Aristotle's chain principle. (shrink)

Kalrnaric. We set out a system T, consisting of normal proofs constructed by means of elegantly symmetrical introduction and elimination rules. In the system T there are two requirements, called ( ) and ()), on applications of discharge rules. T is sound and complete for Kalmaric arguments. ( ) requires nonvacuous discharge of assumptions; ()) requires that the assumption discharged be the sole one available of highest degree. We then consider a 'Duhemian' extension T*, obtained simply by dropping the requirement (...) ()). T* is a proper subsystem of intuitionistic relevant logic. Our main result is that T* is a double negation consistency companion to classical logic. Thus all one needs to add to T* to obtain classical logic is the (intuitionistic) absurdity rule, and the (classical) rule of double nega-. (shrink)

Restall :279–291, 2014) proposes a new, proof-theoretic, logical pluralism. This is in contrast to the model-theoretic pluralism he and Beall proposed in Beall and Restall :475–493, 2000) and in Beall and Restall. What I will show is that Restall has not described the conditions on being admissible to the proof-theoretic logical pluralism in such a way that relevance logic is one of the admissible logics. Though relevance logic is not hard to add formally, one critical component of Restall’s pluralism is (...) that the relevance logic that gets added must have connectives which mean the same thing as the connectives in the already admitted logic. This is what I will show is not possible. (shrink)

This paper studies the relationship between Argumentation Logic, a recently defined logic based on the study of argumentation in AI, and classical Propositional Logic. In particular, it shows that AL and PL are logically equivalent in that they have the same entailment relation from any given classically consistent theory. This equivalence follows from a correspondence between the non-acceptability of sentences in AL and Natural Deduction proofs of the complement of these sentences. The proof of this equivalence uses a restricted form (...) of ND proofs, where hypotheses in the application of the Reductio of Absurdum inference rule are required to be “relevant” to the absurdity derived in the rule. The paper also discusses how the argumentative re-interpretation of PL could help control the application of ex-falso quodlibet in the presence of inconsistencies. (shrink)

ABSTRACT The concept of paraconsistent logical consequence is usually negatively defined as a validity semantics in which not every sentences is deducible or in which inferential explosion does not occur. Paraconsistency has been negatively characterized in this way because paraconsistent logics have been designed specifically to avoid the trivialization of deductive inference entailed by the classical paradoxes of material implication for applications in a system that tolerates syntactical contradictions. The effect of the negative characterization of paraconsistency has been to encourage (...) an unsystematic development of distinct versions of paraconsistent logic. It has also contributed to a restricted overview of the full range of paraconsistent formalisms. After reviewing a standard negative characterization of paraconsistency and commenting on its limitations, I propose a positive characterization that makes possible a constructivistic description of the complete spectrum of distinct families of paraconsistent logics, and the description of a new type of maximally relevant paraconsistency, which I argue compares favorably with previously identified categories of paraconsistent logics. (shrink)

A conclusion follows from given premisses if and only if an acceptable counterfactual-supporting covering generalization of the argument rules out, either definitively or with some modal qualification, simultaneous acceptability of the premisses and non-accepta-bility of the conclusion, even though it does not rule out acceptability of the premisses and does not require acceptability of the conclusion independently of the premisses. Hence the reiterative associated conditional of an argument is true if and only it has such a covering generalization, and a (...) supposed unexpressed premiss supplied to make an argument formally valid should be a covering generalization. (shrink)

An agent can usually hold a very large number of beliefs. However, only a small part of these beliefs is used at a time. Efficient operations for belief change should affect the beliefs of the agent locally, that is, the changes should be performed only in the relevant part of the belief state. In this paper we define a local consequence operator that only considers the relevant part of a belief base. This operator is used to define local versions of (...) the operations for belief change. Representation theorems are given for the local operators. (shrink)