The language of the basic logic of proofs extends the usual propositional language by forming sentences of the sort x is a proof of F for any sentence F. In this paper a complete axiomatization for the basic logic of proofs in Heyting Arithmetic HA was found.

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)

Hereditary structural completeness is established for a range of substructural logics, mainly without the weakening rule, including fragments of various relevant or many-valued logics. Also, structural completeness is disproved for a range of systems, settling some previously open questions.

We study unification problem and problem of admissibility for inference rules in minimal Johanssonsʼ logic J and positive intuitionistic logic IPC+. This paper proves that the problem of admissibility for inference rules with coefficients is decidable for the paraconsistent minimal Johanssonsʼ logic J and the positive intuitionistic logic IPC+. Using obtained technique we show also that the unification problem for these logics is also decidable: we offer algorithms which compute complete sets of unifiers for any unifiable formula. Checking just unifiability (...) of formulas with coefficients also works via verification of admissibility. (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.

We develop canonical rules capable of axiomatizing all systems of multiple-conclusion rules over K4 or IPC, by extension of the method of canonical formulas by Zakharyaschev [37]. We use the framework to give an alternative proof of the known analysis of admissible rules in basic transitive logics, which additionally yields the following dichotomy: any canonical rule is either admissible in the logic, or it is equivalent to an assumption-free rule. Other applications of canonical rules include a generalization of the Blok–Esakia (...) theorem and the theory of modal companions to systems of multiple-conclusion rules or (finitary structural global) consequence relations, and a characterization of splittings in the lattices of consequence relations over monomodal or superintuitionistic logics with the finite model property. (shrink)

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.

This paper contains a proof-theoretic account of unification in transitive reflexive modal logics, which means that the reasoning is syntactic and uses as little semantics as possible. New proofs of theorems on unification types are presented and these results are extended to negationless fragments. In particular, a syntactic proof of Ghilardi’s result that $\mathsf {S4}$ has finitary unification is provided. In this approach the relation between classical valuations, projective unifiers, and admissible rules is clarified.

Admissible rules of a logic are those rules under which the set of theorems of the logic is closed. In this paper, a Gentzen-style framework is introduced for analytic proof systems that derive admissible rules of non-classical logics. While Gentzen systems for derivability treat sequents as basic objects, for admissibility, the basic objects are sequent rules. Proof systems are defined here for admissible rules of classes of modal logics, including K4, S4, and GL, and also Intuitionistic Logic IPC. With minor (...) restrictions, proof search in these systems terminates, giving decision procedures for admissibility in the logics. (shrink)

In this paper we study the admissible rules of intermediate logics. We establish some general results on extensions of models and sets of formulas. These general results are then employed to provide a basis for the admissible rules of the Gabbay–de Jongh logics and to show that these logics have finitary unification type.

We investigate finitarity of unification types in locally finite varieties of Heyting algebras, giving both positive and negative results. We make essential use of finite dualities within a conceptualization for E-unification theory 733–752) relying on the algebraic notion of a projective object.

We characterize (both from a syntactic and an algebraic point of view) the normal K4-logics for which unification is filtering. We also give a sufficient semantic criterion for existence of most general unifiers, covering natural extensions of K4.2⁺ (i.e., of the modal system obtained from K4 by adding to it, as a further axiom schemata, the modal translation of the weak excluded middle principle).

We extend and generalize the work on unifiability of [8]. We give a semantic characterization for unifiability and non-unifiability in the extensions of K4. We apply this in particular to extensions of KD4, GL and K4.3 to obtain a syntactic characterization and give a concrete decision procedure for unifiability for those logics. For that purpose we use universal models.

Unifiability of terms (and formulas) and structural completeness in the variety of relation algebras RA and in the products of modal logic S5 is investigated. Nonunifiable terms (formulas) which are satisfiable in varieties (in logics) are exhibited. Consequently, RA and products of S5 as well as representable diagonal-free n-dimensional cylindric algebras, RDfn, are almost structurally complete but not structurally complete. In case of S5n a basis for admissible rules and the form of all passive rules are provided.

We characterize all finitary consequence relations over S4.3, both syntactically, by exhibiting so-called passive rules that extend the given logic, and semantically, by providing suitable strongly adequate classes of algebras. This is achieved by applying an earlier result stating that a modal logic L extending S4 has projective unification if and only if L contains S4.3. In particular, we show that these consequence relations enjoy the strong finite model property, and are finitely based. In this way, we extend the known (...) results by Bull and Fine, from logics, to consequence relations. We also show that the lattice of consequence relations over S4.3 is countable and distributive and it forms a Heyting algebra. (shrink)

Uniform infinite bases are defined for the single-conclusion and multiple-conclusion admissible rules of the implication–negation fragments of intuitionistic logic and its consistent axiomatic extensions . A Kripke semantics characterization is given for the structurally complete implication–negation fragments of intermediate logics, and it is shown that the admissible rules of this fragment of form a PSPACE-complete set and have no finite basis.

A deductive system is said to be structurally complete if its admissible rules are derivable. In addition, it is called hereditarily structurally complete if all its extensions are structurally complete. Citkin (1978) proved that an intermediate logic is hereditarily structurally complete if and only if the variety of Heyting algebras associated with it omits five finite algebras. Despite its importance in the theory of admissible rules, a direct proof of Citkin’s theorem is not widely accessible. In this paper we offer (...) a self-contained proof of Citkin’s theorem, based on Esakia duality and the method of subframe formulas. As a corollary, we obtain a short proof of Citkin’s 2019 characterization of hereditarily structurally complete positive logics. (shrink)

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.

L.L. Maksimova and L. Esakia, V. Meskhi showed that the modal logic \ has exactly 5 pretabular extensions PM1–PM5. In this paper, we study the problem of unification for all given logics. We showed that PM2 and PM3 have finitary, and PM1, PM4, PM5 have unitary types of unification. Complete sets of unifiers in logics are described.

In this paper, we show that the implication fragment of classical propositional logic is finitary for unification with parameters.

The product of two |$\textbf {Alt}$| logics possesses the polynomial product finite model property and its membership problem is |$\textbf {coNP}$|-complete. Using a reduction from an undecidable domino-tiling problem, we prove that its admissibility problem is undecidable.

Epistemic logics are essential to the design of logical systems that capture elements of reasoning about knowledge. In this paper, we study the computability of unifiability and the unification types in several epistemic logics.

Contact Logics provide a natural framework for representing and reasoning about regions in several areas of computer science. In this paper, we focus our attention on reasoning methods for Contact Logics and address the satisfiability problem and the unifiability problem. Firstly, we give sound and complete tableaux-based decision procedures in Contact Logics and we obtain new results about the decidability/complexity of the satisfiability problem in these logics. Secondly, we address the computability of the unifiability problem in Contact Logics and we (...) obtain new results about the unification type of the unifiability problem in these logics. (shrink)

The problem of unification in a normal modal logic $L$ can be defined as follows: given a formula $\varphi$, determine whether there exists a substitution $\sigma$ such that $\sigma $ is in $L$. In this paper, we prove that for several non-symmetric non-transitive modal logics, there exists unifiable formulas that possess no minimal complete set of unifiers.

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.

The unification problem in a normal modal logic is to determine, given a formula.

We prove that a propositional Linear Temporal Logic with Until and Next has unitary unification. Moreover, for every unifiable in LTL formula A there is a most general projective unifier, corresponding to some projective formula B, such that A is derivable from B in LTL. On the other hand, it can be shown that not every open and unifiable in LTL formula is projective. We also present an algorithm for constructing a most general unifier.

We prove that $\textbf {K}5$ and some of its extensions that do not contain $\textbf {K}4$ are of unification type $1$.

Hume’s famous character Cleanthes claims that there is no difficulty in explaining the existence of causal chains with no first cause since in them each item is causally explained by its predecessor. Relying on logico-mathematical resources, we argue for two theses: (1) if the existence of Cleanthes’ chain can be explained at all, it must be explained by the fact that the causal law ruling it is in force, and (2) the fact that such a causal law is in force (...) cannot explain the occurrence of the events in the chain. In order to perform (1), we manage to express in mathematical terms the intuitive idea that indefinitely delayed explanation is ultimately no explanation. In order to achieve (2), we identify a logical relation we can prove to be as strong as the causal relation at issue in the Cleanthes passage, according to a precise notion of strength of relations. (shrink)