Gabriele Pulcini

The paper compares the multiplicative system for classical propositional logic with its fully additive variant. As is well-known, the latter is obtained from the former by absorbing the structural rules through the joint adoption of the generalized axiom and the context-sharing formulation of the logical rules. We show that the very absorption of the structural rules may have the effect of turning into a merely semantic device. We further argue that this, very simple, case-study may be of some interest when considered in the context of the current debate on semantic pollution. As a matter of fact, and are two proof systems that share not only theorems, but also the very syntactic structures they use, though can be collapsed into an appropriate algebraic setting. The subtext to this observation is twofold: (i) to support and further clarify Avron’s notorious position on the topic, and (ii) to point out a language-independent form of semantic pollution that we call ‘deep’.

We present a hypersequent calculus that is sound and complete with respect to the truth-functionally contingent formulas of classical logic. We investigate its structural properties and provide a Gentzen-style cut-elimination procedure. The most notable feature of the calculus is that it jointly satisfies the subformula property and the property of _deductive purity_, to the effect that only contingent hypersequents occur in formal proofs. Moreover, since the negation of a contingent formula is also contingent, the calculus turns out to be _paraconsistent_, and since the conjunction of a formula with its own negation is not contingent, the paraconsistency is of the _non-adjunctive_ kind.

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.

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.

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

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.

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.

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