We present an axiomatization for Basic Propositional Calculus BPC and give a completeness theorem for the class of transitive Kripke structures. We present several refinements, including a completeness theorem for irreflexive trees. The class of intermediate logics includes two maximal nodes, one being Classical Propositional Calculus CPC, the other being E1, a theory axiomatized by T → ⊥. The intersection CPC ∩ E1 is axiomatizable by the Principle of the Excluded Middle A V ∨ ⌝A. If B is a formula (...) such that → B is not derivable, then the lattice of formulas built from one propositional variable p using only the binary connectives, is isomorphically preserved if B is substituted for p. A formula → B is derivable exactly when B is provably equivalent to a formula of the form → A) →. (shrink)

We investigate logical consequence in temporal logics in terms of logical consecutions. i.e., inference rules. First, we discuss the question: what does it mean for a logical consecution to be 'correct' in a propositional logic. We consider both valid and admissible consecutions in linear temporal logics and discuss the distinction between these two notions. The linear temporal logic LDTL, consisting of all formulas valid in the frame 〈L, ≤, ≥〉 of all integer numbers, is the prime object of our investigation. (...) We describe consecutions admissible LDTL in a semantic way—via consecutions valid in special temporal Kripke/Hintikka models. Then we state that any temporal inference rule has a reduced normal form which is given in terms of uniform formulas of temporal degree 1. Using these facts and enhanced semantic techniques we construct an algorithm, which recognizes consecutions admissible in LDTL. Also, we note that using the same technique it follows that the linear temporal logic L (N) of all natural numbers is also decidable w.r.t. inference rules. So, we prove that both logics LDTL and L (N) are decidable w.r.t. admissible consecutions. In particular, as a consequence, they both are decidable (Known fact), and the given deciding algorithms are explicit. (shrink)

Gabbay has gathered an enormous amount of results; some of them important and novel, others important but already known, many rather routine, however. The organization of this material shows grave defects, both in the exposition and in its logical structure. Intensional logic appears as a vast collection of (often duplicated) loosely connected results. This may be a true reflection of the present state of the subject, but it does not contribute to a better understanding of it, let alone advance it.

Coming fromI andCl, i.e. from intuitionistic and classical propositional calculi with the substitution rule postulated, and using the sign to add a new connective there have been considered here: Grzegorozyk's logicGrz, the proof logicG and the proof-intuitionistic logicI set up correspondingly by the calculiFor any calculus we denote by the set of all formulae of the calculus and by the lattice of all logics that are the extensions of the logic of the calculus, i.e. sets of formulae containing the axioms (...) of and closed with respect to its rules of inference. In the logiclG the sign is decoded as follows: A = (A & A). The result of placing in the formulaA before each of its subformula is denoted byTrA. The maps are defined (in the definitions of x and the decoding of is meant), by virtue of which the diagram is constructed. (shrink)

Kripke-style models with two accessibility relations, one intuitionistic and the other modal, are given for analogues of the modal systemK based on Heyting's prepositional logic. It is shown that these two relations can combine with each other in various ways. Soundness and completeness are proved for systems with only the necessity operator, or only the possibility operator, or both. Embeddings in modal systems with several modal operators, based on classical propositional logic, are also considered. This paper lays the ground for (...) an investigation of intuitionistic analogues of systems stronger thanK. A brief survey is given of the existing literature on intuitionistic modal logic. (shrink)

Tematyka pracy nawiązuje do niezmiernie ważnego nurtu badań logicznych - badań algebr wolnych w klasie algebraicznych (matrycowych) modeli danego rachunku logicznego i uzyskiwanie charakteryzacji tzw. algebr Lindenbauma. Rozważania prowadzone są w dwóch przypadkach: nieskończonej logiki Łukasiewicze i skończenie wartościowych logik Łukasiewicza. W przypadku pierwszym algebraicznymi modelami są tzw. MVn-algebry Changa, a w drugim zdefiniowane przez autora MVn-algebry. Głównymi wynikami są: twierdzenie 4 podające kształt wolnej m-generowanej MNm-algebry oraz twierdzenie 5, uogólniające ten rezultat na klasę algebr Changa.

Propositional modal logic over relational frames is naturally extended with propositional quantifiers by letting them range over arbitrary sets of worlds of the relevant frame. This is also known as second-order propositional modal logic. The propositionally quantified modal logic of a class of relational frames is often not axiomatizable, although there are known exceptions, most notably the case of frames validating the strong modal logic $\mathrm {S5}$. Here, we develop new general methods with which many of the open questions in (...) this area can be answered. We illustrate the usefulness of these methods by applying them to a range of examples, which provide a detailed picture of which normal modal logics define classes of relational frames whose propositionally quantified modal logic is axiomatizable. We also apply these methods to establish new results in the multimodal case. (shrink)

A cardinality result in modal propositional logic.

Gödel logic is the extension of intuitionistic logic by the linearity axiom. Symmetric Gödel logic is a logical system, the language of which is an enrichment of the language of Gödel logic with their dual logical connectives. Symmetric Gödel logic is the extension of symmetric intuitionistic logic. The proof-intuitionistic calculus, the language of which is an enrichment of the language of intuitionistic logic by modal operator was investigated by Kuznetsov and Muravitsky. Bimodal symmetric Gödel logic is a logical system, the (...) language of which is an enrichment of the language of Gödel logic with their dual logical connectives and two modal operators. Bimodal symmetric Gödel logic is embedded into an extension of Gödel–Löb logic, the language of which contains disjunction, conjunction, negation and two modal operators. The variety of bimodal symmetric Gödel algebras, that represent the algebraic counterparts of bimodal symmetric Gödel logic, is investigated. Description of free algebras and characterization of projective algebras in the variety of bimodal symmetric Gödel algebras is given. All finitely generated projective bimodal symmetric Gödel algebras are infinite, while finitely generated projective symmetric Gödel algebras are finite. (shrink)

This paper investigates logical aspects of combining linear orders as semantics for modal and temporal logics, with modalities for possible paths, resulting in a variety of branching time logics over classes of trees. Here we adopt a unified approach to the Priorean, Peircean and Ockhamist semantics for branching time logics, by considering them all as fragments of the latter, obtained as combinations, in various degrees, of languages and semantics for linear time with a modality for possible paths. We then consider (...) a hierarchy of natural classes of trees and bundled trees arising from a given class of linear orders and show that in general they provide different semantics. We also discuss transfer of definability from linear orders to trees and introduce a uniform translation from Priorean to Peircean formulae which transfers definability of properties of linear orders to definability of properties of all paths in trees. (shrink)

We investigate the major mathematical theories of space from a modal standpoint: topology, affine geometry, metric geometry, and vector algebra. This allows us to see new fine-structure in spatial patterns which suggests analogies across these mathematical theories in terms of modal, temporal, and conditional logics. Throughout the modal walk through space, expressive power is analyzed in terms of language design, bisimulations, and correspondence phenomena. The result is both unification across the areas visited, and the uncovering of interesting new questions.

The paper presents a survey of author's results on definable fixed points in modal, temporal, and intuitionistic propositional logics. The well-known Fixed Point Theorem considers the modalized case, but here we investigate the positive case. We give a classification of fixed point theorems, describe some classes of models with definable least fixed points of positive operators, special positive operators, and give some examples of undefinable least fixed points. Some other interesting phenomena are discovered – definability by formulas that do not (...) preserve positivity of parameters and definability by finite sets of formulas. We also consider negative operators, graded modalities, construct undefinable inflationary fixed points, and put some problems. (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)

In Ockhamist branching-time logic [Prior 67], formulas are meant to be evaluated on a specified branch, or history, passing through the moment at hand. The linguistic counterpart of the manifoldness of future is a possibility operator which is read as `at some branch, or history (passing through the moment at hand)'. Both the bundled-trees semantics [Burgess 79] and the $\langle moment, history\rangle$ semantics [Thomason 84] for the possibility operator involve a quantification over sets of moments. The Ockhamist frames are (3-modal) (...) Kripke structures in which this second-order quantification is represented by a first-order quantification. The aim of the present paper is to investigate the notions of modal definability, validity, and axiomatizability concerning 3-modal frames which can be viewed as generalizations of Ockhamist frames. (shrink)

Tense logics in the bimodal propositional language are investigated with respect to the Finite Model Property. In order to prove positive results techniques from investigations of modal logics above K4 are extended to tense logic. General negative results show the limits of the transfer.

It is shown that the many-dimensional modal logic K n , determined by products of n-many Kripke frames, is not finitely axiomatisable in the n-modal language, for any $n > 2$ . On the other hand, K n is determined by a class of frames satisfying a single first-order sentence.

We consider some modal languages with a modal operator $D$ whose semantics is based on the relation of inequality. Basic logical properties such as definability, expressive power and completeness are studied. Also, some connections with a number of other recent proposals to extend the standard modal language are pointed at.

In the propositional modal treatment of two-variable first-order logic equality is modelled by a ‘diagonal’ constant, interpreted in square products of universal frames as the identity relation. Here we study the decision problem of products of two arbitrary modal logics equipped with such a diagonal. As the presence or absence of equality in two-variable first-order logic does not influence the complexity of its satisfiability problem, one might expect that adding a diagonal to product logics in general is similarly harmless. We (...) show that this is far from being the case, and there can be quite a big jump in complexity, even from decidable to the highly undecidable. Our undecidable logics can also be viewed as new fragments of first-order logic where adding equality changes a decidable fragment to undecidable. We prove our results by a novel application of counter machine problems. While our formalism apparently cannot force reliable counter machine computations directly, the presence of a unique diagonal in the models makes it possible to encode both lossy and insertion-error computations, for the same sequence of instructions. We show that, given such a pair of faulty computations, it is then possible to reconstruct a reliable run from them. (shrink)

Tense logics formulated in the bimodal propositional language are investigated with respect to Kripke-completeness (completeness) and decidability. It is proved that all minimal tense extensions of modal logics of finite width (in the sense of K. Kine) as well as all minimal tense extensions of cofinal subframe logics (in the sense of M. Zakharyaschev) are complete. The decidability of all finitely axiomatizable minimal tense extensions of cofinal subframe logics is shown. A number of variations and extensions of these results are (...) also presented. (shrink)

It is proved that all bimodal tense logics which contain the logic of the weak orderings and have unbounded depth do not have the interpolation property.

This paper concerns modal logics appearing from the temporal ordering of domains in two-dimensional Minkowski spacetime. As R. Goldblatt has proved recently, the logic of the whole plane isS4.2. We consider closed or open convex polygons and closed or open domains bounded by simple differentiable curves; this leads to the logics:S4,S4.1,S4.2 orS4.1.2.

This paper studies modal logics whose extensions all have the finite model property, those whose extensions are all recursively axiomatizable, and those whose extensions are all finitely axiomatizable. We call such logics FMP-ensuring, RA-ensuring and FA-ensuring respectively, and prove necessary and sufficient conditions of such logics in $$\mathsf {NExtK4.3}$$. Two infinite descending chains $$\{{\textbf{S}}_{k}\}_{k\in \omega }$$ and $$\{{\textbf{S}} _{k}^{*}\}_{k\in \omega }$$ of logics are presented, in terms of which the necessary and sufficient conditions are formulated as follows: A logic in (...) $$\mathsf {NExtK4.3}$$ is FMP-ensuring iff it extends $${\textbf{S}}_{k}$$ for some $$k\in \omega $$, it is RA-ensuring iff it extends $${\textbf{S}}_{k}^{*}$$ for some $$k\in \omega $$, and it is FA-ensuring iff it is finitely axiomatizable and extends $${\textbf{S}}_{k}^{*}$$ for some $$k\in \omega $$. (shrink)

Defeasible conditionals are statements of the form ‘if A then normally B’. One plausible interpretation introduced in nonmonotonic reasoning dictates that ) is true iff B is true in ‘most’ A-worlds. In this paper, we investigate defeasible conditionals constructed upon a notion of ‘overwhelming majority’, defined as ‘truth in a cofinite subset of \’, the first infinite ordinal. One approach employs the modal logic of the frame \\), used in the temporal logic of discrete linear time. We introduce and investigate (...) conditionals, defined modally over \\); several modal definitions of the conditional connective are examined, with an emphasis on the nonmonotonic ones. An alternative interpretation of ‘majority’ as sets cofinal ) rather than cofinite ) is examined. For these modal approaches over \\), a decision procedure readily emerges, as the modal logic \ of this frame is well-known and a translation of the conditional sentences can be mechanically checked for validity; this allows also for a quick proof of \-completeness of the satisfiability problem for these logics. A second approach employs the conditional version of Scott-Montague semantics, in the form of \-many possible worlds, endowed with neighborhoods populated by collections of cofinite subsets of \. This approach gives rise to weak conditional logics, as expected. The relative strength of the conditionals introduced is compared to KLM logics and other conditional logics in the literature. (shrink)

We show that monadic intuitionistic quantifiers admit the following temporal interpretation: “always in the future” (for$\forall $) and “sometime in the past” (for$\exists $). It is well known that Prior’s intuitionistic modal logic${\sf MIPC}$axiomatizes the monadic fragment of the intuitionistic predicate logic, and that${\sf MIPC}$is translated fully and faithfully into the monadic fragment${\sf MS4}$of the predicate${\sf S4}$via the Gödel translation. To realize the temporal interpretation mentioned above, we introduce a new tense extension${\sf TS4}$of${\sf S4}$and provide a full and faithful translation (...) of${\sf MIPC}$into${\sf TS4}$. We compare this new translation of${\sf MIPC}$with the Gödel translation by showing that both${\sf TS4}$and${\sf MS4}$can be translated fully and faithfully into a tense extension of${\sf MS4}$, which we denote by${\sf MS4.t}$. This is done by utilizing the relational semantics for these logics. As a result, we arrive at the diagram of full and faithful translations shown in Figure 1 which is commutative up to logical equivalence. We prove the finite model property (fmp) for${\sf MS4.t}$using algebraic semantics, and show that the fmp for the other logics involved can be derived as a consequence of the fullness and faithfulness of the translations considered. (shrink)