Free Semantics

Free Semantics is based on normalized natural deduction for the weak relevant logic DW and its near neighbours. This is motivated by the fact that in the determination of validity in truth-functional semantics, natural deduction is normally used. Due to normalization, the logic is decidable and hence the semantics can also be used to construct counter-models for invalid formulae. The logic DW is motivated as an entailment logic just weaker than the logic MC of meaning containment. DW is the logic focussed upon, but the results extend to MC. The semantics is called ‘free semantics’ since it is disjunctively and existentially free in that no disjunctive or existential witnesses are produced, unlike in truth-functional semantics. Such ‘witnesses’ are only assumed in generality and are not necessarily actual. The paper sets up the free semantics in a truth-functional style and gives a natural deduction interpetation of the meta-logical connectives. We then set out a familiar tableau-style system, but based on natural deduction proof rather than truth-functional semantics. A proof of soundness and completeness is given for a reductio system, which is a transform of the tableau system. The reductio system has positive and negative rules in place of the elimination and introduction rules of Brady’s normalized natural deduction system for DW. The elimination-introduction turning points become closures of threads of proof, which are at the points of contradiction for the reductio system.     

Varieties of Linear Calculi

A uniform calculus for linear logic is presented. The calculus has the form of a natural deduction system in sequent calculus style with general introduction and elimination rules. General elimination rules are motivated through an inversion principle, the dual form of which gives the general introduction rules. By restricting all the rules to their single-succedent versions, a uniform calculus for intuitionistic linear logic is obtained. The calculus encompasses both natural deduction and sequent calculus that are obtained as special instances from the uniform calculus. Other instances give all the invertibilities and partial invertibilities for the sequent calculus rules of linear logic. The calculus is normalizing and satisfies the subformula property for normal derivations.     

Normality,Non-contamination and Logical Depth in Classical Natural Deduction

Studia Logica - 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...     

Wie Natürlich ist das System der Natürlichen Deduktion?

How natural is natural deduction?– Gentzen's system of natural deduction intends to fit logical rules to the effective mathematical reasoning in order to overcome the artificiality of deductions in axiomatic systems (¶ 2). In spite of this reform some of Gentzen's rules for natural deduction are criticised by psychologists and natural language philosophers for remaining unnatural. The criticism focuses on the principle of extensionality and on formalism of logic (¶ 3). After sketching the criticism relatively to the main rules, I argue that the criteria of economy, simplicity, pertinence etc., on which the objections are based, transcend the strict domain of logic and apply to arguments in general (¶ 4). (¶ 5) deals with Frege's critique of the concept of naturalness as regards logic. It is shown that this concept means a regression into psychologism and is exposed to the same difficulties as are: relativity, lack of precision, the error of arguing from `is' to `ought' (the naturalistic fallacy). Despite of these, the concept of naturalness plays the role of a diffuse ideal which favours the construction of alternative deductive systems in contrast to the platonic conception of logic (¶ 6).     

A note on sequent calculi intermediate between LJ and LK

We prove that every finitely axiomatizable extension of Heyting's intuitionistic logic has a corresponding cut-free Gentzen-type formulation. It is shown how one can use this result to find the corresponding normalizable natural deduction system and to give a criterion for separability of considered logic. Obviously, the question how to obtain an effective definition of a sequent calculus which corresponds to a concrete logic remains a separate problem for every logic.     

Expressive Power and Incompleteness of Propositional Logics

Natural deduction systems were motivated by the desire to define the meaning of each connective by specifying how it is introduced and eliminated from inference. In one sense, this attempt fails, for it is well known that propositional logic rules (however formulated) underdetermine the classical truth tables. Natural deduction rules are too weak to enforce the intended readings of the connectives; they allow non-standard models. Two reactions to this phenomenon appear in the literature. One is to try to restore the standard readings, for example by adopting sequent rules with multiple conclusions. Another is to explore what readings the natural deduction rules do enforce. When the notion of a model of a rule is generalized, it is found that natural deduction rules express “intuitionistic” readings of their connectives. A third approach is presented here. The intuitionistic readings emerge when models of rules are defined globally, but the notion of a local model of a rule is also natural. Using this benchmark, natural deduction rules enforce exactly the classical readings of the connectives, while this is not true of axiomatic systems. This vindicates the historical motivation for natural deduction rules. One odd consequence of using the local model benchmark is that some systems of propositional logic are not complete for the semantics that their rules express. Parallels are drawn with incompleteness results in modal logic to help make sense of this.     

Cut as Consequence

The papers where Gerhard Gentzen introduced natural deduction and sequent calculi suggest that his conception of logic differs substantially from the now dominant views introduced by Hilbert, Gödel, Tarski, and others. Specifically, (1) the definitive features of natural deduction calculi allowed Gentzen to assert that his classical system nk is complete based purely on the sort of evidence that Hilbert called ‘experimental’, and (2) the structure of the sequent calculi li and lk allowed Gentzen to conceptualize completeness as a question about the relationships among a system's individual rules (as opposed to the relationship between a system as a whole and its ‘semantics’). Gentzen's conception of logic is compelling in its own right. It is also of historical interest, because it allows for a better understanding of the invention of natural deduction and sequent calculi.     

Gödel’s Natural Deduction

This is a companion to a paper by the authors entitled “Gödel on deduction”, which examined the links between some philosophical views ascribed to Gödel and general proof theory. When writing that other paper, the authors were not acquainted with a system of natural deduction that Gödel presented with the help of Gentzen’s sequents, which amounts to Ja?kowski’s natural deduction system of 1934, and which may be found in Gödel’s unpublished notes for the elementary logic course he gave in 1939 at the University of Notre Dame. Here one finds a presentation of this system of Gödel accompanied by a brief reexamination in the light of the notes of some points concerning his interest in sequents made in the preceding paper. This is preceded by a brief summary of Gödel’s Notre Dame course, and is followed by comments concerning Gödel’s natural deduction system.     

A note on the proof theory the λII-calculus

The II-calculus, a theory of first-order dependent function types in Curry-Howard-de Bruijn correspondence with a fragment of minimal first-order logic, is defined as a system of (linearized) natural deduction. In this paper, we present a Gentzen-style sequent calculus for the II-calculus and prove the cut-elimination theorem.The cut-elimination result builds upon the existence of normal forms for the natural deduction system and can be considered to be analogous to a proof provided by Prawitz for first-order logic. The type-theoretic setting considered here elegantly illustrates the distinction between the processes of normalization in a natural deduction system and cut-elimination in a Gentzen-style sequent calculus.We consider an application of the cut-free calculus, via the subformula property, to proof-search in the II-calculus. For this application, the normalization result for the natural deduction calculus alone is inadequate, a (cut-free) calculus with the subformula property being required.This paper was written whilst the author was affiliated to the University of Edinburgh, Scotland, U.K. and revised for publication whilst he was affiliated to the University of Birmingham, England, U.K.Presented byDaniele Mundici     

Curry-Howard Terms for Linear Logic

In this paper we 1. provide a natural deduction system for full first-order linear logic, 2. introduce Curry-Howard-style terms for this version of linear logic, 3. extend the notion of substitution of Curry-Howard terms for term variables, 4. define the reduction rules for the Curry-Howard terms and 5. outline a proof of the strong normalization for the full system of linear logic using a development of Girard's candidates for reducibility, thereby providing an alternative to Girard's proof using proof-nets.     

以言行事观念下的句法学、语义学和语用学

语力逻辑系统既包括本体层面,与真及成真条件有关,也包括认知层面,与以言行事的语力和行为有关。语力逻辑系统可以通过往标准的逻辑系统中添加施事性算子而得到。通过提供一个联系着以言行事的行为的理性承诺的解释,并且通过形成以旅事性行为为前提和结论的自然演绎的推理系统,这类算子标示了以言行事的语力。本文利用一个简单的处理了断言、否定、假设的语力逻辑系统,证明经过恰当的考虑,对以言行事的语力和理性承诺的研究属于语义学,而不属于语用学。这一论证依赖于这样的事实,即表达式的赋值函项可被同时用于处理语力逻辑系统的本体和认知层面,在这两种情况下,这些函项都为建立恰当性和完全性的结果提供了基础。句法学研究的是表达式的结构,而语义学关心的则是语言使用者的意义,无论这些意义是不是习规上的意义。剩下的第三项研究,即所谓语用学,考察的是语言行为的意义是如何被说话者传达给听者的。     

Natural deduction in connectionist systems

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 natural deduction. 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 natural deduction 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.     

Natural Deduction for Non-Classical Logics

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 natural deduction 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.     

Proof-Theoretic Functional Completeness for the Hybrid Logics of Everywhere and Elsewhere

A hybrid logic is obtained by adding to an ordinary modal logic further expressive power in the form of a second sort of propositional symbols called nominals and by adding so-called satisfaction operators. In this paper we consider hybridized versions of S5 (“the logic of everywhere”) and the modal logic of inequality (“the logic of elsewhere”). We give natural deduction systems for the logics and we prove functional completeness results.     

Logic and contingent existence

It is argued here that Prior's non-standard modal system Q, and the Parry–Dunn system of analytic implication, though entirely independent and independently motivated systems, together provide a rationale for explicating the concept of validity in a non-standard way; their implications are explored for the theory of natural deduction as well as for modal logic and the concept of entailment. I give an account of formal logic from this non-standard viewpoint, together with an informal presentation of the system that unites the insights of Prior (drawing on Russell) and, Parry (drawing on Kant), and the motivations for both in the concept of the contingent existence – as opposed to the contingent truth or falsehood – of a proposition.     

The Harmony of Identity

The standard natural deduction rules for the identity predicate have seemed to some not to be harmonious. Stephen Read has suggested an alternative introduction rule that restores harmony but presupposes second-order logic. Here it will be shown that the standard rules are in fact harmonious. To this end, natural deduction will be enriched with a theory of definitional identity. This leads to a novel conception of canonical derivation, on the basis of which the identity elimination rule can be justified in a proof-theoretical manner.

     

Does the deduction theorem fail for modal logic?

Various sources in the literature claim that the deduction theorem does not hold for normal modal or epistemic logic, whereas others present versions of the deduction theorem for several normal modal systems. It is shown here that the apparent problem arises from an objectionable notion of derivability from assumptions in an axiomatic system. When a traditional Hilbert-type system of axiomatic logic is generalized into a system for derivations from assumptions, the necessitation rule has to be modified in a way that restricts its use to cases in which the premiss does not depend on assumptions. This restriction is entirely analogous to the restriction of the rule of universal generalization of first-order logic. A necessitation rule with this restriction permits a proof of the deduction theorem in its usual formulation. Other suggestions presented in the literature to deal with the problem are reviewed, and the present solution is argued to be preferable to the other alternatives. A contraction- and cut-free sequent calculus equivalent to the Hilbert system for basic modal logic shows the standard failure argument untenable by proving the underivability of ${\square\,A}$ from A.     

Classical harmony: Rules of inference and the meaning of the logical constants

The thesis that, in a system of natural deduction, the meaning of a logical constant is given by some or all of its introduction and elimination rules has been developed recently in the work of Dummett, Prawitz, Tennant, and others, by the addition of harmony constraints. Introduction and elimination rules for a logical constant must be in harmony. By deploying harmony constraints, these authors have arrived at logics no stronger than intuitionist propositional logic. Classical logic, they maintain, cannot be justified from this proof-theoretic perspective. This paper argues that, while classical logic can be formulated so as to satisfy a number of harmony constraints, the meanings of the standard logical constants cannot all be given by their introduction and/or elimination rules; negation, in particular, comes under close scrutiny.     

Establishing Connections between Aristotle's Natural Deduction and First-Order Logic

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 natural deduction syllogistic and ?ukasiewicz'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 natural deduction 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.