Showing 1 to 57 of 57 matching Articles
Results per page:
Export (CSV)
By
VillaseñorPineda, Luis; MontesyGómez, Manuel; Caelen, Jean
One major goal of human computer interfaces is to simplify the communication task. Traditionally, users have been restricted to the language of computers for this task. With the emerging of the graphical and multimodal interfaces the effort required for working with a computer is decreasing. However, the problem of communication is still present, and users continue caring about the communication task when they deal with a computer. Our work focuses on improving the communication between the human and the computer. This paper presents the foundations of a multimodal dialog model based on a modal logic, which integrates the speech and the action under the same framework.
more …
By
Kowalski, Tomasz; Kracht, Marcus
9 Citations
In this paper we show that a variety of modal algebras of finite type is semisimple iff it is discriminator iff it is both weakly transitive and cyclic. This fact has been claimed already in [4] (based on joint work by the two authors) but the proof was fatally flawed.
more …
By
Sturm, Holger
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.
By
Segerberg, Krister
The purpose of this paper is to suggest a formal modelling of metaphors as a lingustic tool capable of conveying meanings from one conceptual space to another. This modelling is done within DDL (dynamic doxastic logic).
By
Vakarelov, Dimiter
A new modal logic containing four dynamic modalities with the following informal reading is introduced:
$${\square^\forall}$$
– always necessary,
$${\square^\exists}$$
– sometimes necessary, and their duals –
$${\diamondsuit^\forall}$$
– always possibly, and
$${\diamondsuit^\exists}$$
– sometimes possibly. We present a complete axiomatization with respect to the intended formal semantics and prove decidability via fmp.
more …
By
van Eijck, Jan
12 Citations
We explore some logics of change, focusing on commands to change the world in such a way that certain elementary propositions become true or false. This investigation starts out from the following two simplifying assumptions: (1) the world is a collection of facts (Wittgenstein), and (2), the world can be changed by changing elementary facts (Marx). These assumptions allow us to study the logic of imperatives in the simplest possible setting.
more …
By
Archangelsky, Dmitri A.; Taitslin, Mikhail A.
2 Citations
A conception of an information system has been introduced by Pawlak. The study has been continued in works of Pawlak and Orlowska and in works of Vakarelov. They had proposed some basic relations and had constructed a formal system of a modal logic that describes the relations and some of their Boolean combinations. Our work is devoted to a generalization of this approach. A class of relation systems and a complete calculus construction method for these systems are proposed. As a corollary of our main result, our paper contains a solution of a Vakarelov's problem: how to construct a formal system that describes all the Boolean combinations of the basic relations.
more …
By
Miroiu, Adrian
1 Citations
Some logical properties of modal languages in which actuality is expressible are investigated. It is argued that, if a sentence like 'Actually, Quine is a distinguished philosopher' is understood as a special case of worldindexed sentences (the index being the actual world), then actuality can be expressed only under strong modal assumptions. Some rival rigid and indexical approaches to actuality are discussed.
more …
By
van der Hoek, Wiebe; Thijsse, Elias
7 Citations
We extend our general approach to characterizing information to multiagent systems. In particular, we provide a formal description of an agent's knowledge containing exactly the information conveyed by some (honest) formula ϕ. Only knowing is important for dynamic agent systems in two ways. First of all, one wants to compare different states of knowledge of an agent and, secondly, for agent a's decisions, it may be relevant that (he knows that) agent b does not know more than ϕ. There are three ways to study the question whether a formula ϕ can be interpreted as minimal information. The first method is semantic and inspects ‘minimal’ models for ϕ (with respect to some information order ≤ on states). The second one is syntactic and searches for stable expansions, minimal with respect to some language ℒ*. The third method is a deductive test, known as the disjunction property. We present a condition under which the three methods are equivalent. Then, we show how to construct the order ≤ by collecting ‘layered orders’. Focusing on the multiagent case we identify languages ℒ* for various orders ≤, and show how they yield different notions of honesty for different multimodal systems. We then provide several tools for studying honesty types and illustrate their usefulness on a number of examples, for three modal systems of particular interest. Finally, we relate the different notions of minimal knowledge, and describe possible patterns of honesty for these systems.
more …
By
Mares, Edwin D.; McNamara, Paul
6 Citations
In "Doing Well Enough: Toward a Logic for Common Sense Morality", Paul McNamara sets out a semantics for a deontic logic which contains the operator ‘It is supererogatory that’. As well as having a binary accessibility relation on worlds, that semantics contains a relative ordering relation, ≤. For worlds u, v and w, we say that u ≤w v when v is at least as good as u according to the standards of w. In this paper we axiomatize logics complete over three versions of the semantics. We call the strongest of these logics ‘DWE’ for ‘Doing Well Enough’.
more …
By
Brown, Mark A.
3 Citations
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.
more …
By
Skura, Tomasz
3 Citations
In this paper we study the method of refutation rules in the modal logic K4. We introduce refutation rules with certain normal forms that provide a new syntactic decision procedure for this logic. As corollaries we obtain such results for the following important extensions: S4, the provability logic G, and Grzegorczyk's logic. We also show that treetype models can be constructed from syntactic refutations of this kind.
more …
By
Goranko, Valentin
10 Citations
We give a complete axiomatization of the identities of the basic game algebra valid with respect to the abstract game board semantics. We also show that the additional conditions of termination and determinacy of game boards do not introduce new valid identities.
En route we introduce a simple translation of game terms into plain modal logic and thus translate, while preserving validity both ways, game identities into modal formulae.
The completeness proof is based on reduction of game terms to a certain ‘minimal canonical form’, by using only the axiomatic identities, and on showing that the equivalence of two minimal canonical terms can be established from these identities.
more …
By
Jacquette, Dale
1 Citations
If we agree with Michael Jubien that propositions do not exist, while accepting the existence of abstract sets in a realist mathematical ontology, then the combined effect of these ontological commitments has surprising implications for the metaphysics of modal logic, the ontology of logically possible worlds, and the controversy over modal realism versus actualism. Logically possible worlds as maximally consistent proposition sets exist if sets generally exist, but are equivalently expressed as maximally consistent conjunctions of the same propositions in corresponding sets. A conjunction of propositions, even if infinite in extent, is nevertheless itself a proposition. If sets and hence proposition sets exist but propositions do not exist, then whether or not modal realism is true depends on which of two apparently equivalent methods of identifying, representing, or characterizing logically possible worlds we choose to adopt. I consider a number of reactions to the problem, concluding that the best solution may be to reject the conventional model set theoretical concept of logically possible worlds as maximally consistent proposition sets, and distinguishing between the actual world alone as maximally consistent and interpreting all nonactual merely logically possible worlds as submaximal.
more …
By
Gabbay, Dov M.
12 Citations
Given an argumentation network we associate with it a modal formula representing the ‘logical content’ of the network. We show a onetoone correspondence between all possible complete Caminada labellings of the network and all possible models of the formula.
more …
By
Rybakov, V. V.; Terziler, M.; Gencer, C.
2 Citations
We study quasicharacterizing inference rules (this notion was introduced into consideration by A. Citkin (1977). The main result of our paper is a complete description of all selfadmissible quasicharacterizing inference rules. It is shown that a quasicharacterizing rule is selfadmissible iff the frame of the algebra generating this rule is not rigid. We also prove that selfadmissible rules are always admissible in canonical, in a sense, logics S4 or IPC regarding the type of algebra generating rules.
more …
By
Maruyama, Yoshihiro
3 Citations
This paper explores relationships between manyvalued logic and fuzzy topology from the viewpoint of duality theory. We first show a fuzzy topological duality for the algebras of Łukasiewicz nvalued logic with truth constants, which generalizes Stone duality for Boolean algebras to the nvalued case via fuzzy topology. Then, based on this duality, we show a fuzzy topological duality for the algebras of modal Łukasiewicz nvalued logic with truth constants, which generalizes JónssonTarski duality for modal algebras to the nvalued case via fuzzy topology. We emphasize that fuzzy topological spaces naturally arise as spectrums of algebras of manyvalued logics.
more …
By
Poggiolesi, Francesca
24 Citations
In this paper we present a method, that we call the treehypersequent method, for generating contractionfree and cutfree sequent calculi for modal propositional logics. We show how this method works for the systems K, KD, K4 and KD4, by giving a sequent calculus for these systems which are normally presented in the Hilbert style, and by proving all the main results in a purely syntactical way.
more …
By
Caminada, Martin W. A.; Gabbay, Dov M.
92 Citations
In the current paper, we reexamine how abstract argumentation can be formulated in terms of labellings, and how the resulting theory can be applied in the field of modal logic. In particular, we are able to express the (complete) extensions of an argumentation framework as models of a set of modal logic formulas that represents the argumentation framework. Using this approach, it becomes possible to define the grounded extension in terms of modal logic entailment.
more …
By
Bezhanishvili, Nick; Hodkinson, Ian
2 Citations
We prove that every normal extension of the bimodal system S5^{2} is finitely axiomatizable and that every proper normal extension has NPcomplete satisfiability problem.
By
Maksimova, Larisa
5 Citations
All extensions of the modal Grzegorczyk logic Grz possessing projective Beth's property PB2 are described. It is proved that there are exactly 13 logics over Grz with PB2. All of them are finitely axiomatizable and have the finite model property. It is shown that PB2 is strongly decidable over Grz, i.e. there is an algorithm which, for any finite system Rul of additional axiom schemes and rules of inference, decides if the calculus Grz+Rul has the projective Beth property.
more …
By
Bílková, Marta
10 Citations
We investigate uniform interpolants in propositional modal logics from the prooftheoretical point of view.
Our approach is adopted from Pitts’ proof of uniform interpolationin intuitionistic propositional logic [15]. The method is based on a simulation of certain quantifiers ranging over propositional variables and uses a terminating sequent calculus for which structural rules are admissible.
We shall present such a proof of the uniform interpolation theorem for normal modal logics K and T. It provides an explicit algorithm constructing the interpolants.
more …
By
Fitting, Melvin
11 Citations
This is an expository paper in which the basic ideas of a family of Justification Logics are presented. Justification Logics evolved from a logic called
$\mathsf{LP}$
, introduced by Sergei Artemov (Technical Report MSI 9529, 1995; The Bulletin for Symbolic Logic 7(1): 1–36, 2001), which formed the central part of a project to provide an arithmetic semantics for propositional intuitionistic logic. The project was successful, but there was a considerable bonus:
$\mathsf{LP}$
came to be understood as a logic of knowledge with explicit justifications and, as such, was capable of addressing in a natural way longstanding problems of logical omniscience. Since then,
$\mathsf{LP}$
has become one member of a family of related logics, all logics of knowledge with explicit knowledge terms. In this paper the original problem of intuitionistic foundations is discussed only briefly. We concentrate entirely on issues of reasoning about knowledge.
more …
By
Wansing, Heinrich
26 Citations
This is a purely conceptual paper. It aims at presenting and putting into perspective the idea of a prooftheoretic semantics of the logical operations. The first section briefly surveys various semantic paradigms, and Section 2 focuses on one particular paradigm, namely the prooftheoretic semantics of the logical operations.
more …
By
Hodkinson, Ian
22 Citations
We show that the loosely guarded and packed fragments of firstorder logic have the finite model property. We use a construction of Herwig and Hrushovski. We point out some consequences in temporal predicate logic and algebraic logic.
By
Marx, Maarten
1 Citations
The complexity of the satisfiability problems of various arrow logics and cylindric modal logics is determined. As is well known, relativising these logics makes them decidable. There are several parameters that can be set in such a relativisation. We focus on the following three: the number of variables involved, the similarity type and the kind of relativised models considered. The complexity analysis shows the importance and relevance of these parameters.
more …
By
Wolter, Frank
8 Citations
This paper investigates partitions of lattices of modal logics based on superintuitionistic logics which are defined by forming, for each superintuitionistic logic L and classical modal logic Θ, the set L[Θ] of Lcompanions of Θ. Here L[Θ] consists of those modal logics whose nonmodal fragments coincide with L and which axiomatize Θ if the law of excluded middle p V ⌍p is added. Questions addressed are, for instance, whether there exist logics with the disjunction property in L[Θ], whether L[Θ] contains a smallest element, and whether L[Θ] contains lower covers of Θ. Positive solutions as concerns the last question show that there are (uncountably many) superclean modal logics based on intuitionistic logic in the sense of Vakarelov [28]. Thus a number of problems stated in [28] are solved. As a technical tool the paper develops the splitting technique for lattices of modal logics based on superintuitionistic logics and ap plies duality theory from [34].
more …
By
Zakharyaschev, Michael
1 Citations
This paper gives a characterization of those quasinormal extensions of the modal system S4 into which intuitionistic propositional logic Int is embeddable by the Gödel translation. It is shown that, as in the normal case, the set of quasinormal modal companions of Int contains the greatest logic, M*, for which, however, the analog of the BlokEsakia theorem does not hold. M* is proved to be decidable and Halldéncomplete; it has the disjunction property but does not have the finite model property.
more …
By
Humberstone, Lloyd; Williamson, Timothy
3 Citations
Given a 1ary sentence operator ○, we describe L  another 1ary operator  as as a left inverse of ○ in a given logic if in that logic every formula ϕ is provably equivalent to L○ϕ. Similarly R is a right inverse of ○ if ϕ is always provably equivalent to ○Rϕ. We investigate the behaviour of left and right inverses for ○ taken as the □ operator of various normal modal logics, paying particular attention to the conditions under which these logics are conservatively extended by the addition of such inverses, as well as to the question of when, in such extensions, the inverses behave as normal modal operators in their own right.
more …
By
van Ditmarsch, Hans
39 Citations
Suppose we have a stack of cards that is divided over some players. For certain distributions of cards it is possible to communicate your hand of cards to another player by public announcements, without yet another player learning any of your cards. A solution to this problem consists of some sequence of announcements and is called an exchange. It is called a direct exchange if it consists of (the minimum of) two announcements only. The announcements in an exchange have a special form: they are safe communications, an interesting new form of update. Certain unsafe communications turn out to be unsuccessful updates. A communication is a public announcement that is known to be true. Each communication may be about a set of alternative card deals only, and even about a set of alternatives to the communicating player's own hand only. We list the direct exchanges for a deal of seven cards where the two players holding three cards communicate their hands to each other. Our work may be applicable to the design of cryptographic protocols.
more …
By
Hoek, Wiebe; Jaspars, Jan; Thijsse, Elias
6 Citations
We propose an epistemic logic in which knowledge is fully introspective and implies truth, although truth need not imply epistemic possibility. The logic is presented in sequential format and is interpreted in a natural class of partial models, called balloon models. We examine the notions of honesty and circumscription in this logic: What is the state of an agent that ‘only knows ϕ’ and which honest ϕ enable such circumscription? Redefining stable sets enables us to provide suitable syntactic and semantic criteria for honesty. The rough syntactic definition of honesty is the existence of a minimal stable expansion, so the problem resides in the ordering relation underlying minimality. We discuss three different proposals for this ordering, together with their semantic counterparts, and show their effects on the induced notions of honesty.
more …
By
Koons, Robert C.
Threevalued (strongKleene) modal logic provides the foundation for a new approach to formalizing causal explanation as a relation between partial situations. The approach makes finegrained distinctions between aspects of events, even between aspects that are equivalent in classical logic. The framework can accommodate a variety of ontologies concerning the relata of causal explanation. I argue, however, for a tripartite ontology of objects corresponding to sentential nominals: facts, tropes (or facta or states of affairs), and situations (or events). I axiomatize the relations and use canonical models to demonstrate completeness.
more …
By
Fernández Duque, David
5 Citations
We show that given a finite, transitive and reflexive Kripke model 〈 W, ≼, ⟦ ⋅ ⟧ 〉 and
$${w \in W}$$
, the property of being simulated by w (i.e., lying on the image of a literalpreserving relation satisfying the ‘forth’ condition of bisimulation) is modally undefinable within the class of S4 Kripke models. Note the contrast to the fact that lying in the image of w under a bisimulation is definable in the standard modal language even over the class of K4 models, a fairly standard result for which we also provide a proof.
We then propose a minor extension of the language adding a sequent operator
$${\natural}$$
(‘tangle’) which can be interpreted over Kripke models as well as over topological spaces. Over finite Kripke models it indicates the existence of clusters satisfying a specified set of formulas, very similar to an operator introduced by Dawar and Otto. In the extended language
$${{\sf L}^+ = {\sf L}^{\square\natural}}$$
, being simulated by a point on a finite transitive Kripke model becomes definable, both over the class of (arbitrary) Kripke models and over the class of topological S4 models.
As a consequence of this we obtain the result that any class of finite, transitive models over finitely many propositional variables which is closed under simulability is also definable in L^{+}, as well as Boolean combinations of these classes. From this it follows that the μcalculus interpreted over any such class of models is decidable.
more …
By
Sturm, Holger
Dealing with topics of definability, this paper provides some interesting insights into the expressive power of basic modal logic. After some preliminary work it presents an abstract algebraic characterization of the elementary classes of basic modal logic, that is, of the classes of models that are definable by means of (sets of) basic modal formulas. Taking that for a start, the paper further contains characterization results for modal universal classes and modal positive classes.
more …
By
Miller, Joseph S.; Moss, Lawrence S.
28 Citations
In dynamic epistemic logic and other fields, it is natural to consider relativization as an operator taking sentences to sentences. When using the ideas and methods of dynamic logic, one would like to iterate operators. This leads to iterated relativization. We are also concerned with the transitive closure operation, due to its connection to common knowledge. We show that for three fragments of the logic of iterated relativization and transitive closure, the satisfiability problems are fi1 Σ^{1}_{1}–complete. Two of these fragments do not include transitive closure. We also show that the question of whether a sentence in these fragments has a finite (tree) model is fi0 Σ^{0}_{1}–complete. These results go via reduction to problems concerning domino systems.
more …
By
Marx, Maarten; Mikulás, Szabolcs
3 Citations
We consider the problem of the product finite model property for binary products of modal logics. First we give a new proof for the product finite model property of the logic of products of Kripke frames, a result due to Shehtman. Then we modify the proof to obtain the same result for logics of products of Kripke frames satisfying any combination of seriality, reflexivity and symmetry. We do not consider the transitivity condition in isolation because it leads to infinity axioms when taking products.
more …
By
de Rijke, Maarten
18 Citations
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.
more …
By
Citkin, Alex
1 Citations
We give an example of a variety of Heyting algebras and of a splitting algebra in this variety that is not finitely presentable. Moreover, we show that the corresponding splitting pair cannot be defined by any finitely presentable algebra. Also, using the GödelMcKinseyTarski translation and the BlokEsakia theorem, we construct a variety of Grzegorczyk algebras with similar properties.
more …
By
Pauly, Marc; Parikh, Rohit
42 Citations
Game Logic is a modal logic which extends Propositional Dynamic Logic by generalising its semantics and adding a new operator to the language. The logic can be used to reason about determined 2player games. We present an overview of metatheoretic results regarding this logic, also covering the algebraic version of the logic known as Game Algebra.
more …
By
Blackburn, P.; Cate, B. ten
31 Citations
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 firstorder expressivity).
We show that hybrid logic offers a genuinely firstorder 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 nonorthodox rules. We discuss these rules in detail and prove noneliminability 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 firstorder hybrid logic.
more …
By
Fitting, Melvin
4 Citations
In an earlier paper, [5], I gave semantics and tableau rules for a simple firstorder intensional logic called FOIL, in which both objects and intensions are explicitly present and can be quantified over. Intensions, being nonrigid, are represented in FOIL as (partial) functions from states to objects. Scoping machinery, predicate abstraction, is present to disambiguate sentences like that asserting the necessary identity of the morning and the evening star, which is true in one sense and not true in another.
In this paper I address the problem of axiomatizing FOIL. I begin with an interesting sublogic with predicate abstraction and equality but no quantifiers. In [2] this sublogic was shown to be undecidable if the underlying modal logic was at least K4, though it is decidable in other cases. The axiomatization given is shown to be complete for standard logics without a symmetry condition. The general situation is not known. After this an axiomatization for the full FOIL is given, which is straightforward after one makes a change in the point of view.
more …
By
Maksimova, Larisa
15 Citations
Algebraic approach to study of classical and nonclassical logical calculi was developed and systematically presented by Helena Rasiowa in [48], [47]. It is very fruitful in investigation of nonclassical logics because it makes possible to study large families of logics in an uniform way. In such research one can replace logics with suitable classes of algebras and apply powerful machinery of universal algebra.
In this paper we present an overview of results on interpolation and definability in modal and positive logics,and also in extensions of Johansson's minimal logic. All these logics are strongly complete under algebraic semantics. It allows to combine syntactic methods with studying varieties of algebras and to flnd algebraic equivalents for interpolation and related properties. Moreover, we give exhaustive solution to interpolation and some related problems for many families of propositional logics and calculi.
more …
By
Brandenburger, Adam; Keisler, H. Jerome
31 Citations
A paradox of selfreference in beliefs in games is identified, which yields a gametheoretic impossibility theorem akin to Russell’s Paradox. An informal version of the paradox is that the following configuration of beliefs is impossible:
Ann believes that Bob assumes that
Ann believes that Bob’s assumption is wrong
This is formalized to show that any belief model of a certain kind must have a ‘hole.’ An interpretation of the result is that if the analyst’s tools are available to the players in a game, then there are statements that the players can think about but cannot assume. Connections are made to some questions in the foundations of game theory.
more …
By
Trypuz, Robert
In this paper the class of minimal models C^{ZI} for Kiczuk’s system of physical change ZI is provided and soundness and completeness proofs of ZI with respect to these models are given. ZI logic consists of propositional logic von Wright’s And Then and six specific axioms characterizing the meaning of unary propositional operator “Zm”, read “there is a change in the fact that”. ZI is intended to be a logic which provides a formal account for describing two kinds of process change: the change from one state of the process to its other state (e.g., transmitting or absorbing energy with greater or less than the usual intensity) and the perishing of the process (e.g., cessation of the energetic activity of the sun).
more …
By
Font, Josep Maria; Hájek, Petr
23 Citations
Łukasiewicz's fourvalued modal logic is surveyed and analyzed, together with Łukasiewicz's motivations to develop it. A faithful interpretation of it in classical (nonmodal) twovalued logic is presented, and some consequences are drawn concerning its classification and its algebraic behaviour. Some counterintuitive aspects of this logic are discussed in the light of the presented results, Łukasiewicz's own texts, and related literature.
more …
By
Kracht, Marcus; Wolter, Frank
21 Citations
This papers gives a survey of recent results about simulations of one class of modal logics by another class and of the transfer of properties of modal logics under extensions of the underlying modal language. We discuss: the transfer from normal polymodal logics to their fusions, the transfer from normal modal logics to their extensions by adding the universal modality, and the transfer from normal monomodal logics to minimal tense extensions. Likewise, we discuss simulations of normal polymodal logics by normal monomodal logics, of nominals and the difference operator by normal operators, of monotonic monomodal logics by normal bimodal logics, of polyadic normal modal logics by polymodal normal modal logics, and of intuitionistic modal logics by normal bimodal logics.
more …
By
Naumov, Pavel
2 Citations
The classical propositional logic is known to be sound and complete with respect to the set semantics that interprets connectives as set operations. The paper extends propositional language by a new binary modality that corresponds to partial recursive function type constructor under the above interpretation. The cases of deterministic and nondeterministic functions are considered and for both of them semantically complete modal logics are described and decidability of these logics is established.
more …
By
Bierman, G. M.; de Paiva, V. C. V.
51 Citations
In this paper we consider an intuitionistic variant of the modal logic S4 (which we call IS4). The novelty of this paper is that we place particular importance on the natural deduction formulation of IS4— our formulation has several important metatheoretic properties. In addition, we study models of IS4— not in the framework of Kirpke semantics, but in the more general framework of category theory. This allows not only a more abstract definition of a whole class of models but also a means of modelling proofs as well as provability.
more …
By
Konev, B.; Kontchakov, R.; Wolter, F.; Zakharyaschev, M.
Show all (4)
11 Citations
We investigate computational properties of propositional logics for dynamical systems. First, we consider logics for dynamic topological systems (W.f), fi, where W is a topological space and f a homeomorphism on W. The logics come with ‘modal’ operators interpreted by the topological closure and interior, and temporal operators interpreted along the orbits {w, f(w), f^{2}(w), ˙˙˙} of points w ε W. We show that for various classes of topological spaces the resulting logics are not recursively enumerable (and so not recursively axiomatisable). This gives a ‘negative’ solution to a conjecture of Kremer and Mints. Second, we consider logics for dynamical systems (W, f), where W is a metric space and f and isometric function. The operators for topological interior/closure are replaced by distance operators of the form ‘everywhere/somewhere in the ball of radius a, ‘for a ε Q^{+}. In contrast to the topological case, the resulting logic turns out to be decidable, but not in time bounded by any elementary function.
more …
By
Goranko, Valentin
6 Citations
A certain type of inference rules in (multi) modal logics, generalizing Gabbay's Irreflexivity rule, is introduced and some general completeness results about modal logics axiomatized with such rules are proved.
By
van der Meyden, Ron; Wong, Kashu
34 Citations
Sound and complete axiomatizations are provided for a number of different logics involving modalities for the knowledge of multiple agents and operators for branching time, extending previous work of Halpern, van der Meyden and Vardi [to appear, SIAM Journal on Computing] for logics of knowledge and linear time. The paper considers the system constraints of synchrony, perfect recall and unique initial states, which give rise to interaction axioms. The language is based on the temporal logic CTL*, interpreted with respect to a version of the bundle semantics.
more …
By
Fitting, Melvin
2 Citations
This is a largely expository paper in which the following simple idea is pursued. Take the truth value of a formula to be the set of agents that accept the formula as true. This means we work with an arbitrary (finite) Boolean algebra as the truth value space. When this is properly formalized, complete modal tableau systems exist, and there are natural versions of bisimulations that behave well from an algebraic point of view. There remain significant problems concerning the proper formalization, in this context, of natural language statements, particularly those involving negative knowledge and common knowledge. A case study is presented which brings these problems to the fore. None of the basic material presented here is new to this paper—all has appeared in several papers over many years, by the present author and by others. Much of the development in the literature is more general than here—we have confined things to the Boolean case for simplicity and clarity. Most proofs are omitted, but several of the examples are new. The main virtue of the present paper is its coherent presentation of a systematic point of view—identify the truth value of a formula with the set of those who say the formula is true.
more …
By
Wansing, Heinrich
4 Citations
The paper provides a uniform Gentzenstyle prooftheoretic framework for various subsystems of classical predicate logic. In particular, predicate logics obtained by adopting van Behthem's modal perspective on firstorder logic are considered. The Gentzen systems for these logics augment Belnap's display logic by introduction rules for the existential and the universal quantifier. These rules for ∀x and ∃x are analogous to the display introduction rules for the modal operators □ and ♦ and do not themselves allow the Barcan formula or its converse to be derived. En route from the minimal ‘modal’ predicate logic to full firstorder logic, axiomatic extensions are captured by purely structural sequent rules.
more …
By
Blok, W. J.; Rebagliato, J.
16 Citations
The notion of an algebraic semantics of a deductive system was proposed in [3], and a preliminary study was begun. The focus of [3] was the definition and investigation of algebraizable deductive systems, i.e., the deductive systems that possess an equivalent algebraic semantics. The present paper explores the more general property of possessing an algebraic semantics. While a deductive system can have at most one equivalent algebraic semantics, it may have numerous different algebraic semantics. All of these give rise to an algebraic completeness theorem for the deductive system, but their algebraic properties, unlike those of equivalent algebraic semantics, need not reflect the metalogical properties of the deductive system. Many deductive systems that don't have an equivalent algebraic semantics do possess an algebraic semantics; examples of these phenomena are provided. It is shown that all extensions of a deductive system that possesses an algebraic semantics themselves possess an algebraic semantics. Necessary conditions for the existence of an algebraic semantics are given, and an example of a protoalgebraic deductive system that does not have an algebraic semantics is provided. The monounary deductive systems possessing an algebraic semantics are characterized. Finally, weak conditions on a deductive system are formulated that guarantee the existence of an algebraic semantics. These conditions are used to show that various classes of nonalgebraizable deductive systems of modal logic, relevance logic and linear logic do possess an algebraic semantics.
more …
By
Więckowski, Bartosz
4 Citations
The paper presents an alternative substitutional semantics for firstorder modal logic which, in contrast to traditional substitutional (or truthvalue) semantics, allows for a finegrained explanation of the semantical behavior of the terms from which atomic formulae are composed. In contrast to denotational semantics, which is inherently referenceguided, this semantics supports a nonreferential conception of modal truth and does not give rise to the problems which pertain to the philosophical interpretation of objectual domains (concerning, e.g., possibilia or transworld identity). The paper also proposes the notion of modality de nomine as an alternative to the denotational notion of modality de re.
more …
By
Indrzejczak, Andrzej
The paper is a brief survey of the most important semantic constructions founded on the concept of possible world. It is impossible to capture in one short paper the whole variety of the problems connected with manifold applications of possible worlds. Hence, after a brief explanation of some philosophical matters I take a look at possible worlds from rather technical standpoint of logic and focus on the applications in formal semantics. In particular, I would like to focus on the fruitful marriage of possible world semantics and algebra and its evolution leading to very general construction of Wójcicki called referential semantics and some of its refinements. The presentation is informal and sketchy; the main purpose is to put in one place a short, and readable I hope, description of the most important constructions and to point out the main sources of these solutions.
more …
