Showing 1 to 35 of 35 matching Articles
Results per page:
Export (CSV)
By
Xu, Ming
Post to Citeulike
This paper proves the finite model property and the finite axiomatizability of a class of normal modal logics extending K4.3. The frames for these logics are those for K4.3, in each of which every point has a bounded number of irreflexive successors if it is after an infinite ascending chain of (not necessarily distinct) points.
more …
By
Soncodi, Adrian
Post to Citeulike
In this paper we analyze the propositional extensions of the minimal classical modal logic system E, which form a lattice denoted as CExtE. Our method of analysis uses algebraic calculations with canonical forms, which are a generalization of the normal forms applicable to normal modal logics. As an application, we identify a group of automorphisms of CExtE that is isomorphic to the symmetric group S_{4}.
more …
By
Baltag, A.; Cinà, G.
Post to Citeulike
We give a definition of bisimulation for conditional modalities interpreted on selection functions and prove the correspondence between bisimilarity and modal equivalence, generalizing the Hennessy–Milner Theorem to a wide class of conditional operators. We further investigate the operators and semantics to which these results apply. First, we show how to derive a solid notion of bisimulation for conditional belief, behaving as desired both on plausibility models and on evidence models. These novel definitions of bisimulations are exploited in a series of undefinability results. Second, we treat relativized common knowledge, underlining how the same results still hold for a different modality in a different semantics. Third, we show the flexibility of the approach by generalizing it to multiagent systems, encompassing the case of multiagent plausibility models.
more …
By
Grigolia, Revaz; Kiseliova, Tatiana; Odisharia, Vladimer
Post to Citeulike
Gödel logic (alias Dummett logic) is the extension of intuitionistic logic by the linearity axiom. Symmetric Gödel logic is a logical system, the language of which is an enrichment of the language of Gödel logic with their dual logical connectives. Symmetric Gödel logic is the extension of symmetric intuitionistic logic (L. Esakia, C. Rauszer). The proofintuitionistic calculus, the language of which is an enrichment of the language of intuitionistic logic by modal operator was investigated by Kuznetsov and Muravitsky. Bimodal symmetric Gödel logic is a logical system, the language of which is an enrichment of the language of Gödel logic with their dual logical connectives and two modal operators. Bimodal symmetric Gödel logic is embedded into an extension of (bimodal) Gödel–Löb logic (provability logic), the language of which contains disjunction, conjunction, negation and two (conjugate) modal operators. The variety of bimodal symmetric Gödel algebras, that represent the algebraic counterparts of bimodal symmetric Gödel logic, is investigated. Description of free algebras and characterization of projective algebras in the variety of bimodal symmetric Gödel algebras is given. All finitely generated projective bimodal symmetric Gödel algebras are infinite, while finitely generated projective symmetric Gödel algebras are finite.
more …
By
Allo, Patrick
Post to Citeulike
2 Citations
Modal logics have in the past been used as a unifying framework for the minimality semantics used in defeasible inference, conditional logic, and belief revision. The main aim of the present paper is to add adaptive logics, a general framework for a wide range of defeasible reasoning forms developed by Diderik Batens and his coworkers, to the growing list of formalisms that can be studied with the tools and methods of contemporary modal logic. By characterising the class of abnormality models, this aim is achieved at the level of the modeltheory. By proposing formulae that express the consequence relation of adaptive logic in the objectlanguage, the same aim is also partially achieved at the syntactical level.
more …
By
Unterhuber, Matthias; Schurz, Gerhard
Post to Citeulike
The current special issue focuses on logical and probabilistic approaches to reasoning in uncertain environments, both from a formal, conceptual and argumentative perspective as well as an empirical point of view. In the present introduction we give an overview of the types of problems addressed by the individual contributions of the special issue, based on fundamental distinctions employed in this area. We furthermore describe some of the general features of the special issue.
more …
By
Braüner, Torben
Post to Citeulike
1 Citations
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 socalled 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.
more …
By
Teheux, Bruno
Post to Citeulike
We study two notions of definability for classes of relational structures based on modal extensions of Łukasiewicz finitelyvalued logics. The main results of the paper are the equivalent of the GoldblattThomason theorem for these notions of definability.
more …
By
Omori, Hitoshi; Alama , Jesse
Post to Citeulike
We outline the rather complicated history of attempts at axiomatizing Jaśkowski’s discussive logic
$$\mathbf {D_2}$$
and show that some clarity can be had by paying close attention to the language we work with. We then examine the problem of axiomatizing
$$\mathbf {D_2}$$
in languages involving discussive conjunctions. Specifically, we show that recent attempts by Ciuciura are mistaken. Finally, we present an axiomatization of
$$\mathbf {D_2}$$
in the language Jaśkowski suggested in his second paper on discussive logic, by following a remark of da Costa and Dubikajtis. We also deal with an interesting variant of
$$\mathbf {D_2}$$
, introduced by Ciuciura, in which negation is also taken to be discussive.
more …
By
Tanaka, Yoshihito
Post to Citeulike
Predicate modal logics based on Kwith noncompact extra axioms are discussed and a sufficient condition for the model existence theorem is presented. We deal with various axioms in a general way by an algebraic method, instead of discussing concrete noncompact axioms one by one.
more …
By
Lohmann, Peter; Vollmer, Heribert
Post to Citeulike
15 Citations
Modal dependence logic was introduced recently by Väänänen. It enhances the basic modal language by an operator = (). For propositional variables p_{1}, . . . , p_{n}, = (p_{1}, . . . , p_{n1}, p_{n}) intuitively states that the value of p_{n} is determined by those of p_{1}, . . . , p_{n1}. Sevenster (J. Logic and Computation, 2009) showed that satisfiability for modal dependence logic is complete for nondeterministic exponential time.
In this paper we consider fragments of modal dependence logic obtained by restricting the set of allowed propositional connectives. We show that satisfiability for poor man’s dependence logic, the language consisting of formulas built from literals and dependence atoms using
$${\wedge, \square, \lozenge}$$
(i. e., disallowing disjunction), remains NEXPTIMEcomplete. If we only allow monotone formulas (without negation, but with disjunction), the complexity drops to PSPACEcompleteness.
We also extend Väänänen’s language by allowing classical disjunction besides dependence disjunction and show that the satisfiability problem remains NEXPTIMEcomplete. If we then disallow both negation and dependence disjunction, satisfiability is complete for the second level of the polynomial hierarchy. Additionally we consider the restriction of modal dependence logic where the length of each single dependence atom is bounded by a number that is fixed for the whole logic. We show that the satisfiability problem for this bounded arity dependence logic is PSPACEcomplete and that the complexity drops to the third level of the polynomial hierarchy if we then disallow disjunction.
In this way we completely classify the computational complexity of the satisfiability problem for all restrictions of propositional and dependence operators considered by Väänänen and Sevenster.
more …
By
Tulenheimo, Tero
Post to Citeulike
The present paper provides novel results on the model theory of Independence friendly modal logic. We concentrate on its particularly wellbehaved 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 modeltheoretic 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 truthcondition is in fact expressible in ML.
more …
By
Aucher, Guillaume
Post to Citeulike
2 Citations
In epistemic logic, some axioms dealing with the notion of knowledge are rather convoluted and difficult to interpret intuitively, even though some of them, such as the axioms .2 and .3, are considered to be key axioms by some epistemic logicians. We show that they can be characterized in terms of understandable interaction axioms relating knowledge and belief or knowledge and conditional belief. In order to show it, we first sketch a theory dealing with the characterization of axioms in terms of interaction axioms in modal logic. We then apply the main results and methods of this theory to obtain specific results related to epistemic and doxastic logics.
more …
By
Zhong, Shengyang
Post to Citeulike
1 Citations
In this paper we show that some orthogeometries, i.e. projective geometries each defined using a ternary collinearity relation and equipped with a binary orthogonality relation, which are extensively studied in mathematics and quantum theory, correspond to Kripke frames, each defined using a binary relation, satisfying a few conditions. To be precise, we will define four special kinds of Kripke frames, namely, geometric frames, irreducible geometric frames, complete geometric frames and quantum Kripke frames; and we will show that they correspond to pure orthogeometries (or, equivalently, projective geometries with pure polarities), irreducible pure orthogeometries, Hilbertian geometries and irreducible Hilbertian geometries, respectively. The discovery of these correspondences raises interesting research topics and will enrich the study of logic.
more …
By
Nguyen, Linh Anh; Szałas, Andrzej
Post to Citeulike
4 Citations
Grammar logics were introduced by Fariñas del Cerro and Penttonen in 1988 and have been widely studied. In this paper we consider regular grammar logics with converse (REG^{c} logics) and present sound and complete tableau calculi for the general satisfiability problem of REG^{c} logics and the problem of checking consistency of an ABox w.r.t. a TBox in a REG^{c} logic. Using our calculi we develop ExpTime (optimal) tableau decision procedures for the mentioned problems, to which various optimization techniques can be applied. We also prove a new result that the data complexity of the instance checking problem in REG^{c} logics is coNPcomplete.
more …
By
Omori, Hitoshi; Wansing, Heinrich
Post to Citeulike
In this introduction to the special issue “40 years of FDE”, we offer an overview of the field and put the papers included in the special issue into perspective. More specifically, we first present various semantics and proof systems for FDE, and then survey some expansions of FDE by adding various operators starting with constants. We then turn to unary and binary connectives, which are classified in a systematic manner (affirmative/negative, extensional/intensional). Firstorder FDE is also briefly revisited, and we conclude by listing some open problems for future research.
more …
By
Hollenberg, Marco
Post to Citeulike
1 Citations
Negative definability ([18]) is an alternative way of defining classes of Kripke frames via a modal language, one that enables us, for instance, to define the class of irreflexive frames. Besides a list of closure conditions for negatively definable classes, the paper contains two main theorems. First, a characterization is given of negatively definable classes of (rooted) finite transitive Kripke frames and of such classes defined using both traditional (positive) and negative definitions. Second, we characterize the negatively definable classes of rooted general frames.
more …
By
Hazen, Allen P.; Rin, Benjamin G.; Wehmeier, Kai F.
Post to Citeulike
6 Citations
We show that the actuality operator A is redundant in any propositional modal logic characterized by a class of Kripke models (respectively, neighborhood models). Specifically, we prove that for every formula
$${\phi}$$
in the propositional modal language with A, there is a formula
$${\psi}$$
not containing A such that
$${\phi}$$
and
$${\psi}$$
are materially equivalent at the actual world in every Kripke model (respectively, neighborhood model). Inspection of the proofs leads to corresponding prooftheoretic results concerning the eliminability of the actuality operator in the actuality extension of any normal propositional modal logic and of any “classical” modal logic. As an application, we provide an alternative proof of a result of Williamson’s to the effect that the compound operator A□ behaves, in any normal logic between T and S5, like the simple necessity operator □ in S5.
more …
By
Hansoul, Georges; Teheux, Bruno
Post to Citeulike
14 Citations
This paper presents an algebraic approach of some manyvalued generalizations of modal logic. The starting point is the definition of the [0, 1]valued Kripke models, where [0, 1] denotes the well known MValgebra. Two types of structures are used to define validity of formulas: the class of frames and the class of Ł_{n}valued frames. The latter structures are frames in which we specify in each world u the set (a subalgebra of Ł_{n}) of the allowed truth values of the formulas in u. We apply and develop algebraic tools (namely, canonical and strong canonical extensions) to generate complete modal n + 1valued logics and we obtain manyvalued counterparts of Shalqvist canonicity result.
more …
By
Meadows, Toby
Post to Citeulike
I provide a tableau system and completeness proof for a revised version of Carnap’s semantics for quantified modal logic. For Carnap, a sentence is possible if it is true in some first order model. However, in a similar fashion to second order logic, no sound and complete proof theory can be provided for this semantics. This factor contributed to the ultimate disappearance of Carnapian modal logic from contemporary philosophical discussion. The proof theory I discuss comes close to Carnap’s semantic vision and provides an interesting counterpoint to mainstream approaches to modal logic. Despite its historical origins, my intention is to demonstrate that this approach to modal logic is worthy of contemporary attention and that current debate is the poorer for its absence.
more …
By
Punčochář, Vít
Post to Citeulike
4 Citations
In this paper, Carnap’s modal logic C is reconstructed. It is shown that the Carnapian approach enables us to create some epistemic logics in a relatively straightforward way. These epistemic modifications of C are axiomatized and one of them is compared with intuitionistic logic. At the end of the paper, some connections between this epistemic logic and Medvedev’s logic of finite problems and inquisitive semantics are shortly discussed.
more …
By
Lewitzka, Steffen
Post to Citeulike
4 Citations
There are logics where necessity is defined by means of a given identity connective:
$${\square\varphi := \varphi\equiv\top}$$
(
$${\top}$$
is a tautology). On the other hand, in many standard modal logics the concept of propositional identity (PI)
$${\varphi\equiv\psi}$$
can be defined by strict equivalence (SE)
$${\square(\varphi\leftrightarrow\psi)}$$
. All these approaches to modality involve a principle that we call the Collapse Axiom (CA): “There is only one necessary proposition.” In this paper, we consider a notion of PI which relies on the identity axioms of Suszko’s nonFregean logic SCI. Then S3 proves to be the smallest Lewis modal system where PI can be defined as SE. We extend S3 to a nonFregean logic with propositional quantifiers such that necessity and PI are integrated as noninterdefinable concepts. CA is not valid and PI refines SE. Models are expansions of SCImodels. We show that SCImodels are Boolean prealgebras, and viceversa. This associates nonFregean logic with research on Hyperintensional Semantics. PI equals SE iff models are Boolean algebras and CA holds. A representation result establishes a connection to Fine’s approach to propositional quantifiers and shows that our theories are conservative extensions of S3–S5, respectively. If we exclude the Barcan formula and a related axiom, then the resulting systems are still complete w.r.t. a simpler denotational semantics.
more …
By
Holliday, Wesley H.
Post to Citeulike
1 Citations
Viewing the language of modal logic as a language for describing directed graphs, a natural type of directed graph to study modally is one where the nodes are sets and the edge relation is the subset or superset relation. A wellknown example from the literature on intuitionistic logic is the class of Medvedev frames
$${\langle W, R\rangle}$$
where W is the set of nonempty subsets of some nonempty finite set S, and xRy iff
$${x\supseteq y}$$
, or more liberally, where
$${\langle W, R\rangle}$$
is isomorphic as a directed graph to
$${\langle \wp(S)\setminus\{\emptyset\},\supseteq\rangle}$$
. Prucnal (Stud Logica 38(3):247–262, 1979) proved that the modal logic of Medvedev frames is not finitely axiomatizable. Here we continue the study of Medvedev frames with extended modal languages. Our results concern definability. We show that the class of Medvedev frames is definable by a formula in the language of tense logic, i.e., with a converse modality for quantifying over supersets in Medvedev frames, extended with any one of the following standard devices: nominals (for naming nodes), a difference modality (for quantifying over those y such that
$${x\not= y}$$
), or a complement modality (for quantifying over those y such that
$${x\not\supseteq y}$$
). It follows that either the logic of Medvedev frames in one of these tense languages is finitely axiomatizable—which would answer the open question of whether Medvedev’s (Sov Math Dokl 7:857–860, 1966) “logic of finite problems” is decidable—or else the minimal logics in these languages extended with our defining formulas are the beginnings of infinite sequences of frameincomplete logics.
more …
By
Beklemishev, Lev D.; FernándezDuque, David; Joosten, Joost J.
Post to Citeulike
9 Citations
We introduce the logics GLP_{Λ}, a generalization of Japaridze’s polymodal provability logic GLP_{ω} where Λ is any linearly ordered set representing a hierarchy of provability operators of increasing strength. We shall provide a reduction of these logics to GLP_{ω} yielding among other things a finitary proof of the normal form theorem for the variablefree fragment of GLP_{Λ} and the decidability of GLP_{Λ} for recursive orderings Λ. Further, we give a restricted axiomatization of the variablefree fragment of GLP_{Λ}.
more …
By
Kooi, Barteld; Tamminga, Allard
Post to Citeulike
5 Citations
Every truthfunctional threevalued propositional logic can be conservatively translated into the modal logic S5. We prove this claim constructively in two steps. First, we define a Translation Manual that converts any propositional formula of any threevalued logic into a modal formula. Second, we show that for every S5model there is an equivalent threevalued valuation and vice versa. In general, our Translation Manual gives rise to translations that are exponentially longer than their originals. This fact raises the question whether there are threevalued logics for which there is a shorter translation into S5. The answer is affirmative: we present an elegant linear translation of the Logic of Paradox and of Strong Threevalued Logic into S5.
more …
By
Bezhanishvili, G.; Bezhanishvili, N.; LuceroBryan, J.; Mill, J.
Show all (4)
Post to Citeulike
It is a landmark theorem of McKinsey and Tarski that if we interpret modal diamond as closure (and hence modal box as interior), then
$$\mathsf S4$$
is the logic of any denseinitself metrizable space. The McKinsey–Tarski Theorem relies heavily on a metric that gives rise to the topology. We give a new and more topological proof of the theorem, utilizing Bing’s Metrization Theorem.
more …
By
Ma, Minghui; Chen, Jinsheng
Post to Citeulike
The global consequence relation of a normal modal logic
$$\Lambda $$
is formulated as a global sequent calculus which extends the local sequent theory of
$$\Lambda $$
with global sequent rules. All global sequent calculi of normal modal logics admits global cut elimination. This property is utilized to show that decidability is preserved from the local to global sequent theories of any normal modal logic over
$$\mathsf {K4}$$
. The preservation of Craig interpolation property from local to global sequent theories of any normal modal logic is shown by prooftheoretic method.
more …
By
Bergfeld, Jort M.; Kishida, Kohei; Sack, Joshua; Zhong, Shengyang
Show all (4)
Post to Citeulike
3 Citations
In this paper we show a duality between two approaches to represent quantum structures abstractly and to model the logic and dynamics therein. One approach puts forward a “quantum dynamic frame” (Baltag et al. in Int J Theor Phys, 44(12):2267–2282, 2005), a labelled transition system whose transition relations are intended to represent projections and unitaries on a (generalized) Hilbert space. The other approach considers a “Piron lattice” (Piron in Foundations of Quantum Physics, 1976), which characterizes the algebra of closed linear subspaces of a (generalized) Hilbert space. We define categories of these two sorts of structures and show a duality between them. This result establishes, on one direction of the duality, that quantum dynamic frames represent quantum structures correctly; on the other direction, it gives rise to a representation of dynamics on a Piron lattice.
more …
By
Eva, Benjamin
Post to Citeulike
Topos quantum theory (TQT) represents a whole new approach to the formalization of nonrelativistic quantum theory. It is well known that TQT replaces the orthomodular quantum logic of the traditional Hilbert space formalism with a new intuitionistic logic that arises naturally from the topos theoretic structure of the theory. However, it is less well known that TQT also has a dual logical structure that is paraconsistent. In this paper, we investigate the relationship between these two logical structures and study the implications of this relationship for the definition of modal operators in TQT.
more …
By
LuceroBryan, Joel
Post to Citeulike
2 Citations
We present a geometric construction that yields completeness results for modal logics including K4, KD4, GL and GL_{n} with respect to certain subspaces of the rational numbers. These completeness results are extended to the bimodal case with the universal modality.
more …
By
Bezhanishvili, Guram; Esakia, Leo; Gabelaia, David
Post to Citeulike
24 Citations
We consider two topological interpretations of the modal diamond—as the closure operator (Csemantics) and as the derived set operator (dsemantics). We call the logics arising from these interpretations Clogics and dlogics, respectively. We axiomatize a number of subclasses of the class of nodec spaces with respect to both semantics, and characterize exactly which of these classes are modally definable. It is demonstrated that the dsemantics is more expressive than the Csemantics. In particular, we show that the dlogics of the six classes of spaces considered in the paper are pairwise distinct, while the Clogics of some of them coincide.
more …
By
Fitting, Melvin; Thalmann, Lars; Voronkov, Andrei
Post to Citeulike
15 Citations
Many powerful logics exist today for reasoning about multiagent systems, but in most of these it is hard to reason about an infinite or indeterminate number of agents. Also the naming schemes used in the logics often lack expressiveness to name agents in an intuitive way.
To obtain a more expressive language for multiagent reasoning and a better naming scheme for agents, we introduce a family of logics called termmodal logics. A main feature of our logics is the use of modal operators indexed by the terms of the logics. Thus, one can quantify over variables occurring in modal operators. In termmodal logics agents can be represented by terms, and knowledge of agents is expressed with formulas within the scope of modal operators.
This gives us a flexible and uniform language for reasoning about the agents themselves and their knowledge. This article gives examples of the expressiveness of the languages and provides sequentstyle and tableaubased proof systems for the logics. Furthermore we give proofs of soundness and completeness with respect to the possible world semantics.
more …
By
Banick, Kyle
Post to Citeulike
Predicate approaches to modality have been a topic of increased interest in recent intensional logic. Halbach and Welch (Mind 118(469):71–100, 2009) have proposed a new formal technique to reduce the necessity predicate to an operator, demonstrating that predicate and operator methods are ultimately compatible. This article concerns the question of whether Halbach and Welch’s approach can provide a uniform formal treatment for intensionality. I show that the monotonicity constraint in Halbach and Welch’s proof for necessity fails for almost all possibleworlds theories of knowledge. The nonmonotonicity results demonstrate that the most obvious way of emulating Halbach and Welch’s rapprochement of the predicate and operator fails in the epistemic setting.
more …
By
Bezhanishvili, Guram; Bezhanishvili, Nick
Post to Citeulike
3 Citations
We introduce relativized modal algebra homomorphisms and show that the category of modal algebras and relativized modal algebra homomorphisms is dually equivalent to the category of modal spaces and partial continuous pmorphisms, thus extending the standard duality between the category of modal algebras and modal algebra homomorphisms and the category of modal spaces and continuous pmorphisms. In the transitive case, this yields an algebraic characterization of Zakharyaschev’s subreductions, cofinal subreductions, dense subreductions, and the closed domain condition. As a consequence, we give an algebraic description of canonical, subframe, and cofinal subframe formulas, and provide a new algebraic proof of Zakharyaschev’s theorem that each logic over K4 is axiomatizable by canonical formulas.
more …
