Computation tree logic

The logical operators are the usual ones: ¬, ∨, ∧, ⇒ and ⇔. Along with these operators CTL formulas can also make use of the boolean constants true and false.

The temporal operators are the following:

• Quantifiers over paths
  • A Φ – All: Φ has to hold on all paths starting from the current state.
  • E Φ – Exists: there exists at least one path starting from the current state where Φ holds.
• Path-specific quantifiers
  • X φ – Next: φ has to hold at the next state (this operator is sometimes noted N instead of X).
  • G φ – Globally: φ has to hold on the entire subsequent path.
  • F φ – Finally: φ eventually has to hold (somewhere on the subsequent path).
  • φ U ψ – Until: φ has to hold at least until at some position ψ holds. This implies that ψ will be verified in the future.
  • φ W ψ – Weak until: φ has to hold until ψ holds. The difference with U is that there is no guarantee that ψ will ever be verified. The W operator is sometimes called "unless".

In CTL*, the temporal operators can be freely mixed. In CTL, operators must always be grouped in pairs: one path operator followed by a state operator. See the examples below. CTL* is strictly more expressive than CTL.

In CTL there are minimal sets of operators. All CTL formulas can be transformed to use only those operators. This is useful in model checking. One minimal set of operators is: {true, ∨, ¬, EG, EU, EX}.

Some of the transformations used for temporal operators are:

• EFφ == E[trueU(φ)] ( because Fφ == [trueU(φ)] )
• AXφ == ¬EX(¬φ)
• AGφ == ¬EF(¬φ) == ¬ E[trueU(¬φ)]
• AFφ == A[trueUφ] == ¬EG(¬φ)
• A[φUψ] == ¬( E[(¬ψ)U¬(φ∨ψ)] ∨ EG(¬ψ) )

CTL formulae are interpreted over transition systems. A transition system is a triple ${\displaystyle {\mathcal {M}}=(S,{\rightarrow },L)}$, where ${\displaystyle S}$ is a set of states, ${\displaystyle {\rightarrow }\subseteq S\times S}$ is a transition relation, assumed to be serial, i.e. every state has at least one successor, and ${\displaystyle L}$ is a labelling function, assigning propositional letters to states. Let ${\displaystyle {\mathcal {M}}=(S,\rightarrow ,L)}$ be such a transition model, with ${\displaystyle s\in S}$, and ${\displaystyle \phi \in F}$, where ${\displaystyle F}$ is the set of well-formed formulas over the language of ${\displaystyle {\mathcal {M}}}$.

Then the relation of semantic entailment ${\displaystyle ({\mathcal {M}},s\models \phi )}$ is defined recursively on ${\displaystyle \phi }$:

1. ${\displaystyle {\Big (}({\mathcal {M}},s)\models \top {\Big )}\land {\Big (}({\mathcal {M}},s)\not \models \bot {\Big )}}$
2. ${\displaystyle {\Big (}({\mathcal {M}},s)\models p{\Big )}\Leftrightarrow {\Big (}p\in L(s){\Big )}}$
3. ${\displaystyle {\Big (}({\mathcal {M}},s)\models \neg \phi {\Big )}\Leftrightarrow {\Big (}({\mathcal {M}},s)\not \models \phi {\Big )}}$
4. ${\displaystyle {\Big (}({\mathcal {M}},s)\models \phi _{1}\land \phi _{2}{\Big )}\Leftrightarrow {\Big (}{\big (}({\mathcal {M}},s)\models \phi _{1}{\big )}\land {\big (}({\mathcal {M}},s)\models \phi _{2}{\big )}{\Big )}}$
5. ${\displaystyle {\Big (}({\mathcal {M}},s)\models \phi _{1}\lor \phi _{2}{\Big )}\Leftrightarrow {\Big (}{\big (}({\mathcal {M}},s)\models \phi _{1}{\big )}\lor {\big (}({\mathcal {M}},s)\models \phi _{2}{\big )}{\Big )}}$
6. ${\displaystyle {\Big (}({\mathcal {M}},s)\models \phi _{1}\Rightarrow \phi _{2}{\Big )}\Leftrightarrow {\Big (}{\big (}({\mathcal {M}},s)\not \models \phi _{1}{\big )}\lor {\big (}({\mathcal {M}},s)\models \phi _{2}{\big )}{\Big )}}$
7. ${\displaystyle {\bigg (}({\mathcal {M}},s)\models \phi _{1}\Leftrightarrow \phi _{2}{\bigg )}\Leftrightarrow {\bigg (}{\Big (}{\big (}({\mathcal {M}},s)\models \phi _{1}{\big )}\land {\big (}({\mathcal {M}},s)\models \phi _{2}{\big )}{\Big )}\lor {\Big (}\neg {\big (}({\mathcal {M}},s)\models \phi _{1}{\big )}\land \neg {\big (}({\mathcal {M}},s)\models \phi _{2}{\big )}{\Big )}{\bigg )}}$
8. ${\displaystyle {\Big (}({\mathcal {M}},s)\models AX\phi {\Big )}\Leftrightarrow {\Big (}\forall \langle s\rightarrow s_{1}\rangle {\big (}({\mathcal {M}},s_{1})\models \phi {\big )}{\Big )}}$
9. ${\displaystyle {\Big (}({\mathcal {M}},s)\models EX\phi {\Big )}\Leftrightarrow {\Big (}\exists \langle s\rightarrow s_{1}\rangle {\big (}({\mathcal {M}},s_{1})\models \phi {\big )}{\Big )}}$
10. ${\displaystyle {\Big (}({\mathcal {M}},s)\models AG\phi {\Big )}\Leftrightarrow {\Big (}\forall \langle s_{1}\rightarrow s_{2}\rightarrow \ldots \rangle (s=s_{1})\forall i{\big (}({\mathcal {M}},s_{i})\models \phi {\big )}{\Big )}}$
11. ${\displaystyle {\Big (}({\mathcal {M}},s)\models EG\phi {\Big )}\Leftrightarrow {\Big (}\exists \langle s_{1}\rightarrow s_{2}\rightarrow \ldots \rangle (s=s_{1})\forall i{\big (}({\mathcal {M}},s_{i})\models \phi {\big )}{\Big )}}$
12. ${\displaystyle {\Big (}({\mathcal {M}},s)\models AF\phi {\Big )}\Leftrightarrow {\Big (}\forall \langle s_{1}\rightarrow s_{2}\rightarrow \ldots \rangle (s=s_{1})\exists i{\big (}({\mathcal {M}},s_{i})\models \phi {\big )}{\Big )}}$
13. ${\displaystyle {\Big (}({\mathcal {M}},s)\models EF\phi {\Big )}\Leftrightarrow {\Big (}\exists \langle s_{1}\rightarrow s_{2}\rightarrow \ldots \rangle (s=s_{1})\exists i{\big (}({\mathcal {M}},s_{i})\models \phi {\big )}{\Big )}}$
14. ${\displaystyle {\bigg (}({\mathcal {M}},s)\models A[\phi _{1}U\phi _{2}]{\bigg )}\Leftrightarrow {\bigg (}\forall \langle s_{1}\rightarrow s_{2}\rightarrow \ldots \rangle (s=s_{1})\exists i{\Big (}{\big (}({\mathcal {M}},s_{i})\models \phi _{2}{\big )}\land {\big (}\forall (j<i)({\mathcal {M}},s_{j})\models \phi _{1}{\big )}{\Big )}{\bigg )}}$
15. ${\displaystyle {\bigg (}({\mathcal {M}},s)\models E[\phi _{1}U\phi _{2}]{\bigg )}\Leftrightarrow {\bigg (}\exists \langle s_{1}\rightarrow s_{2}\rightarrow \ldots \rangle (s=s_{1})\exists i{\Big (}{\big (}({\mathcal {M}},s_{i})\models \phi _{2}{\big )}\land {\big (}\forall (j<i)({\mathcal {M}},s_{j})\models \phi _{1}{\big )}{\Big )}{\bigg )}}$

Rules 10–15 above refer to computation paths in models and are what ultimately characterise the "Computation Tree"; they are assertions about the nature of the infinitely deep computation tree rooted at the given state ${\displaystyle s}$.

The formulae ${\displaystyle \phi }$ and ${\displaystyle \psi }$ are said to be semantically equivalent if any state in any model that satisfies one also satisfies the other. This is denoted ${\displaystyle \phi \equiv \psi }$

It can be seen that ${\displaystyle \mathrm {A} }$ and ${\displaystyle \mathrm {E} }$ are duals, being universal and existential computation path quantifiers respectively: ${\displaystyle \neg \mathrm {A} \Phi \equiv \mathrm {E} \neg \Phi }$.

Furthermore, so are ${\displaystyle \mathrm {G} }$ and ${\displaystyle \mathrm {F} }$.

Hence an instance of De Morgan's laws can be formulated in CTL:

${\displaystyle \neg AF\phi \equiv EG\neg \phi }$

${\displaystyle \neg EF\phi \equiv AG\neg \phi }$

${\displaystyle \neg AX\phi \equiv EX\neg \phi }$

It can be shown using such identities that a subset of the CTL temporal connectives is adequate if it contains ${\displaystyle EU}$, at least one of ${\displaystyle \{AX,EX\}}$ and at least one of ${\displaystyle \{EG,AF,AU\}}$ and the boolean connectives.

The important equivalences below are called the expansion laws; they allow unfolding the verification of a CTL connective towards its successors in time.

${\displaystyle AG\phi \equiv \phi \land AXAG\phi }$

${\displaystyle EG\phi \equiv \phi \land EXEG\phi }$

${\displaystyle AF\phi \equiv \phi \lor AXAF\phi }$

${\displaystyle EF\phi \equiv \phi \lor EXEF\phi }$

${\displaystyle A[\phi U\psi ]\equiv \psi \lor (\phi \land AXA[\phi U\psi ])}$

${\displaystyle E[\phi U\psi ]\equiv \psi \lor (\phi \land EXE[\phi U\psi ])}$