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 we argue that hybrid logic is the deductive setting most natural for Kripke semantics. We do so by investigating hybrid axiomatics for a variety of systems, ranging from the basic hybrid language (a decidable system with the same complexity as orthodox propositional modal logic) to the strong Priorean language (which offers full first-order expressivity).We show that hybrid logic offers a genuinely first-order perspective on Kripke semantics: it is possible to define base logics which extend automatically to a (...) wide variety of frame classes and to prove completeness using the Henkin method. In the weaker languages, this requires the use of non-orthodox rules. We discuss these rules in detail and prove non-eliminability and eliminability results. We also show how another type of rule, which reflects the structure of the strong Priorean language, can be employed to give an even wider coverage of frame classes. We show that this deductive apparatus gets progressively simpler as we work our way up the expressivity hierarchy, and conclude the paper by showing that the approach transfers to first-order hybrid logic. (shrink)

The title reflects my conviction that, viewed semantically,modal logic is fundamentally dialogical; this conviction is based on the key role played by the notion of bisimulation in modal model theory. But this dialogical conception of modal logic does not seem to apply to modal proof theory, which is notoriously messy. Nonetheless, by making use of ideas which trace back to Arthur Prior (notably the use of nominals, special proposition symbols which ‘name’ worlds) I will show how to lift the dialogical (...) conception to modal proof theory. I argue that this shift to hybrid logic has consequences for both modal and dialogical logic, and I discuss these in detail. (shrink)

In this paper we discuss whether the relation between formulas in the relating model can be directly introduced into the language of relating logic, and present some stances on that problem. Other questions in the vicinity, such as what kind of functor would be the incorporated relation, or whether the direct incorporation of the relation into the language of relating logic is really needed, will also be addressed.

Natural language provides motivation for studying modal backwards-looking operators such as “now”, “then” and “actually” that evaluate their argument formula at some previously considered point instead of the current one. This paper investigates the expressive power over models of both propositional and first-order basic modal language enriched with such operators. Having defined an appropriate notion of bisimulation for first-order modal logic, I show that backwards-looking operators increase its expressive power quite mildly, contrary to beliefs widespread among philosophers of language and (...) formal semanticists. That in turn presents a strong argument for the use of operator-based systems in the semantics of natural language, instead of systems with explicit quantification over worlds and times that have become a de-facto standard for such applications. The popularity of such explicit-quantification systems is shown to be based on the misinterpretation of a claim by Cresswell, which led many philosophers and linguists to assume that introducing “now” and “then” is expressively equivalent to explicitly quantifying over worlds and times. (shrink)

Quantified hybrid logic is quantified modal logic extended with apparatus for naming states and asserting that a formula is true at a named state. While interpolation and Beth's definability theorem fail in a number of well-known quantified modal logics , their counterparts in quantified hybrid logic have these properties. These are special cases of the main result of the paper: the quantified hybrid logic of any class of frames definable in the bounded fragment of first-order logic has the interpolation property, (...) irrespective of whether varying, constant, expanding, or contracting domains are assumed. (shrink)

This is the first book-length treatment of hybrid logic and its proof-theory. Hybrid logic is an extension of ordinary modal logic which allows explicit reference to individual points in a model. This is useful for many applications, for example when reasoning about time one often wants to formulate a series of statements about what happens at specific times. There is little consensus about proof-theory for ordinary modal logic. Many modal-logical proof systems lack important properties and the relationships between proof systems (...) for different modal logics are often unclear. In the present book we demonstrate that hybrid-logical proof-theory remedies these deficiencies by giving a spectrum of well-behaved proof systems for a spectrum of different hybrid logics. (shrink)

In this note we show that the classical modal technology of Sahlqvist formulas gives quick proofs of the completeness theorems in [8] (D. Gregory, Completeness and decidability results for some propositional modal logics containing "actually" operators, Journal of Philosophical Logic 30(1): 57-78, 2001) and vastly generalizes them. Moreover, as a corollary, interpolation theorems for the logics considered in [8] are obtained. We then compare Gregory's modal language enriched with an "actually" operator with the work of Arthur Prior now known under (...) the name of hybrid logic. This analysis relates the "actually" axioms to standard hybrid axioms, yields the decidability results in [8], and provides a number of complexity results. Finally, we use a bisimulation argument to show that the hybrid language is strictly more expressive than Gregory's language. (shrink)

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

We investigate the expressive power of memory logics. These are modal logics extended with the possibility to store (or remove) the current node of evaluation in (or from) a memory, and to perform membership tests on the current memory. From this perspective, the hybrid logic (↓), for example, can be thought of as a particular case of a memory logic where the memory is an indexed list of elements of the domain.

This paper introduces an axiomatisation for equational hybrid logic based on previous axiomatizations and natural deduction systems for propositional and first-order hybrid logic. Its soundness and completeness is discussed. This work is part of a broader research project on the development a general proof calculus for hybrid logics.

Jean Buridan developed his theory of consequence within a semantical framework compatible with what we now call token-based semantics. In his Treatise on Consequences and Sophismata, Buridan showed...

In this paper, I introduce a quantifier-pluralist theory of time, temporal quantifier relativism. Temporal quantifier relativism includes a restricted quantifier for every instantaneous moment of time. Though it flies in the face of orthodoxy, it compares favorably to rival theories of time. To demonstrate this, I first develop the basic syntax and semantics of temporal quantifier relativism. I then compare the theory to its rivals on three issues: the passage of time, the analysis of change, and temporal ontology.

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)

It is natural to suppose the following three: factivity of knowledge, alda-know synonymy, and the univocity of alda. However, rago-knowledge attribution, expressed by “rago alda” sentences, seems to defeat to hold them at once. In this paper, I try to dissolve this predicament, analyzing “rago alda” sentence as a kind of hybrid language expression. And the theoretical advantages, which my analysis has over other possible, alternative approaches, are to be shown.

This paper deals with structures ${\langle{\bf T}, I\rangle}$ in which T is a tree and I is a function assigning each moment a partition of the set of histories passing through it. The function I is called indistinguishability and generalizes the notion of undividedness. Belnap’s choices are particular indistinguishability functions. Structures ${\langle{\bf T}, I\rangle}$ provide a semantics for a language ${\mathcal{L}}$ with tense and modal operators. The first part of the paper investigates the set-theoretical properties of the set of indistinguishability (...) classes, which has a tree structure. The significant relations between this tree and T are established within a general theory of trees. The aim of second part is testing the expressive power of the language ${\mathcal{L}}$ . The natural environment for this kind of investigations is Belnap’s seeing to it that (stit). It will be proved that the hybrid extension of ${\mathcal{L}}$ (with a simultaneity operator) is suitable for expressing stit concepts in a purely temporal language. (shrink)

In this paper we give axiom systems for classical and intuitionistic hybrid logic. Our axiom systems can be extended with additional rules corresponding to conditions on the accessibility relation expressed by so-called geometric theories. In the classical case other axiomatisations than ours can be found in the literature but in the intuitionistic case no axiomatisations have been published. We consider plain intuitionistic hybrid logic as well as a hybridized version of the constructive and paraconsistent logic N4.

XML documents and, more generally, semistructured data, can be seen as labelled graphs. In this paper we set a correspondence between such graphs and the models of a language of hybrid multimodal logic. This allows us to characterize a schema for semistructured data as a formula of hybrid multimodal logic, and instances of the schema as models of this formula. We also investigate how to express in such a logic integrity constraints on semistructured data, in particular some classes of constraints (...) widely considered in the literature. The contribution of this work is twofold: 1) We generalize the notion of schema, by proposing a definition of schema were references are “well typed”. 2) We formalize semistructured data, schema for semistructured data and integrity constraints in a unique framework, namely hybrid multimodal logic. (shrink)

The Linda paradox is a key topic in current debates on the rationality of human reasoning and its limitations. We present a novel analysis of this paradox, based on the notion of verisimilitude as studied in the philosophy of science. The comparison with an alternative analysis based on probabilistic confirmation suggests how to overcome some problems of our account by introducing an adequately defined notion of verisimilitudinarian confirmation.

The logic of the hide and seek game $$\textbf{LHS}$$ was proposed to capture interactions between agents in pursuit-evasion environments. In this paper, we explore a hybrid extension of $$\textbf{LHS}$$ and show that such an extension is beneficial in several aspects. We will show that it improves the technical properties of the resulting logical system, and expands the potential applications of the system. Specifically, we will investigate the expressive power of the hybrid logic of the hide and seek game $${\mathcal {H}}(\textbf{LHS})$$ (...) and its crucial fragment $${\mathcal {H}}(\textbf{LHS}^{-})$$, at both model and frame levels. We will present complete Hilbert-style proof systems for both the logics $${\mathcal {H}}(\textbf{LHS}^{-})$$ and $${\mathcal {H}}(\textbf{LHS})$$, which in fact provides a solution to a known open problem. (shrink)

Lewis (Noûs 13:455–476, 1979) claimed that branching-time(-like) models can be derived from his sphere models. However, he did not present any specific construction of branching-time(-like) models from his sphere models formally. Meanwhile, Hosokawa (in: Modern logic of modality and its philosophical range: counterfactuals, Gettier problem, and information flow, Tokyo Metropolitan University, 2018) presented a logico-mathematically strict manner in which sphere models can be reconstructed from branching-time models. Subsequently, Hosokawa (J Logic Lang Inf 32:677–706, 2023) presented a proof-theoretically refined version of (...) hybrid tense logic for a certain type of conditionals, which is referred to as hybrid tense logic for temporal conditionals ( $$\textbf{HTL}_{TC}$$ ). In this paper, we interpret a hybrid version $${\textbf{V}}_{\mathcal {HC(@, \downarrow )}}$$ of Lewis’s counterfactual logic $${\textbf{V}}$$ into $$\textbf{HTL}_{TC}$$, and then prove that $$\textbf{HTL}_{TC}$$ is more expressive than $${\textbf{V}}_{\mathcal {HC(@, \downarrow )}}$$ on the class of temporal sphere models, i.e., sphere models derived from a type of branching-time models. (shrink)

Basic hybrid logic extends modal logic with the possibility of naming worlds by means of a distinguished class of atoms (called nominals) and the so-called satisfaction operator, that allows one to state that a given formula holds at the world named a, for some nominal a. Hence, in particular, hybrid formulae include “equality” assertions, stating that two nominals are distinct names for the same world. The treatment of such nominal equalities in proof systems for hybrid logics may induce many redundancies. (...) This paper introduces an internalized tableau system for basic hybrid logic, significantly reducing such redundancies. The calculus enjoys a strong termination property: tableau construction terminates without relying on any specific rule application strategy, and no loop-checking is needed. The treatment of nominal equalities specific of the proposed calculus is briefly compared to other approaches. Its practical advantages are demonstrated by empirical results obtained by use of implemented systems. Finally, it is briefly shown how to extend the calculus to include the global and converse modalities. (shrink)

While classical temporal logics lose track of a state as soon as a temporal operator is applied, several branching-time logics able to repeatedly refer to a state have been introduced in the literature. We study such logics by introducing a new formalism, hybrid branching-time logics, subsuming the other approaches and making the ability to refer to a state more explicit by assigning a name to it. We analyze the expressive power of hybrid branching-time logics and the complexity of their satisfiability (...) problem. As main result, the satisfiability problem for the hybrid versions of several branching-time logics is proved to be 2EXPTIME -complete. To prove the upper bound, the automata-theoretic approach to branching-time logics is extended to hybrid logics. As a result of independent interest, the nonemptiness problem for alternating one-pebble Büchi tree automata is shown to be 2EXPTIME -complete. A common property of the logics studied is that they refer to only one state. This restriction is crucial: The ability to refer to more than one state causes a nonelementary blow-up in complexity. In particular, we prove that satisfiability for NCTL * has nonelementary complexity. (shrink)

A hybrid logic is obtained by adding to an ordinary modal logic further expressive power in the form of a second sort of propositional symbols called nominals and by adding so-called satisfaction operators. In this paper we consider hybridized versions of S5 (“the logic of everywhere”) and the modal logic of inequality (“the logic of elsewhere”). We give natural deduction systems for the logics and we prove functional completeness results.

Like modal logic, temporal logic, and description logic, separation logic has become a popular class of logical formalisms in computer science, conceived as assertion languages for Hoare-style proof systems with the goal to perform automatic program analysis. In a broad sense, separation logic is often understood as a programming language, an assertion language and a family of rules involving Hoare triples. In this survey, we present similarities between separation logic as an assertion language and modal and temporal logics. Moreover, we (...) propose a selection of landmark results about decidability, complexity and expressive power. (shrink)

This paper contains the full code of a prototype implementation in Haskell [5], in ‘literate programming’ style [6], of the tableau-based calculus and proof procedure for hybrid logic presented in [4].

We prove that every first-order formula that is invariant under quasi-injective bisimulations is equivalent to a formula of the hybrid logic . Our proof uses a variation of the usual unravelling technique. We also briefly survey related results, and show in a standard way that it is undecidable whether a first-order formula is invariant under quasi-injective bisimulations.

We show that the bounded fragment of first-order logic and the hybrid language with and operators are equally expressive even with polyadic modalities, but that their fragments are equally expressive only for unary modalities.

In this paper, we show the equivalence between the provability of a proof system of basic hybrid logic and that of translated formulas of the classical predicate logic with equality and explicit substitution by a purely proof–theoretic method. Then we show the equivalence of two groups of proof systems of hybrid logic: the group of labelled deduction systems and the group of modal logic-based systems.

We introduce a general recipe for presenting non-classical logics in a modular and uniform way as labelled deduction systems. Our recipe is based on a labelling mechanism where labels are general entities that are present, in one way or another, in all logics, namely truth-values. More specifically, the main idea underlying our approach is the use of algebras of truth-values, whose operators reflect the semantics we have in mind, as the labelling algebras of our labelled deduction systems. The “truth-values as (...) labels” approach allows us to give generalized systems for multiple-valued logics within the same formalism: since we can take multiple-valued logics as meaning not only finitely or infinitely many-valued logics but also power-set logics, i.e. logics for which the denotation of a formula can be seen as a set of worlds, our recipe allows us to capture also logics such as modal, intuitionistic and relevance logics, thus providing a first step towards the fibring of these logics with many-valued ones. (shrink)

The hybrid logic and the independence friendly modal logic IFML are compared for their expressive powers. We introduce a logic IFML c having a non-standard syntax and a compositional semantics; in terms of this logic a syntactic fragment of IFML is singled out, denoted IFML c . (In the Appendix it is shown that the game-theoretic semantics of IFML c coincides with the compositional semantics of IFML c .) The hybrid logic is proven to be strictly more expressive than IFML (...) c . By contrast, and the full IFML are shown to be incomparable for their expressive powers. Building on earlier research (Tulenheimo and Sevenster 2006), a PSPACE -decidable fragment of the undecidable logic is disclosed. This fragment is not translatable into the hybrid logic and has not been studied previously in connection with hybrid logics. In the Appendix IFML c is shown to lack the property of ‘quasi-positionality’ but proven to enjoy the weaker property of ‘ bounded quasi-positionality’. The latter fact provides from the IFML internal perspective an account of what makes the compositional semantics of IFML c possible. (shrink)

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

In this paper two different natural deduction systems forhybrid logic are compared and contrasted.One of the systems was originally given by the author of the presentpaper whereasthe other system under consideration is a modifiedversion of a natural deductionsystem given by Jerry Seligman.We give translations in both directions between the systems,and moreover, we devise a set of reduction rules forthe latter system bytranslation of already known reduction rules for the former system.

Edited in collaboration with FoLLI, the Association of Logic, Language and Information, this book constitutes the 4th volume of the FoLLI LNAI subline; containing the refereed proceedings of the 15th International Workshop on Logic, Language, Information and Computation, WoLLIC 2008, held in Edinburgh, UK, in July 2008. The 21 revised full papers presented together with the abstracts of 7 tutorials and invited lectures were carefully reviewed and selected from numerous submissions. The papers cover all pertinent subjects in computer science with (...) particular interest in cross-disciplinary topics. Typical areas of interest are: foundations of computing and programming; novel computation models and paradigms; broad notions of proof and belief; formal methods in software and hardware development; logical approach to natural language and reasoning; logics of programs, actions and resources; foundational aspects of information organization, search, flow, sharing, and protection. (shrink)