34 apply (erule LeadsTo_weaken) |
34 apply (erule LeadsTo_weaken) |
35 apply (blast intro: monoD order_trans)+ |
35 apply (blast intro: monoD order_trans)+ |
36 done |
36 done |
37 |
37 |
38 lemma Follows_constant [iff]: "F \<in> (%s. c) Fols (%s. c)" |
38 lemma Follows_constant [iff]: "F \<in> (%s. c) Fols (%s. c)" |
39 by (unfold Follows_def, auto) |
39 by (simp add: Follows_def) |
40 |
40 |
41 lemma mono_Follows_o: "mono h ==> f Fols g \<subseteq> (h o f) Fols (h o g)" |
41 lemma mono_Follows_o: "mono h ==> f Fols g \<subseteq> (h o f) Fols (h o g)" |
42 apply (unfold Follows_def, clarify) |
42 by (auto simp add: Follows_def mono_Increasing_o [THEN [2] rev_subsetD] |
43 apply (simp add: mono_Increasing_o [THEN [2] rev_subsetD] |
43 mono_Always_o [THEN [2] rev_subsetD] |
44 mono_Always_o [THEN [2] rev_subsetD] |
44 mono_LeadsTo_o [THEN [2] rev_subsetD, THEN INT_D]) |
45 mono_LeadsTo_o [THEN [2] rev_subsetD, THEN INT_D]) |
|
46 done |
|
47 |
45 |
48 lemma mono_Follows_apply: |
46 lemma mono_Follows_apply: |
49 "mono h ==> f Fols g \<subseteq> (%x. h (f x)) Fols (%x. h (g x))" |
47 "mono h ==> f Fols g \<subseteq> (%x. h (f x)) Fols (%x. h (g x))" |
50 apply (drule mono_Follows_o) |
48 apply (drule mono_Follows_o) |
51 apply (force simp add: o_def) |
49 apply (force simp add: o_def) |
52 done |
50 done |
53 |
51 |
54 lemma Follows_trans: |
52 lemma Follows_trans: |
55 "[| F \<in> f Fols g; F \<in> g Fols h |] ==> F \<in> f Fols h" |
53 "[| F \<in> f Fols g; F \<in> g Fols h |] ==> F \<in> f Fols h" |
56 apply (unfold Follows_def) |
54 apply (simp add: Follows_def) |
57 apply (simp add: Always_eq_includes_reachable) |
55 apply (simp add: Always_eq_includes_reachable) |
58 apply (blast intro: order_trans LeadsTo_Trans) |
56 apply (blast intro: order_trans LeadsTo_Trans) |
59 done |
57 done |
60 |
58 |
61 |
59 |
62 subsection{*Destruction rules*} |
60 subsection{*Destruction rules*} |
63 |
61 |
64 lemma Follows_Increasing1: "F \<in> f Fols g ==> F \<in> Increasing f" |
62 lemma Follows_Increasing1: "F \<in> f Fols g ==> F \<in> Increasing f" |
65 by (unfold Follows_def, blast) |
63 by (simp add: Follows_def) |
66 |
64 |
67 lemma Follows_Increasing2: "F \<in> f Fols g ==> F \<in> Increasing g" |
65 lemma Follows_Increasing2: "F \<in> f Fols g ==> F \<in> Increasing g" |
68 by (unfold Follows_def, blast) |
66 by (simp add: Follows_def) |
69 |
67 |
70 lemma Follows_Bounded: "F \<in> f Fols g ==> F \<in> Always {s. f s \<subseteq> g s}" |
68 lemma Follows_Bounded: "F \<in> f Fols g ==> F \<in> Always {s. f s \<subseteq> g s}" |
71 by (unfold Follows_def, blast) |
69 by (simp add: Follows_def) |
72 |
70 |
73 lemma Follows_LeadsTo: |
71 lemma Follows_LeadsTo: |
74 "F \<in> f Fols g ==> F \<in> {s. k \<le> g s} LeadsTo {s. k \<le> f s}" |
72 "F \<in> f Fols g ==> F \<in> {s. k \<le> g s} LeadsTo {s. k \<le> f s}" |
75 by (unfold Follows_def, blast) |
73 by (simp add: Follows_def) |
76 |
74 |
77 lemma Follows_LeadsTo_pfixLe: |
75 lemma Follows_LeadsTo_pfixLe: |
78 "F \<in> f Fols g ==> F \<in> {s. k pfixLe g s} LeadsTo {s. k pfixLe f s}" |
76 "F \<in> f Fols g ==> F \<in> {s. k pfixLe g s} LeadsTo {s. k pfixLe f s}" |
79 apply (rule single_LeadsTo_I, clarify) |
77 apply (rule single_LeadsTo_I, clarify) |
80 apply (drule_tac k="g s" in Follows_LeadsTo) |
78 apply (drule_tac k="g s" in Follows_LeadsTo) |
94 |
92 |
95 |
93 |
96 lemma Always_Follows1: |
94 lemma Always_Follows1: |
97 "[| F \<in> Always {s. f s = f' s}; F \<in> f Fols g |] ==> F \<in> f' Fols g" |
95 "[| F \<in> Always {s. f s = f' s}; F \<in> f Fols g |] ==> F \<in> f' Fols g" |
98 |
96 |
99 apply (unfold Follows_def Increasing_def Stable_def, auto) |
97 apply (simp add: Follows_def Increasing_def Stable_def, auto) |
100 apply (erule_tac [3] Always_LeadsTo_weaken) |
98 apply (erule_tac [3] Always_LeadsTo_weaken) |
101 apply (erule_tac A = "{s. z \<le> f s}" and A' = "{s. z \<le> f s}" |
99 apply (erule_tac A = "{s. z \<le> f s}" and A' = "{s. z \<le> f s}" |
102 in Always_Constrains_weaken, auto) |
100 in Always_Constrains_weaken, auto) |
103 apply (drule Always_Int_I, assumption) |
101 apply (drule Always_Int_I, assumption) |
104 apply (force intro: Always_weaken) |
102 apply (force intro: Always_weaken) |
105 done |
103 done |
106 |
104 |
107 lemma Always_Follows2: |
105 lemma Always_Follows2: |
108 "[| F \<in> Always {s. g s = g' s}; F \<in> f Fols g |] ==> F \<in> f Fols g'" |
106 "[| F \<in> Always {s. g s = g' s}; F \<in> f Fols g |] ==> F \<in> f Fols g'" |
109 apply (unfold Follows_def Increasing_def Stable_def, auto) |
107 apply (simp add: Follows_def Increasing_def Stable_def, auto) |
110 apply (erule_tac [3] Always_LeadsTo_weaken) |
108 apply (erule_tac [3] Always_LeadsTo_weaken) |
111 apply (erule_tac A = "{s. z \<le> g s}" and A' = "{s. z \<le> g s}" |
109 apply (erule_tac A = "{s. z \<le> g s}" and A' = "{s. z \<le> g s}" |
112 in Always_Constrains_weaken, auto) |
110 in Always_Constrains_weaken, auto) |
113 apply (drule Always_Int_I, assumption) |
111 apply (drule Always_Int_I, assumption) |
114 apply (force intro: Always_weaken) |
112 apply (force intro: Always_weaken) |
119 |
117 |
120 (*Can replace "Un" by any sup. But existing max only works for linorders.*) |
118 (*Can replace "Un" by any sup. But existing max only works for linorders.*) |
121 lemma increasing_Un: |
119 lemma increasing_Un: |
122 "[| F \<in> increasing f; F \<in> increasing g |] |
120 "[| F \<in> increasing f; F \<in> increasing g |] |
123 ==> F \<in> increasing (%s. (f s) \<union> (g s))" |
121 ==> F \<in> increasing (%s. (f s) \<union> (g s))" |
124 apply (unfold increasing_def stable_def constrains_def, auto) |
122 apply (simp add: increasing_def stable_def constrains_def, auto) |
125 apply (drule_tac x = "f xa" in spec) |
123 apply (drule_tac x = "f xa" in spec) |
126 apply (drule_tac x = "g xa" in spec) |
124 apply (drule_tac x = "g xa" in spec) |
127 apply (blast dest!: bspec) |
125 apply (blast dest!: bspec) |
128 done |
126 done |
129 |
127 |
160 done |
158 done |
161 |
159 |
162 lemma Follows_Un: |
160 lemma Follows_Un: |
163 "[| F \<in> f' Fols f; F \<in> g' Fols g |] |
161 "[| F \<in> f' Fols f; F \<in> g' Fols g |] |
164 ==> F \<in> (%s. (f' s) \<union> (g' s)) Fols (%s. (f s) \<union> (g s))" |
162 ==> F \<in> (%s. (f' s) \<union> (g' s)) Fols (%s. (f s) \<union> (g s))" |
165 apply (unfold Follows_def) |
163 apply (simp add: Follows_def Increasing_Un Always_Un del: Un_subset_iff, auto) |
166 apply (simp add: Increasing_Un Always_Un, auto) |
|
167 apply (rule LeadsTo_Trans) |
164 apply (rule LeadsTo_Trans) |
168 apply (blast intro: Follows_Un_lemma) |
165 apply (blast intro: Follows_Un_lemma) |
169 (*Weakening is used to exchange Un's arguments*) |
166 (*Weakening is used to exchange Un's arguments*) |
170 apply (blast intro: Follows_Un_lemma [THEN LeadsTo_weaken]) |
167 apply (blast intro: Follows_Un_lemma [THEN LeadsTo_weaken]) |
171 done |
168 done |
174 subsection{*Multiset union properties (with the multiset ordering)*} |
171 subsection{*Multiset union properties (with the multiset ordering)*} |
175 |
172 |
176 lemma increasing_union: |
173 lemma increasing_union: |
177 "[| F \<in> increasing f; F \<in> increasing g |] |
174 "[| F \<in> increasing f; F \<in> increasing g |] |
178 ==> F \<in> increasing (%s. (f s) + (g s :: ('a::order) multiset))" |
175 ==> F \<in> increasing (%s. (f s) + (g s :: ('a::order) multiset))" |
179 apply (unfold increasing_def stable_def constrains_def, auto) |
176 apply (simp add: increasing_def stable_def constrains_def, auto) |
180 apply (drule_tac x = "f xa" in spec) |
177 apply (drule_tac x = "f xa" in spec) |
181 apply (drule_tac x = "g xa" in spec) |
178 apply (drule_tac x = "g xa" in spec) |
182 apply (drule bspec, assumption) |
179 apply (drule bspec, assumption) |
183 apply (blast intro: union_le_mono order_trans) |
180 apply (blast intro: union_le_mono order_trans) |
184 done |
181 done |
221 (*The !! is there to influence to effect of permutative rewriting at the end*) |
218 (*The !! is there to influence to effect of permutative rewriting at the end*) |
222 lemma Follows_union: |
219 lemma Follows_union: |
223 "!!g g' ::'b => ('a::order) multiset. |
220 "!!g g' ::'b => ('a::order) multiset. |
224 [| F \<in> f' Fols f; F \<in> g' Fols g |] |
221 [| F \<in> f' Fols f; F \<in> g' Fols g |] |
225 ==> F \<in> (%s. (f' s) + (g' s)) Fols (%s. (f s) + (g s))" |
222 ==> F \<in> (%s. (f' s) + (g' s)) Fols (%s. (f s) + (g s))" |
226 apply (unfold Follows_def) |
223 apply (simp add: Follows_def) |
227 apply (simp add: Increasing_union Always_union, auto) |
224 apply (simp add: Increasing_union Always_union, auto) |
228 apply (rule LeadsTo_Trans) |
225 apply (rule LeadsTo_Trans) |
229 apply (blast intro: Follows_union_lemma) |
226 apply (blast intro: Follows_union_lemma) |
230 (*now exchange union's arguments*) |
227 (*now exchange union's arguments*) |
231 apply (simp add: union_commute) |
228 apply (simp add: union_commute) |