Search

We propose a notion of the Kripke-style model for intersection logic. Using a game interpretation, we prove soundness and completeness of the proposed semantics. In other words, a formula is provable (a type is inhabited) if and only if it is forced in every model. As a by-product, we obtain another proof of normalization for the Barendregt–Coppo–Dezani intersection type assignment system.

I show that the logic $\textsf {TJK}^{d+}$ , one of the strongest logics currently known to support the naive theory of truth, is obtained from the Kripke semantics for constant domain intuitionistic logic by (i) dropping the requirement that the accessibility relation is reflexive and (ii) only allowing reflexive worlds to serve as counterexamples to logical consequence. In addition, I provide a simplified natural deduction system for $\textsf {TJK}^{d+}$ , in which a restricted form of conditional proof is used to establish conditionals.

Following K. Segerberg [22] , D. Kozen [15] and V. Pratt [19] , who have been introduced dynamic propositional logic and dynamic algebras, dynamic propositional Łukasiewicz logic DPŁ (dynamic n-valued propositional Łukasiewicz logic D P Ł n ) and dynamic MV-algebras (dynamic M V n -algebras) are introduced and theories of the logic DPŁ ( D P Ł n ) and dynamic MV-algebras ( M V n -algebras) are developed. Dynamic MV-algebras (dynamic M V n -algebras) are algebraic counterparts of the logic DPŁ ( D P Ł n ), that in turn represent two-sorted algebras that combine the varieties of MV-algebras ( M V n -algebras) ( M , ⊕ , ⊙ , ∼ , 0 , 1 ) and regular algebras ( R , ∪ , ; , ⁎ ) into a single finitely axiomatized variety ( M , R , ◇ ) resembling R-module with “scalar” multiplication ◇. Kripke semantics is developed for dynamic propositional Łukasiewicz logic (dynamic n-valued propositional Łukasiewicz logic D P Ł n ).

We present the logic $${\mathsf {LCB}}$$ LCB which is expressed in a propositional language constantly enriched by new atomic expressions. Our formal framework is the propositional doxastic logic $${\mathsf {KD45}}$$ KD 45 with the belief operator $${\mathcal {B}}$$ B , extended by the $${\mathcal {C}}$$ C operator, to be read it changes that ... . We describe the changing beliefs of an agent who uses progressively expanding language. The approach presented here allows us to weaken pragmatic objections to the so-called principle of negative retrospection accepted in $${\mathsf {KD45}}$$ KD 45 and the problem of logical omniscience. In what follows, we present the expanding propositional language used in our formalism, interpreted using an epistemic version of Kripke semantics. Next, we give a syntactic characterization of logic $${\mathsf {LCB}}$$ LCB and prove the soundness and completeness of $${\mathsf {LCB}}$$ LCB in respect to our semantics. Finally, we compare the idea of expanding language with the notion of agent awareness and we relate our formalism to two epistemic temporal logics.

This paper proposes a generalization of the Kripke semantics of intuitionistic logicIL appropriate forintuitionistic Łukasiewicz logicIŁL —a logic in the intersection betweenIL and (classical) Łukasiewicz logic. This generalised Kripke semantics is based on theposet sumconstruction, used in Bova and Montagna (Theoret Comput Sci 410(12):1143–1158, 2009). to show the decidability (and PSPACE completeness) of the quasiequational theory of commutative, integral and bounded GBL algebras. The main idea is that$$w \Vdash \psi $$w⊩ψ—which forILis a relation between worldswand formulas$$\psi $$ψ, and can be seen as a function taking values in the booleans$$(w \Vdash \psi ) \in {{\mathbb {B}}}$$(w⊩ψ)∈B—becomes a function taking values in the unit interval$$(w \Vdash \psi ) \in [0,1]$$(w⊩ψ)∈[0,1]. An appropriate monotonicity restriction (which we callsloping functions) needs to be put on such functions in order to ensure soundness and completeness of the semantics.

Dynamic epistemic logic is a logic that is aimed at formally expressing how a person’s knowledge changes. We provide a cut-free labelled sequent calculus ($\textbf{GDEL}$) on the background of existing studies of Hilbert-style axiomatization $\textbf{HDEL}$ of dynamic epistemic logic and labelled calculi for public announcement logic. We first show that the $cut$ rule is admissible in $\textbf{GDEL}$ and show that $\textbf{GDEL}$ is sound and complete for Kripke semantics. Moreover, we show that the basis of $\textbf{GDEL}$ is extended from modal logic K to other familiar modal logics including S5 with keeping the admissibility of cut, soundness and completeness.

Propositional and modal inclusion logic are formalisms that belong to the family of logics based on team semantics. This article investigates the model checking and validity problems of these logics. We identify complexity bounds for both problems, covering both lax and strict team semantics. By doing so, we come close to finalizing the programme that aims to completely classify the complexities of the basic reasoning problems for modal and propositional dependence, independence and inclusion logics.

We can look at a first-order (or propositional) intuitionistic Kripke model as an ordered set of classical models. In this paper, we show that for a finite-depth Kripke model in an arbitrary first-order language or propositional language, local (classical) truth of a formula is equivalent to non-classical truth (truth in the Kripke semantics) of a Friedman's translation of that formula, i.e. $ \alpha\Vdash A^\rho \Leftrightarrow \mathfrak{M}_\alpha\models A$. We introduce some applications of this fact. We extend the result of [Ardeshir and Hessam 2002] and show that semi-narrow Kripke models of Heyting Arithmetic $ {\sf HA} $ are locally $ {\sf PA} $.

The majority of works on modal many-valued logics consider Kripke-style possible worlds frames as the principal semantics despite their well-known axiomatizability issues when considering non-Boolean accessibility relations. The present work explores a more general semantical picture, namely a many-valued version of the classical neighborhood semantics. We present it in two levels of generality. First, we work with modal languages containing only the two usual unary modalities, define neighborhood frames over algebras of the logic FL ew with operators, and show their relation with the usual Kripke semantics (this is actually the highest level of generality where one can give a straightforward definition of the Kripke-style semantics). Second, we define generalized neighborhood frames for arbitrary modal languages over a given class of algebras for an arbitrary protoalgebraic logic and, assuming certain additional conditions, axiomatize the logic of all such frames (which generalizes the completeness theorem of the classical modal logic E with respect to classical neighborhood frames).

We study a modal extension of the Continuous First-Order Logic of Ben Yaacov and Pedersen (J Symb Logic 75(1):168–190, 2010). We provide a set of axioms for such an extension. Deduction rules are just Modus Ponens and Necessitation. We prove that our system is sound with respect to a Kripke semantics and, building on Ben Yaacov and Pedersen (2010), that it satisfies a number of properties similar to those of first-order predicate logic. Then, by means of a canonical model construction, we get that every consistent set of formulas is satisfiable. From the latter result we derive an Approximated Strong Completeness Theorem, in the vein of Continuous Logic, and a Compactness Theorem.

Decidability of the validity problem is established for a family of many-valued modal logics, notably Godel modal logics, where propositional connectives are evaluated according to the order of values in a complete sublattice of the real unit interval [ 0 , 1 ] , and box and diamond modalities are evaluated as infima and suprema over (many-valued) Kripke frames. If the sublattice is infinite and the language is sufficiently expressive, then the standard semantics for such a logic lacks the finite model property. It is shown here, however, that, given certain regularity conditions, the finite model property holds for a new semantics for the logic, providing a basis for establishing decidability and PSPACE-completeness. Similar results are also established for S5 logics that coincide with one-variable fragments of first-order many-valued logics. In particular, a first proof is given of the decidability and co-NP-completeness of validity in the one-variable fragment of first-order Godel logic.

This paper explores a new language of neighbourhood structures where existential information can be given about what kind of worlds occur in a neighbourhood of a current world. The resulting system of ‘instantial neighbourhood logic’ INL has a nontrivial mix of features from relational semantics and from neighbourhood semantics. We explore some basic model-theoretic behavior, including a matching notion of bisimulation, and give a complete axiom system for which we prove completeness by a new normal form technique. In addition, we relate INL to other modal logics by means of translations, and determine its precise SAT complexity. Finally, we discuss proof-theoretic fine-structure of INL in terms of semantic tableaux and some expressive fine-structure in terms of fragments, while discussing concrete illustrations of the instantial neighborhood language in topological spaces, in games with powers for players construed in a new way, as well as in dynamic logics of acquiring or deleting evidence. We conclude with some coalgebraic perspectives on what is achieved in this paper. Many of these final themes suggest follow-up work of independent interest.

In the literature, little attention has been paid to the development of solvers for systems of mathematical fuzzy logic, and in particular, there are few works concerned with infinitely-valued logics. In this paper it is presented mNiBLoS (a modal Nice BL-Logics Solver): a modular SMT-based solver complete with respect to a wide family of continuous t-norm based fuzzy modal logics (both with finite and infinite universes), restricting the modal structures to the finite ones. At the propositional level, the solver works with some of the best known infinitely-valued fuzzy logics (including BL, Łukasiewicz, Gödel and product logics), and with all the continuous t-norm based logics that can be finitely expressed in terms of the previous ones; concerning the modal expansion, mNiBLoS imposes no boundary on the cardinality of the modal structures considered. The solver allows to test 1-satisfiability of equations, tautologicity and logical consequence problems. The logical language supported extends the usual one of fuzzy modal logics with rational constants and the Monteiro-Baaz Δ operator. The code of mNiBLoS is of free distribution and can be found in the web page of the author. © 2016 Elsevier Inc., This work was supported by the CSIC Intramural project 201450E045:“Logal: Lógica y algoritmos”, the joint project of Austrian Science Fund (FWF) I1897-N25 and Czech Science Foundation (GACR) 15-34650L, the institutional support RVO:67985807 and the MINECO project EdeTRI:TIN2012-39348-C02-01. The author wishes to thank the anonymous reviewers for their useful commentaries.

In Osorio et al. [Revisiting Z. Notre Dame Journal of Formal Logic, 55(1):129–155, 2014] introduced a paraconsistent three-valued logic, the logic CG 3 ′ which was named after the logic G 3 ′ due to the close relation between them. Authors defined CG 3 ′ via the three-valued matrix that defines G 3 ′ but changing the set of designated truth values. In this article we present a brief study of the Kripke-type semantics for some logics related with CG 3 ′ before constructing a Kripke-type semantics for it.

Starting off from the usual language of modal logic for multi-agent systems dealing with the agents’ knowledge/belief and common knowledge/belief we define so-called epistemic Kripke structures for intu- itionistic (common) knowledge/belief. Then we introduce corresponding deductive systems and show that they are sound and complete with respect to these semantics.

Two conjectures on the covering-based rough set semantics for modal logics in 35 are answered. The C 2 and C 5 semantics give rise to the same modal system S4. There are Galois connections between C 2 and C 5 which lead to the covering-based semantics for the temporal logic system S4t. The P 1 and C 4 semantics give rise to the same modal system KTB.

This paper presents results on the definition of a sequent calculus for Minimal Implicational Propositional Logic (M→) aimed to be used for provability and counter-model generation in this logic. The system tracks the attempts to construct a proof in such a way that, if the original formula is a M→ tautology, the tree structure produced by the proving process is a proof, otherwise, it is used to construct a counter-model using Kripke semantics.

Justification logics connect with modal logics, replacing unstructured modal operators with justification terms explicitly representing interdependence and flow of reasoning. The number of justification logics quickly grew from an initial single instance to a handful to about a dozen examples. In this paper we provide very general, though partly non-constructive, methods that cover all previous examples, and extend to an infinite family of modal logics. The full range of the phenomenon is not known. The extent to which constructive methods apply is also not known, but it is related to the availability of cut-free proof methods for modal logics.

We consider the family of logics from NExt(KTB) which are determined by linear frames with reflexive and symmetric relation of accessibility. The condition of linearity in such frames was first defined in the paper [9]. We prove that the cardinality of the logics under consideration is uncountably infinite.

A new semantics with the finite model property is provided and used to establish decidability for Gödel modal logics based on (crisp or fuzzy) Kripke frames combined locally with Gödel logic. A similar methodology is also used to establish decidability, indeed co-NP-completeness, for a Gödel S5 logic that coincides with the one-variable fragment of first-order Gödel logic.

International audience; In this article we define label-free sequent calculi for the intuitionistic modal logics obtained from the combinations of the axioms T, B, 4 and 5. These calculi are based on a multi-contextual sequent structure, called Tree-sequent, which allows us to define such calculi for such intuitionistic modal logics. From the calculi defined for the IK, IT, IB4 and ITB logics, we also provide new decision procedures and alternative syntactic proofs of decidability.

Combining multi-valued and modal logics into a single system is a long-standing concern in mathematical logic and computer science, see for example [7] and the literature cited there. Recent work in this trend [15, 17, 14] develops modal expansions of many-valued systems that are also inconsistencytolerant, along the tradition initiated by Belnap with his “useful four-valued logic” [3]. Our contribution continues on this line, and the specific problem we address is that of defining and axiomatizing the least modal logic over the four-element Belnap lattice. The problem was inspired by [5], but our solution is quite different from (and in some respects more satisfactory than) that of [5] in that we make an extensive and profitable use of algebraic and topological techniques. In fact, our algebraic and topological analyses of the logic have, in our opinion, an independent interest and contribute to the appeal of our approach. Kripke frames provide a semantics for modal logics that is both flexible with regards to intended applications and interpretations, and highly intuitive. When the non-modal part is multi-valued, though, one may wonder whether the accessibility relation between worlds should remain two-valued or be allowed to assume the same range of truth values as the logic itself. Starting from the point of view of AI applications, [7] argues forcefully that multiple values are an appropriate and useful modeling device. This is the approach taken in [5] and here, too. Our aim is to study the least modal logic over the Belnap lattice, that is, the logic determined by the class of all Kripke frames where the accessibility relation as well as semantic valuations are four-valued.

Models of complex systems are widely used in the physical and social sciences, and the concept of layering, typically building upon graph-theoretic structure, is a common feature. We describe an intuitionistic substructural logic that gives an account of layering. As in bunched systems, the logic includes the usual intuitionistic connectives, together with a non-commutative, non-associative conjunction used to capture layering and its associated implications. We give soundness and completeness theorems for labelled tableaux and Hilbert-type systems with respect to a Kripke semantics on graphs. To demonstrate the utility of the logic, we show how to represent a range of systems and security examples, illuminating the relationship between services/policies and the infrastructures/architectures to which they are applied.

This article outlines a semantic approach to the logics of unknown truths, and the logic of false beliefs, using neighborhood structures, giving results on soundness, completeness, and expressivity. Relational semantics for the logics of unknown truths are also addressed, specically the conditions under which sound axiomatizations of these logics might be obtained from their normal counterparts, and the relationship between refexive insensitive logics (RI-logics) and logics containing the provability operator as the primary modal operator.

International audience; This paper introduces and studies extensions of modal logics by investigating the soundness of classical modal axioms in a weighted framework. It discusses the notion of relevant weight values, in a specific weighted Kripke semantics and exploits accessibility relation properties. Different generalisations of the classical axioms are constructed and, from these, a typology of weighted axioms is built, distinguishing between four types, depending on their relations to their classical counterparts and to the, possibly equivalent, frame conditions.

We show that logics based on linear Kripke frames--with or without constant domains--that have a scattered end piece are not recursively enumerable. This is done by reduction to validity in all finite classical models.

We develop a general method for deriving natural deduction rules from the truth table for a connective. The method applies to both constructive and classical logic. This implies we can derive "constructively valid" rules for any classical connective. We show this constructive validity by giving a general Kripke semantics, that is shown to be sound and complete for the constructive rules. For the well-known connectives $$\vee $$, $$\wedge $$, $$\rightarrow $$, $$\lnot $$ the constructive rules we derive are equivalent to the natural deduction rules we know from Gentzen and Prawitz. However, they have a different shape, because we want all our rules to have a standard "format", to make it easier to define the notions of cut and to study proof reductions. In style they are close to the "general elimination rules" studied by Von Plato [13] and others. The rules also shed some new light on the classical connectives: e.g. the classical rules we derive for $$\rightarrow $$ allow to prove Peirce's law. Our method also allows to derive rules for connectives that are usually not treated in natural deduction textbooks, like the "if-then-else", whose truth table is clear but whose constructive deduction rules are not. We prove that "if-then-else", in combination with $$\bot $$ and $$\top $$, is functionally complete all other constructive connectives can be defined from it. We define the notion of cut, generally for any constructive connective and we describe the process of "cut-elimination".

Quite a number of aspects of concurrency are reflected by the inequational exchange law ( P ⁎ Q ) ; ( R ⁎ S ) ⩽ ( P ; R ) ⁎ ( Q ; S ) between sequential composition ; and concurrent composition ⁎. In particular, recent research has shown that, under a certain semantic definition, validity of this law is equivalent to that of the familiar concurrency rule for Hoare triples. Unfortunately, while the law holds in the standard model of concurrent Kleene algebra, its is not true in the relationally based setting of algebraic separation logic. However, we show that under mild conditions the reverse inequation ( P ; R ) ⁎ ( Q ; S ) ⩽ ( P ⁎ Q ) ; ( R ⁎ S ) still holds there. From this reverse exchange law we derive slightly restricted but still reasonably useful variants of the concurrency rule. Moreover, using a corresponding definition of locality, we obtain also a variant of the frame rule, where ⁎ now is interpreted as separating conjunction. These results allow using the relational setting also for modular and concurrency reasoning. Finally, we interpret the results further by discussing several variations of the approach.

Relational semantics, given by Kripke frames, play an essential role in the study of modal and intuitionistic logic. In [4] it is shown that the theory of relational semantics is also available in the more general setting of substructural logic, at least in an algebraic guise. Building on these ideas, in [5] a type of frames is described which generalise Kripke frames and provide semantics for substructural logics in a purely relational form. In this paper we study full linear logic from an algebraic point of view. The main additional hurdle is the exponential. We analyse this operation algebraically and use canonical extensions to obtain relational semantics. Thus, we extend the work in [4] , [5] and use their approach to obtain relational semantics for full linear logic. Hereby we illustrate the strength of using canonical extension to retrieve relational semantics: it allows a modular and uniform treatment of additional operations and axioms. Traditionally, so-called phase semantics are used as models for (provability in) linear logic [8] . These have the drawback that, contrary to our approach, they do not allow a modular treatment of additional axioms. However, the two approaches are related, as we will explain.

We study a class DL of certain decidable relational logics of binary relations with a single relational constant and restricted composition. The logics in DL are defined in terms of semantic restrictions on the models. The main contribution of the present article is the construction of relational dual tableau decision procedures for the logics in DL . The systems are constructed in the framework of the original methodology of relational proof systems, determined only by axioms and inference rules, without any external techniques. All necessary bookkeeping is contained in the proof tree itself and used according to the explicit rules. All the systems are deterministic, producing exactly one proof tree for every formula. Furthermore, we show how the systems for logics in DL can be used as deterministic decision procedures for some modal and intuitionistic logics.

We study a modal language for negative operators—an intuitionistic-like negation and its paraconsistent dual—added to (bounded) distributive lattices. For each non-classical negation an extra operator is hereby adjoined in order to allow for standard logical inferences to be opportunely restored. We present abstract characterizations and exhibit the main properties of each kind of negative modality, as well as of the associated connectives that express consistency and determinedness at the object-language level. Appropriate sequent-style proof systems and adequate kripke semantics are also introduced, characterizing the minimal normal logic and a few other basic logics containing such negative modalities and their companions.

Provability logic GLP is well-known to be incomplete w.r.t. Kripke semantics. A natural topological semantics of GLP interprets modalities as derivative operators of a polytopological space. Such spaces are called GLP-spaces whenever they satisfy all the axioms of GLP . We develop some constructions to build nontrivial GLP-spaces and show that GLP is complete w.r.t. the class of all GLP-spaces.

It is well-known that the Gödelʼs system T definable functions (N→N)→N are continuous, and that their restrictions from the Baire type (N→N) to the Cantor type (N→2) are uniformly continuous. We offer a new, relatively short and self-contained proof. The main technical idea is a concrete notion of generic element that doesnʼt rely on forcing, Kripke semantics or sheaves, which seems to be related to generic effects in programming. The proof uses standard techniques from programming language semantics, such as dialogues, monads, and logical relations. We write this proof in intensional Martin-Löf type theory (MLTT) from scratch, in Agda notation. Because MLTT has a computational interpretation and Agda can be seen as a programming language, we can run our proof to compute moduli of (uniform) continuity of T-definable functions.

Logics of dependence and independence have semantics that, unlike Tarski semantics, are not based on single assignments (mapping variables to elements of a structure) but on sets of assignments. Sets of assignments are called teams and the semantics is called team semantics. We design model-checking games for logics with team semantics in a general and systematic way. The construction works for any extension of first-order logic by atomic formulae on teams, as long as certain natural conditions are observed which are satisfied by all team properties considered so far in the literature, including dependence, independence, constancy, inclusion, and exclusion. The second-order features of team semantics are reflected by the notion of a consistent winning strategy which is also a second-order notion in the sense that it depends not on single plays but on the space of all plays that are compatible with the strategy. Beyond the application to logics with team semantics, we isolate an abstract, purely combinatorial definition of such games, which may be viewed as second-order reachability games, and study their algorithmic properties. A number of examples are provided that show how logics with team semantics express familiar combinatorial problems in a somewhat unexpected way. Based on our games, we provide a complexity analysis of logics with team semantics.

The logic BI of bunched implications is a combination of intuitionistic logic and multiplicative intuitionistic linear logic. In this paper, a temporal extension tBI of BI is introduced and studied. A Gentzen-type sequent calculus GtBI for tBI is introduced, and the cut-elimination and decidability theorems for GtBI are proved using a theorem for syntactically embedding GtBI into a sequent calculus GBI for BI. A semantics for GtBI is introduced extending the Grothendieck topological semantics for BI, and the completeness theorem with respect to this semantics is proved using a theorem for semantically embedding tBI into BI. A semantics for GtBI without additive falsity constant is introduced extending the Kripke resource semantics for BI without additive falsity constant, and the completeness theorem with respect to this semantics is proved in a similar way. Moreover, an intuitionistic temporal linear logic, ITLL, is introduced as a Gentzen-type sequent calculus, and a theorem for embedding GtBI into ITLL is proved using a temporal extension of the Girard translation of intuitionistic logic into intuitionistic linear logic.

I propose a new semantics for intuitionistic logic, which is a cross between the construction-oriented semantics of Brouwer-Heyting-Kolmogorov and the condition-oriented semantics of Kripke. The new semantics shows how there might be a common semantical underpinning for intuitionistic and classical logic and how intuitionistic logic might thereby be tied to a realist conception of the relationship between language and the world.

In this paper we present two terminating tableau calculi for propositional Dummett logic obeying the subformula property. The ideas of our calculi rely on the linearly ordered Kripke semantics of Dummett logic. The first calculus works on two semantical levels: the present and the next possible world. The second calculus employs the usual object language of tableau systems and exploits a property of the construction of the completeness theorem to introduce a check which is an alternative to loop check mechanisms., 21 pages, rejected at CSL 2012

Monomodal logic has exactly two maximally normal logics, which are also the only quasi-normal logics that are Post complete, and they are complete for validity in Kripke frames. Here we show that addition of a propositional constant to monomodal logic allows the construction of continuum many maximally normal logics that are not valid in any Kripke frame, or even in any complete modal algebra. We also construct continuum many quasi-normal Post complete logics that are not normal. The set of extensions of S4.3 is radically altered by the addition of a constant: we use it to construct continuum many such normal extensions of S4.3, and continuum many non-normal ones, none of which have the finite model property. But for logics with weakly transitive frames there are only eight maximally normal ones, of which five extend K4 and three extend S4.

The logic BN4 was defined by R.T. Brady in 1982. It can be considered as the 4-valued logic of the relevant conditional. E4 is a variant of BN4 that can be considered as the 4-valued logic of (relevant) entailment. The aim of this paper is to define reduced general Routley-Meyer semantics for BN4 and E4. It is proved that BN4 and E4 are strongly sound and complete w.r.t. their respective semantics.

It is observed that a consistent congruential modal logic is not guaranteed to have a consistent extension in which the Box operator becomes a truth-functional connective for one of the four one-place (two-valued) truth functions.

We introduce a general notion of semantic structure for first-order theories, covering a variety of constructions such as Tarski and Kripke seman- tics, and prove that, over Zermelo Fraenkel set theory (ZF), the completeness of such semantics is equivalent to the Boolean Prime Ideal theorem (BPI). In partic- ular, we deduce that the completeness of that type of semantics for non-classical theories is unprovable in intuitionistic Zermelo Fraenkel set theory IZF. Using results of Joyal and McCarty, we conclude also that the completeness of Kripke semantics is equivalent, over IZF, to the Law of Excluded Middle plus BPI. By results from Banaschewski and Bhutani, none of these two principles imply each other, and so this gives the exact strength of Kripke completeness theorem in the sense of constructive reverse mathematics.

In this paper, we give a possible characterisation of the distributivity on bi-approximation semantics. To this end, we introduce new notions of special elements on polarities and show the distributivity is first-order definable on bi-approximation semantics. In addition, we shall investigate the dual representation of those structures and compare them with biapproximation semantics for intuitionistic logic. We shall also discuss that two different methods to validate the distributivity by the splitters and by the adjointness can be explicated with help of the Axiom of Choice as well.

We extend unified correspondence theory to Kripke frames with impossible worlds and their associated regular modal logics. These are logics the modal connectives of which are not required to be normal: only the weaker properties of additivity ◊x∨◊y=◊(x∨y) and multiplicativity □x∧□y=□(x∧y) are required. Conceptually, it has been argued that their lacking necessitation makes regular modal logics better suited than normal modal logics at the formalization of epistemic and deontic settings. From a technical viewpoint, regularity proves to be very natural and adequate for the treatment of algebraic canonicity Jónsson-style. Indeed, additivity and multiplicativity turn out to be key to extend Jónsson’s original proof of canonicity to the full Sahlqvist class of certain regular distributive modal logics naturally generalizing distributive modal logic. Most interestingly, additivity and multiplicativity are key to Jónsson-style canonicity also in the original (i.e. normal DML. Our contributions include: the definition of Sahlqvist inequalities for regular modal logics on a distributive lattice propositional base; the proof of their canonicity following Jónsson’s strategy; the adaptation of the algorithm ALBA to the setting of regular modal logics on two non-classical (distributive lattice and intuitionistic) bases; the proof that the adapted ALBA is guaranteed to succeed on a syntactically defined class which properly includes the Sahlqvist one; finally, the application of the previous results so as to obtain proofs, alternative to Kripke’s, of the strong completeness of Lemmon’s epistemic logics E2-E5 with respect to elementary classes of Kripke frames with impossible worlds.

In this chapter the author gives completeness theorems for some basic reactive Kripke models and semantics.

We provide a Kripke semantics for a STIT logic with the "next" operator. As the atemporal group STIT is undecidable and unaxiomatizable, we are interested in strict fragments of atemporal group STIT. First we prove that the satisfiability problem of a formula of the fragment made up of individual coalitions plus the grand coalition is also NEXPTIME-complete. We then generalize this result to a fragment where coalitions are in a given lattice. We also prove that if we restrict the language to nested coalitions the satisfiability problem is NP-complete if the number of agents is fixed and PSPACEcomplete if the number of agents is variable. Finally we embed individual STIT with the "next" operator into a fragment of atemporal group STIT.

Ordinary Kripke models are not reactive. When we evaluate (test/ measure) a formula A at a model m, the model does not react, respond or change while we evaluate. The model is static and unchanged. This paper studies Kripke models which react to the evaluation process and change themselves during the process. The additional device we add to Kripke semantics to make it reactive is to allow the accessibility relation to access itself. Thus the accessibility relation ${\cal R}$ of a reactive Kripke model contains not only pairs $(a, b) \in {\cal R}$ of possible worlds (b is accessible to a, i.e., there is an accessibility arc from a to b) but also pairs of the form $(t, (a, b))\in {\cal R}$ , meaning that the arc (a,b) is accessible to t, or even connections of the form $((a,b), (c,d))\in {\cal R}$ . This new kind of Kripke semantics allows us to characterise more axiomatic modal logics (with one modality $\square$ ) by a class of reactive frames. There are logics which cannot be characterised by ordinary frames but which can be characterised by reactive frames. We also discuss the manifestation of the `reactive' idea in the context of automata theory, where we allow the automaton to react and change it's own definition as it responds to input, and in graph theory, where the graph can change under us as we manipulate it.

Epistemic logic of shallow depths has been developed by Kaneko–Suzuki using classical logic. In this paper, we adopt intuitionistic logic as the base logic to limit each player’s reasoning to constructive one. The resulting logical system is denoted by IG\(_{EF}\), and we introduce epistemic possible world semantics for IG\(_{EF}\). We show the soundness and completeness of IG\(_{EF}\) with respect to this semantics for it. We also show some applications to game theoretical decision making.

The fragment of the polymodal provability logic GLP in the language with connectives ┬, Λ, and 〈n〉 for all n ∈ ω is considered. For this fragment, a deductive system is constructed, a Kripke semantics is proposed, and a polynomial bound for the complexity of a decision procedure is obtained.

The completeness w.r.t. Kripke frames with equality (or, equivalently, w.r.t. Kripke sheaves, [8] or [4, Sect. 3.6]) is established for three superintuitionistic predicate logics: (Q-H + D*), (Q-H + D*&K), (Q-H + D*&K&J). Here Q-H is intuitionistic predicate logic, J is the principle of the weak excluded middle, K is Kuroda's axiom, and D* (cf. [12]) is a weakened version of the well-known constant domains principle D. Namely, the formula D states that any individual has ancestors in earlier worlds, and D* states that any individual has $${\neg\neg}$$ -ancestors (i.e., ancestors up to $${\neg\neg}$$ -equality) in earlier worlds. In particular, the logic (Q-H + D*&K&J) is the Kripke sheaf completion of (Q-H + E&K&J), where E is a version of Markov's principle (cf. [12]). On the other hand, we show that the logic (Q-H + D*&J) is incomplete w.r.t. Kripke sheaves.

In this paper we study a version of constructive linear-time temporal logic (LTL) with the ''next'' temporal operator. The logic is originally due to Davies, who has shown that the proof system of the logic corresponds to a type system for binding-time analysis via the Curry-Howard isomorphism. However, he did not investigate the logic itself in detail; he has proved only that the logic augmented with negation and classical reasoning is equivalent to (the ''next'' fragment of) the standard formulation of classical linear-time temporal logic. We give natural deduction, sequent calculus and Hilbert-style proof systems for constructive LTL with conjunction, disjunction and falsehood, and show that the sequent calculus enjoys cut elimination. Moreover, we also consider Kripke semantics and prove soundness and completeness. One distinguishing feature of this logic is that distributivity of the ''next'' operator over disjunction ''@?(A@?B)@?@?A@?@?B'' is rejected in view of a type-theoretic interpretation.