This article presents a new semantics for classical propositional logic. We begin by maximally extending the space of sequent proofs so as to admit proofs for any logical formula; then, we extract the new semantics by focusing on the axiomatic structure of proofs. In particular, the interpretation of a formula is given by the ratio between the number of identity axioms out of the total number of axioms occurring in any of its proofs. The outcome is an informational refinement of (...) traditional Boolean semantics, obtained by breaking the symmetry between tautologies and contradictions. (shrink)

This paper is dedicated to extending and adapting to modal logic the approach of fractional semantics to classical logic. This is a multi-valued semantics governed by pure proof-theoretic considerations, whose truth-values are the rational numbers in the closed interval $[0,1]$. Focusing on the modal logic K, the proposed methodology relies on three key components: bilateral sequent calculus, invertibility of the logical rules, and stability (proof-invariance). We show that our semantic analysis of K affords an informational refinement with respect to the (...) standard Kripkean semantics (a new proof of Dugundji’s theorem is a case in point) and it raises the prospect of a proof-theoretic semantics for modal logic. (shrink)

In Schwichtenberg, Schwichtenberg fine-tuned Tait’s technique so as to provide a simplified version of Gentzen’s original cut-elimination procedure for first-order classical logic. In this note we show that, limited to the case of classical propositional logic, the Tait–Schwichtenberg algorithm allows for a further simplification. The procedure offered here is implemented on Kleene’s sequent system G4. The specific formulation of the logical rules for G4 allows us to provide bounds on the height of cut-free proofs just in terms of the logical (...) complexity of their end-sequent. (shrink)

A complementary system for a given logic is a proof system whose theorems are exactly the formulas that are not valid according to the logic in question. This article is a contribution to the complementary proof theory of classical propositional logic. In particular, we present a complementary proof-net system, $$\textsf{CPN}$$ CPN, that is sound and complete with respect to the set of all classically invalid (one-side) sequents. We also show that cut elimination in $$\textsf{CPN}$$ CPN enjoys strong normalization along with (...) strong confluence (and, hence, uniqueness of normal forms). (shrink)

The aim of this paper is to argue that logic can play an important role in the “toolbox” of molecular biology. We show how biochemical pathways, i.e., transitions from a molecular aggregate to another molecular aggregate, can be viewed as deductive processes. In particular, our logical approach to molecular biology — developed in the form of a natural deduction system — is centered on the notion of Curry-Howard isomorphism, a cornerstone in nineteenth-century proof-theory.

Some real life processes, including molecular ones, are context-sensitive, in the sense that their outcome depends on side conditions that are most of the times difficult, or impossible, to express fully in advance. In this paper, we survey and discuss a logical account of context-sensitiveness in molecular processes, based on a kind of non-classical logic. This account also allows us to revisit the relationship between logic and philosophy of science (and philosophy of biology, in particular).

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. (shrink)

Abductive reasoning involves finding the missing premise of an “unsaturated” deductive inference, thereby selecting a possible _explanans_ for a conclusion based on a set of previously accepted premises. In this paper, we explore abductive reasoning from a structural proof-theory perspective. We present a hybrid sequent calculus for classical propositional logic that uses sequents and antisequents to define a procedure for identifying the set of analytic hypotheses that a rational agent would be expected to select as _explanans_ when presented with an (...) abductive problem. Specifically, we show that this set may not include the deductively minimal hypothesis due to the presence of redundant information. We also establish that the set of all analytic hypotheses exhausts all possible solutions to the given problem. Finally, we propose a deductive criterion for differentiating between the best _explanans_ candidates and other hypotheses. (shrink)

We provide a non-Gentzen, though fully syntactical, cut-elimination algorithm for classical propositional logic. The designed procedure is implemented on $$\textsf{GS4}$$ GS 4, the one-sided version of Kleene’s sequent system $$\textsf{G4}$$ G 4. The algorithm here proposed proves to be more ‘dexterous’ than other, more traditional, Gentzen-style techniques as the size of proofs decreases at each step of reduction. As a corollary result, we show that analyticity always guarantees minimality of the size of $$\textsf{GS4}$$ GS 4 -proofs.

In a recent paper, under the auspices of an unorthodox variety of bilateralism, we introduced a new kind of proof-theoretic semantics for the base modal logic \(\mathbf{K}\), whose values lie in the closed interval \([0,1]\) of rational numbers [14]. In this paper, after clarifying our conception of bilateralism – dubbed “soft bilateralism” – we generalize the fractional method to encompass extensions and weakenings of \(\mathbf{K}\). Specifically, we introduce well-behaved hypersequent calculi for the deontic logic \(\mathbf{D}\) and the non-normal modal logics (...) \(\mathbf{E}\) and \(\mathbf{M}\) and thoroughly investigate their structural properties. (shrink)

Permutative logic is a non-commutative conservative extension of linear logic suggested by some investigations on the topology of linear proofs. In order to syntactically reflect the fundamental topological structure of orientable surfaces with boundary, permutative sequents turn out to be shaped like q-permutations. Relaxation is the relation induced on q-permutations by the two structural rules divide and merge; a decision procedure for relaxation has been already provided by stressing some standard achievements in theory of permutations. In these pages, we provide (...) a parallel procedure in which the problem at issue is approached from the point of view afforded by geometry of 2-manifolds and solved by making specific surfaces interact. (shrink)

This book contains more than 15 essays that explore issues in truth, existence, and explanation. It features cutting-edge research in the philosophy of mathematics and logic. Renowned philosophers, mathematicians, and younger scholars provide an insightful contribution to the lively debate in this interdisciplinary field of inquiry. The essays look at realism vs. anti-realism as well as inflationary vs. deflationary theories of truth. The contributors also consider mathematical fictionalism, structuralism, the nature and role of axioms, constructive existence, and generality. In addition, (...) coverage also looks at the explanatory role of mathematics and the philosophical relevance of mathematical explanation. The book will appeal to a broad mathematical and philosophical audience. It contains work from FilMat, the Italian Network for the Philosophy of Mathematics. These papers collected here were also presented at their second international conference, held at the University of Chieti-Pescara, May 2016. (shrink)

The very fact that the Gödel sentence $$\mathcal {G}$$ is independent of Peano Arithmetic fuels controversy over our access to the truth of $$\mathcal {G}$$. In particular, does the truth of $$\mathcal {G}$$ $$ ) precede the truth of its numerical instances $$\varphi $$, $$\varphi $$, $$\varphi, \ldots $$, as the so-called standard argument induces one to believe? This paper offers a shift in perspective on this old problem. We start by reassessing Michael Dummett’s 1963 argument which seems to speak (...) in favour of the priority of the truth of the numerical instances of $$\mathcal {G}$$ over the truth of $$\mathcal {G}$$ itself. In opposition to some recent criticisms of Dummett’s argument, we argue that the latter is not reducible to the standard one. We then point out its prototypical nature in the sense individuated by Jacques Herbrand. This shift in perspective brings us to the claim that the controversy over the priority between $$\mathcal {G}$$ and its numerical instances endures only because the problem is ultimately ill-posed. An encompassing moral about the epistemological mechanism of prototype proofs is also drawn. (shrink)

We offer a critical overview of two sorts of proof systems that may be said to characterize classical propositional logic indirectly (and non-standardly): refutation systems, which prove sound and complete with respect to classical contradictions, and rejection systems, which prove sound and complete with respect to the larger set of all classical non-tautologies. Systems of the latter sort are especially interesting, as they show that classical propositional logic can be given a paraconsistent characterization. In both cases, we consider Hilbert-style systems (...) as well as Gentzen-style sequent calculi and natural-deduction formalisms. (shrink)