This paper studies a propositional logic which is obtained by interpreting implication as formal provability. It is also the logic of finite irreflexive Kripke Models.A Kripke Model completeness theorem is given and several completeness theorems for interpretations into Provability Logic and Peano Arithmetic.

Modern modal logic originated as a branch of philosophical logic in which the concepts of necessity and possibility were investigated by means of a pair of dual operators that are added to a propositional or first-order language. The field owes much of its flavor and success to the introduction in the 1950s of the “possible-worlds” semantics in which the modal operators are interpreted via some “accessibility relation” connecting possible worlds. In subsequent years, modal logic has received attention as an attractive (...) approach towards formalizing such diverse notions as time, knowledge, or action. Nowadays, modal logics are applied in various disciplines, ranging from economics to linguistics and computer science. Consequently, there is by now a large variety of modal languages, with an even greater wealth of interpretations. For instance, many applications require a poly-modal framework consisting of a language with a family of modal operators and a semantics in which the corresponding accessibility relations are connected somehow. (shrink)

Medvedev's intermediate logic (MV) can be defined by means of Kripke semantics as the family of Kripke frames given by finite Boolean algebras without units as partially ordered sets. The aim of this paper is to present a proof of the theorem: For every set of connectives such that the-fragment ofMV equals the fragment of intuitionistic logic. The final part of the paper brings the negative solution to the problem set forth by T. Hosoi and H. Ono, namely: is an (...) intermediate logic based on the axiom (abc) (ab)(a c) separable? (shrink)

Medvedev's intermediate logic (MV) can be defined by means of Kripke semantics as the family of Kripke frames given by finite Boolean algebras without units as partially ordered sets. The aim of this paper is to present a proof of the theorem: For every set of connectives Φ such that {→, ∨, ⅂}  Φ (m=subseteq) {→, ∧, ∨, ⅂}, the Φ-fragment of MV equals the Φ-fragment of intuitionistic logic. The final part of the paper brings the negative solution to (...) the problem set forth by T. Hosoi and H. Ono, namely: is an intermediate logic based on the axiom (⅂a→b ∨ c) → (⅂a→b) ∨ (⅂a→c) separable? (shrink)

We investigate the effect on the complexity of adding the universal modality and the reflexive transitive closure modality to modal logics. From the examples in the literature, one might conjecture that adding the reflexive transitive closure modality is at least as hard as adding the universal modality, and that adding either of these modalities to a multi-modal logic where the modalities do not interact can only increase the complexity to EXPTIME-complete. We show that the first conjecture holds under reasonable assumptions (...) and that, except for a number of special cases which we fully characterize, the hardness part of the second conjecture is true. However, the upper bound part of the second conjecture fails miserably: we show that there exists a uni-modal, decidable, finitely axiomatizable, and canonical logic for which adding the universal modality causes undecidability and for which adding the reflexive transitive closure modality causes high undecidability. (shrink)

For a novice this book is a mathematically-oriented introduction to modal logic, the discipline within mathematical logic studying mathematical models of reasoning which involve various kinds of modal operators. It starts with very fundamental concepts and gradually proceeds to the front line of current research, introducing in full details the modern semantic and algebraic apparatus and covering practically all classical results in the field. It contains both numerous exercises and open problems, and presupposes only minimal knowledge in mathematics. A specialist (...) can use the book as a source of references. Results and methods of many directions in propositional modal logic, from completeness and duality to algorithmic problems, are collected and systematically presented in one volume. (shrink)