doc-src/TutorialI/CTL/PDL.thy
changeset 10159 a72ddfdbfca0
parent 10149 7cfdf6a330a0
child 10171 59d6633835fa
equal deleted inserted replaced
10158:00fdd5c330ea 10159:a72ddfdbfca0
    75 First we prove monotonicity of the function inside @{term lfp}
    75 First we prove monotonicity of the function inside @{term lfp}
    76 *}
    76 *}
    77 
    77 
    78 lemma mono_ef: "mono(\<lambda>T. A \<union> M^-1 ^^ T)"
    78 lemma mono_ef: "mono(\<lambda>T. A \<union> M^-1 ^^ T)"
    79 apply(rule monoI)
    79 apply(rule monoI)
    80 by(blast)
    80 apply blast
       
    81 done
    81 
    82 
    82 text{*\noindent
    83 text{*\noindent
    83 in order to make sure it really has a least fixpoint.
    84 in order to make sure it really has a least fixpoint.
    84 
    85 
    85 Now we can relate model checking and semantics. For the @{text EF} case we need
    86 Now we can relate model checking and semantics. For the @{text EF} case we need
   172 txt{*\noindent
   173 txt{*\noindent
   173 The proof of the induction step is identical to the one for the base case:
   174 The proof of the induction step is identical to the one for the base case:
   174 *}
   175 *}
   175 
   176 
   176 apply(rule ssubst[OF lfp_Tarski[OF mono_ef]])
   177 apply(rule ssubst[OF lfp_Tarski[OF mono_ef]])
   177 by(blast)
   178 apply(blast)
       
   179 done
   178 
   180 
   179 text{*
   181 text{*
   180 The main theorem is proved in the familiar manner: induction followed by
   182 The main theorem is proved in the familiar manner: induction followed by
   181 @{text auto} augmented with the lemma as a simplification rule.
   183 @{text auto} augmented with the lemma as a simplification rule.
   182 *}
   184 *}
   183 
   185 
   184 theorem "mc f = {s. s \<Turnstile> f}";
   186 theorem "mc f = {s. s \<Turnstile> f}";
   185 apply(induct_tac f);
   187 apply(induct_tac f);
   186 by(auto simp add:EF_lemma);
   188 apply(auto simp add:EF_lemma);
       
   189 done;
   187 (*<*)end(*>*)
   190 (*<*)end(*>*)