We give alternative characterizations of exact, extendible and projective formulas in intuitionistic propositional calculus IPC in terms of n -universal models. From these characterizations we derive a new syntactic description of all extendible formulas of IPC in two variables. For the formulas in two variables we also give an alternative proof of Ghilardi’s theorem that every extendible formula is projective.

We establish the dichotomy property for stable canonical multi-conclusion rules for IPC, K4, and S4. This yields an alternative proof of existence of explicit bases of admissible rules for these logics.

It is already known that unifiable formulas in normal modal logic |$\textbf {K}+\square ^{2}\bot $| are either finitary or unitary and unifiable formulas in normal modal logic |$\textbf {Alt}_{1}+\square ^{2}\bot $| are unitary. In this paper, we prove that for all |$d{\geq }3$|⁠, unifiable formulas in normal modal logic |$\textbf {K}+\square ^{d}\bot $| are either finitary or unitary and unifiable formulas in normal modal logic |$\textbf {Alt}_{1}+\square ^{d}\bot $| are unitary.

In the ordinary modal language, KD is the modal logic determined by the class of all serial frames. In this paper, we demonstrate that KD is nullary.

In this paper1 we study admissible consecutions in multi-modal logics with the universal modality. We consider extensions of multi-modal logic S4n augmented with the universal modality. Admissible consecutions form the largest class of rules, under which a logic is closed. We propose an approach based on the context effective finite model property. Theorem 7, the main result of the paper, gives sufficient conditions for decidability of admissible consecutions in our logics. This theorem also provides an explicit algorithm for recognizing such (...) consecutions. Some applications to particular logics with the universal modality are given. (shrink)

This paper offers a brief analysis of the unification problem in modal transitive logics related to the logic S4 : S4 itself, K4, Grz and Gödel-Löb provability logic GL . As a result, new, but not the first, algorithms for the construction of ‘best’ unifiers in these logics are being proposed. The proposed algorithms are based on our earlier approach to solve in an algorithmic way the admissibility problem of inference rules for S4 and Grz . The first algorithms for (...) the construction of ‘best’ unifiers in the above mentioned logics have been given by S. Ghilardi in [ 16 ]. Both the algorithms in [ 16 ] and ours are not much computationally efficient. They have, however, an obvious significant theoretical value a portion of which seems to be the fact that they stem from two different methodological approaches. (shrink)

The paper studies the logic TL(NBox+-wC) – logic of discrete linear time with current time point clusters. Its language uses modalities Diamond+ (possible in future) and Diamond- (possible in past) and special temporal operations, – Box+w (weakly necessary in future) and Box-w (weakly necessary in past). We proceed by developing an algorithm recognizing theorems of TL(NBox+-wC), so we prove that TL(NBox+-wC) is decidable. The algorithm is based on reduction of formulas to inference rules and converting the rules in special reduced (...) normal form, and, then, on checking validity of such rules in models of singleexponential size in the rules. Also we consider the admissibility problem for TL(NBox+-wC) and show how to reduce the problem for admissibility to the decidability of TL(NBox+-wC) itself using definable universal modalities. (shrink)

Visser's rules form a basis for the admissible rules of . Here we show that this result can be generalized to arbitrary intermediate logics: Visser's rules form a basis for the admissible rules of any intermediate logic for which they are admissible. This implies that if Visser's rules are derivable for then has no nonderivable admissible rules. We also provide a necessary and sufficient condition for the admissibility of Visser's rules. We apply these results to some specific intermediate logics and (...) obtain that Visser's rules form a basis for the admissible rules of, for example, De Morgan logic, and that Dummett's logic and the propositional Gödel logics do not have nonderivable admissible rules. (shrink)

We prove that the unification type of Łukasiewicz logic and of its equivalent algebraic semantics, the variety of MV-algebras, is nullary. The proof rests upon Ghilardiʼs algebraic characterisation of unification types in terms of projective objects, recent progress by Cabrer and Mundici in the investigation of projective MV-algebras, the categorical duality between finitely presented MV-algebras and rational polyhedra, and, finally, a homotopy-theoretic argument that exploits lifts of continuous maps to the universal covering space of the circle. We discuss the background (...) to such diverse tools. In particular, we offer a detailed proof of the duality theorem for finitely presented MV-algebras and rational polyhedra—a fundamental result that, albeit known to specialists, seems to appear in print here for the first time. (shrink)

We show that IPC, K4, GL, and S4, as well as all logics inheriting their admissible rules, have independent bases of admissible rules.

We investigate the computational complexity of deciding whether a given inference rule is admissible for some modal and superintuitionistic logics. We state a broad condition under which the admissibility problem is coNEXP-hard. We also show that admissibility in several well-known systems (including GL, S4, and IPC) is in coNE, thus obtaining a sharp complexity estimate for admissibility in these systems.

By a well-known result of Cook and Reckhow [S.A. Cook, R.A. Reckhow, The relative efficiency of propositional proof systems, Journal of Symbolic Logic 44 36–50; R.A. Reckhow, On the lengths of proofs in the propositional calculus, Ph.D. Thesis, Department of Computer Science, University of Toronto, 1976], all Frege systems for the classical propositional calculus are polynomially equivalent. Mints and Kojevnikov [G. Mints, A. Kojevnikov, Intuitionistic Frege systems are polynomially equivalent, Zapiski Nauchnyh Seminarov POMI 316 129–146] have recently shown p-equivalence of (...) Frege systems for the intuitionistic propositional calculus in the standard language, building on a description of admissible rules of IPC by Iemhoff [R. Iemhoff, On the admissible rules of intuitionistic propositional logic, Journal of Symbolic Logic 66 281–294]. We prove a similar result for an infinite family of normal modal logics, including K4, GL, S4, and. (shrink)

This paper contains a brief overview of the area of admissible rules with an emphasis on results about intermediate and modal propositional logics. No proofs are given but many references to the literature are provided.

If the Visser rules are admissible for an intermediate logic, they form a basis for the admissible rules of the logic. How to characterize the admissible rules of intermediate logics for which not all of the Visser rules are admissible is not known. In this paper we give a brief overview of results on admissible rules in the context of intermediate logics. We apply these results to some well-known intermediate logics. We provide natural examples of logics for which the Visser (...) rule are derivable, admissible but nonderivable, or not admissible. (shrink)

In this paper we prove that three of the main propositional logics of dependence, none of which is structural, are structurally complete with respect to a class of substitutions under which the logics are closed. We obtain an analogous result with respect to stable substitutions, for the negative variants of some well-known intermediate logics, which are intermediate theories that are closely related to inquisitive logic.

Many intermediate logics, even extremely well-behaved ones such as IPC, lack the finite model property for admissible rules. We give conditions under which this failure holds. We show that frames which validate all admissible rules necessarily satisfy a certain closure condition, and we prove that this condition, in the finite case, ensures that the frame is of width 2. Finally, we indicate how this result is related to some classical results on finite, free Heyting algebras.

Refutation systems are formal systems for inferring the falsity of formulae. These systems can, in particular, be used to syntactically characterise logics. In this paper, we explore the close connection between refutation systems and admissible rules. We develop technical machinery to construct refutation systems, employing techniques from the study of admissible rules. Concretely, we provide a refutation system for the intermediate logics of bounded branching, known as the Gabbay–de Jongh logics. We show that this gives a characterisation of these logics (...) in terms of their admissible rules. To illustrate the technique, we also provide a refutation system for Medvedev’s logic. (shrink)

We present an algorithm, based both on semantic tableaux and resolution, which is able to check the projectivity of a formula in intuitionistic propositional calculus. Suitably iterated, it also computes projective approximations, thus providing best E-unifiers for the equational theory of Heyting algebras. Applications to admissible inference rules are immediate.