Operators Computation tree logic
1 operators
1.1 logical operators
1.2 temporal operators
1.3 minimal set of operators
operators
logical operators
the logical operators usual ones:
¬
,
∨
,
∧
,
⇒
{\displaystyle \neg ,\lor ,\land ,\rightarrow }
,
⇔
{\displaystyle \leftrightarrow }
. along these operators ctl formulas can make use of boolean constants true , false.
temporal operators
the temporal operators following:
quantifiers on paths
a
ϕ
{\displaystyle \phi }
– all:
ϕ
{\displaystyle \phi }
has hold on paths starting current state.
e
ϕ
{\displaystyle \phi }
– exists: there exists @ least 1 path starting current state
ϕ
{\displaystyle \phi }
holds.
path-specific quantifiers
x
ϕ
{\displaystyle \phi }
– next:
ϕ
{\displaystyle \phi }
has hold @ next state (this operator noted n instead of x).
g
ϕ
{\displaystyle \phi }
– globally:
ϕ
{\displaystyle \phi }
has hold on entire subsequent path.
f
ϕ
{\displaystyle \phi }
– finally:
ϕ
{\displaystyle \phi }
has hold (somewhere on subsequent path).
ϕ
{\displaystyle \phi }
u
ψ
{\displaystyle \psi }
– until:
ϕ
{\displaystyle \phi }
has hold @ least until @ position
ψ
{\displaystyle \psi }
holds. implies
ψ
{\displaystyle \psi }
verified in future.
ϕ
{\displaystyle \phi }
w
ψ
{\displaystyle \psi }
– weak until:
ϕ
{\displaystyle \phi }
has hold until
ψ
{\displaystyle \psi }
holds. difference u there no guarantee
ψ
{\displaystyle \psi }
ever verified. w operator called unless .
in ctl*, temporal operators can freely mixed. in ctl, operator must grouped in two: 1 path operator followed state operator. see examples below. ctl* strictly more expressive ctl.
minimal set of operators
in ctl there minimal set of operators. ctl formulas can transformed use operators. useful in model checking. 1 minimal set of operators is: {true,
∨
,
¬
{\displaystyle \lor ,\neg }
, eg, eu, ex}.
some of transformation used temporal operator are:
ef
ϕ
{\displaystyle \phi }
== e[trueu(
ϕ
{\displaystyle \phi }
)] ( because f
ϕ
{\displaystyle \phi }
== [trueu(
ϕ
{\displaystyle \phi }
)] )
ax
ϕ
{\displaystyle \phi }
==
¬
{\displaystyle \neg }
ex(
¬
{\displaystyle \neg }
ϕ
{\displaystyle \phi }
)
ag
ϕ
{\displaystyle \phi }
==
¬
{\displaystyle \neg }
ef(
¬
{\displaystyle \neg }
ϕ
{\displaystyle \phi }
) ==
¬
{\displaystyle \neg }
e[trueu(
¬
{\displaystyle \neg }
ϕ
{\displaystyle \phi }
)]
af
ϕ
{\displaystyle \phi }
== a[trueu
ϕ
{\displaystyle \phi }
] ==
¬
{\displaystyle \neg }
eg(
¬
{\displaystyle \neg }
ϕ
{\displaystyle \phi }
)
a[
ϕ
{\displaystyle \phi }
u
ψ
{\displaystyle \psi }
] ==
¬
{\displaystyle \neg }
( e[(
¬
{\displaystyle \neg }
ψ
{\displaystyle \psi }
)u
¬
{\displaystyle \neg }
(
ϕ
{\displaystyle \phi }
∨
{\displaystyle \lor }
ψ
{\displaystyle \psi }
)]
∨
{\displaystyle \lor }
eg(
¬
{\displaystyle \neg }
ψ
{\displaystyle \psi }
) )
Comments
Post a Comment