src/HOL/UNITY/Follows.thy
changeset 15102 04b0e943fcc9
parent 13812 91713a1915ee
child 16417 9bc16273c2d4
equal deleted inserted replaced
15101:d027515e2aa6 15102:04b0e943fcc9
    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)