Proof Analysis in Modal Logic

A general method for generating contraction- and cut-free sequent calculi for a large family of normal modal logics is presented. The method covers all modal logics characterized by Kripke frames determined by universal or geometric properties and it can be extended to treat also Gödel–Löb provability logic. The calculi provide direct decision methods through terminating proof search. Syntactic proofs of modal undefinability results are obtained in the form of conservativity theorems.     

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.

     

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.     

Gentzen-Type Methods for Bilattice Negation

A general Gentzen-style framework for handling both bilattice (or strong) negation and usual negation is introduced based on the characterization of negation by a modal-like operator. This framework is regarded as an extension, generalization or re- finement of not only bilattice logics and logics with strong negation, but also traditional logics including classical logic LK, classical modal logic S4 and classical linear logic CL. Cut-elimination theorems are proved for a variety of proposed sequent calculi including CLS (a conservative extension of CL) and CLS_cw (a conservative extension of some bilattice logics, LK and S4). Completeness theorems are given for these calculi with respect to phase semantics, for SLK (a conservative extension and fragment of LK and CLS_cw, respectively) with respect to a classical-like semantics, and for SS4 (a conservative extension and fragment of S4 and CLScw, respectively) with respect to a Kripke-type semantics. The proposed framework allows for an embedding of the proposed calculi into LK, S4 and CL.     

On Different Intuitionistic Calculi and Embeddings from Int to S4

In this paper, we compare several cut-free sequent systems for propositional intuitionistic logic Intwith respect to polynomial simulations. Such calculi can be divided into two classes, namely single-succedent calculi (like Gentzen's LJ) and multi-succedent calculi. We show that the latter allow for more compact proofs than the former. Moreover, for some classes of formulae, the same is true if proofs in single-succedent calculi are directed acyclic graphs (dags) instead of trees. Additionally, we investigate the effect of weakening rules on the structure and length of dag proofs.The second topic of this paper is the effect of different embeddings from Int to S4. We select two different embeddings from the literature and show that translated (propositional) intuitionistic formulae have sometimes exponentially shorter minimal proofs in a cut-free Gentzen system for S4than the original formula in a cut-free single-succedent Gentzen system for Int. Moreover, the length and the structure of proofs of translated formulae crucially depend on the chosen embedding.     

Compositional Z: Confluence Proofs for Permutative Conversion

This paper gives new confluence proofs for several lambda calculi with permutation-like reduction, including lambda calculi corresponding to intuitionistic and classical natural deduction with disjunction and permutative conversions, and a lambda calculus with explicit substitutions. For lambda calculi with permutative conversion, naïve parallel reduction technique does not work, and (if we consider untyped terms, and hence we do not use strong normalization) traditional notion of residuals is required as Ando pointed out. This paper shows that the difficulties can be avoided by extending the technique proposed by Dehornoy and van Oostrom, called the Z theorem: existence of a mapping on terms with the Z property concludes the confluence. Since it is still hard to directly define a mapping with the Z property for the lambda calculi with permutative conversions, this paper extends the Z theorem to compositional functions, called compositional Z, and shows that we can adopt it to the calculi.     

A dialogical route to logical pluralism

This paper argues that adopting a particular dialogical account of logical consequence quite directly gives rise to an interesting form of logical pluralism, the form of pluralism in question arising out of the requirement that deductive proofs be explanatory.

     

SAD as a mathematical assistant—how should we go from here to there?

The System for Automated Deduction (SAD) is developed in the framework of the Evidence Algorithm research project and is intended for automated processing of mathematical texts. The SAD system works on three levels of reasoning: (a) the level of text presentation where proofs are written in a formal natural-like language for subsequent verification; (b) the level of foreground reasoning where a particular theorem proving problem is simplified and decomposed; (c) the level of background deduction where exhaustive combinatorial inference search in classical first-order logic is applied to prove end subgoals.

We present an overview of SAD describing the ideas behind the project, the system's design, and the process of problem formalization in the fashion of SAD. We show that the choice of classical first-order logic as the background logic of SAD is not too restrictive. For example, we can handle binders like Σ or lim without resort to second order or to a full-powered set theory. We illustrate our approach with a series of examples, in particular, with the classical problem .     

Coinductive models and normal forms for modal logics (or how we learned to stop worrying and love coinduction)

We present a coinductive definition of models for modal logics and show that it provides a homogeneous framework in which it is possible to include different modal languages ranging from classical modalities to operators from hybrid and memory logics. Moreover, results that had to be proved separately for each different language—but whose proofs were known to be mere routine—now can be proved in a general way. We show, for example, that we can have a unique definition of bisimulation for all these languages, and prove a single invariance-under-bisimulation theorem.We then use the new framework to investigate normal forms for modal logics. The normal form we introduce may have a smaller modal depth than the original formula, and it is inspired by global modalities like the universal modality and the satisfiability operator from hybrid logics. These modalities can be extracted from under the scope of other operators. We provide a general definition of extractable modalities and show how to compute extracted normal forms. As it is the case with other classical normal forms—e.g., the conjunctive normal form of propositional logic—the extracted normal form of a formula can be exponentially bigger than the original formula, if we require the two formulas to be equivalent. If we only require equi-satisfiability, then every modal formula has an extracted normal form which is only polynomially bigger than the original formula, and it can be computed in polynomial time.     

Double-Negation Elimination in Some Propositional Logics

This article answers two questions (posed in the literature), each concerning the guaranteed existence of proofs free of double negation. A proof is free of double negation if none of its deduced steps contains a term of the formn(n(t)) for some term t, where n denotes negation. The first question asks for conditions on the hypotheses that, if satisfied, guarantee the existence of a double-negation-free proof when the conclusion is free of double negation. The second question asks about the existence of an axiom system for classical propositional calculus whose use, for theorems with a conclusion free of double negation, guarantees the existence of a double-negation-free proof. After giving conditions that answer the first question, we answer the second question by focusing on the Lukasiewicz three-axiom system. We then extend our studies to infinite-valued sentential calculus and to intuitionistic logic and generalize the notion of being double-negation free. The double-negation proofs of interest rely exclusively on the inference rule condensed detachment, a rule that combines modus ponens with an appropriately general rule of substitution. The automated reasoning program Otter played an indispensable role in this study.     

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

Marginalia on Sequent Calculi

The paper discusses the relationship between normal natural deductions and cutfree proofs in Gentzen (sequent) calculi in the absence of term labeling. For Gentzen calculi this is the usual version; for natural deduction this is the version under the complete discharge convention, where open assumptions are always discharged as soon as possible. The paper supplements work by Mints, Pinto, Dyckhoff, and Schwichtenberg on the labeled calculi.     

Definability and Interpolation in Non-Classical Logics

Algebraic approach to study of classical and non-classical logical calculi was developed and systematically presented by Helena Rasiowa in [48], [47]. It is very fruitful in investigation of non-classical logics because it makes possible to study large families of logics in an uniform way. In such research one can replace logics with suitable classes of algebras and apply powerful machinery of universal algebra. In this paper we present an overview of results on interpolation and definability in modal and positive logics,and also in extensions of Johansson's minimal logic. All these logics are strongly complete under algebraic semantics. It allows to combine syntactic methods with studying varieties of algebras and to flnd algebraic equivalents for interpolation and related properties. Moreover, we give exhaustive solution to interpolation and some related problems for many families of propositional logics and calculi. This paper is a version of the invited talk given by the author at the conference Trends in Logic III, dedicated to the memory of A. MOSTOWSKI, H. RASIOWA and C. RAUSZER, and held in Warsaw and Ruciane-Nida from 23rd to 25th September 2005. Presented by Jacek Malinowski     

Radical Interpretation and Logical Pluralism

I examine Quine’s and Davidson’s arguments to the effect that classical logic is the one and only correct logic. This conclusion is drawn from their views on radical translation and interpretation, respectively. I focus on the latter, but I first address, independently, Quine’s argument to the effect that the ‘deviant’ logician, who departs from classical logic, is merely changing the subject. Regarding logical pluralism, the question is whether there is more than one correct logic. I argue that bivalence may be subject matter dependent, but that distribution and the law of excluded middle can probably not be dropped whilst maintaining the standard meanings of the connectives. In discussing the ramifications of the indeterminacy of interpretation, I ask whether it forces Davidsonian interpreters to adopt Dummett’s epistemic conception of truth vis-à-vis their interpretations. And, if so, does this cohere with their attributing a nonepistemic notion of truth to their interpretees? This would be a form of logical pluralism. In addition, I discuss Davidson’s arguments against conceptual schemes. Schemes incommensurable with our own could be construed as wholesale deviant logics, or so I argue. And, if so, their possibility would yield, in turn, the possibility of a radical logical pluralism. I also address Davidson’s application of Tarski’s definition of truth.

     

Proof Theory of Paraconsistent Quantum Logic

Paraconsistent quantum logic, a hybrid of minimal quantum logic and paraconsistent four-valued logic, is introduced as Gentzen-type sequent calculi, and the cut-elimination theorems for these calculi are proved. This logic is shown to be decidable through the use of these calculi. A first-order extension of this logic is also shown to be decidable. The relationship between minimal quantum logic and paraconsistent four-valued logic is clarified, and a survey of existing Gentzen-type sequent calculi for these logics and their close relatives is addressed.     

How to think about informal proofs

It is argued in this study that (i) progress in the philosophy of mathematical practice requires a general positive account of informal proof; (ii) the best candidate is to think of informal proofs as arguments that depend on their matter as well as their logical form; (iii) articulating the dependency of informal inferences on their content requires a redefinition of logic as the general study of inferential actions; (iv) it is a decisive advantage of this conception of logic that it accommodates the many mathematical proofs that include actions on objects other than propositions; (v) this conception of logic permits the articulation of project-sized tasks for the philosophy of mathematical practice, thereby supplying a partial characterisation of normal research in the field.     

Paraconsistency in classical logic

Classical propositional logic can be characterized, indirectly, by means of a complementary formal system whose theorems are exactly those formulas that are not classical tautologies, i.e., contradictions and truth-functional contingencies. Since a formula is contingent if and only if its negation is also contingent, the system in question is paraconsistent. Hence classical propositional logic itself admits of a paraconsistent characterization, albeit “in the negative”. More generally, any decidable logic with a syntactically incomplete proof theory allows for a paraconsistent characterization of its set of theorems. This, we note, has important bearing on the very nature of paraconsistency as standardly characterized.