Nested sequent systems for modal logics are a relatively recent development, within the general area known as deep reasoning. The idea of deep reasoning is to create systems within which one operates at lower levels in formulas than just those involving the main connective or operator. Prefixed tableaus go back to 1972, and are modal tableau systems with extra machinery to represent accessibility in a purely syntactic way. We show that modal nested sequents and prefixed modal tableaus are notational variants (...) of each other, roughly in the same way that tableaus and Gentzen sequent calculi are notational variants. This immediately gives rise to new modal nested sequent systems which may be of independent interest. We discuss some of these, including those for some justification logics that include standard modal operators. (shrink)

We present non-clausal resolution systems for propositional modal logics whose Kripke models do not involve symmetry, and for first order versions whose Kripke models do not involve constant domains. We give systems for K, T , K4 and S4; other logics are also possible. Our systems do not require preliminary reduction to a normal form and, in the first order case, intermingle resolution steps with Skolemization steps.

First - order modal logic is very much under current development, with many different semantics proposed. The use of rigid objects goes back to Saul Kripke. More recently, several semantics based on counterparts have been examined, in a development that goes back to David Lewis. There is yet another line of research, using intensional objects, that traces back to Richard Montague. I have been involved with this line of development for some time. In the present paper, I briefly sketch several (...) of the approaches to first - order modal logic. Then I present one that I call FOIL in the Montague tradition that, I believe, is both expressive and natural. I briefly discuss in what sense it can be made to encompass the other approaches. Finally, I provide tableau rules to go with the FOIL semantics. (shrink)

We propose a natural deduction calculus for the modal logic S4.2. The system is designed to match as much as possible the structure and the properties of the standard system of natural deduction for first-order classical logic, exploiting the formal analogy between modalities and quantifiers. The system is proved sound and complete with respect to (w.r.t.) the standard Hilbert-style formulation of S4.2. Normalization and its consequences are obtained in a natural way, with proofs that closely follow the analogous ones for (...) first-order logic. (shrink)

We present nested sequent systems for propositional Gödel-Dummett logic and its first-order extensions with non-constant and constant domains, built atop nested calculi for intuitionistic logics. To obtain nested systems for these Gödel-Dummett logics, we introduce a new structural rule, called the linearity rule, which (bottom-up) operates by linearising branching structure in a given nested sequent. In addition, an interesting feature of our calculi is the inclusion of reachability rules, which are special logical rules that operate by propagating data and/or checking (...) if data exists along certain paths within a nested sequent. Such rules require us to generalise our nested sequents to include signatures (i.e. finite collections of variables) in the first-order cases, thus giving rise to a generalisation of the usual nested sequent formalism. Our calculi exhibit favourable properties, admitting the height-preserving invertibility of every logical rule and the (height-preserving) admissibility of a large collection of structural and reachability rules. We prove all of our systems sound and cut-free complete, and show that syntactic cut-elimination obtains for the intuitionistic systems. We conclude the paper by discussing possible extensions and modifications, putting forth an array of structural rules that could be used to provide a sizable class of intermediate logics with cut-free nested sequent systems. (shrink)

This paper studies the relationship between labelled and nested calculi for propositional intuitionistic logic, first-order intuitionistic logic with non-constant domains and first-order intuitionistic logic with constant domains. It is shown that Fitting’s nested calculi naturally arise from their corresponding labelled calculi—for each of the aforementioned logics—via the elimination of structural rules in labelled derivations. The translational correspondence between the two types of systems is leveraged to show that the nested calculi inherit proof-theoretic properties from their associated labelled calculi, such as (...) completeness, invertibility of rules and cut admissibility. Since labelled calculi are easily obtained via a logic’s semantics, the method presented in this paper can be seen as one whereby refined versions of labelled calculi (containing nested calculi as fragments) with favourable properties are derived directly from a logic’s semantics. (shrink)

This paper shows how to derive nested calculi from labelled calculi for propositional intuitionistic logic and first-order intuitionistic logic with constant domains, thus connecting the general results for labelled calculi with the more refined formalism of nested sequents. The extraction of nested calculi from labelled calculi obtains via considerations pertaining to the elimination of structural rules in labelled derivations. Each aspect of the extraction process is motivated and detailed, showing that each nested calculus inherits favorable proof-theoretic properties from its associated (...) labelled calculus. (shrink)

In Paradoxa Stoicorum, the Roman philosopher Cicero defends six important Stoic theses. Since these theses seem counterintuitive, and it is not likely that the average person would agree with them, they were generally called "paradoxes". According to the third paradox, (P3), (all) transgressions (wrong actions) are equal and (all) right actions are equal. According to one interpretation of this principle, which I will call (P3′), it means that if it is forbidden that A and it is forbidden that B, then (...) not-A is as good as not-B; and if it is permitted that A and it is permitted that B, then A is as good as B. In this paper, I show how it is possible to prove this thesis in dyadic deontic logic. I also try to defend (P3′) against some philosophical counterarguments. Furthermore, I address the claim that (P3′) is not a correct interpretation of Cicero’s third paradox and the assertion that it does not matter whether (P3′) is true or not. I argue that it does matter whether (P3′) is true or not, but acknowledge that (P3′) is perhaps a slightly different principle than Cicero’s thesis. The upshot is that (P3′) seems to be a plausible principle, and that at least one part of paradox III in Cicero’s Paradoxa Stoicorum appears to be defensible. (shrink)

This is an extended version of the lectures given during the 12-thConference on Applications of Logic in Philosophy and in the Foundationsof Mathematics in Szklarska Poręba. It contains a surveyof modal hybrid logic, one of the branches of contemporary modal logic. Inthe first part a variety of hybrid languages and logics is presented with adiscussion of expressivity matters. The second part is devoted to thoroughexposition of proof methods for hybrid logics. The main point is to showthat application of hybrid logics (...) may remarkably improve the situation inmodal proof theory. (shrink)

The purpose of this paper is to develop a class of semantic tableau systems for some dyadic deontic logics. We will consider 16 different pure dyadic deontic tableau systems and 32 different alethic dyadic deontic tableau systems. Possible world semantics is used to interpret our formal languages. Some relationships between our systems and well known dyadic deontic logics in the literature are pointed out and soundness results are obtained for every tableau system. Completeness results are obtained for all 16 pure (...) dyadic deontic systems and for 16 alethic dyadic deontic systems. (shrink)

The paper settles an open question concerning Negri-style labeled sequent calculi for modal logics and also, indirectly, other proof systems which make (more or less) explicit use of semantic parameters in the syntax and are thus subsumed by labeled calculi, like Brünnler’s deep sequent calculi, Poggiolesi’s tree-hypersequent calculi and Fitting’s prefixed tableau systems. Specifically, the main result we prove (through a semantic argument) is that labeled calculi for the modal logics K and D remain complete w.r.t. valid sequents whose relational (...) part encodes a tree-like structure, when the unique rule which contains an harmful implicit contraction—by which the condition that the premises be less complex than the conclusion is violated—is modified into a contraction-free one respecting the latter condition, thus making the proof-search space finite. (shrink)

This is a thorough treatment of first-order modal logic. The book covers such issues as quantification, equality (including a treatment of Frege's morning star/evening star puzzle), the notion of existence, non-rigid constants and function symbols, predicate abstraction, the distinction between nonexistence and nondesignation, and definite descriptions, borrowing from both Fregean and Russellian paradigms.

Tableau formulations are given for the relevance logics E (Entailment), R (Relevant implication) and RM (Mingle). Proofs of equivalence to modus-ponens-based formulations are vialeft-handed Gentzen sequenzen-kalküle. The tableau formulations depend on a detailed analysis of the structure of tableau rules, leading to certain global requirements. Relevance is caught by the requirement that each node must be used; modality is caught by the requirement that only certain rules can cross a barrier. Open problems are discussed.

An interpolation theorem holds for many standard modal logics, but first order $S5$ is a prominent example of a logic for which it fails. In this paper it is shown that a first order $S5$ interpolation theorem can be proved provided the logic is extended to contain propositional quantifiers. A proper statement of the result involves some subtleties, but this is the essence of it.

We present a syntactical cut-elimination proof for an extended sequent calculus covering the classical modal logics in the \(\mathsf{K}\), \(\mathsf{D}\), \(\mathsf{T}\), \(\mathsf{K4}\), \(\mathsf{D4}\) and \(\mathsf{S4}\) spectrum. We design the systems uniformly since they all share the same set of rules. Different logics are obtained by “tuning” a single parameter, namely a constraint on the applicability of the cut rule and on the (left and right, respectively) rules for \(\Box\) and \(\Diamond\). Starting points for this research are 2-sequents and indexed-based calculi (...) (sequents and tableaux). By extending and modifying existing proposals, we show how to achieve a syntactical proof of the cut-elimination theorem that is as close as possible to the one for first-order classical logic. In doing this, we implicitly show how small is the proof-theoretical distance between classical logic and the systems under consideration. (shrink)

We present two-dimensional tableau systems for the actuality, fixedly, and up-arrow operators. All systems are proved sound and complete with respect to a two-dimensional semantics. In addition, a decision procedure for the actuality logics is discussed.

The purpose of this paper is to develop a class of semantic tableau systems for some counterfactual logics. All in all I will discuss 1024 systems. Possible world semantics is used to interpret our formal languages. Soundness results are obtained for every tableau system and completeness results for a large subclass of these.

This book provides a detailed exposition of one of the most practical and popular methods of proving theorems in logic, called Natural Deduction. It is presented both historically and systematically. Also some combinations with other known proof methods are explored. The initial part of the book deals with Classical Logic, whereas the rest is concerned with systems for several forms of Modal Logics, one of the most important branches of modern logic, which has wide applicability.

In this paper I give conditions under which a matrix characterisation of validity is correct for first order logics where quantifications are restricted by statements from a theory. Unfortunately the usual definition of path closure in a matrix is unsuitable and a less pleasant definition must be used. I derive the matrix theorem from syntactic analysis of a suitable tableau system, but by choosing a tableau system for restricted quantification I generalise Wallen's earlier work on modal logics. The tableau system (...) is only correct if a new condition I call alphabetical monotonicity holds. I sketch how the result can be applied to a wide range of logics such as first order variants of many standard modal logics, including non-serial modal logics. (shrink)

First-order modal logics, as traditionally formulated, are not expressive enough. It is this that is behind the difficulties in formulating a good analog of Herbrand’s Theorem, as well as the well-known problems with equality, non-rigid designators, definite descriptions, and nondesignating terms. We show how all these problems disappear when modal language is made more expressive in a simple, natural way. We present a semantic tableaux system for the enhanced logic, and (very) briefly discuss implementation issues.