equal
deleted
inserted
replaced
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(*>*) |