Building on the work of Peter Hinst and Geo Siegwart, we develop a pragmatised naturaldeduction calculus, i.e. a naturaldeduction calculus that incorporates illocutionary operators at the formal level, and prove its adequacy. In contrast to other linear calculi of naturaldeduction, derivations in this calculus are sequences of object-language sentences which do not require graphical or other means of commentary in order to keep track of assumptions or to indicate subproofs. (Translation of (...) our German paper "Ein Redehandlungskalkül. Ein pragmatisierter Kalkül des natürlichen Schließens nebst Metatheorie"; online available at http://philpapers.org/rec/CORERE.). (shrink)
The relation between logic and thought has long been controversial, but has recently influenced theorizing about the nature of mental processes in cognitive science. One prominent tradition argues that to explain the systematicity of thought we must posit syntactically structured representations inside the cognitive system which can be operated upon by structure sensitive rules similar to those employed in systems of naturaldeduction. I have argued elsewhere that the systematicity of human thought might better be explained as resulting (...) from the fact that we have learned natural languages which are themselves syntactically structured. According to this view, symbols of natural language are external to the cognitive processing system and what the cognitive system must learn to do is produce and comprehend such symbols. In this paper I pursue that idea by arguing that ability in naturaldeduction itself may rely on pattern recognition abilities that enable us to operate on external symbols rather than encodings of rules that might be applied to internal representations. To support this suggestion, I present a series of experiments with connectionist networks that have been trained to construct simple natural deductions in sentential logic. These networks not only succeed in reconstructing the derivations on which they have been trained, but in constructing new derivations that are only similar to the ones on which they have been trained. (shrink)
This article studies the mathematical properties of two systems that model Aristotle's original syllogistic and the relationship obtaining between them. These systems are Corcoran's naturaldeduction syllogistic and Lukasiewicz's axiomatization of the syllogistic. We show that by translating the former into a first-order theory, which we call T RD, we can establish a precise relationship between the two systems. We prove within the framework of first-order logic a number of logical properties about T RD that bear upon the (...) same properties of the naturaldeduction counterpart ? that is, Corcoran's system. Moreover, the first-order logic framework that we work with allows us to understand how complicated the semantics of the syllogistic is in providing us with examples of bizarre, unexpected interpretations of the syllogistic rules. Finally, we provide a first attempt at finding the structure of that semantics, reducing the search to the characterization of the class of models of T RD. (shrink)
Prawitz proved a theorem, formalising 'harmony' in NaturalDeduction systems, which showed that, corresponding to any deduction there is one to the same effect but in which no formula occurrence is both the consequence of an application of an introduction rule and major premise of an application of the related elimination rule. As Gentzen ordered the rules, certain rules in Classical Logic had to be excepted, but if we see the appropriate rules instead as rules for Contradiction, (...) then we can extend the theorem to the classical case. Properly arranged there is a thoroughgoing 'harmony', in the classical rules. Indeed, as we shall see, they are, all together, far more 'harmonious' in the general sense than has been commonly observed. As this paper will show, the appearance of disharmony has only arisen because of the illogical way in which naturaldeduction rules for Classical Logic have been presented. (shrink)
In 1934 a most singular event occurred. Two papers were published on a topic that had (apparently) never before been written about, the authors had never been in contact with one another, and they had (apparently) no common intellectual background that would otherwise account for their mutual interest in this topic.1 These two papers formed the basis for a movement in logic which is by now the most common way of teaching elementary logic by far, and indeed is perhaps all (...) that is known in any detail about logic by a number of philosophers (especially in North America). This manner of proceeding in logic is called ‘naturaldeduction’. And in its own way the instigation of this style of logical proof is as important to the history of logic as the discovery of resolution by Robinson in 1965, or the discovery of the logistical method by Frege in 1879, or even the discovery of the syllogistic by Aristotle in the fourth century BC. (shrink)
Curry's paradox, sometimes described as a general version of the better known Russell's paradox, has intrigued logicians for some time. This paper examines the paradox in a naturaldeduction setting and critically examines some proposed restrictions to the logic by Fitch and Prawitz. We then offer a tentative counterexample to a conjecture by Tennant proposing a criterion for what is to count as a genuine paradox.
Naturaldeduction is the type of logic most familiar to current philosophers, and indeed is all that many modern philosophers know about logic. Yet naturaldeduction is a fairly recent innovation in logic, dating from Gentzen and Ja?kowski in 1934. This article traces the development of naturaldeduction from the view that these founders embraced to the widespread acceptance of the method in the 1960s. I focus especially on the different choices made by writers (...) of elementary textbooks?the standard conduits of the method to a generation of philosophers?with an eye to determining what the ?essential characteristics? of naturaldeduction are. (shrink)
Naturaldeduction (for short: nd-) calculi have not been used systematically as a basis for automated theorem proving in classical logic. To remove objective obstacles to their use we describe (1) a method that allows to give semantic proofs of normal form theorems for nd-calculi and (2) a framework that allows to search directly for normal nd-proofs. Thus, one can try to answer the question: How do we bridge the gap between claims and assumptions in heuristically motivated ways? (...) This informal question motivates the formulation of intercalation calculi. Ic-calculi are the technical underpinnings for (1) and (2), and our paper focuses on their detailed presentation and meta-mathematical investigation in the case of classical predicate logic. As a central theme emerges the connection between restricted forms of nd-proofs and (strategies for) proof search: normal forms are not obtained by removing local "detours", but rather by constructing proofs that directly reflect proof-strategic considerations. That theme warrants further investigation. (shrink)
A system of naturaldeduction rules is proposed for an idealized form of English. The rules presuppose a sharp distinction between proper names and such expressions as the c, a (an) c, some c, any c, and every c, where c represents a common noun. These latter expressions are called quantifiers, and other expressions of the form that c or that c itself, are called quantified terms. Introduction and elimination rules are presented for any, every, some, a (an), (...) and the, and also for any which, every which, and so on, as well as rules for some other concepts. One outcome of these rules is that Every man loves some woman is implied by, but does not imply, Some woman is loved by every man, since the latter is taken to mean the same as Some woman is loved by all men. Also, Jack knows which woman came is implied by Some woman is known by Jack to have come, but not by Jack knows that some woman came. (shrink)
John Corcoran?s naturaldeduction system for Aristotle?s syllogistic is reconsidered.Though Corcoran is no doubt right in interpreting Aristotle as viewing syllogisms as arguments and in rejecting Lukasiewicz?s treatment in terms of conditional sentences, it is argued that Corcoran is wrong in thinking that the only alternative is to construe Barbara and Celarent as deduction rules in a naturaldeduction system.An alternative is presented that is technically more elegant and equally compatible with the texts.The abstract role (...) assigned by tradition and Lukasiewicz to Barbara and Celarent is retained.The two ? perfect syllogisms? serve as ?basic elements? in the construction of an inductively defined set of valid syllogisms.The proposal departs from Lukasiewicz, and follows Corcoran, however, in construing the construction as one in naturaldeduction.The result is a sequent system with fewer rules and in which Barbara and Celarent serve as basic deductions.To compare the theory to Corcoran?s, his original is reformulated in current terms and generalized.It is shown to be equivalent to the proposed sequent system, and several variations are discussed.For all systems mentioned, a method of Henkin?style completeness proofs is given that is more direct and intuitive than Corcoran?s original. (shrink)
Drawing upon Martin-Löf’s semantic framework for his constructive type theory, semantic values are assigned also to natural-deduction derivations, while observing the crucial distinction between (logical) consequence among propositions and inference among judgements. Derivations in Gentzen’s (1934–5) format with derivable formulae dependent upon open assumptions, stand, it is suggested, for proof-objects (of propositions), whereas derivations in Gentzen’s (1936) sequential format are (blue-prints for) proof-acts.
This paper is concerned with a naturaldeduction system for First Degree Entailment (FDE). First, we exhibit a brief history of FDE and of combined systems whose underlying idea is used in developing the naturaldeduction system. Then, after presenting the language and a semantics of FDE, we develop a naturaldeduction system for FDE. We then prove soundness and completeness of the system with respect to the semantics. The system neatly represents the four-valued (...) semantics for FDE. (shrink)
A sequent calculus is given in which the management of weakening and contraction is organized as in naturaldeduction. The latter has no explicit weakening or contraction, but vacuous and multiple discharges in rules that discharge assumptions. A comparison to naturaldeduction is given through translation of derivations between the two systems. It is proved that if a cut formula is never principal in a derivation leading to the right premiss of cut, it is a subformula (...) of the conclusion. Therefore it is sufficient to eliminate those cuts that correspond to detour and permutation conversions in naturaldeduction. (shrink)
We present a framework for machine implementation of families of non-classical logics with Kripke-style semantics. We decompose a logic into two interacting parts, each a naturaldeduction system: a base logic of labelled formulae, and a theory of labels characterizing the properties of the Kripke models. By appropriate combinations we capture both partial and complete fragments of large families of non-classical logics such as modal, relevance, and intuitionistic logics. Our approach is modular and supports uniform proofs of soundness, (...) completeness and proof normalization. We have implemented our work in the Isabelle Logical Framework. (shrink)
In this paper we make some observations about NaturalDeduction derivations [Prawitz, 1965, van Dalen, 1986, Bell and Machover, 1977]. We assume the reader is familiar with it and with proof-theory in general. Our development will be simple, even simple-minded, and concrete. However, it will also be evident that general ideas motivate our examples, and we think both our specific examples and the ideas behind them are interesting and may be useful to some readers. In a sentence, the (...) bare technical content of this paper is: Extending naturaldeduction with global well-formedness conditions can neatly and cheaply capture classical and intermediate logics. The interest here is in the ‘neatly’ and ‘cheaply’. By ‘neatly’ we mean ‘preserving proof-normalisation’,1 and ‘maintaining the subformula property’, and by ‘cheaply’ we mean ‘preserving the formal structure of deductions’ (so that a deduction in the original system is still, formally, a deduction in the extended system, and in particular it requires no extra effort to write just because it is in the extended system). To illustrate what we have in mind consider intuitionistic first-order logic (FOL) [van Dalen, 1986] as a paradigmatic example of a formal notion of deduction. A naturaldeduction derivation (or deduction) is an inductively defined tree structure where each node contains an instance of a formula. A deduction is valid when each successive node follows from its predecessors in accordance with some predetermined inference rules. A particular attraction of NaturalDeduction is its clean and economical presentation. Here for example are deduction (fragments) proving A ∧ B from A and B, and ∀x. (P (x) ∧ Q(x)) from ∀x. P (x) and ∀x. Q(x): ∀x. P (x) (∀E). (shrink)
This is a companion paper to Braüner (2004b, Journal of Logic and Computation 14, 329–353) where a naturaldeduction system for propositional hybrid logic is given. In the present paper we generalize the system to the first-order case. Our naturaldeduction system for first-order hybrid logic can be extended with additional inference rules corresponding to conditions on the accessibility relations and the quantifier domains expressed by so-called geometric theories. We prove soundness and completeness and we prove (...) a normalisation theorem. Moreover, we give an axiom system first-order hybrid logic. (shrink)
The author presents a deduction system for Quantum Logic. This system is a combination of a naturaldeduction system and rules based on the relation of compatibility. This relation is the logical correspondant of the commutativity of observables in Quantum Mechanics or perpendicularity in Hilbert spaces.Contrary to the system proposed by Gibbins and Cutland, the naturaldeduction part of the system is pure: no algebraic artefact is added. The rules of the system are the rules (...) of Classical NaturalDeduction in which is added a control of contexts using the compatibility relation. (shrink)
The paper is devoted to the concise description of some NaturalDeduction System (ND for short) for Linear Temporal Logic. The system's distinctive feature is that it is labelled and analytical. Labels convey necessary semantic information connected with the rules for temporal functors while the analytical character of the rules lets the system work as a decision procedure. It makes it more similar to Labelled Tableau Systems than to standard NaturalDeduction. In fact, our solution of (...) linearity representation is rather independent of the underlying proof method, provided that some form of (analytic) cut is admissible. We will also discuss some generalisations of the system and compare it with other formalizations of linearity. (shrink)
The comprehension principle of set theory asserts that a set can be formed from the objects satisfying any given property. The principle leads to immediate contradictions if it is formalized as an axiom scheme within classical first order logic. A resolution of the set paradoxes results if the principle is formalized instead as two rules of deduction in a naturaldeduction presentation of logic. This presentation of the comprehension principle for sets as semantic rules, instead of as (...) a comprehension axiom scheme, can be viewed as an extension of classical logic, in contrast to the assertion of extra-logical axioms expressing truths about a pre-existing or constructed universe of sets. The paradoxes are disarmed in the extended classical semantics because truth values are only assigned to those sentences that can be grounded in atomic sentences. (shrink)
We give two proofs of strong normalisation for second order classical naturaldeduction. The first one is an adaptation of the method of reducibility candidates introduced in [9] for second order intuitionistic naturaldeduction; the extension to the classical case requires in particular a simplification of the notion of reducibility candidate. The second one is a reduction to the intuitionistic case, using a Kolmogorov translation.
Most automated theorem provers are clausal-form provers based on variants of resolutionrefutation. In my [1990], I described the theorem prover OSCAR that was based instead on naturaldeduction. Some limited evidence was given suggesting that OSCAR was suprisingly efficient. The evidence consisted of a handful of problems for which published data was available describing the performance of other theorem provers. This evidence was suggestive, but based upon too meager a comparison to be conclusive. The question remained, “How does (...)naturaldeduction compare with resolution-refutation?” In the ensuing seven years, OSCAR has evolved in important ways, and other developments have made it possible to collect more accurate comparative data. Specifically, the creation of the TPTP library of problems for theorem provers,1 and the availability of important theorem provers on the world wide web, make objective comparisons easier. These developments recently inspired Geoff Sutcliffe, one of the founders of the TPTP library, to issue a challenge to OSCAR. At CADE-13, a competition was held for clausal-form theorem provers.2 Otter was one of the most successful contestants. In addition, Otter is able to handle problems stated in natural form (as opposed to clausal form), and Otter is readily available for different platforms.3 Sutcliffe selected 212 problems from the TPTP library, and suggested that OSCAR and Otter run these problems on the same hardware. This “Shootout at the ATP corral” took place, with the result that OSCAR was on the average 40 times faster than Otter. In addition, OSCAR was able to find proofs for 16 problems on which Otter failed, and Otter was able to find proofs for 3 problems on which OSCAR failed. Taking into account that Otter was written in C and OSCAR in LISP, the speed difference of the algorithms themselves could be as much as an order of magnitude greater. Apparently, naturaldeduction has some advantages over resolution-refutation.. (shrink)
We give a direct, purely arithmetical and elementary proof of the strong normalization of the cut-elimination procedure for full (i.e., in presence of all the usual connectives) classical naturaldeduction.
Although resolution-based inference is perhaps the industry standard in automated theorem proving, there have always been systems that employed a different format. For example, the Logic Theorist of 1957 produced proofs by using an axiomatic system, and the proofs it generated would be considered legitimate axiomatic proofs; Wang’s systems of the late 1950’s employed a Gentzen-sequent proof strategy; Beth’s systems written about the same time employed his semantic tableaux method; and Prawitz’s systems of again about the same time are often (...) said to employ a naturaldeduction format. [See Newell, et al (1957), Beth (1958), Wang (1960), and Prawitz et al (1960)]. Like sequent proof systems and tableaux proof systems, naturaldeduction systems retain.. (shrink)
In this paper two different naturaldeduction systems forhybrid logic are compared and contrasted.One of the systems was originally given by the author of the presentpaper whereasthe other system under consideration is a modifiedversion of a natural deductionsystem given by Jerry Seligman.We give translations in both directions between the systems,and moreover, we devise a set of reduction rules forthe latter system bytranslation of already known reduction rules for the former system.
We present systems of NaturalDeduction based on Strict Implication for the main normal modal logics between K and S5. In this work we consider Strict Implication as the main modal operator, and establish a natural correspondence between Strict Implication and strict subproofs.
This paper points out an error of Parigot's proof of strong normalization of second order classical naturaldeduction by the CPS-translation, discusses erasing-continuation of the CPS-translation, and corrects that proof by using the notion of augmentations.
This paper points out an error of Parigot's proof of strong normalization of second order classical naturaldeduction by the CPS-translation, discusses erasing-continuation of the CPS-translation, and corrects that proof by using the notion of augmentations.
This volume examines the notion of an analytic proof as a naturaldeduction, suggesting that the proof's value may be understood as its normal form--a concept with significant implications to proof-theoretic semantics.
This paper presents two systems of naturaldeduction for the rejection of non-tautologies of classical propositional logic. The first system is sound and complete with respect to the body of all non-tautologies, the second system is sound and complete with respect to the body of all contradictions. The second system is a subsystem of the first. Starting with Jan Łukasiewicz's work, we describe the historical development of theories of rejection for classical propositional logic. Subsequently, we present the two (...) systems of naturaldeduction and prove them to be sound and complete. We conclude with a ‘Theorem of Inversion’. (shrink)
Future Logic is an original and wide-ranging treatise of formal logic. It deals with deduction and induction, of categorical and conditional propositions, involving the natural, temporal, extensional, and logical modalities. This is the first work ever to strictly formalize the inductive processes of generalization and particularization, through the novel methods of factorial analysis, factor selection and formula revision. This is the first work ever to develop a formal logic of the natural, temporal and extensional types of conditioning (...) (as distinct from logical conditioning), including their production from modal categorical premises. (shrink)
Building on the work of Peter Hinst and Geo Siegwart, we develop a pragmatised naturaldeduction calculus, i.e., a naturaldeduction calculus that incorporates illocutionary operators at the formal level, and prove its adequacy. In contrast to other linear calculi of naturaldeduction, derivations in this calculus are sequences of object-language sentences which do not require graphical or other means of commentary in order to keep track of assumptions or to indicate subproofs.
This paper aims to develop the implications of logical expressivism for a theory of dialogue coherence. I proceed in three steps. Firstly, certain structural properties of cooperative dialogue are identified. Secondly, I describe a variant of the multi-agent naturaldeduction calculus that I introduced in Piwek (J Logic Lang Inf 16(4):403–421, 2007 ) and demonstrate how it accounts for the aforementioned structures. Thirdly, I examine how the aforementioned system can be used to formalise an expressivist account of logical (...) vocabulary that is inspired by Brandom (Making it explicit: reasoning, representing, and discursive commitment, 1994 ; Articulating reasons: an introduction to inferentialism, 2000 ). This account conceives of the logical vocabulary as a tool which allows speakers to describe the inferential practices which underlie their language use, i.e., it allows them to make those practices explicit. The rewards of this exercise are twofold: (1) We obtain a more precise account of logical expressivism which can be defended more effectively against the critique that such accounts lead to cultural relativism. (2) The formalised distinction between engaging in a practice and expressing it, opens the way for a revision of the theory of dialogue coherence. This revision eliminates the need for logically complex formulae to account for certain structural properties of cooperative dialogue. (shrink)
Proof-theoretical notions and techniques, developed on the basis of sentential/symbolic representations of formal proofs, are applied to Euler diagrams. A translation of an Euler diagrammatic system into a naturaldeduction system is given, and the soundness and faithfulness of the translation are proved. Some consequences of the translation are discussed in view of the notion of free ride, which is mainly discussed in the literature of cognitive science as an account of inferential efficacy of diagrams. The translation enables (...) us to formalize and analyze free ride in terms of proof theory. The notion of normal form of Euler diagrammatic proofs is investigated, and a normalization theorem is proved. Some consequences of the theorem are further discussed: in particular, an analysis of the structure of normal diagrammatic proofs; a diagrammatic counterpart of the usual subformula property; and a characterization of diagrammatic proofs compared with naturaldeduction proofs. (shrink)
This paper presents a novel proof-theoretic account of dialogue coherence. It focuses on an abstract class of cooperative information-oriented dialogues and describes how their structure can be accounted for in terms of a multi-agent hybrid inference system that combines naturaldeduction with information transfer and observation. We show how certain dialogue structures arise out of the interplay between the inferential roles of logical connectives (i.e., sentence semantics), a rule for transferring information between agents, and a rule for information (...) flow between agents and their environment. The order of explanation is opposite in direction to that adopted in game-theoretic semantics, where sentence semantics (or a notion of valid inference) is derived from winning dialogue strategies. That approach and the current one may, however, be reconcilable, since we focus on cooperative dialogue, whereas the game-theoretic tradition concentrates on adversarial dialogue. (shrink)
