160 by (Blast_tac 1); |
160 by (Blast_tac 1); |
161 qed "subset_imp_ensures"; |
161 qed "subset_imp_ensures"; |
162 |
162 |
163 bind_thm ("subset_imp_leadsTo", subset_imp_ensures RS leadsTo_Basis); |
163 bind_thm ("subset_imp_leadsTo", subset_imp_ensures RS leadsTo_Basis); |
164 |
164 |
|
165 bind_thm ("leadsTo_refl", subset_refl RS subset_imp_leadsTo); |
|
166 |
165 bind_thm ("empty_leadsTo", empty_subsetI RS subset_imp_leadsTo); |
167 bind_thm ("empty_leadsTo", empty_subsetI RS subset_imp_leadsTo); |
166 Addsimps [empty_leadsTo]; |
168 Addsimps [empty_leadsTo]; |
167 |
169 |
168 bind_thm ("leadsTo_UNIV", subset_UNIV RS subset_imp_leadsTo); |
170 bind_thm ("leadsTo_UNIV", subset_UNIV RS subset_imp_leadsTo); |
169 Addsimps [leadsTo_UNIV]; |
171 Addsimps [leadsTo_UNIV]; |
|
172 |
|
173 |
|
174 |
|
175 (** Variant induction rule: on the preconditions for B **) |
|
176 |
|
177 (*Lemma is the weak version: can't see how to do it in one step*) |
|
178 val major::prems = Goal |
|
179 "[| F : za leadsTo zb; \ |
|
180 \ P zb; \ |
|
181 \ !!A B. [| F : A ensures B; P B |] ==> P A; \ |
|
182 \ !!S. ALL A:S. P A ==> P (Union S) \ |
|
183 \ |] ==> P za"; |
|
184 (*by induction on this formula*) |
|
185 by (subgoal_tac "P zb --> P za" 1); |
|
186 (*now solve first subgoal: this formula is sufficient*) |
|
187 by (blast_tac (claset() addIs leadsTo_refl::prems) 1); |
|
188 by (rtac (major RS leadsTo_induct) 1); |
|
189 by (REPEAT (blast_tac (claset() addIs prems) 1)); |
|
190 val lemma = result(); |
|
191 |
|
192 val major::prems = Goal |
|
193 "[| F : za leadsTo zb; \ |
|
194 \ P zb; \ |
|
195 \ !!A B. [| F : A ensures B; F : B leadsTo zb; P B |] ==> P A; \ |
|
196 \ !!S. ALL A:S. F : A leadsTo zb & P A ==> P (Union S) \ |
|
197 \ |] ==> P za"; |
|
198 by (subgoal_tac "F : za leadsTo zb & P za" 1); |
|
199 by (etac conjunct2 1); |
|
200 by (rtac (major RS lemma) 1); |
|
201 by (blast_tac (claset() addIs [leadsTo_Union]@prems) 3); |
|
202 by (blast_tac (claset() addIs [leadsTo_Basis,leadsTo_Trans]@prems) 2); |
|
203 by (blast_tac (claset() addIs [leadsTo_refl]@prems) 1); |
|
204 qed "leadsTo_induct_pre"; |
170 |
205 |
171 |
206 |
172 Goal "[| F : A leadsTo A'; A'<=B' |] ==> F : A leadsTo B'"; |
207 Goal "[| F : A leadsTo A'; A'<=B' |] ==> F : A leadsTo B'"; |
173 by (blast_tac (claset() addIs [subset_imp_leadsTo, leadsTo_Trans]) 1); |
208 by (blast_tac (claset() addIs [subset_imp_leadsTo, leadsTo_Trans]) 1); |
174 qed "leadsTo_weaken_R"; |
209 qed "leadsTo_weaken_R"; |
252 |
287 |
253 |
288 |
254 |
289 |
255 (** The impossibility law **) |
290 (** The impossibility law **) |
256 |
291 |
257 Goal "F : A leadsTo B ==> B={} --> A={}"; |
|
258 by (etac leadsTo_induct 1); |
|
259 by (ALLGOALS Asm_simp_tac); |
|
260 by (rewrite_goals_tac [ensures_def, constrains_def, transient_def]); |
|
261 by (Blast_tac 1); |
|
262 val lemma = result() RS mp; |
|
263 |
|
264 Goal "F : A leadsTo {} ==> A={}"; |
292 Goal "F : A leadsTo {} ==> A={}"; |
265 by (blast_tac (claset() addSIs [lemma]) 1); |
293 by (etac leadsTo_induct_pre 1); |
|
294 by (ALLGOALS |
|
295 (asm_full_simp_tac |
|
296 (simpset() addsimps [ensures_def, constrains_def, transient_def]))); |
|
297 by (Blast_tac 1); |
266 qed "leadsTo_empty"; |
298 qed "leadsTo_empty"; |
267 |
299 |
268 |
300 |
269 (** PSP: Progress-Safety-Progress **) |
301 (** PSP: Progress-Safety-Progress **) |
270 |
302 |
478 (** LEVEL 6 **) |
510 (** LEVEL 6 **) |
479 by (subgoal_tac "F : (A' Int W Un C) leadsTo (A' Int B' Un C)" 1); |
511 by (subgoal_tac "F : (A' Int W Un C) leadsTo (A' Int B' Un C)" 1); |
480 by (rtac leadsTo_Un_duplicate2 2); |
512 by (rtac leadsTo_Un_duplicate2 2); |
481 by (blast_tac (claset() addIs [leadsTo_Un_Un, |
513 by (blast_tac (claset() addIs [leadsTo_Un_Un, |
482 wlt_leadsTo RS psp2 RS leadsTo_weaken, |
514 wlt_leadsTo RS psp2 RS leadsTo_weaken, |
483 subset_refl RS subset_imp_leadsTo]) 2); |
515 leadsTo_refl]) 2); |
484 by (dtac leadsTo_Diff 1); |
516 by (dtac leadsTo_Diff 1); |
485 by (blast_tac (claset() addIs [subset_imp_leadsTo]) 1); |
517 by (blast_tac (claset() addIs [subset_imp_leadsTo]) 1); |
486 by (subgoal_tac "A Int B <= A Int W" 1); |
518 by (subgoal_tac "A Int B <= A Int W" 1); |
487 by (blast_tac (claset() addSDs [leadsTo_subset] |
519 by (blast_tac (claset() addSDs [leadsTo_subset] |
488 addSIs [subset_refl RS Int_mono]) 2); |
520 addSIs [subset_refl RS Int_mono]) 2); |