Editing Computation tree logic (section)

===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>