equal
deleted
inserted
replaced
24 (*Resembles the previous definition of LeadsTo*) |
24 (*Resembles the previous definition of LeadsTo*) |
25 |
25 |
26 (* Equivalence with the HOL-like definition *) |
26 (* Equivalence with the HOL-like definition *) |
27 lemma LeadsTo_eq: |
27 lemma LeadsTo_eq: |
28 "st_set(B)\<Longrightarrow> A \<longmapsto>w B = {F \<in> program. F:(reachable(F) \<inter> A) \<longmapsto> B}" |
28 "st_set(B)\<Longrightarrow> A \<longmapsto>w B = {F \<in> program. F:(reachable(F) \<inter> A) \<longmapsto> B}" |
29 apply (unfold LeadsTo_def) |
29 unfolding LeadsTo_def |
30 apply (blast dest: psp_stable2 leadsToD2 constrainsD2 intro: leadsTo_weaken) |
30 apply (blast dest: psp_stable2 leadsToD2 constrainsD2 intro: leadsTo_weaken) |
31 done |
31 done |
32 |
32 |
33 lemma LeadsTo_type: "A \<longmapsto>w B <=program" |
33 lemma LeadsTo_type: "A \<longmapsto>w B <=program" |
34 by (unfold LeadsTo_def, auto) |
34 by (unfold LeadsTo_def, auto) |
38 (** Conjoining an Always property **) |
38 (** Conjoining an Always property **) |
39 lemma Always_LeadsTo_pre: "F \<in> Always(I) \<Longrightarrow> (F:(I \<inter> A) \<longmapsto>w A') \<longleftrightarrow> (F \<in> A \<longmapsto>w A')" |
39 lemma Always_LeadsTo_pre: "F \<in> Always(I) \<Longrightarrow> (F:(I \<inter> A) \<longmapsto>w A') \<longleftrightarrow> (F \<in> A \<longmapsto>w A')" |
40 by (simp add: LeadsTo_def Always_eq_includes_reachable Int_absorb2 Int_assoc [symmetric] leadsToD2) |
40 by (simp add: LeadsTo_def Always_eq_includes_reachable Int_absorb2 Int_assoc [symmetric] leadsToD2) |
41 |
41 |
42 lemma Always_LeadsTo_post: "F \<in> Always(I) \<Longrightarrow> (F \<in> A \<longmapsto>w (I \<inter> A')) \<longleftrightarrow> (F \<in> A \<longmapsto>w A')" |
42 lemma Always_LeadsTo_post: "F \<in> Always(I) \<Longrightarrow> (F \<in> A \<longmapsto>w (I \<inter> A')) \<longleftrightarrow> (F \<in> A \<longmapsto>w A')" |
43 apply (unfold LeadsTo_def) |
43 unfolding LeadsTo_def |
44 apply (simp add: Always_eq_includes_reachable Int_absorb2 Int_assoc [symmetric] leadsToD2) |
44 apply (simp add: Always_eq_includes_reachable Int_absorb2 Int_assoc [symmetric] leadsToD2) |
45 done |
45 done |
46 |
46 |
47 (* Like 'Always_LeadsTo_pre RS iffD1', but with premises in the good order *) |
47 (* Like 'Always_LeadsTo_pre RS iffD1', but with premises in the good order *) |
48 lemma Always_LeadsToI: "\<lbrakk>F \<in> Always(C); F \<in> (C \<inter> A) \<longmapsto>w A'\<rbrakk> \<Longrightarrow> F \<in> A \<longmapsto>w A'" |
48 lemma Always_LeadsToI: "\<lbrakk>F \<in> Always(C); F \<in> (C \<inter> A) \<longmapsto>w A'\<rbrakk> \<Longrightarrow> F \<in> A \<longmapsto>w A'" |
121 lemma LeadsTo_state: "F \<in> A \<longmapsto>w state \<longleftrightarrow> F \<in> program" |
121 lemma LeadsTo_state: "F \<in> A \<longmapsto>w state \<longleftrightarrow> F \<in> program" |
122 by (auto dest: LeadsTo_type [THEN subsetD] simp add: LeadsTo_eq) |
122 by (auto dest: LeadsTo_type [THEN subsetD] simp add: LeadsTo_eq) |
123 declare LeadsTo_state [iff] |
123 declare LeadsTo_state [iff] |
124 |
124 |
125 lemma LeadsTo_weaken_R: "\<lbrakk>F \<in> A \<longmapsto>w A'; A'<=B'\<rbrakk> \<Longrightarrow> F \<in> A \<longmapsto>w B'" |
125 lemma LeadsTo_weaken_R: "\<lbrakk>F \<in> A \<longmapsto>w A'; A'<=B'\<rbrakk> \<Longrightarrow> F \<in> A \<longmapsto>w B'" |
126 apply (unfold LeadsTo_def) |
126 unfolding LeadsTo_def |
127 apply (auto intro: leadsTo_weaken_R) |
127 apply (auto intro: leadsTo_weaken_R) |
128 done |
128 done |
129 |
129 |
130 lemma LeadsTo_weaken_L: "\<lbrakk>F \<in> A \<longmapsto>w A'; B \<subseteq> A\<rbrakk> \<Longrightarrow> F \<in> B \<longmapsto>w A'" |
130 lemma LeadsTo_weaken_L: "\<lbrakk>F \<in> A \<longmapsto>w A'; B \<subseteq> A\<rbrakk> \<Longrightarrow> F \<in> B \<longmapsto>w A'" |
131 apply (unfold LeadsTo_def) |
131 unfolding LeadsTo_def |
132 apply (auto intro: leadsTo_weaken_L) |
132 apply (auto intro: leadsTo_weaken_L) |
133 done |
133 done |
134 |
134 |
135 lemma LeadsTo_weaken: "\<lbrakk>F \<in> A \<longmapsto>w A'; B<=A; A'<=B'\<rbrakk> \<Longrightarrow> F \<in> B \<longmapsto>w B'" |
135 lemma LeadsTo_weaken: "\<lbrakk>F \<in> A \<longmapsto>w A'; B<=A; A'<=B'\<rbrakk> \<Longrightarrow> F \<in> B \<longmapsto>w B'" |
136 by (blast intro: LeadsTo_weaken_R LeadsTo_weaken_L LeadsTo_Trans) |
136 by (blast intro: LeadsTo_weaken_R LeadsTo_weaken_L LeadsTo_Trans) |
254 lemma PSP2: "\<lbrakk>F \<in> A \<longmapsto>w A'; F \<in> B Co B'\<rbrakk>\<Longrightarrow> F:(B' \<inter> A) \<longmapsto>w ((B \<inter> A') \<union> (B' - B))" |
254 lemma PSP2: "\<lbrakk>F \<in> A \<longmapsto>w A'; F \<in> B Co B'\<rbrakk>\<Longrightarrow> F:(B' \<inter> A) \<longmapsto>w ((B \<inter> A') \<union> (B' - B))" |
255 by (simp (no_asm_simp) add: PSP Int_ac) |
255 by (simp (no_asm_simp) add: PSP Int_ac) |
256 |
256 |
257 lemma PSP_Unless: |
257 lemma PSP_Unless: |
258 "\<lbrakk>F \<in> A \<longmapsto>w A'; F \<in> B Unless B'\<rbrakk>\<Longrightarrow> F:(A \<inter> B) \<longmapsto>w ((A' \<inter> B) \<union> B')" |
258 "\<lbrakk>F \<in> A \<longmapsto>w A'; F \<in> B Unless B'\<rbrakk>\<Longrightarrow> F:(A \<inter> B) \<longmapsto>w ((A' \<inter> B) \<union> B')" |
259 apply (unfold op_Unless_def) |
259 unfolding op_Unless_def |
260 apply (drule PSP, assumption) |
260 apply (drule PSP, assumption) |
261 apply (blast intro: LeadsTo_Diff LeadsTo_weaken subset_imp_LeadsTo) |
261 apply (blast intro: LeadsTo_Diff LeadsTo_weaken subset_imp_LeadsTo) |
262 done |
262 done |
263 |
263 |
264 (*** Induction rules ***) |
264 (*** Induction rules ***) |
325 |
325 |
326 lemma Stable_completion: |
326 lemma Stable_completion: |
327 "\<lbrakk>F \<in> A \<longmapsto>w A'; F \<in> Stable(A'); |
327 "\<lbrakk>F \<in> A \<longmapsto>w A'; F \<in> Stable(A'); |
328 F \<in> B \<longmapsto>w B'; F \<in> Stable(B')\<rbrakk> |
328 F \<in> B \<longmapsto>w B'; F \<in> Stable(B')\<rbrakk> |
329 \<Longrightarrow> F \<in> (A \<inter> B) \<longmapsto>w (A' \<inter> B')" |
329 \<Longrightarrow> F \<in> (A \<inter> B) \<longmapsto>w (A' \<inter> B')" |
330 apply (unfold Stable_def) |
330 unfolding Stable_def |
331 apply (rule_tac C1 = 0 in Completion [THEN LeadsTo_weaken_R]) |
331 apply (rule_tac C1 = 0 in Completion [THEN LeadsTo_weaken_R]) |
332 prefer 5 |
332 prefer 5 |
333 apply blast |
333 apply blast |
334 apply auto |
334 apply auto |
335 done |
335 done |
337 lemma Finite_stable_completion: |
337 lemma Finite_stable_completion: |
338 "\<lbrakk>I \<in> Fin(X); |
338 "\<lbrakk>I \<in> Fin(X); |
339 (\<And>i. i \<in> I \<Longrightarrow> F \<in> A(i) \<longmapsto>w A'(i)); |
339 (\<And>i. i \<in> I \<Longrightarrow> F \<in> A(i) \<longmapsto>w A'(i)); |
340 (\<And>i. i \<in> I \<Longrightarrow>F \<in> Stable(A'(i))); F \<in> program\<rbrakk> |
340 (\<And>i. i \<in> I \<Longrightarrow>F \<in> Stable(A'(i))); F \<in> program\<rbrakk> |
341 \<Longrightarrow> F \<in> (\<Inter>i \<in> I. A(i)) \<longmapsto>w (\<Inter>i \<in> I. A'(i))" |
341 \<Longrightarrow> F \<in> (\<Inter>i \<in> I. A(i)) \<longmapsto>w (\<Inter>i \<in> I. A'(i))" |
342 apply (unfold Stable_def) |
342 unfolding Stable_def |
343 apply (rule_tac C1 = 0 in Finite_completion [THEN LeadsTo_weaken_R], simp_all) |
343 apply (rule_tac C1 = 0 in Finite_completion [THEN LeadsTo_weaken_R], simp_all) |
344 apply (rule_tac [3] subset_refl, auto) |
344 apply (rule_tac [3] subset_refl, auto) |
345 done |
345 done |
346 |
346 |
347 ML \<open> |
347 ML \<open> |