We introduce a notion of bisimulation for graded modal logic. Using this notion, the model theory of graded modal logic can be developed in a uniform manner. We illustrate this by establishing the finite model property and proving invariance and definability results.

We extend the languages of both basic and graded modal logic with the infinity diamond, a modality that expresses the existence of infinitely many successors having a certain property. In both cases we define a natural notion of bisimilarity for the resulting formalisms, that we dub $\mathtt {ML}^{\infty }$ and $\mathtt {GML}^{\infty }$, respectively. We then characterise these logics as the bisimulation-invariant fragments of the naturally corresponding predicate logic, viz., the extension of first-order logic with (...) the infinity quantifier. Furthermore, for both $\mathtt {ML}^{\infty }$ and $\mathtt {GML}^{\infty }$ we provide a sound and complete axiomatisation for the set of formulas that are valid in every Kripke frame, we prove a small model property with respect to a widened class of weighted models, and we establish decidability of the satisfiability problem. (shrink)

We introduce a notion of bisimulation for graded modal logic. Using this notion, the model theory of graded modal logic can be developed in a uniform manner. We illustrate this by establishing the finite model property and proving invariance and definability results.

We introduce a class of neighbourhood frames for graded modal logic embedding Kripke frames into neighbourhood frames. This class of neighbourhood frames is shown to be first-order definable but not modally definable. We also obtain a new definition of graded bisimulation with respect to Kripke frames by modifying the definition of monotonic bisimulation.

We prove a completeness theorem for Kmath image, the infinitary extension of the graded version K0 of the minimal normal logic K, allowing conjunctions and disjunctions of countable sets of formulas. This goal is achieved using both the usual tools of the normal logics with graded modalities and the machinery of the predicate infinitary logics in a version adapted to modal logic.

This paper proposes a new model of graded modal judgment. It begins by problematizing the phenomenon: given plausible constraints on the logic of epistemic modality, it is impossible to model graded attitudes toward modal claims as judgments of probability targeting epistemically modal propositions. This paper considers two alternative models, on which modal operators are non-proposition-forming: (1) Moss (2015), in which graded attitudes toward modal claims are represented as judgments of probability targeting (...) a “proxy” proposition, belief in which would underwrite belief in the modal claim. (2) A model on which graded attitudes toward modal claims are represented as judgments of credence taking as their objects (non-propositional) modal representations (rather than proxy propositions). The second model, like Moss’ model, is shown to be semantically and mathematically tractable. The second model, however, can be straightforwardly integrated into a plausible model of the role of graded attitudes toward modal claims in cognition and normative epistemology. (shrink)

In this work we extend results from [4], [3] and [2] about propositional calculi with graded modalities to the predicative level. Our semantic is based on Kripke models with a single domain of interpretation for all the worlds. Therefore the axiomatic system will need a suitable generalization of the Barcan formula. We haven't considered semantics with world-relative domains because they don't present any new difficulties with respect to classical case. Our language will have, as in [1], constant and function (...) symbols, but they will have a rigid interpretation. In this instance the terms will be considered rigid designators, that is, their interpretations will be the same in all possible worlds (cfr. [5]). Nevertheless we will not consider languages with identity: in this way we avoid the problems of identity in modal contexts. On the other hand, we think that in that context would arise essentially the same problems which occur in classical predicative modal logic. Finally we will consider only denumerable languages because the extension to non denumerable ones isn't conceptually problematic. (shrink)

This work intends to be a generalization and a simplification of the techniques employed in [2], by the proposal of a general strategy to prove satisfiability theorems for NLGM-s (= normal logics with graded modalities), analogously to the well known technique of the canonical models by Lemmon and Scott for classical modal logics.

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 prove the canonical models introduced in [D] do not exist for some graded normal logics with symmetric models, namelyKB°, KBD°, KBT°, so that we define a new kind of canonical models, the general ones, and show they exist and work well in every case.

Graphs are among the most frequently used structures in Computer Science. Some of the properties that must be checked in many applications are connectivity, acyclicity and the Eulerian and Hamiltonian properties. In this work, we analyze how we can express these four properties with modal logics. This involves two issues: whether each of the modal languages under consideration has enough expressive power to describe these properties and how complex it is to use these logics to actually test whether (...) a given graph has some desired property. First, we show that these properties are not definable in a basic modal logic or in any bisimulation-invariant extension of it, like the modal μ-calculus. We then show that it is possible to express some of the above properties in a basic hybrid logic. Unfortunately, the Hamiltonian and Eulerian properties still cannot be efficiently checked. In a second attempt, we propose an extension of CTL* with nominals and show that the Hamiltonian property can be more efficiently checked in this logic than in the previous one. In a third attempt, we extend the basic hybrid logic with the ↓ operator and show that we can check the Hamiltonian property with optimal complexity in this logic. Finally, we tackle the Eulerian property in two different ways. First, we develop a generic method to express edge-related properties in hybrid logics and use it to express the Eulerian property. Second, we express a necessary and sufficient condition for the Eulerian property to hold using a graded modal logic. (shrink)

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

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

We prove strong completeness results for some modal logics with the universal modality, with respect to their topological semantics over 0-dimensional dense-in-themselves metric spaces. We also use failure of compactness to show that, for some languages and spaces, no standard modal deductive system is strongly complete.

Possibilistic logic and modal logic are knowledge representation frameworks sharing some common features, such as the duality between possibility and necessity, and the decomposability of necessity for conjunctions, as well as some obvious differences since possibility theory is graded. At the semantic level, possibilistic logic relies on possibility distributions and modal logic on accessibility relations. In the last 30 years, there have been a series of attempts for bridging the two frameworks in one (...) way or another. In this paper, we compare the relational semantics of epistemic logics with simpler possibilistic semantics of a fragment of such logics that only uses modal formulas of depth 1. This minimal epistemic logic handles both all-or-nothing beliefs and explicitly ignored facts. We also contrast epistemic logic with the S5-based rough set logic. Finally, this paper presents extensions of generalized possibilistic logic with objective and non-nested multimodal formulas, in the style of modal logics KD45 and S5. (shrink)

This paper deals with the system of modal logicGL, in particular with a formulation of it in terms of sequents. We prove some proof theoretical properties ofGL that allow to get the cut-elimination theorem according to Gentzen's procedure, that is, by double induction on grade and rank.

The paper presents an infinite hierarchy PR m [ m = 1, 2, . . . ] of sound and complete axiomatic systems for modal logic with graded probabilistic modalities , which are to reflect what I have elsewhere called the Bolding-Ekelöf degrees of evidential strength as applied to the establishment of matters of fact in law-courts. Our present approach is seen to differ from earlier work by the author in that it treats the logic of (...) these graded modalities not only from a semantical or model-theoretic viewpoint but from a prooftheoretical and axiomatic stance as well. A paramount feature of the approach is its use of so-called systematic frame constants as labels of diverse grades of probability. Apart from this novel feature our approach can be seen to go back to pioneering work by Lou Goble in 1970. (shrink)

We present a natural standard translation of inquisitive modal logic $\mathrm{InqML}$ into first-order logic over the natural two-sorted relational representations of the intended models, which captures the built-in higher-order features of $\mathrm{InqML}$. This translation is based on a graded notion of flatness that ties the inherent second-order, team-semantic features of $\mathrm{InqML}$ over information states to subsets or tuples of bounded size. A natural notion of pseudo-models, which relaxes the non-elementary constraints on the intended models, gives rise (...) to an elementary, purely model-theoretic proof of the compactness property for $\mathrm{InqML}$. Moreover, we prove a Hennessy-Milner theorem for $\mathrm{InqML}$, which crucially uses $\omega $ -saturated pseudo-models and the new standard translation. As corollaries we also obtain van Benthem style characterisation theorems. (shrink)

A concept language with role intersection and number restriction is defined and its modal equivalent is provided. The main reasoning tasks of satisfiability and subsumption checking are formulated in terms of modal logic and an algorithm for their solution is provided. An axiomatization for a restricted graded modal language with intersection of modalities (the modal counterpart of the concept language we examine)is given and used in the proposed algorithm.

The paper presents a survey of author's results on definable fixed points in modal, temporal, and intuitionistic propositional logics. The well-known Fixed Point Theorem considers the modalized case, but here we investigate the positive case. We give a classification of fixed point theorems, describe some classes of models with definable least fixed points of positive operators, special positive operators, and give some examples of undefinable least fixed points. Some other interesting phenomena are discovered – definability by formulas that do (...) not preserve positivity of parameters and definability by finite sets of formulas. We also consider negative operators, graded modalities, construct undefinable inflationary fixed points, and put some problems. (shrink)

Biological modalities (e.g., biological possibility, necessity and counterfactuality) play an important explanatory role in biological practice. However, biological modalities lack truth conditions and the inferential relationship between biological and other modalities is unclear. This thesis addresses these problems, first, by improving upon Daniel Dennett's Library of Mendel. Second, a family of modal logics is introduced. In the simplest model, states are interpreted as codons, the binary relation is interpreted as single substitution mutation and the valuation induces a partition of (...) blocks of codons that code for some amino acid. In addition, the proposed framework allows for a grading of biological possibility and captures various competing notions of biological possibility. Applications include a model checker and a lawless Lewis-style semantics for biological counterfactuals. In short, this thesis lays the groundwork for a theory of biological modalities. (shrink)

Reprinted in Quine, W. V. O. 1966. The Ways of Paradox. (New York: Random House.).

Epistemic logic has grown from its philosophical beginnings to find diverse applications in computer science, and as a means of reasoning about the knowledge and belief of agents. This book provides a broad introduction to the subject, along with many exercises and their solutions. The authors begin by presenting the necessary apparatus from mathematics and logic, including Kripke semantics and the well-known modal logics K, T, S4 and S5. Then they turn to applications in the context of (...) distributed systems and artificial intelligence. These include the notions of common knowledge, distributed knowledge, explicit and implicit belief, the interplays between knowledge and time, and knowledge and action, as well as a graded (or numerical) variant of the epistemic operators. The authors also discuss extensively the problem of logical omniscience. They cover Halpern & Moses' theory of honest formulas, and they make a digression into the realm of nonmonotonic reasoning and preferential entailment. They discuss Moore's autoepistemic logic, together with Levesque's related logic of "all I know". Furthermore, they show how one can base default and counterfactual reasoning on epistemic logic. Graduate students in philosophy or in computer science, especially those with an interest in AI, will find this book useful. (shrink)

Filling the need for an accessible, carefully structured introductory text in symbolic logic, Modern Logic has many features designed to improve students' comprehension of the subject, including a proof system that is the same as the award-winning computer program MacLogic, and a special appendix that shows how to use MacLogic as a teaching aid. There are graded exercises at the end of each chapter--more than 900 in all--with selected answers at the end of the book. Unlike competing (...) texts, Modern Logic gives equal weight to semantics and proof theory and explains their relationship, and develops in detail techniques for symbolizing natural language in first-order logic. After a general introduction featuring the notion of logical form, the book offers sections on classical sentential logic, monadic predicate logic, and full first-order logic with identity. A concluding section deals with extensions of and alternatives to classical logic, including modal logic, intuitionistic logic, and fuzzy logic. For students of philosophy, mathematics, computer science, or linguistics, Modern Logic provides a thorough understanding of basic concepts and a sound basis for more advanced work. (shrink)

In this paper a unified framework for dealing with a broad family of propositional multimodal logics is developed. The key tools for presentation of the logics are the notions of closure relation operation and monotonous relation operation. The two classes of logics: FiRe-logics (finitely reducible logics) and LaFiRe-logics (FiRe-logics with local agreement of accessibility relations) are introduced within the proposed framework. Further classes of logics can be handled indirectly by means of suitable translations. It is shown that the logics from (...) these classes have the finite model property with respect to the class of ♦-formulae, i.e. each ♦-formula has a ℒ-model iff it has a finite ℒ-model. Roughly speaking, a ♦-formula is logically equivalent to a formula in negative normal form without occurrences of modal operators with necessity force. In the proof we introduce a substantial modification of Claudio Cerrato's filtration technique that has been originally designed for graded modal logics. The main core of the proof consists in building adequate restrictions of models while preserving the semantics of the operators used to build terms indexing the modal operators. (shrink)

In this paper a unified framework for dealing with a broad family of propositional multimodal logics is developed. The key tools for presentation of the logics are the notions of closure relation operation and monotonous relation operation. The two classes of logics: FiRe-logics (finitely reducible logics) and LaFiRe-logics (FiRe-logics with local agreement of accessibility relations) are introduced within the proposed framework. Further classes of logics can be handled indirectly by means of suitable translations. It is shown that the logics from (...) these classes have the finite model property with respect to the class of -formulae, i.e. each -formula has a -model iff it has a finite -model. Roughly speaking, a -formula is logically equivalent to a formula in negative normal form without occurrences of modal operators with necessity force. In the proof we introduce a substantial modification of Claudio Cerrato's filtration technique that has been originally designed for graded modal logics. The main core of the proof consists in building adequate restrictions of models while preserving the semantics of the operators used to build terms indexing the modal operators. (shrink)

In this paper, we introduce a general technology, calledtaming, for finding well-behaved versions of well-investigated logics. Further, we state completeness, decidability, definability and interpolation results for a multimodal logic, calledarrow logic, with additional operators such as thedifference operator, andgraded modalities. Finally, we give a completeness proof for a strong version of arrow logic.

A sentence of first-order logic is satisfiable if it is true in some structure, and finitely satisfiable if it is true in some finite structure. The question arises as to whether there exists an algorithm for determining whether a given formula of first-order logic is satisfiable, or indeed finitely satisfiable. This question was answered negatively in 1936 by Church and Turing (for satisfiability) and in 1950 by Trakhtenbrot (for finite satisfiability).In contrast, the satisfiability and finite satisfiability problems are (...) algorithmically solvable for restricted subsets---or, as we say, fragments---of first-order logic, a fact which is today of considerable interest in Computer Science. This book provides an up-to-date survey of the principal axes of research, charting the limits of decision in first-order logic and exploring the trade-off between expressive power and complexity of reasoning. Divided into three parts, the book considers for which fragments of first-order logic there is an effective method for determining satisfiability or finite satisfiability. Furthermore, if these problems are decidable for some fragment, what is their computational complexity? Part I focusses on fragments defined by restricting the set of available formulas. Topics covered include the Aristotelian syllogistic and its relatives, the two-variable fragment, the guarded fragment, the quantifier-prefix fragments and the fluted fragment. Part II investigates logics with counting quantifiers. Starting with De Morgan's numerical generalization of the Aristotelian syllogistic, we proceed to the two-variable fragment with counting quantifiers and its guarded subfragment, explaining the applications of the latter to the problem of query answering in structured data. Part III concerns logics characterized by semantic constraints, limiting the available interpretations of certain predicates. Taking propositional modal logic and graded modal logic as our cue, we return to the satisfiability problem for two-variable first-order logic and its relatives, but this time with certain distinguished binary predicates constrained to be interpreted as equivalence relations or transitive relations. The work finishes, slightly breaching the bounds of first-order logic proper, with a chapter on logics interpreted over trees. (shrink)

I propose an account of indicative conditionals that combines features of minimal change semantics and information semantics. As in information semantics, conditionals are interpreted relative to an information state in accordance with the Ramsey test idea: “if p then q” is supported at a state s iff q is supported at the hypothetical state s[p] obtained by restricting s to the p-worlds. However, information states are not modeled as simple sets of worlds, but by means of a Lewisian system of (...) spheres. Worlds in the inner sphere are considered possible; worlds outside of it are ruled out, but to different degrees. In this way, even when a state supports “not p”, it is still possible to suppose p consistently. I argue that this account does better than its predecessors with respect to a set of desiderata concerning inferences with conditionals. In particular, it captures three important facts: that a conditional is logically independent from its antecedent; that a sequence of antecedents behaves like a single conjunctive antecedent ; and that conditionals restrict the quantification domain of epistemic modals. I also discuss two ways to construe the role of a premise, and propose a generalized notion of entailment that keeps the two apart. (shrink)

This landmark work provides a systematic introduction to systems of modal logic and stands as the first presentation of what have become central ideas in philosophy of language and metaphysics, from the "new theory of reference" and non-linguistic necessity and essentialism to "Kripke semantics.".

Arthur Norman Prior (1914-69) was a logician and philosopher from New Zealand who contributed crucially to the development of ‘non-standard’ logics, especially of the modal variety. His greatest achievement was the invention of modern temporal logic, worked out in close connection with modal logic. However, his work in logic had a much broader scope. He was also the founder of hybrid logic, and he made important contributions to deontic logic, modal logic, (...) the theory of quantification, the nature of propositions and the history of logic. In addition, he discussed questions of ethics, free will, and general theology. Prior’s philosophical works comprise about 200 titles. His earliest articles center on philosophical theology and historical studies of Scottish Reformed Theology. This led on to the publication of his first influential work on ethics: Logic and The Basis of Ethics (1949). With the invention of tense-logic in the early 1950s, his focus shifted to investigations into the syntax of tempo-modal logic leading to his seminal Time and Modality (1957), a volume derived from his John Locke Lectures in Oxford in 1956. Furthermore Prior, together with the Irish mathematician and logician C.A. Meredith (1904-76), made important early contributions to the semantics of possible worlds. Prior’s tense-logic provided a strong conceptual framework for problems pertaining to the philosophy of time. In Time and Modality, Prior discussed the philosophical implications of Ruth Barcan’s famous formulae for tense-logic, and in the 1960s he worked on the notion of the present. The most persistent problem running through Prior’s work is his study of the questions surrounding human freedom and divine foreknowledge, and more general philosophical problems emerging from this classical theological question. His thorough analysis of this problem, with the conceptual tools of tense-logic, received a crucial impetus from his correspondence with the young Saul Kripke, when the latter suggested the semantic tool of branching time to Prior. Prior’s development of two solutions based on branching time for the problem of future contingency, the Peircean and the Ockham solution, was most thoroughly developed in Past, Present and Future (1967), the most important work published by Prior. Characteristically for Prior’s methodological approach, the development of these two solutions were at the same time a development of two new systems of tense logic, and vice versa. One of Prior’s significant contributions to logic was his work on world propositions and instant propositions. In the course of developing these notions he also made one of the earliest formulations of hybrid logic. In Papers on Time and Tense (1968), he presented this idea in a more detailed manner in the context of his four grades of tense-logical involvement. (shrink)

We investigate a recently devised polyhedral semantics for intermediate logics, in which formulas are interpreted in n-dimensional polyhedra. An intermediate logic is polyhedrally complete if it is complete with respect to some class of polyhedra. The first main result of this paper is a necessary and sufficient condition for the polyhedral completeness of a logic. This condition, which we call the Nerve Criterion, is expressed in terms of Alexandrov’s notion of the nerve of a poset. It affords a (...) purely combinatorial characterisation of polyhedrally complete logics. Using the Nerve Criterion we show, easily, that there are continuum many intermediate logics that are not polyhedrally complete but which have the finite model property. We also provide, at considerable combinatorial labour, a countably infinite class of logics axiomatised by the Jankov–Fine formulas of ‘starlike trees’ all of which are polyhedrally complete. The polyhedral completeness theorem for these ‘starlike logics’ is the second main result of this paper. (shrink)

A textbook on modal logic, intended for readers already acquainted with the elements of formal logic, containing nearly 500 exercises. Brian F. Chellas provides a systematic introduction to the principal ideas and results in contemporary treatments of modality, including theorems on completeness and decidability. Illustrative chapters focus on deontic logic and conditionality. Modality is a rapidly expanding branch of logic, and familiarity with the subject is now regarded as a necessary part of every philosopher's technical (...) equipment. Chellas here offers an up-to-date and reliable guide essential for the student. (shrink)