Gentzen-type sequent calculi GBD+, GBDe, GBD1, and GBD2 are respectively introduced for De and Omori’s axiomatic extensions BD+, BDe, BD1, and BD2 of Belnap–Dunn logic by adding classical negation. These calculi are constructed based on a small modification of the original characteristic axiom scheme for negated implication. Theorems for syntactically and semantically embedding these calculi into a Gentzen-type sequent calculus LK for classical logic are proved. The cut-elimination, decidability, and completeness theorems for these (...) calculi are obtained using these embedding theorems. Similar results excluding cut-elimination results are also obtained for alternative Gentzen-type sequent calculi gBD+, gBDe, gBD1, and gBD2 for BD+, BDe, BD1, and BD2, respectively. These alternative calculi are constructed based on the original characteristic axiom scheme for negated implication. (shrink)

In this study, an extended paradefinite logic with classical negation (EPLC), which has the connectives of conflation, paraconsistent negation, classical negation, and classical implication, is introduced as a Gentzen-type sequent calculus. The logic EPLC is regarded as a modification of Arieli, Avron, and Zamansky’s ideal four-valued paradefinite logic (4CC) and as an extension of De and Omori’s extended Belnap–Dunn logic with classical negation (BD+) and Avron’s self-extensional four-valued paradefinite logic (SE4). The completeness, cut-elimination, and decidability theorems (...) for EPLC are proved and EPLC is shown to be embeddable into classical logic. The strong equivalence substitution property and the admissibilities of the rules of negative symmetry, contraposition, and involution are shown for EPLC. Some alternative simple Gentzen-type sequent calculi, which are theorem-equivalent to EPLC, are obtained via these characteristic properties. (shrink)

Gentzen writes in the published version of his doctoral thesis Untersuchungen über das logische Schliessen that he was able to prove the normalization theorem only for intuitionistic natural deduction, but not for classical. To cover the latter, he developed classical sequent calculus and proved a corresponding theorem, the famous cut elimination result. Its proof was organized so that a cut elimination result for an intuitionistic sequent calculus came out as a special case, namely the one (...) in which the sequents have at most one formula in the right, succedent part. Thus, there was no need for a direct proof of normalization for intuitionistic natural deduction. The only traces of such a proof in the published thesis are some convertibilities, such as when an implication introduction is followed by an implication elimination [1934–35, II.5.13]. It remained to Dag Prawitz in 1965 to work out a proof of normalization. Another, less known proof was given also in 1965 by Andres Raggio.We found in February 2005 an early handwritten version of Gentzen's thesis, with exactly the above title, but with rather different contents: Most remarkably, it contains a detailed proof of normalization for what became the standard system of natural deduction. The manuscript is located in the Paul Bernays collection at the ETH-Zurichwith the signum Hs. 974: 271. Bernays must have gotten it well before the time of his being expelled from Göttingen on the basis of the racial laws in April 1933. (shrink)

The variety \ of semi-Heyting algebras was introduced by H. P. Sankappanavar [13] as an abstraction of the variety of Heyting algebras. Semi-Heyting algebras are the algebraic models for a logic HsH, known as semi-intuitionistic logic, which is equivalent to the one defined by a Hilbert style calculus in Cornejo :9–25, 2011) [6]. In this article we introduce a Gentzen style sequent calculus GsH for the semi-intuitionistic logic whose associated logic GsH is the same as HsH. (...) The advantage of this presentation of the logic is that we can prove a cut-elimination theorem for GsH that allows us to prove the decidability of the logic. As a direct consequence, we also obtain the decidability of the equational theory of semi-Heyting algebras. (shrink)

The logic of the weak law of excluded middleKC p is obtained by adding the formula A A as an axiom scheme to Heyting's intuitionistic logicH p . A cut-free sequent calculus for this logic is given. As the consequences of the cut-elimination theorem, we get the decidability of the propositional part of this calculus, its separability, equality of the negationless fragments ofKC p andH p , interpolation theorems and so on. From the proof-theoretical point of view, (...) the formulation presented in this paper makes clearer the relations betweenKC p ,H p , and the classical logic. In the end, an interpretation of classical propositional logic in the propositional part ofKC p is given. (shrink)

The logical formalism of abductive reasoning is still an open discussion and various theories have been presented about it. Abduction is a type of non-monotonic and defeasible reasonings, and the logic containing such a reasoning is one of the types of non-nonmonotonic and defeasible logics, such as inductive logic. Abduction is a kind of natural reasoning and it is a solution to the problems having this form "the phenomenon of φ cannot be explained by the theory of Θ" and (...) we need to search for (or to adduce) an explanation for φ. Taking α as the explanation and <Θ,φ> as the abductive problem, Θ∪{α}⊨φ is the logical format of a strong abductive reasoning. In this article, the proof theory for first-order abductive calculus is proposed based on Gentzen-type first-order proof theory. Considering its dual, i.e., the semantic tableaux, and without the need to translate the formulas, this calculation is sound and complete. After examining the structural rules of this calculus, some metalogical considerations and open problems such as consistency, completeness and undecidability of this account have been addressed. (shrink)

Gentzens natural deduction. Thereby the appearance of the cuts in translation is explained.

This study aims to introduce a modal extension M4CC of Arieli, Avron, and Zamansky's ideal paraconsistent four-valued logic 4CC as a Gentzen-type sequent calculus and prove the Kripke-completeness and cut-elimination theorems for M4CC. The logic M4CC is also shown to be decidable and embeddable into the normal modal logic S4. Furthermore, a subsystem of M4CC, which has some characteristic properties that do not hold for M4CC, is introduced and the Kripke-completeness and cut-elimination theorems for this subsystem (...) are proved. This subsystem is also shown to be decidable and embeddable into S4. (shrink)

A theorem for embedding a first-order linear- time temporal logic LTL into its intuitionistic counterpart ILTL is proved using Baratella-Masini's temporal extension of the Gödel-Gentzen negative translation of classical logic into intuitionistic logic. A substructural counterpart LLTL of ILTL is introduced, and a theorem for embedding ILTL into LLTL is proved using a temporal extension of the Girard translation of intuitionistic logic into intuitionistic linear logic. These embedding theorems are proved syntactically based on Gentzen-type sequent calculi.

In this paper, the positive fragment of the logic math formula of contraction-less relevant implication is extended with the addition of a paraconsistent negation connective similar to the strong negation connective in Nelson's paraconsistent four-valued logic math formula. This extended relevant logic is called math formula, and it has the property of constructible falsity which is known to be a characteristic property of math formula. A Gentzen-type sequent calculus math formula for math formula is introduced, and (...) the cut-elimination and decidability theorems for math formula are proved. Two extended Routley-Meyer semantics are introduced for math formula, and the completeness theorems with respect to these semantics are proved. (shrink)

Gerhard Gentzen has been described as logic’s lost genius, whom Gödel called a better logician than himself. This work comprises articles by leading proof theorists, attesting to Gentzen’s enduring legacy to mathematical logic and beyond. The contributions range from philosophical reflections and re-evaluations of Gentzen’s original consistency proofs to the most recent developments in proof theory. Gentzen founded modern proof theory. His sequent calculus and natural deduction system beautifully explain the deep symmetries of logic. (...) They underlie modern developments in computer science such as automated theorem proving and type theory. (shrink)

The paper is a brief survey of some sequent calculi which do not follow strictly the shape of sequent calculus introduced by Gentzen. We propose the following rough classification of all SC: Systems which are based on some deviations from the ordinary notion of a sequent are called generalised; remaining ones are called ordinary. Among the latter we distinguish three types according to the proportion between the number of primitive sequents and rules. In particular, in (...) one of these types, called Gentzen’s type, we have a subtype of standard SC due to Gentzen. Hence by nonstandard ones we mean all these ordinary SC where other kinds of rules are applied than those admitted in standard Gentzen’s sequent calculi. We describe briefly some of the most interesting or important nonstandard SC belonging to the three abovementioned types. (shrink)

Gentzen writes in the published version of his doctoral thesis Untersuchungen über das logische Schliessen that he was able to prove the normalization theorem only for intuitionistic natural deduction, but not for classical. To cover the latter, he developed classical sequent calculus and proved a corresponding theorem, the famous cut elimination result. Its proof was organized so that a cut elimination result for an intuitionistic sequent calculus came out as a special case, namely the one (...) in which the sequents have at most one formula in the right, succedent part. Thus, there was no need for a direct proof of normalization for intuitionistic natural deduction. The only traces of such a proof in the published thesis are some convertibilities, such as when an implication introduction is followed by an implication elimination [1934–35, II.5.13]. It remained to Dag Prawitz in 1965 to work out a proof of normalization. Another, less known proof was given also in 1965 by Andres Raggio.We found in February 2005 an early handwritten version of Gentzen's thesis, with exactly the above title, but with rather different contents: Most remarkably, it contains a detailed proof of normalization for what became the standard system of natural deduction. The manuscript is located in the Paul Bernays collection at the ETH-Zurichwith the signum Hs. 974: 271. Bernays must have gotten it well before the time of his being expelled from Göttingen on the basis of the racial laws in April 1933. (shrink)

We consider four natural deduction systems: Fitch-style systems, Gentzen-style systems (in the form of dags), general deduction Frege systems and nested deduction Frege systems, as well as dag-like Gentzen-style sequent calculi. All these calculi soundly and completely formalize classical propositional logic. -/- We show that general deduction Frege systems and Gentzen-style natural calculi provide at most quadratic speedup over nested deduction Frege systems and Fitch-style natural calculi and at most cubic speedup over Gentzen-style sequent (...) calculi. (shrink)

We present a sequent calculus of a paraconsistent logic QMPT0, which has the paraconsistent-type excluded middle law (PEML) as an initial sequent. Our system shows that the presence of PEML is essentially important for QMPT0. It also has special rules when the set of constant symbols is finite. We also discuss the cut-elimination property of our system.

The lambdaPi-calculus, a theory of first-order dependent function types in Curry-Howard-de Bruijn correspondence with a fragment of minimal first-order logic, is defined as a system of (linearized) natural deduction. In this paper, we present a Gentzen-style sequent calculus for the lambdaPi-calculus and prove the cut-elimination theorem. The cut-elimination result builds upon the existence of normal forms for the natural deduction system and can be considered to be analogous to a proof provided by Prawitz for first-order (...) logic. The type-theoretic setting considered here elegantly illustrates the distinction between the processes of normalization in a natural deduction system and cut-elimination in a Gentzen-style sequent calculus. (shrink)

The paper contains an exposition of some non standard approach to gentzenization of modal logics. The first section is devoted to short discussion of desirable properties of Gentzen systems and the short review of various sequential systems for modal logics. Two non standard, cut-free sequent systems are then presented, both based on the idea of using special modal sequents, in addition to usual ones. First of them, GSC I is well suited for nonsymmetric modal logics The second one, (...) GSC II is devised specially for symmetric, i.e. Blogics. GSC I and GSC II are not different formalizations, from the theoretical point of view GSC I may be seen as a simplification of the more general approach present in GSC II. They are considered separately, mainly because Blogics demand different, and more complicated, strategy in completeness proof, whereas non symmetric logics are easily and uniformly characterised by means of Fitting's Consistency Properties. The weakest modal logic captured by this formalization is minimal regular logic C, but many stronger logics are obtainable by addition of suitable structural rules, which conforms to Do en's methodology. Both variants of GSC satisfy also other, besides cut-freedom, desirable properties. (shrink)

Gentzen’s approach to deductive systems, and Carnap’s and Popper’s treatment of probability in logic were two fruitful ideas that appeared in logic of the mid-twentieth century. By combining these two concepts, the notion of sentence probability, and the deduction relation formalized in the sequent calculus, we introduce the notion of ’probabilized sequent’ \ with the intended meaning that “the probability of truthfulness of \ belongs to the interval [a, b]”. This method makes it possible to define (...) a system of derivations based on ’axioms’ of the form \, obtained as a result of empirical research, and then infer conclusions of the form \. We discuss the consistency, define the models, and prove the soundness and completeness for the defined probabilized sequent calculus. (shrink)

We prove that every finitely axiomatizable extension of Heyting's intuitionistic logic has a corresponding cut-free Gentzen-type formulation. It is shown how one can use this result to find the corresponding normalizable natural deduction system and to give a criterion for separability of considered logic. Obviously, the question how to obtain an effective definition of a sequent calculus which corresponds to a concrete logic remains a separate problem for every logic.

In advanced books and courses on logic (e.g. Sm], BM]) Gentzen-type systems or their dual, tableaux, are described as techniques for showing validity of formulae which are more practical than the usual Hilbert-type formalisms. People who have learnt these methods often wonder why the Automated Reasoning community seems to ignore them and prefers instead the resolution method. Some of the classical books on AD (such as CL], Lo]) do not mention these methods at all. Others (such as (...) Ro]) do, but the connections and reasons for preference remain unclear after reading them (at least to the present author, and obviously also the authors of OS], in which a theorem-prover, based exclusively on tableaux, is described). The confusion becomes greater when the reader is introduced to Kowalski's form of a clause ( Ko], Bu]), which is nothing but a Gentzen's sequent of atomic formulae, and when he realizes that resolution is just a form of a Cut, and so that while the elimination of cuts is the principal tool in proof-theory, its use is the main technique in AD! (shrink)

We introduce an implication-free fragment image of ω-arithmetic, having Exchange rule for sequents dropped. Exchange rule for formulas is, instead, an admissible rule in image. Our main result is that cut-free proofs of image are isomorphic with recursive winning strategies of a set of games called “1-backtracking games” in [S. Berardi, Th. Coquand, S. Hayashi, Games with 1-backtracking, Games for Logic and Programming Languages, Edinburgh, April 2005].We also show that image is a sound and complete formal system for the implication-free (...) fragment of LCM , Seventh International Conference on Typed Lambda Calculi and Applications, in: Lecture Notes in Computer Science, vol. 3461, 2005, pp. 11–22. Invited paper]). A simple syntactical description of this fragment was still missing. No sound and complete formal system is known for LCM itself. (shrink)

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

The decidability of the logic of pure ticket entailment means that the problem of inhabitation of simple types by combinators over the base { B, B′, I, W } is decidable too. Type-assignment systems are often formulated as natural deduction systems. However, our decision procedure for this logic, which we presented in earlier papers, relies on two sequent calculi and it does not yield directly a combinator for a theorem of ${T_\to}$. Here we describe an algorithm to extract (...) an inhabitant from a sequent calculus proof—without translating the proof into another proof system. (shrink)

We introduce a dual-context style sequent calculus which is complete with respectto Kripke semantics where implication is interpreted as strict implication in the modal logic K. The cut-elimination theorem for this calculus is proved by a variant of Gentzen's method.

The tetravalent modal logic is one of the two logics defined by Font and Rius :481–518, 2000) in connection with Monteiro’s tetravalent modal algebras. These logics are expansions of the well-known Belnap–Dunn’s four-valued logic that combine a many-valued character with a modal character. In fact, $${\mathcal {TML}}$$ TML is the logic that preserves degrees of truth with respect to tetravalent modal algebras. As Font and Rius observed, the connection between the logic $${\mathcal {TML}}$$ TML and the algebras is not so (...) good as in $${{\mathcal {TML}}}^N$$ TML N, but, as a compensation, it has a better proof-theoretic behavior, since it has a strongly adequate Gentzen calculus :481–518, 2000). In this work, we prove that the sequent calculus given by Font and Rius does not enjoy the cut-elimination property. Then, using a general method proposed by Avron et al., we provide a sequent calculus for $${\mathcal {TML}}$$ TML with the cut-elimination property. Finally, inspired by the latter, we present a natural deduction system, sound and complete with respect to the tetravalent modal logic. (shrink)

A new combined temporal logic called synchronized linear-time temporal logic (SLTL) is introduced as a Gentzen-type sequent calculus. SLTL can represent the n -Cartesian product of the set of natural numbers. The cut-elimination and completeness theorems for SLTL are proved. Moreover, a display sequent calculus δ SLTL is defined.

We provide a logical matrix semantics and a Gentzen-style sequent calculus for the first-degree entailments valid in W. T. Parry’s logic of Analytic Implication. We achieve the former by introducing a logical matrix closely related to that inducing paracomplete weak Kleene logic, and the latter by presenting a calculus where the initial sequents and the left and right rules for negation are subject to linguistic constraints.

I present a sequent calculus that extends a nonmonotonic reflexive consequence relation as defined over an atomic first-order language without variables to one defined over a logically complex first-order language. The extension preserves reflexivity, is conservative (therefore nonmonotonic) and supraintuitionistic, and is conducted in a way that lets us codify, within the logically extended object language, important features of the base thus extended. In other words, the logical operators in this calculus play what Brandom (2008) calls expressive (...) roles. Expressivist logical systems have already been proposed for propositional logics (see Hlobil, 2016, and Kaplan, 2018) but not for first-order logics. An advantage of this calculus over standard first-order calculi (e.g., those in Gentzen, 1935/1964) is that universally quantified variables behave as they should even in the presence of arbitrary nonlogical axioms. I claim that because of this robust well-behavedness of variables, this calculus also provides logical inferentialists with a way to understand the meanings of variables in terms of the roles those variables play in a wide range of inferences that is not limited to purely logical ones (e.g, mathematical inferences). (shrink)

Gentzen’s classical sequent calculus has explicit structural rules for contraction and weakening. They can be absorbed by replacing the axiom P,¬P by Γ,P,¬P for any context Γ, and replacing the original disjunction rule with Γ,A,B implies Γ,AB.This paper presents a classical sequent calculus which is also free of contraction and weakening, but more symmetrically: both contraction and weakening are absorbed into conjunction, leaving the axiom rule intact. It uses a blended conjunction rule, combining the standard (...) context-sharing and context-splitting rules: Γ,Δ,A and Γ,Σ,B implies Γ,Δ,Σ,AB. We refer to this system as minimal sequent calculus.We prove a minimality theorem for the propositional fragment : any propositional sequent calculus S is complete if and only if S contains. Thus one can view as a minimal complete core of Gentzen’s. (shrink)

The cut-free Gentzen-type sequent calculus LLK for the logic of likelihood is introduced in the paper. It is proved that the calculus is sound and complete for LL. Using the introduced calculus LLK, a decision procedure for LL is presented.

A first-order temporal non-commutative logic TN[l], which has no structural rules and has some l-bounded linear-time temporal operators, is introduced as a Gentzen-type sequent calculus. The logic TN[l] allows us to provide not only time-dependent, resource-sensitive, ordered, but also hierarchical reasoning. Decidability, cut-elimination and completeness (w.r.t. phase semantics) theorems are shown for TN[l]. An advantage of TN[l] is its decidability, because the standard first-order linear-time temporal logic is undecidable. A correspondence theorem between TN[l] and a resource (...) indexed non-commutative logic RN[l] is also shown. This theorem is intended to state that “time” is regarded as a “resource”. (shrink)

Motivated by semantic inferentialism and logical expressivism proposed by Robert Brandom, in this paper, I submit a nonmonotonic modal relevant sequent calculus equipped with special operators, □ and R. The base level of this calculus consists of two different types of atomic axioms: material and relevant. The material base contains, along with all the flat atomic sequents (e.g., Γ0, p |~0 p), some non-flat, defeasible atomic sequents (e.g., Γ0, p |~0 q); whereas the relevant base consists of (...) the local region of such a material base that is sensitive to relevance. The rules of the calculus uniquely and conservatively extend these two types of nonmonotonic bases into logically complex material/relevant consequence relations and incoherence properties, while preserving Containment in the material base and Reflexivity in the relevant base. The material extension is supra-intuitionistic, whereas the relevant extension is stronger than a logic slightly weaker than R. The relevant extension also avoids the fallacies of relevance. Although the extended material consequence relation is defeasible and insensitive to relevance, it has local regions of indefeasibility and relevance (the latter of which is marked by the relevant extension). The newly introduced operators, □ and R, codify these local regions within the same extended material consequence relation. (shrink)

A first-order dynamic non-commutative logic, which has no structural rules and has some program operators, is introduced as a Gentzen-type sequent calculus. Decidability, cut-elimination and completeness theorems are shown for DN or its fragments. DN is intended to represent not only program-based, resource-sensitive, ordered, sequence-based, but also hierarchical reasoning.

Quasi-Boolean modal algebras are quasi-Boolean algebras with a modal operator satisfying the interaction axiom. Sequential quasi-Boolean modal logics and the relational semantics are introduced. Kripke-completeness for some quasi-Boolean modal logics is shown by the canonical model method. We show that every descriptive persistent quasi-Boolean modal logic is canonical. The finite model property of some quasi-Boolean modal logics is proved. A cut-free Gentzen sequent calculus for the minimal quasi-Boolean logic is developed and we show that it has the (...) Craig interpolation property. (shrink)

Gentzen's “Untersuchungen” [1] gave a translation from natural deduction to sequent calculus with the property that normal derivations may translate into derivations with cuts. Prawitz in [8] gave a translation that instead produced cut-free derivations. It is shown that by writing all elimination rules in the manner of disjunction elimination, with an arbitrary consequence, an isomorphic translation between normal derivations and cut-free derivations is achieved. The standard elimination rules do not permit a full normal form, which explains (...) the cuts in Gentzen's translation. Likewise, it is shown that Prawitz' translation contains an implicit process of cut elimination. (shrink)

The Lambek calculus introduced in Lambek [6] is a strengthening of the type reduction calculus of Ajdukiewicz [1]. We study Associative Lambek Calculus L in Gentzen style axiomatization enriched with a finite set Γ of nonlogical axioms, denoted by L(Γ).It is known that finite axiomatic extensions of Associative Lambek Calculus generate all recursively enumerable languages (see Buszkowski [2]). Then we confine nonlogical axioms to sequents of the form p → q, where p and q (...) are atomic types. For calculus L(Γ) we prove interpolation lemma (modifying the Roorda proof for L [10]) and the binary reduction lemma (using the Pentus method [9] with modification from [3]). In consequence we obtain the weak equivalence of the Context-Free Grammars and grammars based on L(Γ). (shrink)

We explore the consequences, for logical system-building, of taking seriously the aim of having irredundant rules of inference, and a preference for proofs of stronger results over proofs of weaker ones. This leads one to reconsider the structural rules of REFLEXIVITY, THINNING, and CUT. REFLEXIVITY survives in the minimally necessary form $\varphi:\varphi$. Proofs have to get started. CUT is subject to a CUT-elimination theorem, to the effect that one can always make do without applications of CUT. So CUT is redundant, (...) and should not be a rule of the system. CUT-elimination, however, in the context of the usual forms of logical rules, requires the presence, in the system, of THINNING. But THINNING, it turns out, is not really necessary. Provided only that one liberalizes the statement of certain logical rules in an appropriate way, one can make do without CUT or THINNING. From the methodological point of view of this study, the logical rules ought to be framed in this newly liberalized form. These liberalized logical rules determine the system of core logic. Given any intuitionistic Gentzen proof of $\Delta:\varphi$, one can determine from it a Core proof of some subsequent of $\Delta:\varphi$. Given any classical Gentzen proof of $\Delta:\varphi$, one can determine from it a classical Core proof of some subsequent of $\Delta:\varphi$. In both cases the Core proof is of a result at least as strong as that of the Gentzen proof; and the only structural rule used is $\varphi:\varphi$. (shrink)

A modal extension of multilattice logic, called modal multilattice logic, is introduced as a Gentzen-type sequent calculus \. Theorems for embedding \ into a Gentzen-type sequent calculus S4C and vice versa are proved. The cut-elimination theorem for \ is shown. A Kripke semantics for \ is introduced, and the completeness theorem with respect to this semantics is proved. Moreover, the duality principle is proved as a characteristic property of \.

A classical paraconsistent logic, which is regarded as a modified extension of first-degree entailment logic, is introduced as a Gentzen-type sequent calculus. This logic can simulate the classical negation in classical logic by paraconsistent double negation in CP. Theorems for syntactically and semantically embedding CP into a Gentzen-type sequent calculus LK for classical logic and vice versa are proved. The cut-elimination and completeness theorems for CP are also shown using these embedding theorems. (...) Similar results are also obtained for an intuitionistic paraconsistent logic, and several versions of Glivenko and Gödel-Gentzen translation theorems are proved for CP and IP. (shrink)

In this paper, bi-intuitionistic multilattice logic, which is a combination of multilattice logic and the bi-intuitionistic logic also known as Heyting–Brouwer logic, is introduced as a Gentzen-type sequent calculus. A Kripke semantics is developed for this logic, and the completeness theorem with respect to this semantics is proved via theorems for embedding this logic into bi-intuitionistic logic. The logic proposed is an extension of first-degree entailment logic and can be regarded as a bi-intuitionistic variant of the (...) original classical multilattice logic determined by the algebraic structure of multilattices. Similar completeness and embedding results are also shown for another logic called bi-intuitionistic connexive multilattice logic, obtained by replacing the connectives of intuitionistic implication and co-implication with their connexive variants. (shrink)

The logic of Conditional Beliefs has been introduced by Board, Baltag, and Smets to reason about knowledge and revisable beliefs in a multi-agent setting. In this article both the semantics and the proof theory for this logic are studied. First, a natural semantics forCDLis defined in terms of neighbourhood models, a multi-agent generalisation of Lewis’ spheres models, and it is shown that the axiomatization ofCDLis sound and complete with respect to this semantics. Second, it is shown that the neighbourhood semantics (...) is equivalent to the original one defined in terms of plausibility models, by means of a direct correspondence between the two types of models. On the basis of neighbourhood semantics, a labelled sequent calculus forCDLis obtained. The calculus has strong proof-theoretic properties, in particular admissibility of contraction and cut, and it provides a decision procedure for the logic. Furthermore, its semantic completeness is used to obtain a constructive proof of the finite model property of the logic. Finally, it is shown that other doxastic operators can be easily captured within neighbourhood semantics. This fact provides further evidence of the naturalness of neighbourhood semantics for the analysis of epistemic/doxastic notions. (shrink)

The interpretation of implications as rules motivates a different left-introduction schema for implication in the sequent calculus, which is conceptually more basic than the implication-left schema proposed by Gentzen. Corresponding to results obtained for systems with higher-level rules, it enjoys the subformula property and cut elimination in a weak form.

This paper studies intersection and union type assignment for the calculus , a proof-term syntax for Gentzen’s classical sequent calculus, with the aim of defining a type-based semantics, via setting up a system that is closed under conversion. We will start by investigating what the minimal requirements are for a system, for to be complete ; this coincides with System , the notion defined in Dougherty et al. [18]; however, we show that this system (...) is not sound , so our goal cannot be achieved. We will then show that System is also not complete, but can recover from this by presenting System as an extension of and showing that it satisfies completeness; it still lacks soundness. We show how to restrict so that it satisfies soundness as well by limiting the applicability of certain type assignment rules, but only when limiting reduction to call-by-name or call-by-value reduction; in restricting the system this way, we sacrifice completeness. These results when combined show that, with respect to full reduction, it is not possible to define a sound and complete intersection and union type assignment system for. (shrink)