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.

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)

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)

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)

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)