Questions tagged [modal-logic]

Questions relating to deductions relating to the expressions "it is necessary that" and "it is possible that"

Filter by
Sorted by
Tagged with
-3 votes
0 answers
17 views

Please can someone explain how to translate intuitionistic logic into S4? [closed]

I understand this is an easy question, but I cannot quite get my head around it.
user avatar
-1 votes
0 answers
7 views

How does the technique of 'existence-relativisation' allow us to embed varying-domain semantics in constant-domain semantics?

How can the technique of 'existence-relativisation' embed varying-domain semantics in constant-domain semantics?
user avatar
1 vote
1 answer
27 views

Proving axiom M in modal logic from K plus A → ◊A

I'm slowly working my way through Garson's Modal Logic for Philosophers. I'm stuck on exercise 2.1c. It asks me to prove axiom M (= ◻A → A) in system K (propositional logic + necessitation and ...
user avatar
  • 35
-1 votes
0 answers
17 views

The question asks about basic tense logics and tried to proof if a schema is valid or not

Consider the following schema: FHA → A Determine whether or not it is valid. If it is valid, prove this; if it isn’t show this by constructing a countermode
user avatar
0 votes
0 answers
11 views

Proof that M-Trees Can Be Converted into M - Proofs

I'm studying modal logic through Garson's book, and I got to the part of proving that given a K - tree, there's a corresponding K - proof. I did a proof for the minimal system K case, but I can't ...
user avatar
0 votes
1 answer
47 views

Is the converse of (◇◇A -> ◇A) true too?

Axiom 4 in System S4 is this: ◻A -> ◻◻A Its corollary is this: ◇◇A -> ◇A As I understood with the corollary, it means that "If the fact that A is true in at least one world, true in at ...
user avatar
2 votes
2 answers
39 views

Is the distribution axiom in modal logic biconditional and does it hold for diamond as well as box?

I'm a new learner of (normal) modal logic. I'm slowly teaching myself and have some questions related (broadly) to the distribution axiom: $\square (p \to q) \to (\square p \to \square q)$. I have no ...
user avatar
  • 35
3 votes
0 answers
42 views

Literature for modal logic and coalgebras (focused on logic and category theory)

I've been looking for literature that focuses on coalgebras and modal logic. But all literature I can find is mostly related to automata theory, or otherwise takes heavy influence from computer ...
user avatar
  • 63
0 votes
1 answer
63 views

Is modal logic required to handle assumptions in logic? (Tic Tac Toe example)

Suppose the Tic Tac Toe board is like this: \begin{array}{c|c|c} 1 & 2 & 3 \\ \hline 4 & 5 & 6 \\ \hline 7 & 8 & 9 \end{array} and I define a predicate ...
user avatar
  • 1,063
0 votes
1 answer
58 views

Prove that $\mathbf{L}$ is almost a normal modal logic.

Suppose we have a logic $\mathbf{L}$ containing all the propositional tautologies and the formula $\square(p\wedge q)\leftrightarrow(\square p \wedge\square q)$, and it is closed by Modus Ponens, ...
user avatar
  • 815
2 votes
1 answer
251 views

Computation tree logic (CTL): Are AG, AF, EG or EF idempotent?

I'm studying CTL and I got stuck on the following problem: Determine if the following operations are idempotent or not: AG, AF, EG or EF. I have the following definitions: Let M = (S,→,L) be a model ...
user avatar
1 vote
1 answer
25 views

Prove of K ⊢ A ↔ B then K ⊢ C [A/q ] ↔ C [B/q ]

I am currently reading "Boxes and Diamonds: An Open Introduction to Modal Logic". Here is the PDF to the book: https://builds.openlogicproject.org/courses/boxes-and-diamonds/bd-screen.pdf ...
user avatar
  • 23
1 vote
1 answer
62 views

Hughes and Cresswell's definition of consistency

On page 46 of Hughes and Cresswell's A New Introduction To Modal Logic, we have the following definition of consistency. Consistency : We shall say that an axiomatic system is consistent iff not ...
user avatar
3 votes
1 answer
87 views

Excercise 1.5.1 from Blackburn, de Rijke and Venema's Modal Logic

I've recently started to learn Modal Logic using this book as a reference. At the end of Section 1.5 "Modal Consequence Relations" there are some excercises about the topic. The first one ...
user avatar
  • 815
0 votes
0 answers
93 views

Is there a mathematical system that is: complete, consistent, and decidable?

I know very little about modal logic (only some set theory) in mathematics, but I am aware that there exists a completeness theorem, incompleteness theorem, and the axiom choice, and that maths is not ...
user avatar
1 vote
2 answers
59 views

Every normal modal logic Σ contains ¬♢⊥.

The following proposition comes from this PDF: http://builds.openlogicproject.org/content/normal-modal-logic/normal-modal-logic.pdf (p.31) It says: Every normal modal logic Σ contains ¬♢⊥. The problem ...
user avatar
  • 23
1 vote
1 answer
27 views

Does consistency of Peano arithmetic follow from arithmetical completeness of modal logic GL?

Solovay's Arithmetical Completeness theorem states that if $A$ is sentence of modal logic, then if every realization $A^*$ of $A$ is proved by $\mathsf{PA}$, then $\mathsf{GL}\vdash A$. By ...
user avatar
1 vote
1 answer
46 views

Formulas of basic modal logic involving only $\top$, $\bot$, propositional connectives and modalities

I am given a Kripke model $\mathcal{M}=(W, R, L)$ where $W=\{w_1, w_2, w_3, w_4\}$ $R=\{(w_1, w_2), (w_2, w_3), (w_4, w_1), (w_4, w_3)\}$, and for all $w \in W$, $L(w)=\varnothing$. For each $w \in W$,...
user avatar
2 votes
1 answer
64 views

proving $\Box(p \to q) \to (\Box p \to \Box q)$ or $(\Box p \land \Box q) \to \Box (p \land q)$ from necessitation and other propositions

Does anyone know of any propositions that would suffice, along with the necessitation rule, to prove either of the following two propositions? $\Box(p \to q) \to (\Box p \to \Box q)$ $(\Box p \land \...
user avatar
1 vote
0 answers
65 views

Intuition behind Solovay's proof of arithmetical completeness theorem

Solovay's Arithmetical Completeness theorem states that if $A$ is sentence of modal logic, then if every realization $A^*$ of $A$ is proved by $\mathsf{PA}$, then $\mathsf{GL}\vdash A$. The way this ...
user avatar
-1 votes
1 answer
66 views

Forming simple epistemic logic formula from a given sentence

Sentence: I don't know if I know whether Lionel Messi is the GOAT. $a$: I/Myself $φ$: Lionel Messi is the GOAT Attempt 1: $\,\lnot K_{a}\,(K_{a}φ \, \lor K_{a}\lnotφ)$ Attempt 2: $\,\lnot K_{a} \,\to ...
user avatar
0 votes
0 answers
34 views

Prove that if $\mathcal{C}\vDash C\rightarrow \Box B$ then $\mathcal{C}\vDash C\rightarrow\Box\forall x B$

$\mathcal{C}$ is the class of all variable domain existence models. Further, we are supposing that $x$ does not occur free in $C$. But now consider this counter-model $M=\langle W,R,D,f,V\rangle$ ...
user avatar
1 vote
0 answers
23 views

How to show that the canonical model for $K4.3$ contains proper clusters?

It is a well-known result that the canonical models for some temporal logics, e.g, $K_t4.3$ and $K_tQ$, contain proper clusters (equivalent class of points seeing each other). As a result, we need to ...
user avatar
  • 19
0 votes
0 answers
23 views

Constructing the largest bisimulation from matchings

I'm reading the textbook 'First Steps in Modal Logic' by Sally Popkorn (the pen name of Harold Simmons). I got stuck in a transfinite construction of the largest bisimulation from matchings. Here are ...
user avatar
  • 740
0 votes
0 answers
43 views

Prove $M\Vdash\Box(\Box p\rightarrow p)\rightarrow\Box p$ for a model $M=\langle W,R,V\rangle$ in which $R$ is transitive and converse well-founded

Prove $M\Vdash\Box(\Box p\rightarrow p)\rightarrow\Box p$ for a model $M=\langle W,R,V\rangle$ in which $R$ is transitive and converse well-founded. I proceed by reductio. So suppose $M\nVdash\Box(\...
user avatar
1 vote
1 answer
37 views

Why does $\mu X .\langle a\rangle X$ not make any sense in $\mu$-calculus?

I've been reading up on modal $\mu$-calculus via this paper "The mu-calculus and model-checking" to get a better intuition for fixed-point logic. In the paper, the authors state that the ...
user avatar
  • 125
1 vote
3 answers
106 views

Modal Logic: Equivalence between two formulas

I want to know if these two modal formulas are equivalent: $\forall x (B(x) \to \diamond (B(x) \land \lnot x))$ $\equiv$ $\forall x (B(x) \to \diamond \lnot x)$. The -> direction holds and I have a ...
user avatar
  • 342
1 vote
1 answer
65 views

How do I handle an $v=u$ relation in propositional modal logic?

(Garson p. 102)$^\eqref{reff-1}$, in a brief discussion about the linear view of time, introduces us to the Connectedness Axiom (L): $\square(\square A\to B)\lor\square((B \land \square B)\to A).$ (L) ...
user avatar
  • 1,011
2 votes
0 answers
73 views

Show that the canonical model for $\mathbf{S5}$ is not universal

Show that the canonical model for $\mathbf{S5}$ is not universal. We know that the canonical model $M$ for $\mathbf{S5}$ is based on the class of frames $\mathscr{F}$ where $R$ is an equivalence ...
user avatar
0 votes
1 answer
80 views

Proving that □A → A is valid iff R is reflexive?

How to prove, in modal logic, that \square $A\to A$ is valid iff $R$ is reflexive? (shouldn't this be the definition of $T$ axiom in modal logic)? (NOTE: The question was edited because I made a ...
user avatar
0 votes
1 answer
44 views

Prove that (1) implies (2), where (1) is: If $A$ is consistent, then $A$ is satisfiable; and (2) is: if $\vDash A$, then $\vdash A$.

Below's my attempt at this proof. My question, in particular, is about line c. Does $\nvdash_\Sigma A$ imply $\vdash_\Sigma \lnot A$ for any wff $A$ in any normal modal system $\Sigma$? And if not, ...
user avatar
0 votes
0 answers
39 views

Prove if $A\in\Gamma$ then $\Gamma\vdash_\Sigma A$

Prove if $A\in\Gamma$ then $\Gamma\vdash_\Sigma A$, where $\Gamma$ is a set of modal formulas and $\Sigma$ is a modal system. We are given the following definition of derivability: A formula $A$ is ...
user avatar
4 votes
1 answer
91 views

Is there a computable procedure for testing whether a given modal schema is true in a given finite relational model?

Is there a computable procedure for testing whether a given modal schema is true in a given finite relational model? This is inspired by question 2 on page 19 by internal numbering (PDF page 34) of ...
user avatar
  • 6,381
0 votes
0 answers
26 views

Use induction on the complexity of $C$ to prove that if $K\vdash A\leftrightarrow B$ then $K\vdash C[A/q]\leftrightarrow C[B/q]$

Use induction on the complexity of $C$ to prove that if $K\vdash A\leftrightarrow B$ then $K\vdash C[A/q]\leftrightarrow C[B/q]$ This is question 3.3 from OLP's Boxes and Diamonds. I have found proofs ...
user avatar
2 votes
1 answer
125 views

Non-tableau calculi for system K

What proof calculi are there besides the method of analytic tableaux for System K? The method of analytic tableaux is tricky to typeset and takes a lot of space, especially for modal logic. I'm ...
user avatar
  • 6,381
2 votes
2 answers
87 views

What is a non-normal modal logic? Is there a family of semantics that covers both normal and non-normal modal logics?

What is a non-normal modal logic? Is there a semantics for modal logic that's broad enough to cover a range of normal and non-normal modal logics and has the normal modal logics as a definable ...
user avatar
  • 6,381
1 vote
1 answer
67 views

Prove that if $\Box p \rightarrow \Box\Box p$ is valid on a frame $F=\langle W,R\rangle$ then $R$ is transitive

Prove that if $\Box p \rightarrow \Box\Box p$ is valid on a frame $F=\langle W,R\rangle$, then $R$ is transitive. Suppose $F\vDash\Box p\rightarrow \Box\Box p$, where $F=\langle W,R\rangle$. Let $u,v,...
user avatar
3 votes
1 answer
80 views

Is $\forall x \square \varphi \leftrightarrow \square \forall x \varphi$ a valid formula for all formulas $\varphi$?

I haven't yet studied formal semantics of a modal logic with quantifiers, so forgive me if I make any rookie mistakes. My thinking goes like this. The modal quantifier $\square$ ranges over the set of ...
user avatar
  • 1,815
3 votes
1 answer
47 views

Rooted Kripke frames connection to $K$

I was reading the Modal logic book from Chagrov and Zakharyaschev. I read the following theorem (generation theorem 3.11): If $N$ is a generated submodel of $M$, then for every point x and every ...
user avatar
1 vote
2 answers
42 views

For every intuitionistic kripke frame $F = (W, R)$ and every formula $\phi$ and points $x,y \in W$ if $x \models \phi$ and $x R y$ then $y\models\phi$

I need to show that: For every intuitionistic kripke frame $F = (W, R)$ and every formula $\phi$ and every points $x,y \in W$ if $x \models \phi$ and $x R y$ then $y \models \phi$ I know it's done by ...
user avatar
1 vote
1 answer
28 views

Show $K_\rho$ is a proper extension of $K_\eta$

Show $K_\rho$ is a proper extension of $K_\eta$: $K_\rho$ is an extension of $K$ where $R$ is reflexive. And $K_\eta$ is an extension of $K$ where $R$ is extendable. So, I reasoned as follows: $K_\rho$...
user avatar
4 votes
1 answer
72 views

Prove or disprove statement for the smallest normal modal logic

I've come to the following problem: Let n $\geq$ 1 and $\phi_1 \dots \phi_n$ are modal formulas: Prove or disprove that the following are equivalent: $\bullet$ At least one of the $\phi_1 \dots \...
user avatar
2 votes
1 answer
96 views

Prove $(\Box(p\supset q)\land\Diamond(p\land r))\supset\Diamond(q\land r)$ in K

$(\Box(p\supset q)\land\Diamond(p\land r))\supset\Diamond(q\land r)$ Here's what I have so far: $((p\supset q)\land(p\land r))\supset(q\land r)$, PC-valid WFF $\Box(((p\supset q)\land(p\land r))\...
user avatar
1 vote
1 answer
53 views

How to prove $(\Box (p\supset q)\land\Box( q\supset r))\supset\Box(p\supset r)$ in K

$(\Box (p\supset q)\land\Box( q\supset r))\supset\Box(p\supset r)$ This is problem 2.1a in Hughes/Cresswell pg. 48. So far I have this: $(p \supset q)\supset((q\supset r)\supset(p\supset r)$, PC6 $[(...
user avatar
3 votes
0 answers
78 views

Express exponential reachability in graphs

In first-order logic in the language of graphs, can one express that there is a pair of nodes connected by a path of length $2^m-1$ using only $\leq m$ quantifiers? My question comes from the point of ...
user avatar
  • 4,397
2 votes
1 answer
76 views

By convention, what are the tautologies and the consequence relation of modal logics?

When looking at a modal logic as a propositional logic, it seems like there are a few choices for which sentences form the tautologies (A, B, C below) and what the consequence relation should be (D, E ...
user avatar
  • 6,381
2 votes
1 answer
60 views

What kind of modal logics do you get if you replace the semantics of negation with Routley negation?

What kind of "almost modal" logics do you get is you replace the semantics for negation with the semantics for Routley negation in an otherwise-standard Kripke frame? I.e. if we replace the ...
user avatar
  • 6,381
0 votes
0 answers
34 views

Why express different modal logics in set theoretic terms?

On pg. 31 of Girle's Modal Logics and Philosophy he starts describing various modal logics in set theoretic notation, where the sets denoted are referencing truth-tree formation rules in the context ...
user avatar
0 votes
1 answer
41 views

Satisfiable or valid formulae

(a) $P\rightarrow \diamondsuit Q \wedge \square P \wedge \neg Q$ (b) $\neg \square \neg Q, \diamondsuit \neg P \wedge \square (\square \neg P \rightarrow \diamondsuit Q)$ I want to state for each of ...
user avatar
  • 199
0 votes
1 answer
52 views

Find and prove a necessary and sufficient condition for a Kripke Frame

I am studying Kripke frames in modal logic and I am trying to understand how to solve the task below (the task comes from a workbook and this particular question lacks a conclusion). I know that ...
user avatar
  • 199

1
2 3 4 5
10