Natural Deduction for the Sheffer Stroke and Peirce’s Arrow (and any Other Truth-Functional Connective)

Methods available for the axiomatization of arbitrary finite-valued logics can be applied to obtain sound and complete intelim rules for all truth-functional connectives of classical logic including the Sheffer stroke (nand) and Peirce’s arrow (nor). The restriction to a single conclusion in standard systems of natural deduction requires the introduction of additional rules to make the resulting systems complete; these rules are nevertheless still simple and correspond straightforwardly to the classical absurdity rule. Omitting these rules results in systems for intuitionistic versions of the connectives in question.     

Harmonising natural deduction

Prawitz proved a theorem, formalising ‘harmony’ in Natural Deduction 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 natural deduction rules for Classical Logic have been presented.     

The enduring scandal of deduction

Deductive inference is usually regarded as being “tautological” or “analytical”: the information conveyed by the conclusion is contained in the information conveyed by the premises. This idea, however, clashes with the undecidability of first-order logic and with the (likely) intractability of Boolean logic. In this article, we address the problem both from the semantic and the proof-theoretical point of view. We propose a hierarchy of propositional logics that are all tractable (i.e. decidable in polynomial time), although by means of growing computational resources, and converge towards classical propositional logic. The underlying claim is that this hierarchy can be used to represent increasing levels of “depth” or “informativeness” of Boolean reasoning. Special attention is paid to the most basic logic in this hierarchy, the pure “intelim logic”, which satisfies all the requirements of a natural deduction system (allowing both introduction and elimination rules for each logical operator) while admitting of a feasible (quadratic) decision procedure. We argue that this logic is “analytic” in a particularly strict sense, in that it rules out any use of “virtual information”, which is chiefly responsible for the combinatorial explosion of standard classical systems. As a result, analyticity and tractability are reconciled and growing degrees of computational complexity are associated with the depth at which the use of virtual information is allowed.     

Harmony and Autonomy in Classical Logic

Michael Dummett and Dag Prawitz have argued that a constructivist theory of meaning depends on explicating the meaning of logical constants in terms of the theory of valid inference, imposing a constraint of harmony on acceptable connectives. They argue further that classical logic, in particular, classical negation, breaks these constraints, so that classical negation, if a cogent notion at all, has a meaning going beyond what can be exhibited in its inferential use.I argue that Dummett gives a mistaken elaboration of the notion of harmony, an idea stemming from a remark of Gerhard Gentzen"s. The introduction-rules are autonomous if they are taken fully to specify the meaning of the logical constants, and the rules are harmonious if the elimination-rule draws its conclusion from just the grounds stated in the introduction-rule. The key to harmony in classical logic then lies in strengthening the theory of the conditional so that the positive logic contains the full classical theory of the conditional. This is achieved by allowing parametric formulae in the natural deduction proofs, a form of multiple-conclusion logic.     

Some Comments on Ian Rumfitt’s Bilateralism

Ian Rumfitt has proposed systems of bilateral logic for primitive speech acts of assertion and denial, with the purpose of ‘exploring the possibility of specifying the classically intended senses for the connectives in terms of their deductive use’ (Rumfitt Mind109, 781–823 (4): 810f). Rumfitt formalises two systems of bilateral logic and gives two arguments for their classical nature. I assess both arguments and conclude that only one system satisfies the meaning-theoretical requirements Rumfitt imposes in his arguments. I then formalise an intuitionist system of bilateral logic which also meets those requirements. Thus Rumfitt cannot claim that only classical bilateral rules of inference succeed in imparting a coherent sense onto the connectives. My system can be extended to classical logic by adding the intuitionistically unacceptable half of a structural rule Rumfitt uses to codify the relation between assertion and denial. Thus there is a clear sense in which, in the bilateral framework, the difference between classicism and intuitionism is not one of the rules of inference governing negation, but rather one of the relation between assertion and denial.     

A Double Deduction System for Quantum Logic Based On Natural Deduction

The author presents a deduction system for Quantum Logic. This system is a combination of a natural deduction 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 natural deduction part of the system is pure: no algebraic artefact is added. The rules of the system are the rules of Classical Natural Deduction in which is added a control of contexts using the compatibility relation.The author uses his system to prove the following theorem: if propositions of a quantum logical propositional calculus system are mutually compatible, they form a classical subsystem.     

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

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.     

Normalization and excluded middle. I

The usual rule used to obtain natural deduction formulations of classical logic from intuitionistic logic, namely is stronger then necessary, and will give classical logic when added to minimal logic. A rule which is precisely strong enough to give classical logic from intuitionistic logic, and which is thus exactly equivalent to the law of the excluded middle, is It is a special case of a version of Peirce's law: In this paper it is shown how to normalize logics defined using these last two rules. Part I deals with propositional logics and first order predicate logics. Part II will deal with first order arithmetic and second order logics. This research was supported in part by grants EQ1648, EQ2908, and CE 110 of the program Fonds pour la Formation de Chercheurs et l'aide à la Recherche (F.C.A.R.) of the Quèbec Ministry of Education.     

Gentzen-Style Axiomatizations for Some Conservative Extensions of Basic Propositional Logic

We introduce two Gentzen-style sequent calculus axiomatizations for conservative extensions of basic propositional logic. Our first axiomatization is an ipmrovement of, in the sense that it has a kind of the subformula property and is a slight modification of. In this system the cut rule is eliminated. The second axiomatization is a classical conservative extension of basic propositional logic. Using these axiomatizations, we prove interpolation theorems for basic propositional logic.     

Cn-Definitions of Propositional Connectives

We attempt to define the classical propositional logic by use of appropriate derivability conditions called Cn-definitions. The conditions characterize basic properties of propositional connectives.     

基于广义谢弗竖的分析性模态公理系统

沿着安德森等人开创的方向,我们将分析性公理系统从经典逻辑推向模态逻辑,所定义的广义谢弗竖混合了模态词和广义析舍。在这篇论文中,我们给出常见的正规模态逻辑的分析性公理系统及其强完全性定理和插值定理,并讨论演绎关系的性质：单调性和切割性。     

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.     

On The Computational Consequences of Independence in Propositional Logic

Sandu and Pietarinen [Partiality and Games: Propositional Logic. Logic J. IGPL 9 (2001) 101] study independence friendly propositional logics. That is, traditional propositional logic extended by means of syntax that allow connectives to be independent of each other, although the one may be subordinate to the other. Sandu and Pietarinen observe that the IF propositional logics have exotic properties, like functional completeness for three-valued functions. In this paper we focus on one of their IF propositional logics and study its properties, by means of notions from computational complexity. This approach enables us to compare propositional logic before and after the IF make-over. We observe that all but one of the best-known decision problems experience a complexity jump, provided that the complexity classes at hand are not equal. Our results concern every discipline that incorporates some notion of independence such as computer science, natural language semantics, and game theory. A corollary of one of our theorems illustrates this claim with respect to the latter discipline.     

SLAP: Specification logic of actions with probability

A logic for specifying probabilistic transition systems is presented. Our perspective is that of agents performing actions. A procedure for deciding whether sentences in this logic are valid is provided. One of the main contributions of the paper is the formulation of the decision procedure: a tableau system which appeals to solving systems of linear equations. The tableau rules eliminate propositional connectives, then, for all open branches of the tableau tree, systems of linear equations are generated and checked for feasibility. Proofs of soundness, completeness and termination of the decision procedure are provided.     

Identical Twins,Deduction Theorems,and Pattern Functions: Exploring the Implicative BCSK Fragment of S5

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.     

Translations Between Gentzen–Prawitz and Jaśkowski–Fitch Natural Deduction Proofs

Two common forms of natural deduction proof systems are found in the Gentzen–Prawitz and Ja?kowski–Fitch systems. In this paper, I provide translations between proofs in these systems, pointing out the ways in which the translations highlight the structural rules implicit in the systems. These translations work for classical, intuitionistic, and minimal logic. I then provide translations for classical S4 proofs.

     

Categorical Abstract Algebraic Logic: Behavioral π-Institutions

Recently, Caleiro, Gon¸calves and Martins introduced the notion of behaviorally algebraizable logic. The main idea behind their work is to replace, in the traditional theory of algebraizability of Blok and Pigozzi, unsorted equational logic with multi-sorted behavioral logic. The new notion accommodates logics over many-sorted languages and with non-truth-functional connectives. Moreover, it treats logics that are not algebraizable in the traditional sense while, at the same time, shedding new light to the equivalent algebraic semantics of logics that are algebraizable according to the original theory. In this paper, the notion of an abstract multi-sorted π-institution is introduced so as to transfer elements of the theory of behavioral algebraizability to the categorical setting. Institutions formalize a wider variety of logics than deductive systems, including logics involving multiple signatures and quantifiers. The framework developed has the same relation to behavioral algebraizability as the classical categorical abstract algebraic logic framework has to the original theory of algebraizability of Blok and Pigozzi.     

A New–old Characterisation of Logical Knowledge

We seek means of distinguishing logical knowledge from other kinds of knowledge, especially mathematics. The attempt is restricted to classical two-valued logic and assumes that the basic notion in logic is the proposition. First, we explain the distinction between the parts and the moments of a whole, and theories of ‘sortal terms’, two theories that will feature prominently. Second, we propose that logic comprises four ‘momental sectors’: the propositional and the functional calculi, the calculus of asserted propositions, and rules for (in)valid deduction, inference or substitution. Third, we elaborate on two neglected features of logic: the various modes of negating some part(s) of a proposition R, not only its ‘external’ negation not-R; and the assertion of R in the pair of propositions ‘it is (un)true that R’ belonging to the neglected logic of asserted propositions, which is usually left unstated. We also address the overlooked task of testing the asserted truth-value of R. Fourth, we locate logic among other foundational studies: set theory and other theories of collections, metamathematics, axiomatisation, definitions, model theory, and abstract and operator algebras. Fifth, we test this characterisation in two important contexts: the formulation of some logical paradoxes, especially the propositional ones; and indirect proof-methods, especially that by contradiction. The outcomes differ for asserted propositions from those for unasserted ones. Finally, we reflect upon self-referring self-reference, and on the relationships between logical and mathematical knowledge. A subject index is appended.     

On A Neglected Path to Intuitionism

According to Quine, in any disagreement over basic logical laws the contesting parties must mean different things by the connectives or quantifiers implicated in those laws; when a deviant logician ‘tries to deny the doctrine he only changes the subject’. The standard (Heyting) semantics for intuitionism offers some confirmation for this thesis, for it represents an intuitionist as attaching quite different senses to the connectives than does a classical logician. All the same, I think Quine was wrong, even about the dispute between classicists and intuitionists. I argue for this by presenting an account of consequence, and a cognate semantic theory for the language of the propositional calculus, which (a) respects the meanings of the connectives as embodied in the familiar classical truth-tables, (b) does not presuppose Bivalence, and with respect to which (c) the rules of the intuitionist propositional calculus are sound and complete. Thus the disagreement between classicists and intuitionists, at least, need not stem from their attaching different senses to the connectives; one may deny the doctrine without changing the subject. The basic notion of my semantic theory is truth at a possibility, where a possibility is a way that (some) things might be, but which differs from a possible world in that the way in question need not be fully specific or determinate. I compare my approach with a previous theory of truth at a possibility due to Lloyd Humberstone, and with a previous attempt to refute Quine’s thesis due to John McDowell.