This article has participated in the activity of “New person creation Ceremony”, and started the road of digging gold creation together.

Temporal logic is divided into linear temporal logic and bifurcated temporal logic. There is a logic called computing tree logic in bifurcated temporal logic

Linear Temporal Logic (LTL)

Linear time properties (LT Properties)

• A linear time attribute is an infinite set of paths on an AP. It is often difficult to directly specify what these attributes are, but we can use logic to concisely specify the laws of these attributes. First let’s look at ways of directly specifying mutual exclusion and starvation freedom at every moment:
  • in
    $AP=\{c_1,c_2\}$To specify a mutex:
    • P_{mutex}=A_0A_1A_2\cdotsPmutex=A0A1A2… And to 0 or less i0 \ leq i0 acuities were I have {c1, c2} \ {c_1, c_2 \} \ ⊈ Ai nsubseteq A_i {c1, c2} ⊈ Ai
  • in
    $AP=\{c_1,w_1,c_2,w_2\}$On the specified hunger free method:
    • P_{nostarve}= A0A1A2 \cdotsPnostarve=A0A1A2

  
  $(\overset{\infty}{\exists } j.w_1 \in A_j)\Rightarrow (\overset{\infty}{\exists } j.c_1 \in A_j)\wedge (\overset{\infty}{\exists } j.w_2 \in A_j)\Rightarrow(\overset{\infty}{\exists } j.c_2 \in A_j)$

• Mutual exclusion: Two processes cannot enter a critical resource at the same time
• Hunger and freedom: While I keep waiting to get to critical resources, I can finally keep getting to critical resources

• What LTL does: Describes the logic of LT features, but does not give specific moments, only relative characteristics of time

The grammar of the LTL

• Propositional logic: Describes the static behavior of a system at a given moment. The three most commonly used in LTL are:

  • Atomic statement: A ∈APa \in APa∈AP
  • The negation law: ¬ϕ\neg \phi¬ϕ
  • Binding law: ϕ∧ψ\phi \wedge \psiϕ∧ψ

• Temporal operator: describes the properties of the system under the trajectory, including the following two basic ones:

  • The next moment was met with ϕ\ PHI ϕ : the infection of ϕ\bigcirc \phi infection, read next
  • ϕ\phi \ ϕ⋃ψ is met at every moment until ϕ⋃ \phi \bigcup \psiϕ⋃

• An operator derived from propositional logic and tense operators:

  • 
    $\phi \vee \psi \equiv \neg(\neg \phi \wedge \neg \psi)$
  • 
    $\phi \Rightarrow \psi \equiv \neg \phi \vee \psi$
  • 
    $\phi \Leftrightarrow \psi \equiv (\phi \Rightarrow \psi) \wedge (\psi \Rightarrow \phi)$
  • 
    $\phi \bigoplus \psi \equiv (\phi \wedge \neg \psi) \wedge (\neg \phi \wedge \psi)$
  • 
    $true \equiv \phi \vee \psi$
  • 
    $false \equiv \neg true$
  • 
    $\Diamond \phi \equiv true \ U \phi$

    ◊\Diamond◊ means that at some point in the future ϕ\phiϕ will be met

  • 
    $\Box \phi \equiv \neg \Diamond \neg \phi$

    □ Box□ reads always, indicating that from this point forward, ϕ\phiϕ will always be met

• These operators were of priority, infection \neg,\bigcirc¬ and infection was borne out first, followed by ⋃\bigcup⋃, then ∨,∧\vee,\wedge∨,∧, and finally →\to→

• An intuitive explanation of the operator:

On a trajectory, if only BBB is satisfied at each moment from a certain point on, then that moment is satisfied at a⋃ba \ Bigcup ba⋃b even if aaa does not occur

• At this point, let’s use LTL language to express the logic of mutual exclusion and hunger freedom at every moment:
  • □ (C1 ∧ C2)\Box \ NEg (C_1 \wedge C_2)□ (C1 ∧ C2)
  • Hungry and free: (□◊ W1 □◊ C1)∧(□◊ W2 □◊ C2)(\Box \Diamond w_1 \Rightarrow \Box \Diamond C_1) \wedge (\Box \Diamond w_2\Rightarrow \Box \ Diamond c_2) (/ ◊ ◊ / w1 ⇒ c1) Sunday afternoon (/ ◊ w2 ⇒ / ◊ c2)

  □◊ W1 \Box \Diamond W_1 □◊w1 looking at the outermost layer first, regard ◊ W1 \Diamond W_1 ◊ W1 as a ϕ\phiϕ, then □ϕ\Box \phi□ϕ means that from this point on, ϕ\phi is always met; Again on the inner layer ◊ W1 \Diamond W_1 ◊ W1, indicating that infinitely many ◊ satisfy W1W_1W1; So, the sum means that from this point on it will always satisfy w1w_1w1 indefinitely

LTL semantic

• By LTL formulas
  $\varphi$The LT properties caused by AP are:
  $Words(\varphi)=\{\sigma \in (2^{AP})^\omega |\sigma \vDash \varphi \}$, including
  $\sigma$It’s a trajectory,
  $\sigma=A_0A_1A_2\cdots$, the LT property can be deduced as follows:
  • σ⊨true\sigma \vDash trueσ⊨true indicates that the path σ\sigma sigma must have a correct path
  • 
    $\sigma \vDash a,iff \ a\in A_0(i.e.,A_0 \vDash a)$If and only if
    $a$It’s a set of states
    $A_0$One of the possibilities is path
    $\sigma$Contained in the
    $a$

    A0A_0A0 covers all the possibilities of the initial state, and AAA is just one of them

  • 
    $\sigma \vDash \varphi_1 \wedge \varphi,iff \ \sigma \vDash \varphi_1 \ and \ \sigma \vDash \varphi_2$Is if path
    $\sigma$Contains the state
    $\varphi_1$and
    $\varphi_2$, then
    $\sigma$contains
    $\varphi_1 \wedge \varphi_2$

    I.E.I.E.I.E. means “that’s it.”

  • 
    $\sigma \vDash \neg \varphi,iff \ \sigma \nvDash \varphi$
  • 
    $\sigma \vDash \bigcirc \varphi,iff \ \sigma[i..] =A_1A_2A_3\cdots\vDash \varphi$

    Sigma/I.. = AiAi ai + 1 + 2. \ sigma/I.. A_ A_iA_ = {I + 1} {2} I + \ cdots sigma/I.. =AiAi+1Ai+2… indicates the suffix of σ\sigmaσ starting from index III

  • 
    $\sigma \vDash \Diamond \varphi,iff \ \exists j \geqslant 0.\sigma [j..] \vDash \varphi$
  • 
    $\sigma \vDash \Box \varphi,iff \ \forall j \geqslant 0.\sigma [j..] \vDash \varphi$
  • 
    $\sigma \vDash \Box\Diamond \varphi,iff \ \forall j \geqslant 0.\exists \geqslant \sigma [i..] \vDash \varphi$
  • 
    $\sigma \vDash \Diamond\Box \varphi,iff \ \exists j \geqslant 0.\forall \geqslant \sigma [i..] \vDash \varphi$
• Example:

According to the figure above, we can deduce four properties of this TS:

• From the initial state, each state satisfies AAA, i.e. TS⊨□aTS \vDash \Box aTS⊨□ A
• From the initial state, each state satisfies, if the state does not satisfy BBB, then the state satisfies A ∧¬ba \wedge \neg ba∧¬b, TS ⊨ – (such ⇒ / (a Sunday afternoon b) b) TS \ vDash \ Box (\ \ Rightarrow neg b \ Box (a, wedge, neg b)) TS ⊨ – (such ⇒ b/(a Sunday afternoon b))
• Starting from the initial state s1S_1S1 on the left, the next state can satisfy both AAA and BBB. However, starting from the initial state on the right, the next state of S3S_3S3 is still S3S_3S3. S3s_3s3 cannot satisfy both AAA and BBB. Therefore, The infection of ⊭ infection (A ∧ B) Of TS \nvDash \ Bigcirc (A \wedge B)TS⊭ infection (A ∧ B)
• Starting from the initial state s1S_1S1 on the left, each state satisfies BBB until a∧¬ba \wedge \neg ba∧¬b is no longer satisfied, but from the initial state on the right, it does not. So TS⊭b⋃(a∧¬b)TS \nvDash b \ Bigcup (a \wedge \neg b)TS⊭b⋃(a∧¬b)

Use LTL to denote our common properties

• Reachability
  • ◊ψ\Diamond \psi◊ψ : Simple Reachability
  • ϕ⋃ψ\phi \bigcup \psiϕ⋃ψ

  ◊ A \neg \Diamond a¬ a:

• Safety:
  • Invariant: □ϕ\Box \phi□ϕ
• Liveness: □(ϕ satellite ψ)and others\Box(\phi \Rightarrow \Diamond \psi) and others□(ϕ satellite ψ)and others
• Fairness: □◊ϕ and others\Box \Diamond \phi \ and \ others□◊ϕ and others
• Equivalence: If Words (ϕ) = Words (bits) Words (\ phi) = Words (\ psi) Words (ϕ) = Words (bits), then the ϕ \ phi ϕ and bits of \ psi bits of equivalence, expressed as ϕ ≡ bits, phi, equiv, psi ϕ ≡ bits
• Duality Law:
  • 
    $\neg \Box \phi \equiv \Diamond \neg \phi$
  • 
    $\neg \Diamond \phi \equiv \Box \neg \phi$
  • 
    $\neg \bigcirc \phi \equiv \bigcirc \neg \phi$
• Idempotency law:
  • 
    $\Box \Box \phi \equiv \Box \phi$
  • 
    $\Diamond \Diamond \phi \equiv \Diamond \phi$
  • 
    $\phi \bigcup ( \phi \bigcup \psi) \equiv \phi \bigcup \psi$
  • 
    $(\phi \bigcup \psi) \bigcup \psi \equiv \phi \bigcup \psi$
• Absorption law:
  • 
    $\Diamond \Box \Diamond \phi \equiv \Box \Diamond \phi$
  • 
    $\Box \Diamond \Box \phi \equiv \Diamond \Box \phi$
• Distribution law:
  • 
    $\bigcirc(\phi \bigcup \psi) \equiv (\bigcirc \phi) \bigcup (\bigcirc \psi)$
  • 
    $\Diamond(\phi \vee\psi) \equiv \Diamond \phi \vee \Diamond \psi$
  • 
    $\Box(\phi \wedge \psi) \equiv \Box \phi \wedge \Box \psi$

  Note:

  • 
    $\Diamond(\phi \bigcup \psi) \not\equiv (\Diamond\phi) \bigcup (\Diamond\psi)$
  • 
    $\Diamond(\phi \wedge \psi) \not\equiv \Diamond\phi \wedge \Diamond\psi$
  • 
    $\Box(\phi \vee \psi) \not\equiv \Box \phi \vee \Box \psi$
  • ◊(A ∧ B)≢◊ A ∧◊ B \Diamond(a \wedge b) \not\equiv \Diamond A \wedge \Diamond B (a∧ B)≡◊ A ∧◊ B:

$TS\nvDash \Diamond(a \wedge b)$, but
$TS\vDash \Diamond a \wedge \Diamond b)$

• Expansion laws:
  • 
    $\phi \bigcup \psi \equiv \psi \vee ( \phi \wedge \bigcirc ( \phi \bigcup \psi))$
  • 
    $\Diamond \phi \equiv \phi \vee \bigcirc \Diamond \phi))$
  • 
    $\Box \phi \equiv \phi \wedge \bigcirc \Box \phi))$

A full description of these features is available in this article: blog.csdn.net/qq_37400312…

Fairness

• Definition: If all processes in a path are consistent with the actual conditions, the path is fair.
  • For paths that do not meet the fairness requirement, the paths can be excluded to ensure fairness.
  • Hunger free usually occurs under conditions of fairness.
  • Fairness is usually necessary to establish a problem of activity.
• Examples of life:
  • Interleaved execution of two traffic light processes at an intersection:
    $TS = TrLight_1||TrLight_2$Given an active property, the natural language description is: every traffic light is green an infinite number of times. This property means that the traffic light will be in the green state for an infinite number of times in the process of state transformation.
    • Path: {red1, red2}, {green1, red2}, {red1, green2}, {green1, red2}. \ {red_1, red_2 \}, \ {green_1, red_2 \}, \ {red_1, green_2 \}, \ {green_1, red _2\}\cdots{red1,red2},{green1,red2},{red1,green2},{green1,red2},{green1,red2}…
    • Path: {red1, red2}, {green1, red2}, {red1, red2}, {green1, red2}. \ {red_1, red_2 \}, \ {green_1, red_2 \}, \ {red_1, red_2 \}, \ {green_1, red_2 \} \cdots{red1,red2},{green1,red2},{red1,red2},{green1,red2},{green1,red2},{green1,red2}…

Fairness constraints

• Explanation: a program, there are some paths will never perform, so, no matter the path after the execution is right or wrong, we don’t need to test it, so we are in the process of verification, need to add some constraints, to avoid us to verify some never walk the path, this constraint, we call it a fairness constraint

• Action-based fairness is represented by A-fair. There are three cases: unconditional fairness, strong fairness, and weak fairness

  • For one that has no initial state
    $TS = (S,Act,\to,I,AP,L)$
    • No initial state
    • 
      $A \subseteq Act$
    • Infinite executing fragment ρ=s0→α0s1→α1s2… \rho = s_0 \overset{\alpha_0}{\rightarrow} s_1 \overset{\alpha_1}{\rightarrow} S_2 \ cdots rho = s0 – alpha 0 s1 – alpha 1 s2..
  • Unconditional A-fair: If the path meets the Unconditional fairness constraints, then
    $A$One or more actions that exist in the.
    • Explanation: When ρ\rhoρ is an unconditional fair path, this is done infinitely often for actions in AAA on this path, Such as A = {} omega ⊆ Act {NC, W, C}, rho = s0 > NCs1 > Ws2 to Cs3, NC.. Sn – NC.. Sm – NC. A = \ {\ omega \} \ subseteq Act \ {NC, W, C \}, \ rho = s_0 \overset{NC}{\rightarrow}s_1\overset{W}{\rightarrow}s_2\overset{C}{\rightarrow}s_3\overset{NC}{\rightarrow}\cdots s_n\overset{NC}{\rightarrow}\cdots s_m Overset {NC}{\rightarrow}\cdotsA={ω}⊆Act{NC,W,C},ρ=s0→NCs1→Ws2→Cs3→NC… sn→NC… sm→NC
    • Formula:

  True ∀ K induces 0,∃j induces K,α J ∈Atrue \Rightarrow \forall K \geqslant 0,\exist J \geqslant K,\alpha_j \in Atrue k induces 0,∃ J induces K,α J ∈A For any position KKK of the action sequence in the trajectory, A position JJJ can always be found on or after KKK, and the action of this position αj∈A\alpha_j \in Aαj∈A

  • Strongly Fair (Strongly A-Fair) : If the trajectory meets the Strongly fair constraint, if
    $A$Exists in an infinite number of times an action is intended to be performed, which results
    $A$There are one or more actions that can be executed indefinitely.
    • Formula:

  (∀ ⩾ 0 k, ∃ ⩾ k j, Act (sj) studying A indicates ∅) ⇒ ∀ ⩾ 0 k, ∃ ⩾ k j, alpha j ∈ a. (\ \ geqslant forall k 0, \ exist j \ geqslant k, Act (s_j) \ cap A \ neq \ varnothing) \ \ geqslant Rightarrow \ forall k 0, \ exist j \ geqslant k \ alpha_j \ in A (∀ ⩾ 0 k, ∃ ⩾ k j, Act (sj) studying A  = ∅) ⇒ ∀ ⩾ 0 k, ∃ ⩾ k j, alpha j ∈ a. For any position KKK of the state sequence in the trajectory, if a position JJJ can always be found on or after KKK, Such that all direct actions of state sjs_jsj Act(sj)Act(s_j)Act(sj) have actions in AAA (i.e. Act(Sj)∩A≠∅Act(s_j) \cap A \neq \varnothingAct(sj)∩A=∅, An infinite number of times you want to perform), then there must be an infinite number of times you perform an action in AAA

  • Weakly fair (Weakly fair) : If the locus meets the Weakly fair constraint, if
    $A$At some point in time, there are infinite times
    $A$If the action in the
    $A$There are one or more actions that can be executed indefinitely.
    • Formula:

  (∃ ⩾ 0 k, ∀ j ⩾ k, Act (sj) studying A indicates ∅) ⇒ ∀ ⩾ 0 k, ∃ ⩾ k j, alpha j ∈ a. (\ \ geqslant exist k 0, \ \ geqslant forall j k, Act (s_j) \ cap A \ neq \ varnothing) \ \ geqslant Rightarrow \ forall k 0, \ exist j \ geqslant k \ alpha_j \ in A (∃ ⩾ 0 k, ∀ j ⩾ k, Act (sj) studying A  = ∅) ⇒ ∀ ⩾ 0 k, ∃ ⩾ k j, alpha j ∈ a. For a certain position KKK of the state sequence in the trajectory, if a position JJJ can always be found on or behind KKK, Such that all direct actions of state sjs_jsj Act(sj)Act(s_j)Act(sj) have actions in AAA (i.e. Act(Sj)∩A≠∅Act(s_j) \cap A \neq \varnothingAct(sj)∩A=∅, An infinite number of times you want to perform), then there must be an infinite number of times you perform an action in AAA

  Among them, The Act (s) = {alpha ∈ Act ∣ ∃ ‘s ∈ s, s – alpha s’} Act (s) = \ {\ alpha \ | \ exist in Act s’ \ in s, s \ overset {\ alpha} {\ rightarrow} s’ \} Act (s) = {alpha ∈ Act ∣ ∃ ‘s ∈ s, s – alpha s’}

  • Example 1:
    • Take action A={enter1,enter2}A=\{enter_1,enter_2 \}A={enter1,enter2} to determine whether the red trace below satisfies strong fairness. (The red track starts at position 2, and the status wheel at position 234 is executed indefinitely in the form of a closed loop)

– Answer: – In the red track, we see the state
$\left \langle w_1,n_2,y=1 \right \rangle$An infinite number of times you want to execute
$enter_1$The state of
$\left \langle w_1,w_2,y=1 \right \rangle$An infinite number of times you want to execute
$enter_1$and
$enter_2$The end result of a trajectory is an infinite number of executions
$enter_2$, so this trajectory satisfies strong fairness.

• Example 2:

  • Take action A={req2}A= {req_2 \}A={req2} and judge whether the red track below satisfies weak fairness. (The red track starts at position 1, and the status wheel at position 123 is executed indefinitely in the form of a closed circle)

  

  • The answer:
    • In the red track, we see that starting from the first state, every state wants to do req2REq_2REQ2 infinitely many times, but there is no infinite number of times in AAA, so this trajectory does not satisfy weak fairness.

• The termination of a procedure or process under unconditional fairness:

$\begin{aligned} proc \ Inc \ =& \ while \ \left \langle x \geqslant 0 \ do \ x := x + 1 \right \rangle \ od \\ proc \ Reset \ = &x := −1 \end{aligned}$

XXX is a shared variable with an initial value of 0

• Fairness has a strong or weak constraint on the path
  • The purpose of fairness is to exclude “unreasonable” paths, but if we remove excessive or insufficient, the verification results will be affected to some extent.
  • Too much constraint (when removing excess) :
    • A total path ⊆\subseteq a reasonable path ⊆\subseteq a ⊆ path for verification
    • If the validation result is false, then the model corresponding to a reasonable path is problematic
    • If the verification result is true, it does not mean that the model corresponding to the reasonable path is correct
  • Too weak constraint (when insufficient is removed) :
    • A total path ⊆\subseteq a verification path ⊆\subseteq a reasonable path
    • If the verification result is true, then the model corresponding to the reasonable path is correct
    • If the validation result is false, there is no indication that the model corresponding to a reasonable path is wrong

The fairness section is covered in another article, but I have repasted it to make it easier to understand the fairness constraints of LTL. The link to the other article is blog.csdn.net/qq_37400312…

Fairness constraints of LTL

Assuming that ϕ\phiϕ and ψ\psiψ are propositional logic formulae on AP, then

• The unconditional LTL fairness constraints are of the following form: UFAIR =□◊ψufair = \Box \Diamond \ pSIufair =□◊ψ
• The strong LTL fairness constraint is of the following form: Sfair =□◊ϕ→□◊ ϕ = sfair= Box \Diamond \phi \to Box \Diamond \psisfair=□◊ϕ→□ ϕ, Then every moment from now on will be able to execute ψ\psi sometime in the future
• The form of the weak LTL fairness constraint is as follows: Wfair =◊□ϕ→◊□ψwfair = \Diamond \Box \phi \to \Diamond \Box \psiwfair=◊□ϕ→ ψ, which will always want to implement ϕ\phi at some point in the future, Then it will always be able to execute ψ\psi at some point in the future

ϕ\phiϕ means that they want to administer, and ψ\psiψ means that they can administer

The fairness hypothesis of LTL

• Strong fairness hypothesis: Sfair =⋃0< I ⩽k(□◊ϕ I →□◊ψ I)sfair=\underset{0< I \leqslant k}{\bigcup}(\Box\Diamond \phi_i \to \Box\Diamond Sfair \ psi_i) = 0 < I ⩽ k ⋃ (/ ◊ ϕ I – – ◊ bits of I)
• Common format: Fair = Ufair ∧sfair∧wfairfair = Ufair \wedge sfair \wedge Wfairfair = Ufair ∧sfair∧wfair
• Rule of thumb: strong or unconditional fairness hypothesis is conducive to solving disputes, while weak fairness is sufficient to solve the indecisiveness caused by interweaving

Computation Tree Logic (CTL)

Linear temporal logic and branching temporal logic

• Linear temporal logic: statements with (all) paths starting with states. Such as:
  • S ⊨□(x⩽20)s \vDash \Box(x \leqslant 20)s⊨□(x⩽20), indicating that all paths starting from S satisfy the requirements of x⩽20x\leqslant 20x X.X.X
• Branching temporal logic: statements about all or some paths that begin in a state. Such as:
  • S ⊨∀□(x⩽20) S \vDash \ Forall \Box (x \leqslant 20) S ⊨∀□(x \leqslant 20), means that all paths starting from S are satisfied with X ⩽20x\leqslant 20x smiley 20
  • S ⊨∃□(x⩽20)s \vDash \exists \Box (x \leqslant 20)s⊨∃□(x⩽20) : indicates that a path exists from s that meets the requirements of x⩽20x\leqslant 20x X.X.X

To check whether there is ∃φ\exists \varphi∃φ in the LTL, you can detect it with THE ∀¬φ\forall \neg \varphi∀¬φ of the CTL

Transition systems to Trees

The Transition systems:Trees:We see that the Transition systems have an infinite number of paths, and we can represent each path with numbers, but we can’t represent all of them, and this is the first four transitions, and we can’t represent all of them, But we can tell if a path satisfies a property by using Transition systems.

States and operators

• Statements on states:
  • Atomic statement: A ∈APa \in APa∈AP
  • The negation law: ¬ϕ\neg \phi¬ϕ
  • Binding law: ϕ∧ψ\phi \wedge \psiϕ∧ψ
  • There is a path to achieving ϕ\phiϕ : ∃ϕ\exists \phi∃
  • All paths can realize ϕ\phiϕ : ∀ϕ\forall \phi∀ϕ
• Statements on paths:
  • The next state was borne out: the infection of ϕ\ bigcirC \phi was borne out
  • ϕ\phiϕ is satisfied until ϕ psi is satisfied: ϕ⋃ ϕ phi bigcup psiϕ⋃ψ

  Infection \bigcirc infection and ⋃\bigcup⋃ will be used alternately with ∃\exists∃ and forall∀

• Derivation operator:
  • There are paths meet ϕ \ phi ϕ : ∃ ◊ ϕ ≡ ∃ (true ⋃ ϕ), the exists, Diamond, phi \ equiv \ exists (true \ bigcup \ phi) ∃ ◊ ϕ ≡ ∃ (true ⋃ ϕ)
  • All the paths satisfy ϕ \ phi ϕ : ∀ ◊ ϕ ≡ ∀ (true ⋃ ϕ), forall, Diamond, phi \ equiv \ forall (true \ bigcup \ phi) ∀ ◊ ϕ ≡ ∀ (true ⋃ ϕ)
  • Path exists always meet ϕ \ phi ϕ : ∃ / ϕ ≡ such ∀ ◊ such ϕ, exists, Box, phi \ equiv \ neg \ forall, Diamond, neg, phi ∃ / ϕ ≡ such ∀ ◊ such ϕ
  • All paths always meet ϕ \ phi ϕ : ∀ / ϕ ≡ such ∃ ◊ such ϕ \ forall \ Box \ phi \ equiv \ neg \ exists, Diamond, neg, phi ∀ / ϕ ≡ such ∃ ◊ such ϕ
  • Weak until:

  
  $\exists(\phi W \psi) \equiv \neg \forall ((\phi \wedge \neg \psi)\bigcup(\neg \phi \wedge \neg \psi))$
  $\forall (\phi W \psi) \equiv \neg \exists((\phi \wedge \neg \psi)\bigcup(\neg \phi \wedge \neg \psi))$

The semantic

Visualization of semantics

Semantics of CTL state formula

S ⊨ϕs \vDash \phis⊨ϕ represents ϕ if and only if the formula ϕ\phiϕ holds in the state SSS

• S ⊨as \vDash as⊨a, is true if aaa belongs to a path from state SSS, that is, a∈L(s)a \in L(s)a∈L(s)
• S ⊨ such ϕ s \ vDash \ neg \ phis ⊨ such ϕ, iff rope (s ⊨ ϕ) iff \ \ neg (s \ vDash \ phi) iff rope (s ⊨ ϕ)
• S ⊨ such ϕ s \ vDash \ neg \ phis ⊨ such ϕ, iff (s ⊨ ϕ) (s ⊨ bits) iff \ [s \ vDash \ phi) (s \ vDash \ psi) iff (s ⊨ ϕ) (s ⊨ bits)
• S ⊨∃ϕs \vDash \exists \phis⊨∃ϕ, iff iff ~iff some paths from SSS satisfying π\ PI π⊨ϕ\ PI \vDash \phiπ⊨ϕ
• S ⊨∀ϕs \vDash \forall \phis⊨∀ϕ, iff iff ~ all paths of iff from SSS satisfy π\ PI \ π π⊨ϕ\ PI \vDash \phiπ⊨ϕ

Semantics of CTL path formula

ϕ ⊨ϕ\ PI \vDash \phiπ⊨ϕ indicates that the path PI \ PI π satisfies the formula ϕ\phiϕ

• 
  $\pi \vDash \bigcirc \phi iff \ \pi [1] \vDash \phi$
• 
  $\pi \vDash \phi \ \bigcup \psi \ iff \ (\exists j \geqslant 0.\pi [j] \vDash \psi \wedge \forall 0 \leqslant k <j.\pi[k]\vDash \phi)$

π[I]\ PI [I]π[I] denotes the state on path π\ PI π sis_isi

Migrating system semantics

• Meet state of CTL formula ϕ \ phi ϕ collection of Sat (ϕ) the Sat (\ phi) the Sat (ϕ) is defined as: the Sat (ϕ) = {s ∈ s ∣ s ⊨ ϕ} the Sat (\ phi) = \ \ {s in s \ | s vDash \ phi \} the Sat (ϕ) = {s ∈ s ∣ s ⊨ ϕ}
• As all initial states satisfy ϕ\phiϕ, TS satisfies the CTL formula: TS⊨ϕ iff ∀s0⊨ϕTS \vDash \phi \ iff \forall_{s_0} \vDash \phiTS⊨ϕ iff ∀s0⊨ϕ

TS may not meet ϕ\phiϕ nor even ϕ\neg \phi¬ϕ, i.e., TS⊭ and TS⊭¬ϕTS \nvDash \phi \ and \ TS \nvDash \neg \phiTS⊭ϕ and TS \nvDash \neg \phiTS⊭ϕ and TS \nvDash \neg \phiTS⊭ϕ and TS \nvDash \neg \phiTS

Some common properties of CTLS

• Equivalence: If the two CTLS: ϕ \ phi ϕ and bits of \ psi bits of Sat (ϕ) = Sat (bits) the Sat (\ phi) = Sat (\ psi) the Sat (ϕ) = Sat (bits), the ϕ \ phi ϕ and bits of \ psi bits of equivalence, namely ϕ ≡ bits, phi, equiv, psi ϕ ≡ bits

$\phi \equiv \psi \ iff \ TS \vDash \phi \wedge TS \vDash \psi$

• Expansion laws
  • 
    $\forall (\phi \bigcup \psi) \equiv \psi \vee (\phi \wedge \forall \bigcirc \forall (\phi \bigcup \psi))$
  • 
    $\forall \Diamond \phi \equiv \phi \vee \forall \bigcirc \forall \Diamond \phi$
  • 
    $\forall \Box \phi \equiv \phi \wedge \forall \bigcirc \forall \Box \phi$
  • 
    $\exists (\phi \bigcup \psi) \equiv \psi \vee (\phi \wedge \forall \bigcirc \forall (\phi \bigcup \psi))$
  • 
    $\exists \Diamond \phi \equiv \phi \vee \exists \bigcirc \exists \Diamond \phi$
  • 
    $\exists \Box \phi \equiv \phi \wedge \exists \bigcirc \exists \Box \phi$
• Distribution laws
  • 
    $\forall \Box(\phi \wedge \psi) \equiv \forall \Box \phi \wedge \forall \Box \psi$
  • 
    $\exists \Diamond (\phi \vee \psi) \equiv \exists \Diamond \phi \vee \exists \Diamond \psi$

  • 
    $\exists \Box(\phi \wedge \psi) \not\equiv \exists \Box \phi \wedge \exists \Box \psi$
  • 
    $\forall \Diamond (\phi \vee \psi) \equiv \forall \Diamond \phi \vee \forall \Diamond \psi$