src/HOL/Subst/Subst.ML
changeset 4089 96fba19bcbe2
parent 4060 600f266eac45
child 4477 b3e5857d8d99
equal deleted inserted replaced
4088:9be9e39fd862 4089:96fba19bcbe2
    39 by (ALLGOALS Asm_full_simp_tac);
    39 by (ALLGOALS Asm_full_simp_tac);
    40 by (ALLGOALS Blast_tac);
    40 by (ALLGOALS Blast_tac);
    41 qed "agreement";
    41 qed "agreement";
    42 
    42 
    43 goal Subst.thy   "~ v: vars_of(t) --> t <| (v,u)#s = t <| s";
    43 goal Subst.thy   "~ v: vars_of(t) --> t <| (v,u)#s = t <| s";
    44 by (simp_tac (!simpset addsimps [agreement] addsplits [expand_if]) 1);
    44 by (simp_tac (simpset() addsimps [agreement] addsplits [expand_if]) 1);
    45 qed_spec_mp"repl_invariance";
    45 qed_spec_mp"repl_invariance";
    46 
    46 
    47 val asms = goal Subst.thy 
    47 val asms = goal Subst.thy 
    48      "v : vars_of(t) --> w : vars_of(t <| (v,Var(w))#s)";
    48      "v : vars_of(t) --> w : vars_of(t <| (v,Var(w))#s)";
    49 by (induct_tac "t" 1);
    49 by (induct_tac "t" 1);
    59 
    59 
    60 
    60 
    61 local fun prove s = prove_goal Subst.thy s
    61 local fun prove s = prove_goal Subst.thy s
    62                   (fn prems => [cut_facts_tac prems 1,
    62                   (fn prems => [cut_facts_tac prems 1,
    63                                 REPEAT (etac rev_mp 1),
    63                                 REPEAT (etac rev_mp 1),
    64                                 simp_tac (!simpset addsimps [subst_eq_iff]) 1])
    64                                 simp_tac (simpset() addsimps [subst_eq_iff]) 1])
    65 in 
    65 in 
    66   val subst_refl      = prove "r =$= r";
    66   val subst_refl      = prove "r =$= r";
    67   val subst_sym       = prove "r =$= s ==> s =$= r";
    67   val subst_sym       = prove "r =$= s ==> s =$= r";
    68   val subst_trans     = prove "[| q =$= r; r =$= s |] ==> q =$= s";
    68   val subst_trans     = prove "[| q =$= r; r =$= s |] ==> q =$= s";
    69 end;
    69 end;
   109 
   109 
   110 goal Subst.thy "(t <| r <> s) = (t <| r <| s)";
   110 goal Subst.thy "(t <| r <> s) = (t <| r <| s)";
   111 by (induct_tac "t" 1);
   111 by (induct_tac "t" 1);
   112 by (ALLGOALS Asm_simp_tac);
   112 by (ALLGOALS Asm_simp_tac);
   113 by (alist_ind_tac "r" 1);
   113 by (alist_ind_tac "r" 1);
   114 by (ALLGOALS (asm_simp_tac (!simpset addsplits [expand_if])));
   114 by (ALLGOALS (asm_simp_tac (simpset() addsplits [expand_if])));
   115 qed "subst_comp";
   115 qed "subst_comp";
   116 
   116 
   117 Addsimps [subst_comp];
   117 Addsimps [subst_comp];
   118 
   118 
   119 goal Subst.thy "(q <> r) <> s =$= q <> (r <> s)";
   119 goal Subst.thy "(q <> r) <> s =$= q <> (r <> s)";
   120 by (simp_tac (!simpset addsimps [subst_eq_iff]) 1);
   120 by (simp_tac (simpset() addsimps [subst_eq_iff]) 1);
   121 qed "comp_assoc";
   121 qed "comp_assoc";
   122 
   122 
   123 goal Subst.thy "!!s. [| theta =$= theta1; sigma =$= sigma1|] ==> \
   123 goal Subst.thy "!!s. [| theta =$= theta1; sigma =$= sigma1|] ==> \
   124              \       (theta <> sigma) =$= (theta1 <> sigma1)";
   124              \       (theta <> sigma) =$= (theta1 <> sigma1)";
   125 by (asm_full_simp_tac (!simpset addsimps [subst_eq_def]) 1);
   125 by (asm_full_simp_tac (simpset() addsimps [subst_eq_def]) 1);
   126 qed "subst_cong";
   126 qed "subst_cong";
   127 
   127 
   128 
   128 
   129 goal Subst.thy "(w, Var(w) <| s) # s =$= s"; 
   129 goal Subst.thy "(w, Var(w) <| s) # s =$= s"; 
   130 by (simp_tac (!simpset addsimps [subst_eq_iff]) 1);
   130 by (simp_tac (simpset() addsimps [subst_eq_iff]) 1);
   131 by (rtac allI 1);
   131 by (rtac allI 1);
   132 by (induct_tac "t" 1);
   132 by (induct_tac "t" 1);
   133 by (ALLGOALS (asm_full_simp_tac (!simpset addsplits [expand_if])));
   133 by (ALLGOALS (asm_full_simp_tac (simpset() addsplits [expand_if])));
   134 qed "Cons_trivial";
   134 qed "Cons_trivial";
   135 
   135 
   136 
   136 
   137 goal Subst.thy "!!s. q <> r =$= s ==>  t <| q <| r = t <| s";
   137 goal Subst.thy "!!s. q <> r =$= s ==>  t <| q <| r = t <| s";
   138 by (asm_full_simp_tac (!simpset addsimps [subst_eq_iff]) 1);
   138 by (asm_full_simp_tac (simpset() addsimps [subst_eq_iff]) 1);
   139 qed "comp_subst_subst";
   139 qed "comp_subst_subst";
   140 
   140 
   141 
   141 
   142 (****  Domain and range of Substitutions ****)
   142 (****  Domain and range of Substitutions ****)
   143 
   143 
   144 goal Subst.thy  "(v : sdom(s)) = (Var(v) <| s ~= Var(v))";
   144 goal Subst.thy  "(v : sdom(s)) = (Var(v) <| s ~= Var(v))";
   145 by (alist_ind_tac "s" 1);
   145 by (alist_ind_tac "s" 1);
   146 by (ALLGOALS (asm_simp_tac (!simpset addsplits [expand_if])));
   146 by (ALLGOALS (asm_simp_tac (simpset() addsplits [expand_if])));
   147 by (Blast_tac 1);
   147 by (Blast_tac 1);
   148 qed "sdom_iff";
   148 qed "sdom_iff";
   149 
   149 
   150 
   150 
   151 goalw Subst.thy [srange_def]  
   151 goalw Subst.thy [srange_def]  
   158 qed "empty_iff_all_not";
   158 qed "empty_iff_all_not";
   159 
   159 
   160 goal Subst.thy  "(t <| s = t) = (sdom(s) Int vars_of(t) = {})";
   160 goal Subst.thy  "(t <| s = t) = (sdom(s) Int vars_of(t) = {})";
   161 by (induct_tac "t" 1);
   161 by (induct_tac "t" 1);
   162 by (ALLGOALS
   162 by (ALLGOALS
   163     (asm_full_simp_tac (!simpset addsimps [empty_iff_all_not, sdom_iff])));
   163     (asm_full_simp_tac (simpset() addsimps [empty_iff_all_not, sdom_iff])));
   164 by (ALLGOALS Blast_tac);
   164 by (ALLGOALS Blast_tac);
   165 qed "invariance";
   165 qed "invariance";
   166 
   166 
   167 goal Subst.thy  "v : sdom(s) -->  v : vars_of(t <| s) --> v : srange(s)";
   167 goal Subst.thy  "v : sdom(s) -->  v : vars_of(t <| s) --> v : srange(s)";
   168 by (induct_tac "t" 1);
   168 by (induct_tac "t" 1);
   169 by (case_tac "a : sdom(s)" 1);
   169 by (case_tac "a : sdom(s)" 1);
   170 by (ALLGOALS (asm_full_simp_tac (!simpset addsimps [sdom_iff, srange_iff])));
   170 by (ALLGOALS (asm_full_simp_tac (simpset() addsimps [sdom_iff, srange_iff])));
   171 by (ALLGOALS Blast_tac);
   171 by (ALLGOALS Blast_tac);
   172 qed_spec_mp "Var_in_srange";
   172 qed_spec_mp "Var_in_srange";
   173 
   173 
   174 goal Subst.thy 
   174 goal Subst.thy 
   175      "!!v. [| v : sdom(s); v ~: srange(s) |] ==>  v ~: vars_of(t <| s)";
   175      "!!v. [| v : sdom(s); v ~: srange(s) |] ==>  v ~: vars_of(t <| s)";
   176 by (blast_tac (!claset addIs [Var_in_srange]) 1);
   176 by (blast_tac (claset() addIs [Var_in_srange]) 1);
   177 qed "Var_elim";
   177 qed "Var_elim";
   178 
   178 
   179 goal Subst.thy  "v : vars_of(t <| s) --> v : srange(s) | v : vars_of(t)";
   179 goal Subst.thy  "v : vars_of(t <| s) --> v : srange(s) | v : vars_of(t)";
   180 by (induct_tac "t" 1);
   180 by (induct_tac "t" 1);
   181 by (ALLGOALS (asm_full_simp_tac (!simpset addsimps [sdom_iff,srange_iff])));
   181 by (ALLGOALS (asm_full_simp_tac (simpset() addsimps [sdom_iff,srange_iff])));
   182 by (Blast_tac 2);
   182 by (Blast_tac 2);
   183 by (safe_tac (!claset addSIs [exI, vars_var_iff RS iffD1 RS sym]));
   183 by (safe_tac (claset() addSIs [exI, vars_var_iff RS iffD1 RS sym]));
   184 by (Auto_tac());
   184 by (Auto_tac());
   185 qed_spec_mp "Var_intro";
   185 qed_spec_mp "Var_intro";
   186 
   186 
   187 goal Subst.thy
   187 goal Subst.thy
   188     "v : srange(s) --> (? w. w : sdom(s) & v : vars_of(Var(w) <| s))";
   188     "v : srange(s) --> (? w. w : sdom(s) & v : vars_of(Var(w) <| s))";
   189 by (simp_tac (!simpset addsimps [srange_iff]) 1);
   189 by (simp_tac (simpset() addsimps [srange_iff]) 1);
   190 qed_spec_mp "srangeD";
   190 qed_spec_mp "srangeD";
   191 
   191 
   192 goal Subst.thy
   192 goal Subst.thy
   193    "sdom(s) Int srange(s) = {} = (! t. sdom(s) Int vars_of(t <| s) = {})";
   193    "sdom(s) Int srange(s) = {} = (! t. sdom(s) Int vars_of(t <| s) = {})";
   194 by (simp_tac (!simpset addsimps [empty_iff_all_not]) 1);
   194 by (simp_tac (simpset() addsimps [empty_iff_all_not]) 1);
   195 by (fast_tac (!claset addIs [Var_in_srange] addDs [srangeD]) 1);
   195 by (fast_tac (claset() addIs [Var_in_srange] addDs [srangeD]) 1);
   196 qed "dom_range_disjoint";
   196 qed "dom_range_disjoint";
   197 
   197 
   198 goal Subst.thy "!!u. ~ u <| s = u ==> (? x. x : sdom(s))";
   198 goal Subst.thy "!!u. ~ u <| s = u ==> (? x. x : sdom(s))";
   199 by (full_simp_tac (!simpset addsimps [empty_iff_all_not, invariance]) 1);
   199 by (full_simp_tac (simpset() addsimps [empty_iff_all_not, invariance]) 1);
   200 by (Blast_tac 1);
   200 by (Blast_tac 1);
   201 qed "subst_not_empty";
   201 qed "subst_not_empty";
   202 
   202 
   203 
   203 
   204 goal Subst.thy "(M <| [(x, Var x)]) = M";
   204 goal Subst.thy "(M <| [(x, Var x)]) = M";
   205 by (induct_tac "M" 1);
   205 by (induct_tac "M" 1);
   206 by (ALLGOALS (asm_simp_tac (!simpset addsplits [expand_if])));
   206 by (ALLGOALS (asm_simp_tac (simpset() addsplits [expand_if])));
   207 qed "id_subst_lemma";
   207 qed "id_subst_lemma";
   208 
   208 
   209 Addsimps [id_subst_lemma];
   209 Addsimps [id_subst_lemma];