Semantics of CTL Computation tree logic

1 semantics of ctl

1.1 definition
1.2 characterisation of ctl
1.3 semantic equivalences

semantics of ctl
definition

ctl formulae interpreted on transition systems. transition system triple





m


=
(
s
,
→
,
l
)


{\displaystyle {\mathcal {m}}=(s,\rightarrow ,l)}

,



s


{\displaystyle s}

set of states,



→⊆
s
×
s


{\displaystyle \rightarrow \subseteq s\times s}

transition relation, assumed serial, i.e. every state has @ least 1 successor, ,



l


{\displaystyle l}

labelling function, assigning propositional letters states. let





m


=
(
s
,
→
,
l
)


{\displaystyle {\mathcal {m}}=(s,\rightarrow ,l)}

such transition model

with



s
∈
s
,
ϕ
∈
f


{\displaystyle s\in s,\phi \in f}

f set of wffs on language of





m




{\displaystyle {\mathcal {m}}}

.

then relation of semantic entailment



(


m


,
s
⊨
ϕ
)


{\displaystyle ({\mathcal {m}},s\models \phi )}

defined structural induction on



ϕ


{\displaystyle \phi }

:

characterisation of ctl

rules 10–15 above refer computation paths in models , characterise computation tree ; assertions nature of infinitely deep computation tree rooted @ given state



s


{\displaystyle s}

.

semantic equivalences

the formulae



ϕ


{\displaystyle \phi }

,



ψ


{\displaystyle \psi }

said semantically equivalent if state in model satisfies 1 satisfies other. denoted



ϕ
≡
ψ


{\displaystyle \phi \equiv \psi }

it can seen , e duals, being universal , existential computation path quantifiers respectively:



¬
a
ϕ
≡
e
¬
ϕ


{\displaystyle \neg a\phi \equiv e\neg \phi }

.

furthermore, g , f.

hence instance of de morgan s laws can formulated in ctl:

¬
a
f
ϕ
≡
e
g
¬
ϕ


{\displaystyle \neg af\phi \equiv eg\neg \phi }






¬
e
f
ϕ
≡
a
g
¬
ϕ


{\displaystyle \neg ef\phi \equiv ag\neg \phi }






¬
a
x
ϕ
≡
e
x
¬
ϕ


{\displaystyle \neg ax\phi \equiv ex\neg \phi }

it can shown using such identities subset of ctl temporal connectives adequate if contains



e
u


{\displaystyle eu}

, @ least 1 of



{
a
x
,
e
x
}


{\displaystyle \{ax,ex\}}

, @ least 1 of



{
e
g
,
a
f
,
a
u
}


{\displaystyle \{eg,af,au\}}

, boolean connectives.

the important equivalences below called expansion laws; allow unfold verification of ctl connective towards successors in time.

a
g
ϕ
≡
ϕ
∧
a
x
a
g
ϕ


{\displaystyle ag\phi \equiv \phi \land axag\phi }






e
g
ϕ
≡
ϕ
∧
e
x
e
g
ϕ


{\displaystyle eg\phi \equiv \phi \land exeg\phi }






a
f
ϕ
≡
ϕ
∨
a
x
a
f
ϕ


{\displaystyle af\phi \equiv \phi \lor axaf\phi }






e
f
ϕ
≡
ϕ
∨
e
x
e
f
ϕ


{\displaystyle ef\phi \equiv \phi \lor exef\phi }






a
[
ϕ
u
ψ
]
≡
ψ
∨
(
ϕ
∧
a
x
a
[
ϕ
u
ψ
]
)


{\displaystyle a[\phi u\psi ]\equiv \psi \lor (\phi \land axa[\phi u\psi ])}






e
[
ϕ
u
ψ
]
≡
ψ
∨
(
ϕ
∧
e
x
e
[
ϕ
u
ψ
]
)


{\displaystyle e[\phi u\psi ]\equiv \psi \lor (\phi \land exe[\phi u\psi ])}