The syntax of hml has, in addition to the boolean operators, a modality hai. Uniform interpolation and sequent calculi in modal logic. Terminating sequent calculi for two intuitionistic modal. Dunn 1973 and an elegant and very general approach called display logic developed by nuel belnap 1982. A sequent calculus and theorem prover for standard. Consequently formulae are given by the grammar a p j. Krishnaswami 1 computer science department carnegie mellon university pittsburgh, usa abstract in this paper, we give a sequent calculus for separation logic. Oct 24, 2019 inspired by recent work on proof theory for modal logic, this paper develops a cutfree labelled sequent calculus obtained by imitating herzbergers limit rule for revision sequences as a clause in a possible world semantics. The book is about gentzen calculi for the main systems of modal logic. Tableaux for intuitionistic logic 186 further study 193 9. Sequent calculi for skeptical reasoning in predicate default. Sequent calculi for normal modal logics can be obtained uniformly from a basic calculus, as has been observed in 23. A cutfreegentzenstylesequentcalculusfor the modal logics5.
Judgemental modal logic, pfenning et al, from 2001 separation logic, reynolds and ohearn modalities as monads, moggi et al, lax logic, mendler et al, from 1990, simpson framework, negri sequent calculus avron hypersequents, dosens higerorder sequents, belnap display calculus, bruennlerstrassburger, poggiolesi and others \nested sequents. This is a graduatelevel text for a first course in propositional modal logic. Starting from an informal introduction, we proceed to a description of the deci. In the first part we introduce and discuss the main philosophical ideas related to proof theory, and we try to identify criteria for distinguishing good sequent calculi. With the help of two completeness theorems, one between the labelled sequent calculus and the corresponding possible world semantics, and one between the axiomatic. Classical modal display logic in the calculus of structures. After presenting the rules making up the system, we consider the structure of these rules from both a pragmatic and \aesthetic viewpoint. Firstly, in our calculus all the structural rules are heightpreserving admissible even the contractionrules, and the logical and modal rules are. In this section we give an axiomatic, or hilbertstyle, formulation of is4. Deep sequent systems for modal logic department of computer.
This book is far from offering a comprehensive presentation of generalized sequent systems for modal logics broadly conceived. Several authors have proposed many sequent calculus for s5, however, each of them presents some di. A sequent calculus for krestricted common sense modal. This paper presents sequent calculi in which proof search is terminating for two intuitionistic modal logics, the intuitionistic versions of the classical modal logics k and kd without a diamond operator.
The sequent calculus for the modal logic d by silvio valentini dep. The modal logic d for deontic is usually presented as the extension of the minimal normal modal logic k by the axiom schema. Pdf a cutfree simple sequent calculus for modal logic s5. So far the calculus of structures has captured essentially those modal logics which can also be captured using the sequent calculus or hypersequents. There are also many extensions of the sequent calculus notably they are labelled sequent calculus see e. Moreover, the sequent calculus for biintuitionistic logic and subsystems. In particular, this is the case for the modal logics s5 of universal kripke frames and bof symmetric kripke frames, biintuitionistic logic 31, 32, as well as several paraconsistent logics 8 see example 5. On a computational interpretation of sequent calculus for. Display logic is a generalised sequent calculus framework due to nuel belnap 3. Epistemic logic, conditional logic, neighbourhood semantics, sequent calculus, decision procedure.
To create another computational model for modal logic s4, in terms of sequent calculus to do this, a sequent calculus and its corresponding calculus for intuitionistic s4 are proposed 1 prooftheoretically based on. In proof theory and mathematical logic, sequent calculus is a family of formal systems sharing a certain style of inference and certain formal properties. Lecture notes andrzej szalas college of economics and computer science, olsztyn, poland and. The search for generalized cutfree sequent calculi for modal logics has produced display calculus 3, hypersequent calculus 2,labelled sequent calculus 10, hybrid logic calculus. Uniform interpolation and sequent calculi in modal logic 5 as is often done implicitly in papers on sequent calculi, we will from now on confuse the metalevel with the objectlevel by omitting overscores and the word \meta, trusting that it will always be clear from the. To the best of our 1this conditional system is related to modal logic t.
Our goal of describing a proof search procedure for natural. Gentzen sequent calculi are established for several intuitionistic modal logics. Countermodels from sequent calculi in multimodal logics. Main differences and relations between sequent calculus. In this logic, to each agent i is associated a knowledge modality k i, so that the. A sequent calculus for a modal logic on finite data trees. Uniform interpolation and sequent calculi in modal logic 5 as is often done implicitly in papers on sequent calculi, we will from now on confuse the metalevel with the objectlevel by omitting overscores and the word \meta, trusting that it will always be clear from the context or does not matter on which level we are. Hypersequent calculi for modal logics prism university of calgary. The first sequent calculi systems, lk and lj, were introduced in 19341935 by gerhard gentzen as a tool for studying natural deduction in firstorder logic in classical and intuitionistic versions, respectively. This thesis surveys and examines hypersequent approaches to the proof theory of modal logics. The propositions without logical connectives are called atomic. Stable model logic programming logic programming is a broad and widely studied sub. The following characteristics are fundamental to all display calculi 15, 14. Cut is eliminable from derivations, we have to change the notion of sequent as follows.
About the open logic project the open logic text is an opensource, collaborative textbook of formal meta logic and formal methods, starting at an intermediate level i. An axiomatic formulation of is4 in this paper we shall only consider propositional is4. We present a sound and complete sequent calculus for this logic, which yields the optimal pspace complexity bound for its validity problem. Gentzen calculi for modal propositional logic springerlink. But traditional sequent calculi lack the modularity inherent in hilbert calculi.
Inspired by recent work on proof theory for modal logic, this paper develops a cutfree labelled sequent calculus obtained by imitating herzbergers limit rule for revision sequences as a clause in a possible world semantics. Classical modal display logic in the calculus of structures and minimal cutfree deep inference calculi for s5. A sequent calculus for a modal logic on finite data trees david baelde, simon lunel, sylvain schmitz to cite this version. We assume the reader to be familiar with the basic notions of sequent calculi cf. There is a sequent calculus for the negationfree fragment of the logic r due to gregory mints 1972 and j. Though aimed at a nonmathematical audience in particular, students of philosophy and computer science, it is rigorous. Gentzen sequent calculi for some intuitionistic modal. It is also called propositional logic, statement logic, sentential calculus, sentential logic, or sometimes zerothorder logic. We assume the reader to be familiar with the basic notions of sequent. A cutfree simple sequent calculus for modal logic s5 halshs. Proof theory for modal logic university of helsinki. It is written from the semantical point of view rather than the more usual proof theoretic approach, and the book covers all. Keywords modal logic s5, proof theory, deep inference, calculus of structures, cutadmissibility.
Pdf we present a sequent calculus for the deontic logic d and prove its main syntactic and semantic properties, i. A modal formula ais provable in s5 if and only if ta is provable in monadic predicate logic. Proof theory of modal logic download ebook pdf, epub. Questions for a proof theory of modal logic proof analysis in modal logic firstorder modal logic completeness for kripke semantics other nonclassical logics does the deduction theorem fail for modal logic. For several standard sequent calculi for classical propositional logic, cpc, a corresponding calculus for intuitionistic propositional logic, ipc, can be obtained by restricting the right side of the sequents to one formula or, depending on the calculus, at most one formula. It deals with propositions which can be true or false and argument flow. Herzbergers limit rule with labelled sequent calculus. Bierman department of computer science, university of warwick. The main concern is display logic, a certain refinement of gentzens sequent calculus developed by nuel d. Relevance logic stanford encyclopedia of philosophy. Terminating sequent calculi for two intuitionistic modal logics. References problems of proof theory in modal logic sara negri university of helsinki workshop on recent trends in proof theory.
About the open logic project the open logic text is an opensource, collaborative textbook of formal metalogic and formal methods, starting at an intermediate level i. A modal sequent calculus for propositional separation logic. Sequent calculus in this chapter we develop the sequent calculus as a formal system for proof search in natural deduction. The twodimensional modal logic of davies and humberstone 3 is an important aid to our understanding the relationship between actuality. Compound propositions are formed by connecting propositions by logical connectives. Graphical calculi for normal modal logics are developed based on a reformulation of the graphical calculus for classical propositional logic. A modal sequent calculus for propositional separation logic neelakantan r. A structure for the logic is just a labelled transition system. A sequent calculus for krestricted common sense modal predicate logic takahiro sawasaki graduate school of letters, hokkaido university sapporo, hokkaido, japan taka. Sequent calculus systems for the modal logic s5 have been widely studied for a long time. Gentzen calculi for modal propositional logic francesca. Keywords nested sequents modal logic cut elimination deep inference mathematics subject classi. The sequent calculus was originally introduced by gentzen gen35, primarily as a technical device for proving consistency of predicate logic. Sequent calculi for skeptical reasoning in predicate.