Editing Computation tree logic (section)

==Semantics of CTL==

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

Then the relation of semantic [[entailment]] <math>(\mathcal{M}, s \models \phi)</math> is defined recursively on <math>\phi</math>:
# <math>\Big( (\mathcal{M}, s) \models \top \Big) \land \Big( (\mathcal{M}, s) \not\models \bot \Big)</math>
# <math>\Big( (\mathcal{M}, s) \models p \Big) \Leftrightarrow \Big( p \in L(s) \Big)</math>
# <math>\Big( (\mathcal{M}, s) \models \neg\phi \Big) \Leftrightarrow \Big( (\mathcal{M}, s) \not\models \phi \Big)</math>
# <math>\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)</math>
# <math>\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)</math>
# <math>\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)</math>
# <math>\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)</math>
# <math>\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)</math>
# <math>\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)</math>
# <math>\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)</math>
# <math>\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)</math>
# <math>\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)</math>
# <math>\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)</math>
# <math>\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)</math>
# <math>\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)</math>

===Characterisation of CTL===
Rules 10&ndash;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 <math>s</math>.

===Semantic equivalences===
The formulae <math>\phi</math> and <math>\psi</math> are said to be semantically equivalent if any state in any model that satisfies one also satisfies the other.
This is denoted <math>\phi \equiv \psi</math>

It can be seen that <math>\mathrm A</math> and <math>\mathrm E</math> are duals, being universal and existential computation path quantifiers respectively:
<math>\neg \mathrm A\Phi \equiv \mathrm E \neg \Phi </math>.

Furthermore, so are <math>\mathrm G</math> and <math>\mathrm F</math>.

Hence an instance of [[De Morgan's laws]] can be formulated in CTL:
:<math>\neg AF\phi \equiv EG\neg\phi</math>
:<math>\neg EF\phi \equiv AG\neg\phi</math>
:<math>\neg AX\phi \equiv EX\neg\phi</math>

It can be shown using such identities that a subset of the CTL temporal connectives is adequate if it contains <math>EU</math>, at least one of <math>\{AX,EX\}</math> and at least one of <math>\{EG,AF,AU\}</math> 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.
:<math>AG\phi \equiv \phi \land AX AG \phi</math>
:<math>EG\phi \equiv \phi \land EX EG \phi</math>
:<math>AF\phi \equiv \phi \lor AX AF \phi</math>
:<math>EF\phi \equiv \phi \lor EX EF \phi</math>
:<math>A[\phi U \psi] \equiv \psi \lor (\phi \land AX A [\phi U \psi])</math>
:<math>E[\phi U \psi] \equiv \psi \lor (\phi \land EX E [\phi U \psi])</math>