Expressivity of Second Order Propositional Modal Logic

We consider second-order propositional modal logic (SOPML), an extension of the basic modal language with propositional quantifiers introduced by Kit Fine in 1970. We determine the precise expressive power of SOPML by giving analogues of the Van Benthem–Rosen theorem and the Goldblatt Thomason theorem. Furthermore, we show that the basic modal language is the bisimulation invariant fragment of SOPML, and we characterize the bounded fragment of first-order logic as being the intersection of first-order logic and SOPML.     

Notes on Logics of Metric Spaces

In [14], we studied the computational behaviour of various first-order and modal languages interpreted in metric or weaker distance spaces. [13] gave an axiomatisation of an expressive and decidable metric logic. The main result of this paper is in showing that the technique of representing metric spaces by means of Kripke frames can be extended to cover the modal (hybrid) language that is expressively complete over metric spaces for the (undecidable) two-variable fragment of first-order logic with binary pred-icates interpreting the metric. The frame conditions needed correspond rather directly with a Boolean modal logic that is, again, of the same expressivity as the two-variable fragment. We use this representation to derive an axiomatisation of the modal hybrid variant of the two-variable fragment, discuss the compactness property in distance logics, and derive some results on (the failure of) interpolation in distance logics of various expressive power. Presented by Melvin Fitting     

走向模型论的模态逻辑

增加特定的基数量词,扩张一阶语言,就可以导致实质性地增强语言的表达能力,这样许多超出一阶逻辑范围的数学概念就能得到处理。由于在模型的层次上基本模态逻辑可以看作一阶逻辑的互模拟不变片断,显然它不能处理这些数学概念。因此,增加说明后继状态类上基数概念的模态词,原则上我们就能以模态的方式处理所有基数。我们把讨论各种模型论逻辑的方式转移到模态方面。     

Toward model-theoretic modal logics

Adding certain cardinality quantifiers into first-order language will give substantially more expressive languages. Thus, many mathematical concepts beyond first-order logic can be handled. Since basic modal logic can be seen as the bisimular invariant fragment of first-order logic on the level of models, it has no ability to handle modally these mathematical concepts beyond first-order logic. By adding modalities regarding the cardinalities of successor states, we can, in principle, investigate modal logics of all cardinalities. Thus ways of exploring model-theoretic logics can be transferred to modal logics.     

First-order Expressivity for S5-models: Modal vs. Two-sorted Languages

Standard models for model predicate logic consist of a Kripke frame whose worlds come equipped with relational structures. Both modal and two-sorted predicate logic are natural languages for speaking about such models. In this paper we compare their expressivity. We determine a fragment of the two-sorted language for which the modal language is expressively complete on S5-models. Decidable criteria for modal definability are presented.     

An application of Rieger-Nishimura formulas to the intuitionistic modal logics

The main results of the paper are the following: For each monadic prepositional formula which is classically true but not intuitionistically so, there is a continuum of intuitionistic monotone modal logics L such that L+ is inconsistent.There exists a consistent intuitionistic monotone modal logic L such that for any formula of the kind mentioned above the logic L+ is inconsistent.There exist at least countably many maximal intuitionistic monotone modal logics.The author appreciates very much referees' suggestions which helped to improve the exposition.     

Interpolation and Definability in Guarded Fragments

The guarded fragment (GF) was introduced by Andréka, van Benthem and Németi as a fragment of first order logic which combines a great expressive power with nice, modal behavior. It consists of relational first order formulas whose quantifiers are relativized by atoms in a certain way. Slightly generalizing the admissible relativizations yields the packed fragment (PF). In this paper we investigate interpolation and definability in these fragments. We first show that the interpolation property of first order logic fails in restriction to GF and PF. However, each of these fragments turns out to have an alternative interpolation property that closely resembles the interpolation property usually studied in modal logic. These results are strong enough to entail the Beth definability property for GF and PF. Even better, every guarded or packed finite variable fragment has the Beth property. For interpolation, we characterize exactly which finite variable fragments of GF and PF enjoy this property.     

Modal Logic,Truth, and the Master Modality

In the paper (Braüner, 2001) we gave a minimal condition for the existence of a homophonic theory of truth for a modal or tense logic. In the present paper we generalise this result to arbitrary modal logics and we also show that a modal logic permits the existence of a homophonic theory of truth if and only if it permits the definition of a so-called master modality. Moreover, we explore a connection between the master modality and hybrid logic: We show that if attention is restricted to bidirectional frames, then the expressive power of the master modality is exactly what is needed to translate the bounded fragment of first-order logic into hybrid logic in a truth preserving way. We believe that this throws new light on Arthur Prior's fourth grade tense logic.     

A general method for proving decidability of intuitionistic modal logics

We generalise the result of [H. Ganzinger, C. Meyer, M. Veanes, The two-variable guarded fragment with transitive relations, in: Proc. 14th IEEE Symposium on Logic in Computer Science, IEEE Computer Society Press, 1999, pp. 24–34] on decidability of the two variable monadic guarded fragment of first order logic with constraints on the guard relations expressible in monadic second order logic. In [H. Ganzinger, C. Meyer, M. Veanes, The two-variable guarded fragment with transitive relations, in: Proc. 14th IEEE Symposium on Logic in Computer Science, IEEE Computer Society Press, 1999, pp. 24–34], such constraints apply to one relation at a time. We modify their proof to obtain decidability for constraints involving several relations. Now we can use this result to prove decidability of multi-modal modal logics where conditions on accessibility relations involve more than one relation. Our main application is intuitionistic modal logic, where the intuitionistic and modal accessibility relations usually interact in a non-trivial way.     

A logic of comparative obligation

Normal systems of modal logic, interpreted as deontic logics, are unsuitable for a logic of conflicting obligations. By using modal operators based on a more complex semantics, however, we can provide for conflicting obligations, as in [9], which is formally similar to a fragment of the logic of ability later given in [2], Having gone that far, we may find it desirable to be able to express and consider claims about the comparative strengths, or degrees of urgency, of the conflicting obligations under which we stand. This paper, building on the formalism of the logic of ability in [2], provides a complete and decidable system for such a language.     

Expressivity of Imperfect Information Logics without Identity

In this article we investigate the family of independence-friendly (IF) logics in the equality-free setting, concentrating on questions related to expressive power. Various natural equality-free fragments of logics in this family translate into existential second-order logic with prenex quantification of function symbols only and with the first-order parts of formulae equality-free. We study this fragment of existential second-order logic. Our principal technical result is that over finite models with a vocabulary consisting of unary relation symbols only, this fragment of second-order logic is weaker in expressive power than first-order logic (with equality). Results about the fragment could turn out useful for example in the study of independence-friendly modal logics. In addition to proving results of a technical nature, we address issues related to a perspective from which IF logic is regarded as a specification framework for games, and also discuss the general significance of understanding fragments of second-order logic in investigations related to non-classical logics.     

On Fork Arrow Logic and its Expressive Power

We compare fork arrow logic, an extension of arrow logic, and its natural first-order counterpart (the correspondence language) and show that both have the same expressive power. Arrow logic is a modal logic for reasoning about arrow structures, its expressive power is limited to a bounded fragment of first-order logic. Fork arrow logic is obtained by adding to arrow logic the fork modality (related to parallelism and synchronization). As a result, fork arrow logic attains the expressive power of its first-order correspondence language, so both can express the same input–output behavior of processes.     

Identical Twins,Deduction Theorems,and Pattern Functions: Exploring the Implicative BCSK Fragment of S5

We recapitulate (Section 1) some basic details of the system of implicative BCSK logic, which has two primitive binary implicational connectives, and which can be viewed as a certain fragment of the modal logic S5. From this modal perspective we review (Section 2) some results according to which the pure sublogic in either of these connectives (i.e., each considered without the other) is an exact replica of the material implication fragment of classical propositional logic. In Sections 3 and 5 we show that for the pure logic of one of these implicational connectives two – in general distinct – consequence relations (global and local) definable in the Kripke semantics for modal logic turn out to coincide, though this is not so for the pure logic of the other connective, and that there is an intimate relation between formulas constructed by means of the former connective and the local consequence relation. (Corollary 5.8. This, as we show in an Appendix, is connected to the fact that the ‘propositional operations’ associated with both of our implicational connectives are close to being what R. Quackenbush has called pattern functions.) Between these discussions Section 4 examines some of the replacement-of-equivalents properties of the two connectives, relative to these consequence relations, and Section 6 closes with some observations about the metaphor of identical twins as applied to such pairs of connectives.     

The first axiomatization of relevant logic

This is a review, with historical and critical comments, of a paper by I. E. Orlov from 1928, which gives the oldest known axiomatization of the implication-negation fragment of the relevant logic R. Orlov's paper also foreshadows the modal translation of systems with an intuitionistic negation into S4-type extensions of systems with a classical, involutive, negation. Orlov introduces the modal postulates of S4 before Becker, Lewis and Gödel. Orlov's work, which seems to be nearly completely ignored, is related to the contemporancous work on the axiomatization of intuitionistic logic.     

Hybrid logic with the difference modality for generalisations of graphs

We discuss recent work generalising the basic hybrid logic with the difference modality to any reasonable notion of transition. This applies equally to both subrelational transitions such as monotone neighbourhood frames or selection function models as well as those with more structure such as Markov chains and alternating temporal frames. We provide a generic canonical cut-free sequent system and a terminating proof-search strategy for the fragment without the difference modality but including the global modality.     

Weak Rejection

Linguistic evidence supports the claim that certain, weak rejections are less specific than assertions. On the basis of this evidence, it has been argued that rejected sentences cannot be premisses and conclusions in inferences. We give examples of inferences with weakly rejected sentences as premisses and conclusions. We then propose a logic of weak rejection which accounts for the relevant phenomena and is motivated by principles of coherence in dialogue. We give a semantics for which this logic is sound and complete, show that it axiomatizes the modal logic KD45 and prove that it still derives classical logic on its asserted fragment. Finally, we defend previous logics of strong rejection as being about the linguistically preferred interpretations of weak rejections.     

模态逻辑典范框架的生成子框架

模态逻辑的典范性由“局部”典范性拼接而成。本文讨论了“局部”典范性问题,即一个模态逻辑的典范框架的什么样的生成子框架是该逻辑的框架。主要的结果是证明了一个逻辑的典范框架的有界宽的生成子框架都是该逻辑的框架,并且典范框架内嵌了所有该逻辑的有穷宽框架。     

IF Modal Logic and Classical Negation

The present paper provides novel results on the model theory of Independence friendly modal logic. We concentrate on its particularly well-behaved fragment that was introduced in Tulenheimo and Sevenster (Advances in Modal Logic, 2006). Here we refer to this fragment as ‘Simple IF modal logic’ (IFML _s ). A model-theoretic criterion is presented which serves to tell when a formula of IFML _s is not equivalent to any formula of basic modal logic (ML). We generalize the notion of bisimulation familiar from ML; the resulting asymmetric simulation concept is used to prove that IFML _s is not closed under complementation. In fact we obtain a much stronger result: the only IFML _s formulas admitting their classical negation to be expressed in IFML _s itself are those whose truth-condition is in fact expressible in ML.     

Vagueness-Adaptive Logic: A Pragmatical Approach to Sorites Paradoxes

Kripke-completeness of every classical modal logic with Sahlqvist formulas is one of the basic general results on completeness of classical modal logics. This paper shows a Sahlqvist theorem for modal logic over the relevant logic Bin terms of Routley-Meyer semantics. It is shown that usual Sahlqvist theorem for classical modal logics can be obtained as a special case of our theorem.     

Complete axiomatizations for XPath fragments

We provide complete axiomatizations for several fragments of Core XPath, the navigational core of XPath 1.0 introduced by Gottlob, Koch and Pichler. A complete axiomatization for a given fragment is a set of equivalences from which every other valid equivalence is derivable; equivalences can be thought of as (undirected) rewrite rules. Specifically, we axiomatize single axis fragments of Core XPath as well as full Core XPath. Our completeness proofs use results and techniques from modal logic.