Search

We construct four binary consequence systems axiomatizing entailment relations between formulas of classical, intuitionistic, dual-intuitionistic and modal (S4) logics, respectively. It is shown that the intuitionistic consequence system is embeddable in the modal (S4) one by the usual modal translation prefixing □ to every subformula of the translated formula. An analogous modal translation of dual-intuitionistic formulas then consists of prefixing ◊ to every subformula of the translated formula. The philosophical importance of this result is briefly discussed.

We present a version of separation logic for modular reasoning about concurrent programs with dynamically allocated storable locks and dynamic thread creation. The assertions of the program logic are modelled by a Kripke model over a recursively de. ned set of worlds and the program logic is proved sound through a Kripke relation to the standard operational semantics. This constitutes an elegant solution to the circularity issue arising from lock resource invariants depending on worlds containing lock resource invariants.

Order-sorted logic is a useful tool for knowledge representation and reasoning because it enables representation of sorted terms and formulas along with partially ordered sorts (called sort-hierarchy). However, this logic cannot represent more complex sorted expressions when they are true in any possible world (as rigid) or some possible worlds (as modality) such as time, space, belief, or situation. In this study, we extend order-sorted logic by introducing existential rigidity and many modalities. In the extended logic, sorted modal formulas are interpreted over the Cartesian product of sets of possible worlds. We present a new labeled tableau calculus to check the (un)satisfiability and validity of sorted modal formulas.

Previous work has introduced the setting of Logic Labelled Transition Systems, called Logic LTS or LLTS for short, together with a variant of ready simulation as its fully-abstract refinement preorder, which allows one to compose operational specifications using a CSP-style parallel operator and the propositional connectives conjunction and disjunction. In this article, we show how a temporal logic for specifying safety properties may be embedded into LLTS so that (a) the temporal operators are compositional for ready simulation; (b) ready simulation, when restricted to pairs of processes and formulas, coincides with the logic’s satisfaction relation; (c) ready simulation, when restricted to formulas, is entailment. The utility of this setting as a semantic foundation for mixed operational and temporal-logic specification languages is demonstrated by means of a simple example. We also adopt the concept of may- and must-transitions from modal transition systems for notational convenience, and investigate the relation between modal refinement on modal transition systems and ready simulation on LLTS.

The γ/em>-admissibility is one of the most important problems in the realm of relevant logics. To prove the γ-admissibility, either the method of normal models or the method using metavaluations may be employed. The γ-admissibility of a wide class of relevant modal logics has been discussed in Part I based on a former method, but the γ-admissibility based on metavaluations has not hitherto been fully considered. Sahlqvist axioms are well known as a means of expressing generalized forms of formulas with modal operators. This paper shows that γ is admissible for relevant modal logics with restricted Sahlqvist axioms in terms of the method using metavaluations.

In this paper, I will show how multi-valued logics are used for model checking. Model checking is an automatic technique to analyze correctness of hardware and software systems. A model checker is based on a temporal logic or a modal fixed point logic. That is to say, a system to be checked is formalized as a Kripke model, a property to be satisfied by the system is formalized as a temporal formula or a modal formula, and the model checker checks that the Kripke model satisfies the formula. Although most existing model checkers are based on 2-valued logics, recently new attempts have been made to extend the underlying logics of model checkers to multi-valued logics. I will summarize these new results.

We give an exponential lower bound on number of proof-lines in the proof system K of modal logic, i.e., we give an example of K-tautologies ψ1, ψ2, … s.t. every K-proof of ψi must have a number of proof-lines exponential in terms of the size of ψi. The result extends, for the same sequence of K-tautologies, to the systems K4, Gödel–Löb's logic, S andS4. We also determine some speed-up relations between different systems of modal logic on formulas of modal-depth one.

In this paper, the constrained epistemic default logic and action model logic was combined to model the dynamic cognitive update process by introducing a cognitive operator. The description of the logic framework was given in this study, and the related theorems were proved to show the interpretation of the constrained epistemic action model logic. As constrained epistemic default logic restricts the current possible epistemic state and action model logic can describe epistemic actions, the new proposed logic can better portray the cognitive operations and the restriction of the corresponding accessibility relations.

We establish a generic upper bound \(\textsc {ExpTime} \) for reasoning with global assumptions in coalgebraic modal logics. Unlike earlier results of this kind, we do not require a tractable set of tableau rules for the instance logics, so that the result applies to wider classes of logics. Examples are Presburger modal logic, which extends graded modal logic with linear inequalities over numbers of successors, and probabilistic modal logic with polynomial inequalities over probabilities. We establish the theoretical upper bound using a type elimination algorithm. We also provide a global caching algorithm that offers potential for practical reasoning.

We introduce a new notion of structural refinement, a sound abstraction of logical implication, for the modal nu-calculus. Using new translations between the modal nu-calculus and disjunctive modal transition systems, we show that these two specification formalisms are structurally equivalent. Using our translations, we also transfer the structural operations of composition and quotient from disjunctive modal transition systems to the modal nu-calculus. This shows that the modal nu-calculus supports composition and decomposition of specifications., Accepted at ICTAC 2014

Building on a new approach to polyadic modal languages and Sahlqvist formulas introduced in [10] we define Sahlqvist formulas in hybrid polyadic modal languages containing nominals and universal modality or satisfaction operators. Particularly interesting is the case of reversive polyadic languages, closed under all ‘inverses’ of polyadic modalities because the minimal valuations arising in the computation of the first-order equivalents of polyadic Sahlqvist formulae are definable in such languages and that makes the proof of first-order definability and canonicity of these formulas a simple syntactic exercise. Furthermore, the first-order definability of Sahlqvist formulas immediately transfers to arbitrary polyadic languages, while the direct transfer of canonicity requires a more involved proof-theoretic analysis.

By $$ {\user1{\mathcal{L}}} $$ we denote the set of all propositional formulas. Let $$ {\user1{\mathcal{C}}} $$ be the set of all clauses. Define $$ {\user1{\mathcal{C}}}_{0} = {\user1{\mathcal{C}}} \cup {\left\{ {\neg L\eta :\eta \in {\user1{\mathcal{C}}}} \right\}} $$ . In Sec. 2 of this paper we prove that for normal modal logics $$ {\user1{\mathcal{S}}} $$ , the notions of $$ {\left( {{\user1{\mathcal{S}}},{\user1{\mathcal{C}}}_{0} } \right)} $$ -expansions and $$ {\user1{\mathcal{S}}} $$ -expansions coincide. In Sec. 3, we prove that if I consists of default clauses then the notions of $$ {\user1{\mathcal{S}}} $$ -expansions for I and $$ {\left( {{\user1{\mathcal{S}}},{\user1{\mathcal{C}}}} \right)} $$ -expansions for I coincide. To this end, we first show, in Sec. 3, that the notion of $$ {\user1{\mathcal{S}}} $$ -expansions for I is the same as that of $$ {\left( {{\user1{\mathcal{S}}},{\user1{\mathcal{L}}}} \right)} $$ -expansions for I.

We show that some common varieties of modal K4 -algebras have finitary unification type, thus providing effective best solutions for equations in free algebras. Applications to admissible inference rules are immediate.

This paper deals with modal Horn formulas. It contains a characterization of the classes of models definable by modal universal Horn formulas as well as a preservation result for modal universal Horn formulas.

This paper presents the axioinatization—without the rule of irreflexivity—of the modal logic of inequality as well as a method for proving its completeness. This method uses the technics of the frame of subordination.

Which modal logics can be ‘naturally’ captured by a sequent system? Clearly, this question hinges on what one believes to be natural, i.e. which format of sequent rules one is willing to accept. This paper studies the relationship between the format of sequent rules and the corresponding syntactical shape of axioms in an equivalent Hilbert-system. We identify three different such formats, the most general of which captures most logics in the S5-cube. The format is based on restricting the context in rule premises and the correspondence is established by translating axioms into rules of our format and vice versa. As an application we show that there is no set of sequent rules of this format which is sound and cut-free complete for S5 and for which cut elimination can be shown by the standard permutation-of-rules argument.

We investigate an axiomatization of the notion of common belief (knowledge) that makes use of no rules of inference (apart from Modus Ponens and Necessitation) and highlight the property of the set of accessibility relations that characterizes each axiom. Mathematics Subject Classification: 03B45, 68T25.

We develop cut-free calculi of sequents for normal modal logics by using treesequents, which are trees of sequences of formulas. We introduce modal operators corresponding to the ways we move formulas along the branches of such trees, only considering fixed distance movements. Finally, we exhibit syntactic cut-elimination theorems for all the main normal modal logics. Mathematics Subject Classification: 03B45, 03F05.

We consider structural completeness in modal logics. The main result is the necessary and sufficient condition for modal logics over K4 to be hereditarily structurally complete: a modal logic λ is hereditarily structurally complete iff λ is not included in any logic from the list of twenty special tabular logics. Hence there are exactly twenty maximal structurally incomplete modal logics above K4 and they are all tabular.

In 1951 C.I.Lewis published a logic of general terms (or properties) that he called the calculus of predicates. Although this system is of less significance than Lewis’s earlier work on propositional modal logic, it has considerable historical interest and does not deserve the almost total neglect it has received. My aim here is to situate this system in the context of Lewis’s earlier work and to examine several of its central features.After sketching the historical background, I present the syntax of Lewis‘s system, discuss his reasons for preferring it to quantified modal logic, and develop a semantics for it that is suggested by Lewis‘s informal discussion of his system together with his general views on meaning.I then discuss Lewis’s sketchy extension of his system to include quantifiers and examine his claim that it can serve as a foundation for logic in general. I conclude by noting two minor changes in CP that, from today‘s vantage point, would count as improvements

In this work, the problem of performing abduction in modal logics is addressed, along the lines of [3], where a proof theoretical abduction method for full first order classical logic is defined, based on tableaux and Gentzen-type systems. This work applies the same methodology to face modal abduction. The non-classical context enforces the value of analytical proof systems as tools to face the meta-logical and proof-theoretical questions involved in abductive reasoning. The similarities and differences between quantifiers and modal operators are investigated and proof theoretical abduction methods for the modal systems K, D, T and S4 are defined, that are sound and complete. The construction of the abductive explanations is in strict relation with the expansion rules for the modal logics, in a modular manner that makes local modifications possible. The method given in this paper is general, in the sense that it can be adapted to any propositional modal logic for which analytic tableaux are provided. Moreover, the way towards an extension to first order modal logic is straightforward.

We define analogues of modal Sahlqvist formulas for the modal mu-calculus, and prove a correspondence theorem for them.

This chapter discusses modal logic: the logic of possibility and necessity. After a brief review of modal logic in the second section, the third section presents basic results of propositional tense logic. The fourth section develops a system of quantified tense logic. With these technical preliminaries out of the way, the fifth section explains why tense logic ultimately fails as a linguistic theory of verb tense. The sixth section presents the main objection to tense primitivism: that tense logic has insufficient expressive resources to serve as a metaphysical theory of time. The seventh section argues that the tense primitivist can overcome these problems by treating times as maximally consistent sets of sentences. The eighth section discusses a key difference between time and modality: the lack of a temporal analogue of actualism.

Notions of lower and upper approximations are proposed for multiple-source tolerance approximation spaces which consist of a number of tolerance relations over the same domain. A modal logic is proposed for reasoning about the defined notions of approximations. A sound and complete deductive system for the logic is presented. Decidability is also proved.

This paper studies an interpretation of the Chance Discovery (CD) as the unification problem in the linear modal logic S4.3. We prove that any formula unifiable in S4.3 has a most general unifier, and we give an algorithm which, for any unifiable formula, constructs a most general unifier. More precisely, we merely write out, explicitly, the formulas giving substitutions for a most-general unifier. From computational viewpoint, we find an algorithm for the construction of sets of 'best unifiers' (complete collections of 'most' general unifiers) in the linear modal logic S4.3.

The problem of Common Knowledge will be considered in two classes of models: a class K* of Kripke models and a class S of Scott models. Two modal logic systems will be defined. Those systems, KC and MC, include an axiomatisation of Common Knowledge. We prove determination of each system by the corresponding class of models.

International audience; We present a modal language that includes explicit operators to count the number of elements that a model might include in the extension of a formula, and we discuss how this logic has been previously investigated under different guises. We show that the language is related to graded modalities and to hybrid logics. We illustrate a possible application of the language to the treatment of plural objects and queries in natural language. We investigate the expressive power of this logic via bisimulations, discuss the complexity of its satisfiability problem, define a new reasoning task that retrieves the cardinality bound of the extension of a given input formula, and provide an algorithm to solve it.

International audience; In this paper we propose proof systems without labels for the intuitionistic modal logic IS5 that are based on a new multi-contextual sequent structure appropriate to deal with such a logic. We first give a label-free natural deduction system and thus derive natural deduction systems for the classical modal logic S5 and also for an intermediate logic IM5. Then we define a label-free sequent calculus for IS5 and prove its soundness and completeness. The study of this calculus leads to a decision procedure for IS5 and thus to an alternative syntactic proof of its decidability.

We present a sound and complete model of lambda-calculus reductions based on structures inspired by modal logic (closely related to Kripke structures). Accordingly we can construct a logic which is sound and complete for the same models, and we identify lambda-terms with certain simple sentences (predicates) in this logic, by direct compositional translation. Reduction then becomes identified with logical entailment. Thus, the models suggest a new way to identify logic and computation. Both have elementary and concrete representations in our models; where these representations overlap, they coincide. In a concluding speculation, we note a certain subclass of the models which seems to play a role analogous to that played by the cumulative hierarchy models in axiomatic set theory and the natural numbers in formal arithmetic -- there are many models of the respective theories, but only some, characterised by a fully second order interpretation, are the 'intended' ones.

We introduce negation into coinductive logic programming (co-LP) via what we term Coinductive SLDNF (co-SLDNF) resolution. We present declarative and operational semantics of co-SLDNF resolution and present their equivalence under the restriction of rationality. Co-LP with co-SLDNF resolution provides a powerful, practical and efficient operational semantics for Fitting’s Kripke-Kleene three-valued logic with restriction of rationality. Further, applications of co-SLDNF resolution are also discussed and illustrated where Co-SLDNF resolution allows one to develop elegant implementations of modal logics. Moreover it provides the capability of non-monotonic inference (e.g., predicate Answer Set Programming) that can be used to develop novel and effective first-order modal non-monotonic inference engines.

Higher dimensional automata (HDAs) are a model of concurrency that can express most of the traditional partial order models like Mazurkiewicz traces, pomsets, event structures, or Petri nets. Modal logics, interpreted over Kripke structures, are the logics for reasoning about sequential behavior and interleaved concurrency. Modal logic is a well behaved subset of first-order logic; many variants of modal logic are decidable. However, there are no modal-like logics for the more expressive HDA models. In this paper we introduce and investigate a modal logic over HDAs which incorporates two modalities for reasoning about "during" and "after". We prove that this general higher dimensional modal logic (HDML) is decidable and we define a complete axiomatic system for it. We also show how, when the HDA model is restricted to Kripke structures, a syntactic restriction of HDML becomes the standard modal logic. Then we isolate the class of HDAs that encode Mazurkiewicz traces and show how HDML can be restricted to LTrL (the linear time temporal logic over Mazurkiewicz traces).

The first part of the chapter is dedicated to a brief summary of the main notions and results of what is usually called normal modal logic. In the second part of the chapter we present the ordinary sequent calculi that have been developed for modal logic. It turns out that these calculi do not satisfy many of the properties of a good sequent calculus. In the last section we begin to consider how one might generalise the classical sequent calculus.

The main aim of this paper is to study inductive modal logics – bi-modal logics, containing the Segerberg’s induction axiom Seg, known from PDL. An adequate semantical characterization of Seg is given, and completeness theorems for a number of inductive modal logics are proved by a generalization of Segerberg’s filtration from PDL.