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 present a basis for the admissible rules of intuitionistic propositional logic. Thereby a conjecture by de Jongh and Visser is proved. We also present a proof system for the admissible rules, and give semantic criteria for admissibility.

This paper concerns modal logics of provability — Gödel-Löb systemGL and Solovay logicS — the smallest and the greatest representation of arithmetical theories in propositional logic respectively. We prove that the decision problem for admissibility of rules (with or without parameters) inGL andS is decidable. Then we get a positive solution to Friedman''s problem forGL andS. We also show that A. V. Kuznetsov''s problem of the existence of finite basis for admissible rules forGL andS has a negative solution. Afterwards we (...) give an algorithm deciding the solvability of logical equations inGL andS and constructing some solutions. (shrink)

This chapter contains sections titled: Enriching Extensional Logic with Intensional Notions Changing Views of Modal Logic A Précis of Basic Modal Logic The Major Applications Fine‐Structure of Expressive Power System Combination: Action and Information Back to the Heartland Conclusion.

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)

This paper was written with two aims in mind. A large part of it is just an exposition of Tarski's theory of truth. Philosophers do not agree on how Tarski's theory is related to their investigations. Some of them doubt whether that theory has any relevance to philosophical issues and in particular whether it can be applied in dealing with the problems of philosophy (theory) of science.In this paper I argue that Tarski's chief concern was the following question. Suppose a (...) language L belongs to the class of languages for which, in full accordance with some formal conditions set in advance, we are able to define the class of all the semantic interpretations the language may acquire. Every interpretation of L can be viewed as a certain structure to which the expressions of the language may refer. Suppose that a specific interpretation of the language L was singled out as the intended one. Suppose, moreover, that the intended interpretation can be characterized in a metalanguage L +. If the above assumptions are satisfied, can the notion of truth for L be defined in the metalanguage L + and, if it can, how can this be done? (shrink)

This paper was written with two aims in mind. A large part of it is just an exposition of Tarski’s theory of truth. Philosophers do not agree on how Tarski’s theory is related to their investigations. Some of them doubt whether that theory has any relevance to philosophical issues and in particular whether it can be applied in dealing with the problems of philosophy (theory) of science. In this paper I argue that Tarski’s chief concern was the following question. Suppose (...) a language L belongs to the class of languages for which, in full accordance with some formal conditions set in advance, we are able to define the class of all the semantic interpretations the language may acquire. Every interpretation of L can be viewed as a certain structure to which the expressions of the language may refer. Suppose that a specific interpretation of the language L was singled out as the intended one. Suppose, moreover, that the intended interpretation can be characterized in a metalanguage L +. If the above assumptions are satisfied, can the notion of truth for L be defined in the metalanguage L + and, if it can, how can this be done? Many students of Tarski’s conception will find the above exposition inconsistent with their own views on the essence of Tarski’s conception. On the other hand, as it is argued in this paper, the proposed interpretation of Tarski’s ideas allows one to use Tarski’s theory as a fundamental tool for semantic analyses of various theories, factual theories in particular. More specifically, it is argued that Tarski’s theory of truth allows one to clearly oppose a theory meant to be certain deductive system (a set of accepted sentences, say axioms, and a logical machinery for deducing from them new ones) and a theory meant to be a certain semantic system, i.e a set of sentences that serve to communicate some states of affairs and to use that opposition to explicate and occasionally also define the notion of truth. The opposition in question is of the utmost significance for analyzing some developments in both mathematics and factual sciences. The approach which is concerned with the logical relations between the elements of science such an approach is throughout this paper called analytical is put into question. The growth of science is determined by how well scientific theories are able to account for factual states of affairs. The intuitive notion of truth applied by the scientists does not necessarily correspond in a straightforward way to its Tarskian counterpart. On the other hand, as is claimed in this paper, the Tarskian notion of truth offers as adequate explication of intuitive notion of truth as possible. (shrink)

Unification was originally introduced in automated deduction and term rewriting, but has recently also found applications in other fields. In this article, we give a survey of the results on unification obtained in two closely related, yet different, application areas of unification: description logics and modal logics.

This paper was written with two aims in mind. A large part of it is just an exposition of Tarski’s theory of truth. Philosophers do not agree on how Tarski’s theory is related to their investigations. Some of them doubt whether that theory has any relevance to philosophical issues and in particular whether it can be applied in dealing with the problems of philosophy (theory) of science. In this paper I argue that Tarski’s chief concern was the following question. Suppose (...) a language L belongs to the class of languages for which, in full accordance with some formal conditions set in advance, we are able to define the class of all the semantic interpretations the language may acquire. Every interpretation of L can be viewed as a certain structure to which the expressions of the language may refer. Suppose that a specific interpretation of the language L was singled out as the intended one. Suppose, moreover, that the intended interpretation can be characterized in a metalanguage L +. If the above assumptions are satisfied, can the notion of truth for L be defined in the metalanguage L + and, if it can, how can this be done? Many students of Tarski’s conception will find the above exposition inconsistent with their own views on the essence of Tarski’s conception. On the other hand, as it is argued in this paper, the proposed interpretation of Tarski’s ideas allows one to use Tarski’s theory as a fundamental tool for semantic analyses of various theories, factual theories in particular. More specifically, it is argued that Tarski’s theory of truth allows one to clearly oppose a theory meant to be certain deductive system (a set of accepted sentences, say axioms, and a logical machinery for deducing from them new ones) and a theory meant to be a certain semantic system, i.e a set of sentences that serve to communicate some states of affairs and to use that opposition to explicate and occasionally also define the notion of truth. The opposition in question is of the utmost significance for analyzing some developments in both mathematics and factual sciences. The approach which is concerned with the logical relations between the elements of science such an approach is throughout this paper called analytical is put into question. The growth of science is determined by how well scientific theories are able to account for factual states of affairs. The intuitive notion of truth applied by the scientists does not necessarily correspond in a straightforward way to its Tarskian counterpart. On the other hand, as is claimed in this paper, the Tarskian notion of truth offers as adequate explication of intuitive notion of truth as possible. (shrink)

While specifications and verifications of concurrent systems employ Linear Temporal Logic , it is increasingly likely that logical consequence in image will be used in the description of computations and parallel reasoning. Our paper considers logical consequence in the standard image with temporal operations image and image . The prime result is an algorithm recognizing consecutions admissible in image, so we prove that image is decidable w.r.t. admissible inference rules. As a consequence we obtain algorithms verifying the validity of consecutions (...) in image and solving the satisfiability problem. We start by a simple reduction of logical consecutions of image to equivalent ones in the reduced normal form . Then we apply a semantic technique based on image-Kripke structures with formula definable subsets. This yields necessary and sufficient conditions for a consecution to be not admissible in image. These conditions lead to an algorithm which recognizes consecutions admissible in image by verifying the validity of consecutions in special finite Kripke structures of size square polynomial in reduced normal forms of the consecutions. As a consequence, this also solves the satisfiability problem for image. (shrink)

We show that the variety of Heyting algebras has finitary unification type. We also show that the subvariety obtained by adding it De Morgan law is the biggest variety of Heyting algebras having unitary unification type. Proofs make essential use of suitable characterizations (both from the semantic and the syntactic side) of finitely presented projective algebras.

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

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.

An algorithm recognizing admissibility of inference rules in generalized form (rules of inference with parameters or metavariables) in the intuitionistic calculus H and, in particular, also in the usual form without parameters, is presented. This algorithm is obtained by means of special intuitionistic Kripke models, which are constructed for a given inference rule. Thus, in particular, the direct solution by intuitionistic techniques of Friedman's problem is found. As a corollary an algorithm for the recognition of the solvability of logical equations (...) in H and for constructing some solutions for solvable equations is obtained. A semantic criterion for admissibility in H is constructed. (shrink)

Questions connected with the admissibility of rules of inference and the solvability of the substitution problem for modal and intuitionistic logic are considered in an algebraic framework. The main result is the decidability of the universal theory of the free modal algebra imageω extended in signature by adding constants for free generators. As corollaries we obtain: there exists an algorithm for the recognition of admissibility of rules with parameters in the modal system Grz, the substitution problem for Grz and for (...) the intuitionistic calculus H is decidable, intuitionistic propositional calculus H is decidable with respect to admissibility . A semantical criterion for the admissibility of rules of inference in Grz is given. (shrink)

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)

We show that some common varieties of modal K4-algebras have finitary unification type, thus providing effective best solutions for equations in free algebras. Applications to admissible inference rules are immediate.