Questions tagged [modal-logic]
Questions relating to deductions relating to the expressions "it is necessary that" and "it is possible that"
469
questions
-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.
- 1
-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?
- 1
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 ...
- 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
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 ...
- 77
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 ...
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 ...
- 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 ...
- 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 ...
- 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, ...
- 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 ...
user1021384
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
...
- 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 ...
- 13
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 ...
- 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 ...
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 ...
- 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 ...
- 81
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$,...
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 \...
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 ...
- 81
-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 ...
- 11
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$ ...
- 199
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 ...
- 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 ...
- 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(\...
- 199
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 ...
- 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 ...
- 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) ...
- 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 ...
- 199
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 ...
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, ...
- 199
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 ...
- 199
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 ...
- 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 ...
- 199
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 ...
- 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 ...
- 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,...
- 199
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 ...
- 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 ...
- 644
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 ...
- 644
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$...
- 199
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 \...
- 644
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))\...
- 199
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
$[(...
- 199
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 ...
- 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 ...
- 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 ...
- 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 ...
- 199
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 ...
- 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 ...
- 199