The <Emphasis Type="Italic">λ</Emphasis>-Calculus and the Unity of Structural Proof Theory

In the context of intuitionistic implicational logic, we achieve a perfect correspondence (technically an isomorphism) between sequent calculus and natural deduction, based on perfect correspondences between left-introduction and elimination, cut and substitution, and cut-elimination and normalisation. This requires an enlarged system of natural deduction that refines von Plato’s calculus. It is a calculus with modus ponens and primitive substitution; it is also a “coercion calculus”, in the sense of Cervesato and Pfenning. Both sequent calculus and natural deduction are presented as typing systems for appropriate extensions of the λ-calculus. The whole difference between the two calculi is reduced to the associativity of applicative terms (sequent calculus = right associative, natural deduction = left associative), and in fact the achieved isomorphism may be described as the mere inversion of that associativity. The novel natural deduction system is a “multiary” calculus, because “applicative terms” may exhibit a list of several arguments. But the combination of “multiarity” and left-associativity seems simply wrong, leading necessarily to non-local reduction rules (reason: normalisation, like cut-elimination, acts at the head of applicative terms, but natural deduction focuses at the tail of such terms). A solution is to extend natural deduction even further to a calculus that unifies sequent calculus and natural deduction, based on the unification of cut and substitution. In the unified calculus, a sequent term behaves like in the sequent calculus, whereas the reduction steps of a natural deduction term are interleaved with explicit steps for bringing heads to focus. A variant of the calculus has the symmetric role of improving sequent calculus in dealing with tail-active permutative conversions.     

Controlled integration of the cut rule into connection tableau calculi

In this paper techniques are developed and compared that increase the inferential power of tableau systems for classical first-order logic. The mechanisms are formulated in the framework of connection tableaux, which is an amalgamation of the connection method and the tableau calculus, and a generalization of model elimination. Since connection tableau calculi are among the weakest proof systems with respect to proof compactness, and the (backward) cut rule is not suitable for the first-order case, we study alternative methods for shortening proofs. The techniques we investigate are the folding-up and the folding-down operations. Folding up represents an efficient way of supporting the basic calculus, which is top-down oriented, with lemmata derived in a bottom-up manner. It is shown that both techniques can also be viewed as controlled integrations of the cut rule. To remedy the additional redundancy imported into tableau proof procedures by the new inference rules, we develop and apply an extension of the regularity condition on tableaux and the mechanism of anti-lemmata which realizes a subsumption concept on tableaux. Using the framework of the theorem prover SETHEO, we have implemented three new proof procedures that overcome the deductive weakness of cut-free tableau systems. Experimental results demonstrate the superiority of the systems with folding up over the cut-free variant and the one with folding down.Work supported by the Deutsche Forschungsgemeinschaft and the Esprit Basic Research Action 6471 Medlar II.     

Regaining cut admissibility in deduction modulo using abstract completion

Deduction modulo is a way to combine computation and deduction in proofs, by applying the inference rules of a deductive system (e.g. natural deduction or sequent calculus) modulo some congruence that we assume here to be presented by a set of rewrite rules. Using deduction modulo is equivalent to proving in a theory corresponding to the rewrite rules, and leads to proofs that are often shorter and more readable. However, cuts may be not admissible anymore.We define a new system, the unfolding sequent calculus, and prove its equivalence with the sequent calculus modulo, especially w.r.t. cut-free proofs. It permits to show that it is even undecidable to know if cuts can be eliminated in the sequent calculus modulo a given rewrite system.Then, to recover the cut admissibility, we propose a procedure to complete the rewrite system such that the sequent calculus modulo the resulting system admits cuts. This is done by generalizing the Knuth–Bendix completion in a non-trivial way, using the framework of abstract canonical systems.These results enlighten the entanglement between computation and deduction, and the power of abstract completion procedures. They also provide an effective way to obtain systems admitting cuts, therefore extending the applicability of deduction modulo in automated theorem proving.     

Connection Tableaux with Lazy Paramodulation

It is well known that the connection refinement of clause tableaux with paramodulation is incomplete (even with weak connections). In this paper, we present a new connection tableau calculus for logic with equality. This calculus is based on a lazy form of paramodulation where parts of the unification step become auxiliary subgoals in a tableau and may be subjected to subsequent paramodulations. Our calculus uses ordering constraints and a certain form of the basicness restriction.     

Accelerating tableaux proofs using compact representations

In this article a modified form of tableau calculus, calledTableau Graph Calculus, is presented for overcoming the well-known inefficiencies of the traditional tableau calculus to a large extent. This calculus is based on a compact representation of analytic tableaux by using graph structures calledtableau graphs. These graphs are obtained from the input formula in linear time and incorporate most of the rule applications of normal tableau calculus during the conversion process. The size of this representation is linear with respect to the length of the input formula and the graph closely resembles the proof tree of tableau calculi thus retaining the naturalness of the proof procedure. As a result of this preprocessing step, tableau graph calculus has only a single rule which is repeatedly applied to obtain a proof. Many optimizations for the applications of this rule, to effectively prune the search space, are presented as well. Brief details of an implemented prover called FAUST, embedded within the higher-order theorem prover called HOL, are also given. Applications of FAUST within a hardware verification context are also sketched.This work has been partly financed by german national grant under the project Automated System Design, SFB No. 358.     

A Sequent Calculus for Subtyping Polymorphic Types

We present two complete systems for polymorphic types with sub- typing. One system is in the style of natural deduction, while another is a Gentzen-style sequent calculus system. We prove several meta- mathematical properties for these systems including cut elimination, subject reduction, coherence, and decidability of type reconstruction. Following the approach by J. Mitchell, the sequents are given a simple semantics using logical relations over applicative structures. The systems are complete with respect to this semantics. The logic which emerges from this paper can be seen as a successor to the original Hilbert style system proposed by J. Mitchell in 1988, and to the “half way” sequent calculus of G. Longo, K. Milsted, and S. Soloviev proposed in 1995.     

Tableau Methods for a Logic with Term Declarations

We study free variable tableau methods for logics with term declarations. We show how to define a substitutivity rule preserving the soundness of the tableaux and we prove that some other attempts lead to unsound systems. Based on this rule, we define a sound and complete free variable tableau system and we show how to restrict its application to close branches by defining a sorted unification calculus.     

Optimal Axiomatizations of Finitely Valued Logics

We investigate the problem of finding optimal axiomatizations for operators and distribution quantifiers in finitely valued first-order logics. We show that the problem can be viewed as the minimization of certain propositional formulas. We outline a general procedure leading to optimized operator and quantifier rules for the sequent calculus, for natural deduction, and for clause formation. The main tools are variants of two-valued and many-valued propositional resolution, as well as a novel rule called combination. In the case of operators and quantifiers based on semilattices, rules with a minimal branching degree can be obtained by instantiating a schema, which can also be used for optimal tableaux with sets-as-signs.     

Craig Interpolation with Clausal First-Order Tableaux

We develop foundations for computing Craig-Lyndon interpolants of two given formulas with first-order theorem provers that construct clausal tableaux. Provers that can be understood in this way include efficient machine-oriented systems based on calculi of two families: goal-oriented such as model elimination and the connection method, and bottom-up such as the hypertableau calculus. We present the first interpolation method for first-order proofs represented by closed tableaux that proceeds in two stages, similar to known interpolation methods for resolution proofs. The first stage is an induction on the tableau structure, which is sufficient to compute propositional interpolants. We show that this can linearly simulate different prominent propositional interpolation methods that operate by an induction on a resolution deduction tree. In the second stage, interpolant lifting, quantified variables that replace certain terms (constants and compound terms) by variables are introduced. We justify the correctness of interpolant lifting (for the case without built-in equality) abstractly on the basis of Herbrand’s theorem and for a different characterization of the formulas to be lifted than in the literature. In addition, we discuss various subtle aspects that are relevant for the investigation and practical realization of first-order interpolation based on clausal tableaux.

     

On the Computational Representation of Classical Logical Connectives

Many programming calculi have been designed to have a Curry-Howard correspondence with a classical logic. We investigate the effect that different choices of logical connective have on such calculi, and the resulting computational content.We identify two connectives 'if-and-only-if' and 'exclusive or' whose computational content is not well known, and whose cut elimination rules are non-trivial to define. In the case of the former, we define a term calculus and show that the computational content of several other connectives can be simulated. We show this is possible even for connectives not logically expressible with 'if-and-only-if'.     

Graded tableaux for Rational Pavelka Logic

In this article, a sound and complete tableau system for Rational Pavelka Logic (RPL) is introduced. Extended formulas are used as the counterpart of the graded formulas. In this calculus, if we want to show that the graded formula (x, r) is tableau provable (in the finite fuzzy theory F, respectively), we develop a tableau for the extended formula [r, x] (for the set of extended formulas {[r, x], [x₁, a₁],…, [x_n, a_n] }, respectively). If this tableau closes we claim that (x, r) is tableau provable (in the fuzzy theory F, respectively). We claim also that x is valid at the degree equal to the l.u.b. that allows the closure of the tableaux. Our tableaux are a first step toward efficient procedures of automated deduction in narrow fuzzy logic with truth constants. © 2005 Wiley Periodicals, Inc. Int J Int Syst 20: 1273–1285, 2005.     

A Framework for Proof Systems

Linear logic can be used as a meta-logic to specify a range of object-level proof systems. In particular, we show that by providing different polarizations within a focused proof system for linear logic, one can account for natural deduction (normal and non-normal), sequent proofs (with and without cut), and tableaux proofs. Armed with just a few, simple variations to the linear logic encodings, more proof systems can be accommodated, including proof system using generalized elimination and generalized introduction rules. In general, most of these proof systems are developed for both classical and intuitionistic logics. By using simple results about linear logic, we can also give simple and modular proofs of the soundness and relative completeness of all the proof systems we consider.     

Using Tableaux to Automate the Lambek and Other Categorial Calculi

We argue that, although labeled deduction can be quite costly in general, the complexity of keeping track of the label constraints built to encode the structure of the proofs does not necessarily render the strategy impractical. The point is illustrated with LLKE, a tableaux system for specification and test of categorial grammars. The paper presents and discusses the application of theorem proving in labeled analytic tableaux to natural language processing (NLP), describes algorithms and rules for tableau generation, introduces a new label-checking strategy, and identifies places where the complexity of the task can be tamed.     

Issues in the Analysis of Proof-Search Strategies in Sequential Presentations of Logics

Many proof search strategies can be expressed as restrictions on the order of application of the rules of the sequent calculus. Properties of these strategies are then shown by permutation arguments, such as showing that a given strategy is complete by transforming an arbitrary proof into one which obeys the strategy. Such analyses involve some very tedious manipulations of proofs, and are potentially overwhelming for humans. In this paper we investigate the development of systematic techniques for the analysis of sequent calculi. We show how a particular specification of inference rules leads to a detailed analysis of permutation properties for these rules, and we also investigate how to detect redundancies in proofs resulting from these rules.     

Superposition-based Equality Handling for Analytic Tableaux

We present a variant of the basic ordered superposition rules to handle equality in an analytic free-variable tableau calculus. We prove completeness of this calculus by an adaptation of the model generation technique commonly used for completeness proofs of superposition in the context of resolution calculi. The calculi and the completeness proof are compared to earlier results of Degtyarev and Voronkov. Some variations and refinements are discussed.     

Eliminability of cut in hypersequent calculi for some modal logics of linear frames

Hypersequent calculi, introduced independently by Pottinger and Avron, provide a powerful generalization of ordinary sequent calculi. In the paper we present a proof of eliminability of cut in hypersequent calculi for three modal logics of linear frames: K4.3, KD4.3 and S4.3. Our cut-free calculus is based on Avron's HC formalization for Gödel–Dummett's logic. The presented proof of eliminability of cut is purely syntactical and based on Ciabattoni, Metcalfe, Montagna's proof of eliminability of cut for hypersequent calculi for some fuzzy logics with modalities.     

A modular and parameterized presentation of pregroup calculus

The concept of pregroup was introduced by Lambek for natural language analysis, with a close link to non-commutative linear logic. We reformulate the pregroup calculus so as to extend it by composition with other logics and calculi. The cut elimination property and the decidability property of the sequent calculus proposed in the article are shown. Properties of composed calculi are also discussed.