The structure of derivations in natural deduction is analyzed through isomorphism with a suitable sequent calculus, with twelve hidden convertibilities revealed in usual natural deduction. A general formulation of conjunction and implication elimination rules is given, analogous to disjunction elimination. Normalization through permutative conversions now applies in all cases. Derivations in normal form have all major premisses of elimination rules as assumptions. Conversion in any order terminates.Through the condition that in a cut-free derivation of the sequent Γ⇒C, no inactive weakening (...) or contraction formulas remain in Γ, a correspondence with the formal derivability relation of natural deduction is obtained: All formulas of Γ become open assumptions in natural deduction, through an inductively defined translation. Weakenings are interpreted as vacuous discharges, and contractions as multiple discharges. In the other direction, non-normal derivations translate into derivations with cuts having the cut formula principal either in both premisses or in the right premiss only. (shrink)

The main concern of this paper is the design of a noetherian and confluent normalization for LK 2. The method we present is powerful: since it allows us to recover as fragments formalisms as seemingly different as Girard's LC and Parigot's λμ, FD, delineates other viable systems as well, and gives means to extend the Krivine/Leivant paradigm of `programming-with-proofs' to classical logic ; it is painless: since we reduce strong normalization and confluence to the same properties for linear logic using (...) appropriate embeddings ; it is unifying: it organizes known solutions in a simple pattern that makes apparent the how and why of their making. A comparison of our method to that of embedding LK into LJ brings to the fore the latter's defects for these `deconstructive purposes'. (shrink)

We present a single sequent calculus common to classical, intuitionistic and linear logics. The main novelty is that classical, intuitionistic and linear logics appear as fragments, i.e. as particular classes of formulas and sequents. For instance, a proof of an intuitionistic formula A may use classical or linear lemmas without any restriction: but after cut-elimination the proof of A is wholly intuitionistic, what is superficially achieved by the subformula property and more deeply by a very careful treatment of structural rules. (...) This approach is radically different from the one that consists in “changing the rule of the game” when we want to change logic, e.g. pass from one style of sequent to another: here, there is only one logic, which—depending on its use—may appear classical, intuitionistic or linear. (shrink)

Go back to An-fang, the Peace Square at An-Fang, the Beginning Place at An-Fang, where all things start (… ) An-Fang was near a city, the only living city with a pre-atomic name (… ) The headquarters of the People Programmer was at An-Fang, and there the mistake happened: A ruby trembled. Two tourmaline nets failed to rectify the laser beam. A diamond noted the error. Both the error and the correction went into the general computer. Cordwainer SmithThe Dead Lady (...) of Clown Town, 1964. (shrink)

This paper proposes a synthetic presentation of the proof construction paradigm, which underlies most of the research and development in the so-called “logic programming” area. Two essential aspects of this paradigm are discussed here: true non-determinism and partial information. A new formulation of Focussing, the basic property used to deal with non-determinism in proof construction, is presented. This formulation is then used to introduce a general constraint-based technique capable of dealing with partial information in proof construction. One of the baselines (...) of the paper is to avoid to rely on syntax to describe the key mechanisms of the paradigm. In fact, the bipolar decomposition of formulas captures their main structure, which can then be directly mapped into a sequent system that uses only atoms. This system thus completely “dissolves” the syntax of the formulas and retains only their behavioural content as far as proof construction is concerned. One step further is taken with the so-called “abstract” proofs, which dissolves in a similar way the specific tree-like syntax of the proofs themselves and retains only what is relevant to proof construction. (shrink)

This paper proposes a synthetic presentation of the proof construction paradigm, which underlies most of the research and development in the so-called “logic programming” area. Two essential aspects of this paradigm are discussed here: true non-determinism and partial information. A new formulation of Focussing, the basic property used to deal with non-determinism in proof construction, is presented. This formulation is then used to introduce a general constraint-based technique capable of dealing with partial information in proof construction. One of the baselines (...) of the paper is to avoid to rely on syntax to describe the key mechanisms of the paradigm. In fact, the bipolar decomposition of formulas captures their main structure, which can then be directly mapped into a sequent system that uses only atoms. This system thus completely “dissolves” the syntax of the formulas and retains only their behavioural content as far as proof construction is concerned. One step further is taken with the so-called “abstract” proofs, which dissolves in a similar way the specific tree-like syntax of the proofs themselves and retains only what is relevant to proof construction. (shrink)