doc-src/TutorialI/CTL/document/CTL.tex
changeset 10242 028f54cd2cc9
parent 10237 875bf54b5d74
child 10281 9554ce1c2e54
equal deleted inserted replaced
10241:e0428c2778f1 10242:028f54cd2cc9
    42 \end{isamarkuptext}%
    42 \end{isamarkuptext}%
    43 {\isachardoublequote}mc{\isacharparenleft}AF\ f{\isacharparenright}\ \ \ \ {\isacharequal}\ lfp{\isacharparenleft}af{\isacharparenleft}mc\ f{\isacharparenright}{\isacharparenright}{\isachardoublequote}%
    43 {\isachardoublequote}mc{\isacharparenleft}AF\ f{\isacharparenright}\ \ \ \ {\isacharequal}\ lfp{\isacharparenleft}af{\isacharparenleft}mc\ f{\isacharparenright}{\isacharparenright}{\isachardoublequote}%
    44 \begin{isamarkuptext}%
    44 \begin{isamarkuptext}%
    45 \noindent
    45 \noindent
    46 Because \isa{af} is monotone in its second argument (and also its first, but
    46 Because \isa{af} is monotone in its second argument (and also its first, but
    47 that is irrelevant) \isa{af\ A} has a least fixpoint:%
    47 that is irrelevant) \isa{af\ A} has a least fixed point:%
    48 \end{isamarkuptext}%
    48 \end{isamarkuptext}%
    49 \isacommand{lemma}\ mono{\isacharunderscore}af{\isacharcolon}\ {\isachardoublequote}mono{\isacharparenleft}af\ A{\isacharparenright}{\isachardoublequote}\isanewline
    49 \isacommand{lemma}\ mono{\isacharunderscore}af{\isacharcolon}\ {\isachardoublequote}mono{\isacharparenleft}af\ A{\isacharparenright}{\isachardoublequote}\isanewline
    50 \isacommand{apply}{\isacharparenleft}simp\ add{\isacharcolon}\ mono{\isacharunderscore}def\ af{\isacharunderscore}def{\isacharparenright}\isanewline
    50 \isacommand{apply}{\isacharparenleft}simp\ add{\isacharcolon}\ mono{\isacharunderscore}def\ af{\isacharunderscore}def{\isacharparenright}\isanewline
    51 \isacommand{apply}\ blast\isanewline
    51 \isacommand{apply}\ blast\isanewline
    52 \isacommand{done}%
    52 \isacommand{done}%
    58 \isacommand{theorem}\ AF{\isacharunderscore}lemma{\isadigit{1}}{\isacharcolon}\isanewline
    58 \isacommand{theorem}\ AF{\isacharunderscore}lemma{\isadigit{1}}{\isacharcolon}\isanewline
    59 \ \ {\isachardoublequote}lfp{\isacharparenleft}af\ A{\isacharparenright}\ {\isasymsubseteq}\ {\isacharbraceleft}s{\isachardot}\ {\isasymforall}\ p\ {\isasymin}\ Paths\ s{\isachardot}\ {\isasymexists}\ i{\isachardot}\ p\ i\ {\isasymin}\ A{\isacharbraceright}{\isachardoublequote}%
    59 \ \ {\isachardoublequote}lfp{\isacharparenleft}af\ A{\isacharparenright}\ {\isasymsubseteq}\ {\isacharbraceleft}s{\isachardot}\ {\isasymforall}\ p\ {\isasymin}\ Paths\ s{\isachardot}\ {\isasymexists}\ i{\isachardot}\ p\ i\ {\isasymin}\ A{\isacharbraceright}{\isachardoublequote}%
    60 \begin{isamarkuptxt}%
    60 \begin{isamarkuptxt}%
    61 \noindent
    61 \noindent
    62 In contrast to the analogous property for \isa{EF}, and just
    62 In contrast to the analogous property for \isa{EF}, and just
    63 for a change, we do not use fixpoint induction but a weaker theorem,
    63 for a change, we do not use fixed point induction but a weaker theorem,
    64 \isa{lfp{\isacharunderscore}lowerbound}:
    64 \isa{lfp{\isacharunderscore}lowerbound}:
    65 \begin{isabelle}%
    65 \begin{isabelle}%
    66 \ \ \ \ \ f\ S\ {\isasymsubseteq}\ S\ {\isasymLongrightarrow}\ lfp\ f\ {\isasymsubseteq}\ S%
    66 \ \ \ \ \ f\ S\ {\isasymsubseteq}\ S\ {\isasymLongrightarrow}\ lfp\ f\ {\isasymsubseteq}\ S%
    67 \end{isabelle}
    67 \end{isabelle}
    68 The instance of the premise \isa{f\ S\ {\isasymsubseteq}\ S} is proved pointwise,
    68 The instance of the premise \isa{f\ S\ {\isasymsubseteq}\ S} is proved pointwise,
   308 Let us close this section with a few words about the executability of our model checkers.
   308 Let us close this section with a few words about the executability of our model checkers.
   309 It is clear that if all sets are finite, they can be represented as lists and the usual
   309 It is clear that if all sets are finite, they can be represented as lists and the usual
   310 set operations are easily implemented. Only \isa{lfp} requires a little thought.
   310 set operations are easily implemented. Only \isa{lfp} requires a little thought.
   311 Fortunately the HOL library proves that in the case of finite sets and a monotone \isa{F},
   311 Fortunately the HOL library proves that in the case of finite sets and a monotone \isa{F},
   312 \isa{lfp\ F} can be computed by iterated application of \isa{F} to \isa{{\isacharbraceleft}{\isacharbraceright}} until
   312 \isa{lfp\ F} can be computed by iterated application of \isa{F} to \isa{{\isacharbraceleft}{\isacharbraceright}} until
   313 a fixpoint is reached. It is actually possible to generate executable functional programs
   313 a fixed point is reached. It is actually possible to generate executable functional programs
   314 from HOL definitions, but that is beyond the scope of the tutorial.%
   314 from HOL definitions, but that is beyond the scope of the tutorial.%
   315 \end{isamarkuptext}%
   315 \end{isamarkuptext}%
   316 \end{isabellebody}%
   316 \end{isabellebody}%
   317 %%% Local Variables:
   317 %%% Local Variables:
   318 %%% mode: latex
   318 %%% mode: latex