src/HOLCF/IOA/meta_theory/Sequence.ML
changeset 4098 71e05eb27fb6
parent 4042 8abc33930ff0
child 4477 b3e5857d8d99
equal deleted inserted replaced
4097:ddd1c18121e0 4098:71e05eb27fb6
    17 (* ---------------------------------------------------------------- *)
    17 (* ---------------------------------------------------------------- *)
    18 (*                               Map                                *)
    18 (*                               Map                                *)
    19 (* ---------------------------------------------------------------- *)
    19 (* ---------------------------------------------------------------- *)
    20 
    20 
    21 goal thy "Map f`UU =UU";
    21 goal thy "Map f`UU =UU";
    22 by (simp_tac (!simpset addsimps [Map_def]) 1);
    22 by (simp_tac (simpset() addsimps [Map_def]) 1);
    23 qed"Map_UU";
    23 qed"Map_UU";
    24 
    24 
    25 goal thy "Map f`nil =nil";
    25 goal thy "Map f`nil =nil";
    26 by (simp_tac (!simpset addsimps [Map_def]) 1);
    26 by (simp_tac (simpset() addsimps [Map_def]) 1);
    27 qed"Map_nil";
    27 qed"Map_nil";
    28 
    28 
    29 goal thy "Map f`(x>>xs)=(f x) >> Map f`xs";
    29 goal thy "Map f`(x>>xs)=(f x) >> Map f`xs";
    30 by (simp_tac (!simpset addsimps [Map_def, Cons_def,flift2_def]) 1);
    30 by (simp_tac (simpset() addsimps [Map_def, Cons_def,flift2_def]) 1);
    31 qed"Map_cons";
    31 qed"Map_cons";
    32 
    32 
    33 (* ---------------------------------------------------------------- *)
    33 (* ---------------------------------------------------------------- *)
    34 (*                               Filter                             *)
    34 (*                               Filter                             *)
    35 (* ---------------------------------------------------------------- *)
    35 (* ---------------------------------------------------------------- *)
    36 
    36 
    37 goal thy "Filter P`UU =UU";
    37 goal thy "Filter P`UU =UU";
    38 by (simp_tac (!simpset addsimps [Filter_def]) 1);
    38 by (simp_tac (simpset() addsimps [Filter_def]) 1);
    39 qed"Filter_UU";
    39 qed"Filter_UU";
    40 
    40 
    41 goal thy "Filter P`nil =nil";
    41 goal thy "Filter P`nil =nil";
    42 by (simp_tac (!simpset addsimps [Filter_def]) 1);
    42 by (simp_tac (simpset() addsimps [Filter_def]) 1);
    43 qed"Filter_nil";
    43 qed"Filter_nil";
    44 
    44 
    45 goal thy "Filter P`(x>>xs)= (if P x then x>>(Filter P`xs) else Filter P`xs)"; 
    45 goal thy "Filter P`(x>>xs)= (if P x then x>>(Filter P`xs) else Filter P`xs)"; 
    46 by (simp_tac (!simpset addsimps [Filter_def, Cons_def,flift2_def,If_and_if]) 1);
    46 by (simp_tac (simpset() addsimps [Filter_def, Cons_def,flift2_def,If_and_if]) 1);
    47 qed"Filter_cons";
    47 qed"Filter_cons";
    48 
    48 
    49 (* ---------------------------------------------------------------- *)
    49 (* ---------------------------------------------------------------- *)
    50 (*                               Forall                             *)
    50 (*                               Forall                             *)
    51 (* ---------------------------------------------------------------- *)
    51 (* ---------------------------------------------------------------- *)
    52 
    52 
    53 goal thy "Forall P UU";
    53 goal thy "Forall P UU";
    54 by (simp_tac (!simpset addsimps [Forall_def,sforall_def]) 1);
    54 by (simp_tac (simpset() addsimps [Forall_def,sforall_def]) 1);
    55 qed"Forall_UU";
    55 qed"Forall_UU";
    56 
    56 
    57 goal thy "Forall P nil";
    57 goal thy "Forall P nil";
    58 by (simp_tac (!simpset addsimps [Forall_def,sforall_def]) 1);
    58 by (simp_tac (simpset() addsimps [Forall_def,sforall_def]) 1);
    59 qed"Forall_nil";
    59 qed"Forall_nil";
    60 
    60 
    61 goal thy "Forall P (x>>xs)= (P x & Forall P xs)";
    61 goal thy "Forall P (x>>xs)= (P x & Forall P xs)";
    62 by (simp_tac (!simpset addsimps [Forall_def, sforall_def,
    62 by (simp_tac (simpset() addsimps [Forall_def, sforall_def,
    63                                  Cons_def,flift2_def]) 1);
    63                                  Cons_def,flift2_def]) 1);
    64 qed"Forall_cons";
    64 qed"Forall_cons";
    65 
    65 
    66 (* ---------------------------------------------------------------- *)
    66 (* ---------------------------------------------------------------- *)
    67 (*                               Conc                               *)
    67 (*                               Conc                               *)
    68 (* ---------------------------------------------------------------- *)
    68 (* ---------------------------------------------------------------- *)
    69 
    69 
    70 
    70 
    71 goal thy "(x>>xs) @@ y = x>>(xs @@y)"; 
    71 goal thy "(x>>xs) @@ y = x>>(xs @@y)"; 
    72 by (simp_tac (!simpset addsimps [Cons_def]) 1);
    72 by (simp_tac (simpset() addsimps [Cons_def]) 1);
    73 qed"Conc_cons";
    73 qed"Conc_cons";
    74 
    74 
    75 (* ---------------------------------------------------------------- *)
    75 (* ---------------------------------------------------------------- *)
    76 (*                               Takewhile                          *)
    76 (*                               Takewhile                          *)
    77 (* ---------------------------------------------------------------- *)
    77 (* ---------------------------------------------------------------- *)
    78 
    78 
    79 goal thy "Takewhile P`UU =UU";
    79 goal thy "Takewhile P`UU =UU";
    80 by (simp_tac (!simpset addsimps [Takewhile_def]) 1);
    80 by (simp_tac (simpset() addsimps [Takewhile_def]) 1);
    81 qed"Takewhile_UU";
    81 qed"Takewhile_UU";
    82 
    82 
    83 goal thy "Takewhile P`nil =nil";
    83 goal thy "Takewhile P`nil =nil";
    84 by (simp_tac (!simpset addsimps [Takewhile_def]) 1);
    84 by (simp_tac (simpset() addsimps [Takewhile_def]) 1);
    85 qed"Takewhile_nil";
    85 qed"Takewhile_nil";
    86 
    86 
    87 goal thy "Takewhile P`(x>>xs)= (if P x then x>>(Takewhile P`xs) else nil)"; 
    87 goal thy "Takewhile P`(x>>xs)= (if P x then x>>(Takewhile P`xs) else nil)"; 
    88 by (simp_tac (!simpset addsimps [Takewhile_def, Cons_def,flift2_def,If_and_if]) 1);
    88 by (simp_tac (simpset() addsimps [Takewhile_def, Cons_def,flift2_def,If_and_if]) 1);
    89 qed"Takewhile_cons";
    89 qed"Takewhile_cons";
    90 
    90 
    91 (* ---------------------------------------------------------------- *)
    91 (* ---------------------------------------------------------------- *)
    92 (*                               Dropwhile                          *)
    92 (*                               Dropwhile                          *)
    93 (* ---------------------------------------------------------------- *)
    93 (* ---------------------------------------------------------------- *)
    94 
    94 
    95 goal thy "Dropwhile P`UU =UU";
    95 goal thy "Dropwhile P`UU =UU";
    96 by (simp_tac (!simpset addsimps [Dropwhile_def]) 1);
    96 by (simp_tac (simpset() addsimps [Dropwhile_def]) 1);
    97 qed"Dropwhile_UU";
    97 qed"Dropwhile_UU";
    98 
    98 
    99 goal thy "Dropwhile P`nil =nil";
    99 goal thy "Dropwhile P`nil =nil";
   100 by (simp_tac (!simpset addsimps [Dropwhile_def]) 1);
   100 by (simp_tac (simpset() addsimps [Dropwhile_def]) 1);
   101 qed"Dropwhile_nil";
   101 qed"Dropwhile_nil";
   102 
   102 
   103 goal thy "Dropwhile P`(x>>xs)= (if P x then Dropwhile P`xs else x>>xs)"; 
   103 goal thy "Dropwhile P`(x>>xs)= (if P x then Dropwhile P`xs else x>>xs)"; 
   104 by (simp_tac (!simpset addsimps [Dropwhile_def, Cons_def,flift2_def,If_and_if]) 1);
   104 by (simp_tac (simpset() addsimps [Dropwhile_def, Cons_def,flift2_def,If_and_if]) 1);
   105 qed"Dropwhile_cons";
   105 qed"Dropwhile_cons";
   106 
   106 
   107 (* ---------------------------------------------------------------- *)
   107 (* ---------------------------------------------------------------- *)
   108 (*                               Last                               *)
   108 (*                               Last                               *)
   109 (* ---------------------------------------------------------------- *)
   109 (* ---------------------------------------------------------------- *)
   110 
   110 
   111 
   111 
   112 goal thy "Last`UU =UU";
   112 goal thy "Last`UU =UU";
   113 by (simp_tac (!simpset addsimps [Last_def]) 1);
   113 by (simp_tac (simpset() addsimps [Last_def]) 1);
   114 qed"Last_UU";
   114 qed"Last_UU";
   115 
   115 
   116 goal thy "Last`nil =UU";
   116 goal thy "Last`nil =UU";
   117 by (simp_tac (!simpset addsimps [Last_def]) 1);
   117 by (simp_tac (simpset() addsimps [Last_def]) 1);
   118 qed"Last_nil";
   118 qed"Last_nil";
   119 
   119 
   120 goal thy "Last`(x>>xs)= (if xs=nil then Def x else Last`xs)"; 
   120 goal thy "Last`(x>>xs)= (if xs=nil then Def x else Last`xs)"; 
   121 by (simp_tac (!simpset addsimps [Last_def, Cons_def]) 1);
   121 by (simp_tac (simpset() addsimps [Last_def, Cons_def]) 1);
   122 by (res_inst_tac [("x","xs")] seq.casedist 1);
   122 by (res_inst_tac [("x","xs")] seq.casedist 1);
   123 by (asm_simp_tac (!simpset setloop split_tac [expand_if]) 1);
   123 by (asm_simp_tac (simpset() setloop split_tac [expand_if]) 1);
   124 by (REPEAT (Asm_simp_tac 1));
   124 by (REPEAT (Asm_simp_tac 1));
   125 qed"Last_cons";
   125 qed"Last_cons";
   126 
   126 
   127 
   127 
   128 (* ---------------------------------------------------------------- *)
   128 (* ---------------------------------------------------------------- *)
   129 (*                               Flat                               *)
   129 (*                               Flat                               *)
   130 (* ---------------------------------------------------------------- *)
   130 (* ---------------------------------------------------------------- *)
   131 
   131 
   132 goal thy "Flat`UU =UU";
   132 goal thy "Flat`UU =UU";
   133 by (simp_tac (!simpset addsimps [Flat_def]) 1);
   133 by (simp_tac (simpset() addsimps [Flat_def]) 1);
   134 qed"Flat_UU";
   134 qed"Flat_UU";
   135 
   135 
   136 goal thy "Flat`nil =nil";
   136 goal thy "Flat`nil =nil";
   137 by (simp_tac (!simpset addsimps [Flat_def]) 1);
   137 by (simp_tac (simpset() addsimps [Flat_def]) 1);
   138 qed"Flat_nil";
   138 qed"Flat_nil";
   139 
   139 
   140 goal thy "Flat`(x##xs)= x @@ (Flat`xs)"; 
   140 goal thy "Flat`(x##xs)= x @@ (Flat`xs)"; 
   141 by (simp_tac (!simpset addsimps [Flat_def, Cons_def]) 1);
   141 by (simp_tac (simpset() addsimps [Flat_def, Cons_def]) 1);
   142 qed"Flat_cons";
   142 qed"Flat_cons";
   143 
   143 
   144 
   144 
   145 (* ---------------------------------------------------------------- *)
   145 (* ---------------------------------------------------------------- *)
   146 (*                               Zip                                *)
   146 (*                               Zip                                *)
   179 by (Simp_tac 1);
   179 by (Simp_tac 1);
   180 qed"Zip_nil";
   180 qed"Zip_nil";
   181 
   181 
   182 goal thy "Zip`(x>>xs)`nil= UU"; 
   182 goal thy "Zip`(x>>xs)`nil= UU"; 
   183 by (stac Zip_unfold 1);
   183 by (stac Zip_unfold 1);
   184 by (simp_tac (!simpset addsimps [Cons_def]) 1);
   184 by (simp_tac (simpset() addsimps [Cons_def]) 1);
   185 qed"Zip_cons_nil";
   185 qed"Zip_cons_nil";
   186 
   186 
   187 goal thy "Zip`(x>>xs)`(y>>ys)= (x,y) >> Zip`xs`ys"; 
   187 goal thy "Zip`(x>>xs)`(y>>ys)= (x,y) >> Zip`xs`ys"; 
   188 by (rtac trans 1);
   188 by (rtac trans 1);
   189 by (stac Zip_unfold 1);
   189 by (stac Zip_unfold 1);
   190 by (Simp_tac 1);
   190 by (Simp_tac 1);
   191 (* FIX: Why Simp_tac 2 times. Does continuity in simpflication make job sometimes not 
   191 (* FIX: Why Simp_tac 2 times. Does continuity in simpflication make job sometimes not 
   192   completely ready ? *)
   192   completely ready ? *)
   193 by (simp_tac (!simpset addsimps [Cons_def]) 1);
   193 by (simp_tac (simpset() addsimps [Cons_def]) 1);
   194 qed"Zip_cons";
   194 qed"Zip_cons";
   195 
   195 
   196 
   196 
   197 Delsimps [sfilter_UU,sfilter_nil,sfilter_cons,
   197 Delsimps [sfilter_UU,sfilter_nil,sfilter_cons,
   198           smap_UU,smap_nil,smap_cons,
   198           smap_UU,smap_nil,smap_cons,
   238 
   238 
   239 
   239 
   240 section "Cons";
   240 section "Cons";
   241 
   241 
   242 goal thy "a>>s = (Def a)##s";
   242 goal thy "a>>s = (Def a)##s";
   243 by (simp_tac (!simpset addsimps [Cons_def]) 1);
   243 by (simp_tac (simpset() addsimps [Cons_def]) 1);
   244 qed"Cons_def2";
   244 qed"Cons_def2";
   245 
   245 
   246 goal thy "x = UU | x = nil | (? a s. x = a >> s)";
   246 goal thy "x = UU | x = nil | (? a s. x = a >> s)";
   247 by (simp_tac (!simpset addsimps [Cons_def2]) 1);
   247 by (simp_tac (simpset() addsimps [Cons_def2]) 1);
   248 by (cut_facts_tac [seq.exhaust] 1);
   248 by (cut_facts_tac [seq.exhaust] 1);
   249 by (fast_tac (HOL_cs addDs [not_Undef_is_Def RS iffD1]) 1);
   249 by (fast_tac (HOL_cs addDs [not_Undef_is_Def RS iffD1]) 1);
   250 qed"Seq_exhaust";
   250 qed"Seq_exhaust";
   251 
   251 
   252 
   252 
   277 
   277 
   278 goal thy "~(a>>x) << UU";
   278 goal thy "~(a>>x) << UU";
   279 by (rtac notI 1);
   279 by (rtac notI 1);
   280 by (dtac antisym_less 1);
   280 by (dtac antisym_less 1);
   281 by (Simp_tac 1);
   281 by (Simp_tac 1);
   282 by (asm_full_simp_tac (!simpset addsimps [Cons_not_UU]) 1);
   282 by (asm_full_simp_tac (simpset() addsimps [Cons_not_UU]) 1);
   283 qed"Cons_not_less_UU";
   283 qed"Cons_not_less_UU";
   284 
   284 
   285 goal thy "~a>>s << nil";
   285 goal thy "~a>>s << nil";
   286 by (stac Cons_def2 1);
   286 by (stac Cons_def2 1);
   287 by (resolve_tac seq.rews 1);
   287 by (resolve_tac seq.rews 1);
   292 by (stac Cons_def2 1);
   292 by (stac Cons_def2 1);
   293 by (resolve_tac seq.rews 1);
   293 by (resolve_tac seq.rews 1);
   294 qed"Cons_not_nil";
   294 qed"Cons_not_nil";
   295 
   295 
   296 goal thy "nil ~= a>>s";
   296 goal thy "nil ~= a>>s";
   297 by (simp_tac (!simpset addsimps [Cons_def2]) 1);
   297 by (simp_tac (simpset() addsimps [Cons_def2]) 1);
   298 qed"Cons_not_nil2";
   298 qed"Cons_not_nil2";
   299 
   299 
   300 goal thy "(a>>s = b>>t) = (a = b & s = t)";
   300 goal thy "(a>>s = b>>t) = (a = b & s = t)";
   301 by (simp_tac (HOL_ss addsimps [Cons_def2]) 1);
   301 by (simp_tac (HOL_ss addsimps [Cons_def2]) 1);
   302 by (stac (hd lift.inject RS sym) 1);
   302 by (stac (hd lift.inject RS sym) 1);
   304 by (rtac scons_inject_eq 1);
   304 by (rtac scons_inject_eq 1);
   305 by (REPEAT(rtac Def_not_UU 1));
   305 by (REPEAT(rtac Def_not_UU 1));
   306 qed"Cons_inject_eq";
   306 qed"Cons_inject_eq";
   307 
   307 
   308 goal thy "(a>>s<<b>>t) = (a = b & s<<t)";
   308 goal thy "(a>>s<<b>>t) = (a = b & s<<t)";
   309 by (simp_tac (!simpset addsimps [Cons_def2]) 1);
   309 by (simp_tac (simpset() addsimps [Cons_def2]) 1);
   310 by (stac (Def_inject_less_eq RS sym) 1);
   310 by (stac (Def_inject_less_eq RS sym) 1);
   311 back();
   311 back();
   312 by (rtac iffI 1);
   312 by (rtac iffI 1);
   313 (* 1 *)
   313 (* 1 *)
   314 by (etac (hd seq.inverts) 1);
   314 by (etac (hd seq.inverts) 1);
   318 by (etac conjE 1);
   318 by (etac conjE 1);
   319 by (etac monofun_cfun_arg 1);
   319 by (etac monofun_cfun_arg 1);
   320 qed"Cons_inject_less_eq";
   320 qed"Cons_inject_less_eq";
   321 
   321 
   322 goal thy "seq_take (Suc n)`(a>>x) = a>> (seq_take n`x)";
   322 goal thy "seq_take (Suc n)`(a>>x) = a>> (seq_take n`x)";
   323 by (simp_tac (!simpset addsimps [Cons_def]) 1);
   323 by (simp_tac (simpset() addsimps [Cons_def]) 1);
   324 qed"seq_take_Cons";
   324 qed"seq_take_Cons";
   325 
   325 
   326 Addsimps [Cons_not_nil2,Cons_inject_eq,Cons_inject_less_eq,seq_take_Cons,
   326 Addsimps [Cons_not_nil2,Cons_inject_eq,Cons_inject_less_eq,seq_take_Cons,
   327           Cons_not_UU,Cons_not_less_UU,Cons_not_less_nil,Cons_not_nil];
   327           Cons_not_UU,Cons_not_less_UU,Cons_not_less_nil,Cons_not_nil];
   328 
   328 
   341 
   341 
   342 goal thy "!! P. [| adm P; P UU; P nil; !! a s. P s ==> P (a>>s)|] ==> P x";
   342 goal thy "!! P. [| adm P; P UU; P nil; !! a s. P s ==> P (a>>s)|] ==> P x";
   343 by (etac seq.ind 1);
   343 by (etac seq.ind 1);
   344 by (REPEAT (atac 1));
   344 by (REPEAT (atac 1));
   345 by (def_tac 1);
   345 by (def_tac 1);
   346 by (asm_full_simp_tac (!simpset addsimps [Cons_def]) 1);
   346 by (asm_full_simp_tac (simpset() addsimps [Cons_def]) 1);
   347 qed"Seq_induct";
   347 qed"Seq_induct";
   348 
   348 
   349 goal thy "!! P.[|P UU;P nil; !! a s. P s ==> P(a>>s) |]  \
   349 goal thy "!! P.[|P UU;P nil; !! a s. P s ==> P(a>>s) |]  \
   350 \               ==> seq_finite x --> P x";
   350 \               ==> seq_finite x --> P x";
   351 by (etac seq_finite_ind 1);
   351 by (etac seq_finite_ind 1);
   352 by (REPEAT (atac 1));
   352 by (REPEAT (atac 1));
   353 by (def_tac 1);
   353 by (def_tac 1);
   354 by (asm_full_simp_tac (!simpset addsimps [Cons_def]) 1);
   354 by (asm_full_simp_tac (simpset() addsimps [Cons_def]) 1);
   355 qed"Seq_FinitePartial_ind";
   355 qed"Seq_FinitePartial_ind";
   356 
   356 
   357 goal thy "!! P.[| Finite x; P nil; !! a s. [| Finite s; P s|] ==> P (a>>s) |] ==> P x";
   357 goal thy "!! P.[| Finite x; P nil; !! a s. [| Finite s; P s|] ==> P (a>>s) |] ==> P x";
   358 by (etac sfinite.induct 1);
   358 by (etac sfinite.induct 1);
   359 by (assume_tac 1);
   359 by (assume_tac 1);
   360 by (def_tac 1);
   360 by (def_tac 1);
   361 by (asm_full_simp_tac (!simpset addsimps [Cons_def]) 1);
   361 by (asm_full_simp_tac (simpset() addsimps [Cons_def]) 1);
   362 qed"Seq_Finite_ind"; 
   362 qed"Seq_Finite_ind"; 
   363 
   363 
   364 
   364 
   365 (* rws are definitions to be unfolded for admissibility check *)
   365 (* rws are definitions to be unfolded for admissibility check *)
   366 fun Seq_induct_tac s rws i = res_inst_tac [("x",s)] Seq_induct i
   366 fun Seq_induct_tac s rws i = res_inst_tac [("x",s)] Seq_induct i
   367                          THEN (REPEAT_DETERM (CHANGED (Asm_simp_tac (i+1))))
   367                          THEN (REPEAT_DETERM (CHANGED (Asm_simp_tac (i+1))))
   368                          THEN simp_tac (!simpset addsimps rws) i;
   368                          THEN simp_tac (simpset() addsimps rws) i;
   369 
   369 
   370 fun Seq_Finite_induct_tac i = etac Seq_Finite_ind i
   370 fun Seq_Finite_induct_tac i = etac Seq_Finite_ind i
   371                               THEN (REPEAT_DETERM (CHANGED (Asm_simp_tac i)));
   371                               THEN (REPEAT_DETERM (CHANGED (Asm_simp_tac i)));
   372 
   372 
   373 fun pair_tac s = res_inst_tac [("p",s)] PairE
   373 fun pair_tac s = res_inst_tac [("p",s)] PairE
   376 (* induction on a sequence of pairs with pairsplitting and simplification *)
   376 (* induction on a sequence of pairs with pairsplitting and simplification *)
   377 fun pair_induct_tac s rws i = 
   377 fun pair_induct_tac s rws i = 
   378            res_inst_tac [("x",s)] Seq_induct i 
   378            res_inst_tac [("x",s)] Seq_induct i 
   379            THEN pair_tac "a" (i+3) 
   379            THEN pair_tac "a" (i+3) 
   380            THEN (REPEAT_DETERM (CHANGED (Simp_tac (i+1)))) 
   380            THEN (REPEAT_DETERM (CHANGED (Simp_tac (i+1)))) 
   381            THEN simp_tac (!simpset addsimps rws) i;
   381            THEN simp_tac (simpset() addsimps rws) i;
   382 
   382 
   383 
   383 
   384 
   384 
   385 (* ------------------------------------------------------------------------------------ *)
   385 (* ------------------------------------------------------------------------------------ *)
   386 
   386 
   387 section "HD,TL";
   387 section "HD,TL";
   388 
   388 
   389 goal thy "HD`(x>>y) = Def x";
   389 goal thy "HD`(x>>y) = Def x";
   390 by (simp_tac (!simpset addsimps [Cons_def]) 1);
   390 by (simp_tac (simpset() addsimps [Cons_def]) 1);
   391 qed"HD_Cons";
   391 qed"HD_Cons";
   392 
   392 
   393 goal thy "TL`(x>>y) = y";
   393 goal thy "TL`(x>>y) = y";
   394 by (simp_tac (!simpset addsimps [Cons_def]) 1);
   394 by (simp_tac (simpset() addsimps [Cons_def]) 1);
   395 qed"TL_Cons";
   395 qed"TL_Cons";
   396 
   396 
   397 Addsimps [HD_Cons,TL_Cons];
   397 Addsimps [HD_Cons,TL_Cons];
   398 
   398 
   399 (* ------------------------------------------------------------------------------------ *)
   399 (* ------------------------------------------------------------------------------------ *)
   400 
   400 
   401 section "Finite, Partial, Infinite";
   401 section "Finite, Partial, Infinite";
   402 
   402 
   403 goal thy "Finite (a>>xs) = Finite xs";
   403 goal thy "Finite (a>>xs) = Finite xs";
   404 by (simp_tac (!simpset addsimps [Cons_def2,Finite_cons]) 1);
   404 by (simp_tac (simpset() addsimps [Cons_def2,Finite_cons]) 1);
   405 qed"Finite_Cons";
   405 qed"Finite_Cons";
   406 
   406 
   407 Addsimps [Finite_Cons];
   407 Addsimps [Finite_Cons];
   408 goal thy "!! x. Finite (x::'a Seq) ==> Finite y --> Finite (x@@y)";
   408 goal thy "!! x. Finite (x::'a Seq) ==> Finite y --> Finite (x@@y)";
   409 by (Seq_Finite_induct_tac 1);
   409 by (Seq_Finite_induct_tac 1);
   419 by (Asm_full_simp_tac 1);
   419 by (Asm_full_simp_tac 1);
   420 (* cons *)
   420 (* cons *)
   421 by (strip_tac 1);
   421 by (strip_tac 1);
   422 by (Seq_case_simp_tac "x" 1);
   422 by (Seq_case_simp_tac "x" 1);
   423 by (Seq_case_simp_tac "y" 1);
   423 by (Seq_case_simp_tac "y" 1);
   424 by (SELECT_GOAL (auto_tac (!claset,!simpset))1);
   424 by (SELECT_GOAL (auto_tac (claset(),simpset()))1);
   425 by (eres_inst_tac [("x","sa")] allE 1);
   425 by (eres_inst_tac [("x","sa")] allE 1);
   426 by (eres_inst_tac [("x","y")] allE 1);
   426 by (eres_inst_tac [("x","y")] allE 1);
   427 by (Asm_full_simp_tac 1);
   427 by (Asm_full_simp_tac 1);
   428 qed"FiniteConc_2";
   428 qed"FiniteConc_2";
   429 
   429 
   461 qed"Map2Finite";
   461 qed"Map2Finite";
   462 
   462 
   463 
   463 
   464 goal thy "!! s. Finite s ==> Finite (Filter P`s)";
   464 goal thy "!! s. Finite s ==> Finite (Filter P`s)";
   465 by (Seq_Finite_induct_tac 1);
   465 by (Seq_Finite_induct_tac 1);
   466 by (asm_simp_tac (!simpset setloop split_tac [expand_if]) 1);
   466 by (asm_simp_tac (simpset() setloop split_tac [expand_if]) 1);
   467 qed"FiniteFilter";
   467 qed"FiniteFilter";
   468 
   468 
   469 
   469 
   470 (* ----------------------------------------------------------------------------------- *)
   470 (* ----------------------------------------------------------------------------------- *)
   471 
   471 
   543 
   543 
   544 section "Last";
   544 section "Last";
   545 
   545 
   546 goal thy "!! s. Finite s ==> s~=nil --> Last`s~=UU";
   546 goal thy "!! s. Finite s ==> s~=nil --> Last`s~=UU";
   547 by (Seq_Finite_induct_tac  1);
   547 by (Seq_Finite_induct_tac  1);
   548 by (asm_simp_tac (!simpset setloop split_tac [expand_if]) 1);
   548 by (asm_simp_tac (simpset() setloop split_tac [expand_if]) 1);
   549 qed"Finite_Last1";
   549 qed"Finite_Last1";
   550 
   550 
   551 goal thy "!! s. Finite s ==> Last`s=UU --> s=nil";
   551 goal thy "!! s. Finite s ==> Last`s=UU --> s=nil";
   552 by (Seq_Finite_induct_tac  1);
   552 by (Seq_Finite_induct_tac  1);
   553 by (asm_simp_tac (!simpset setloop split_tac [expand_if]) 1);
   553 by (asm_simp_tac (simpset() setloop split_tac [expand_if]) 1);
   554 by (fast_tac HOL_cs 1);
   554 by (fast_tac HOL_cs 1);
   555 qed"Finite_Last2";
   555 qed"Finite_Last2";
   556 
   556 
   557 
   557 
   558 (* ------------------------------------------------------------------------------------ *)
   558 (* ------------------------------------------------------------------------------------ *)
   561 section "Filter, Conc";
   561 section "Filter, Conc";
   562 
   562 
   563 
   563 
   564 goal thy "Filter P`(Filter Q`s) = Filter (%x. P x & Q x)`s";
   564 goal thy "Filter P`(Filter Q`s) = Filter (%x. P x & Q x)`s";
   565 by (Seq_induct_tac "s" [Filter_def] 1);
   565 by (Seq_induct_tac "s" [Filter_def] 1);
   566 by (asm_full_simp_tac (!simpset setloop split_tac [expand_if] ) 1);
   566 by (asm_full_simp_tac (simpset() setloop split_tac [expand_if] ) 1);
   567 qed"FilterPQ";
   567 qed"FilterPQ";
   568 
   568 
   569 goal thy "Filter P`(x @@ y) = (Filter P`x @@ Filter P`y)";
   569 goal thy "Filter P`(x @@ y) = (Filter P`x @@ Filter P`y)";
   570 by (simp_tac (!simpset addsimps [Filter_def,sfiltersconc]) 1);
   570 by (simp_tac (simpset() addsimps [Filter_def,sfiltersconc]) 1);
   571 qed"FilterConc";
   571 qed"FilterConc";
   572 
   572 
   573 (* ------------------------------------------------------------------------------------ *)
   573 (* ------------------------------------------------------------------------------------ *)
   574 
   574 
   575 section "Map";
   575 section "Map";
   582 by (Seq_induct_tac "x" [] 1);
   582 by (Seq_induct_tac "x" [] 1);
   583 qed"MapConc";
   583 qed"MapConc";
   584 
   584 
   585 goal thy "Filter P`(Map f`x) = Map f`(Filter (P o f)`x)";
   585 goal thy "Filter P`(Map f`x) = Map f`(Filter (P o f)`x)";
   586 by (Seq_induct_tac "x" [] 1);
   586 by (Seq_induct_tac "x" [] 1);
   587 by (asm_full_simp_tac (!simpset setloop split_tac [expand_if] ) 1);
   587 by (asm_full_simp_tac (simpset() setloop split_tac [expand_if] ) 1);
   588 qed"MapFilter";
   588 qed"MapFilter";
   589 
   589 
   590 goal thy "nil = (Map f`s) --> s= nil";
   590 goal thy "nil = (Map f`s) --> s= nil";
   591 by (Seq_case_simp_tac "s" 1);
   591 by (Seq_case_simp_tac "s" 1);
   592 qed"nilMap";
   592 qed"nilMap";
   627 
   627 
   628 bind_thm ("ForallTL",ForallTL1 RS mp);
   628 bind_thm ("ForallTL",ForallTL1 RS mp);
   629 
   629 
   630 goal thy "Forall P s  --> Forall P (Dropwhile Q`s)";
   630 goal thy "Forall P s  --> Forall P (Dropwhile Q`s)";
   631 by (Seq_induct_tac "s" [Forall_def,sforall_def] 1);
   631 by (Seq_induct_tac "s" [Forall_def,sforall_def] 1);
   632 by (asm_full_simp_tac (!simpset setloop (split_tac [expand_if])) 1);
   632 by (asm_full_simp_tac (simpset() setloop (split_tac [expand_if])) 1);
   633 qed"ForallDropwhile1";
   633 qed"ForallDropwhile1";
   634 
   634 
   635 bind_thm ("ForallDropwhile",ForallDropwhile1 RS mp);
   635 bind_thm ("ForallDropwhile",ForallDropwhile1 RS mp);
   636 
   636 
   637 
   637 
   664 
   664 
   665 section "Forall, Filter";
   665 section "Forall, Filter";
   666 
   666 
   667 
   667 
   668 goal thy "Forall P (Filter P`x)";
   668 goal thy "Forall P (Filter P`x)";
   669 by (simp_tac (!simpset addsimps [Filter_def,Forall_def,forallPsfilterP]) 1);
   669 by (simp_tac (simpset() addsimps [Filter_def,Forall_def,forallPsfilterP]) 1);
   670 qed"ForallPFilterP";
   670 qed"ForallPFilterP";
   671 
   671 
   672 (* holds also in other direction, then equal to forallPfilterP *)
   672 (* holds also in other direction, then equal to forallPfilterP *)
   673 goal thy "Forall P x --> Filter P`x = x";
   673 goal thy "Forall P x --> Filter P`x = x";
   674 by (Seq_induct_tac "x" [Forall_def,sforall_def,Filter_def] 1);
   674 by (Seq_induct_tac "x" [Forall_def,sforall_def,Filter_def] 1);
   705 by (rtac adm_all 1);
   705 by (rtac adm_all 1);
   706 (* base cases *)
   706 (* base cases *)
   707 by (Simp_tac 1);
   707 by (Simp_tac 1);
   708 by (Simp_tac 1);
   708 by (Simp_tac 1);
   709 (* main case *)
   709 (* main case *)
   710 by (asm_full_simp_tac (!simpset setloop split_tac [expand_if] ) 1);
   710 by (asm_full_simp_tac (simpset() setloop split_tac [expand_if] ) 1);
   711 qed"FilternPnilForallP1";
   711 qed"FilternPnilForallP1";
   712 
   712 
   713 bind_thm ("FilternPnilForallP",FilternPnilForallP1 RS mp);
   713 bind_thm ("FilternPnilForallP",FilternPnilForallP1 RS mp);
   714 
   714 
   715 (* inverse of ForallnPFilterPUU. proved by 2 lemmas because of adm problems *)
   715 (* inverse of ForallnPFilterPUU. proved by 2 lemmas because of adm problems *)
   716 
   716 
   717 goal thy "!! ys. Finite ys ==> Filter P`ys ~= UU";
   717 goal thy "!! ys. Finite ys ==> Filter P`ys ~= UU";
   718 by (Seq_Finite_induct_tac 1);
   718 by (Seq_Finite_induct_tac 1);
   719 by (asm_full_simp_tac (!simpset setloop split_tac [expand_if] ) 1);
   719 by (asm_full_simp_tac (simpset() setloop split_tac [expand_if] ) 1);
   720 qed"FilterUU_nFinite_lemma1";
   720 qed"FilterUU_nFinite_lemma1";
   721 
   721 
   722 goal thy "~ Forall (%x. ~P x) ys --> Filter P`ys ~= UU";
   722 goal thy "~ Forall (%x. ~P x) ys --> Filter P`ys ~= UU";
   723 by (Seq_induct_tac "ys" [Forall_def,sforall_def] 1);
   723 by (Seq_induct_tac "ys" [Forall_def,sforall_def] 1);
   724 by (asm_full_simp_tac (!simpset setloop split_tac [expand_if] ) 1);
   724 by (asm_full_simp_tac (simpset() setloop split_tac [expand_if] ) 1);
   725 qed"FilterUU_nFinite_lemma2";
   725 qed"FilterUU_nFinite_lemma2";
   726 
   726 
   727 goal thy   "!! P. Filter P`ys = UU ==> \
   727 goal thy   "!! P. Filter P`ys = UU ==> \
   728 \                (Forall (%x. ~P x) ys  & ~Finite ys)";
   728 \                (Forall (%x. ~P x) ys  & ~Finite ys)";
   729 by (rtac conjI 1);
   729 by (rtac conjI 1);
   730 by (cut_inst_tac [] (FilterUU_nFinite_lemma2 RS mp COMP rev_contrapos) 1);
   730 by (cut_inst_tac [] (FilterUU_nFinite_lemma2 RS mp COMP rev_contrapos) 1);
   731 by (Auto_tac());
   731 by (Auto_tac());
   732 by (blast_tac (!claset addSDs [FilterUU_nFinite_lemma1]) 1);
   732 by (blast_tac (claset() addSDs [FilterUU_nFinite_lemma1]) 1);
   733 qed"FilternPUUForallP";
   733 qed"FilternPUUForallP";
   734 
   734 
   735 
   735 
   736 goal thy  "!! Q P.[| Forall Q ys; Finite ys; !!x. Q x ==> ~P x|] \
   736 goal thy  "!! Q P.[| Forall Q ys; Finite ys; !!x. Q x ==> ~P x|] \
   737 \   ==> Filter P`ys = nil";
   737 \   ==> Filter P`ys = nil";
   753 
   753 
   754 section "Takewhile, Forall, Filter";
   754 section "Takewhile, Forall, Filter";
   755 
   755 
   756 
   756 
   757 goal thy "Forall P (Takewhile P`x)";
   757 goal thy "Forall P (Takewhile P`x)";
   758 by (simp_tac (!simpset addsimps [Forall_def,Takewhile_def,sforallPstakewhileP]) 1);
   758 by (simp_tac (simpset() addsimps [Forall_def,Takewhile_def,sforallPstakewhileP]) 1);
   759 qed"ForallPTakewhileP";
   759 qed"ForallPTakewhileP";
   760 
   760 
   761 
   761 
   762 goal thy"!! P. [| !!x. Q x==> P x |] ==> Forall P (Takewhile Q`x)";
   762 goal thy"!! P. [| !!x. Q x==> P x |] ==> Forall P (Takewhile Q`x)";
   763 by (rtac ForallPForallQ 1);
   763 by (rtac ForallPForallQ 1);
   785 Addsimps [ForallPTakewhileP,ForallPTakewhileQ,
   785 Addsimps [ForallPTakewhileP,ForallPTakewhileQ,
   786           FilterPTakewhileQnil,FilterPTakewhileQid];
   786           FilterPTakewhileQnil,FilterPTakewhileQid];
   787 
   787 
   788 goal thy "Takewhile P`(Takewhile P`s) = Takewhile P`s";
   788 goal thy "Takewhile P`(Takewhile P`s) = Takewhile P`s";
   789 by (Seq_induct_tac "s" [Forall_def,sforall_def] 1);
   789 by (Seq_induct_tac "s" [Forall_def,sforall_def] 1);
   790 by (asm_full_simp_tac (!simpset setloop (split_tac [expand_if])) 1);
   790 by (asm_full_simp_tac (simpset() setloop (split_tac [expand_if])) 1);
   791 qed"Takewhile_idempotent";
   791 qed"Takewhile_idempotent";
   792 
   792 
   793 goal thy "Forall P s --> Takewhile (%x. Q x | (~P x))`s = Takewhile Q`s";
   793 goal thy "Forall P s --> Takewhile (%x. Q x | (~P x))`s = Takewhile Q`s";
   794 by (Seq_induct_tac "s" [Forall_def,sforall_def] 1);
   794 by (Seq_induct_tac "s" [Forall_def,sforall_def] 1);
   795 qed"ForallPTakewhileQnP";
   795 qed"ForallPTakewhileQnP";
   901 
   901 
   902 
   902 
   903 goal thy "!! n.[| x=y; s=t;!! k. k<n ==> seq_take k`y1 = seq_take k`y2|] \
   903 goal thy "!! n.[| x=y; s=t;!! k. k<n ==> seq_take k`y1 = seq_take k`y2|] \
   904 \ ==> seq_take n`(x @@ (s>>y1)) =  seq_take n`(y @@ (t>>y2))";
   904 \ ==> seq_take n`(x @@ (s>>y1)) =  seq_take n`(y @@ (t>>y2))";
   905 
   905 
   906 by (auto_tac (!claset addSIs [take_reduction1 RS spec RS mp],!simpset));
   906 by (auto_tac (claset() addSIs [take_reduction1 RS spec RS mp],simpset()));
   907 qed"take_reduction";
   907 qed"take_reduction";
   908 
   908 
   909 (* ------------------------------------------------------------------
   909 (* ------------------------------------------------------------------
   910           take-lemma and take_reduction for << instead of = 
   910           take-lemma and take_reduction for << instead of = 
   911    ------------------------------------------------------------------ *)
   911    ------------------------------------------------------------------ *)
   922 qed"take_reduction_less1";
   922 qed"take_reduction_less1";
   923 
   923 
   924 
   924 
   925 goal thy "!! n.[| x=y; s=t;!! k. k<n ==> seq_take k`y1 << seq_take k`y2|] \
   925 goal thy "!! n.[| x=y; s=t;!! k. k<n ==> seq_take k`y1 << seq_take k`y2|] \
   926 \ ==> seq_take n`(x @@ (s>>y1)) <<  seq_take n`(y @@ (t>>y2))";
   926 \ ==> seq_take n`(x @@ (s>>y1)) <<  seq_take n`(y @@ (t>>y2))";
   927 by (auto_tac (!claset addSIs [take_reduction_less1 RS spec RS mp],!simpset));
   927 by (auto_tac (claset() addSIs [take_reduction_less1 RS spec RS mp],simpset()));
   928 qed"take_reduction_less";
   928 qed"take_reduction_less";
   929 
   929 
   930 
   930 
   931 val prems = goalw thy [seq.take_def]
   931 val prems = goalw thy [seq.take_def]
   932 "(!! n. seq_take n`s1 << seq_take n`s2)  ==> s1<<s2";
   932 "(!! n. seq_take n`s1 << seq_take n`s2)  ==> s1<<s2";
   960 goal thy "!! Q. [|!! s. [| Forall Q s; A s |] ==> (f s) = (g s) ; \
   960 goal thy "!! Q. [|!! s. [| Forall Q s; A s |] ==> (f s) = (g s) ; \
   961 \           !! s1 s2 y. [| Forall Q s1; Finite s1; ~ Q y; A (s1 @@ y>>s2)|] \
   961 \           !! s1 s2 y. [| Forall Q s1; Finite s1; ~ Q y; A (s1 @@ y>>s2)|] \
   962 \                         ==> (f (s1 @@ y>>s2)) = (g (s1 @@ y>>s2)) |] \
   962 \                         ==> (f (s1 @@ y>>s2)) = (g (s1 @@ y>>s2)) |] \
   963 \              ==> A x --> (f x)=(g x)";
   963 \              ==> A x --> (f x)=(g x)";
   964 by (case_tac "Forall Q x" 1);
   964 by (case_tac "Forall Q x" 1);
   965 by (auto_tac (!claset addSDs [divide_Seq3],!simpset));
   965 by (auto_tac (claset() addSDs [divide_Seq3],simpset()));
   966 qed"take_lemma_principle1";
   966 qed"take_lemma_principle1";
   967 
   967 
   968 goal thy "!! Q. [|!! s. [| Forall Q s; A s |] ==> (f s) = (g s) ; \
   968 goal thy "!! Q. [|!! s. [| Forall Q s; A s |] ==> (f s) = (g s) ; \
   969 \           !! s1 s2 y. [| Forall Q s1; Finite s1; ~ Q y; A (s1 @@ y>>s2)|] \
   969 \           !! s1 s2 y. [| Forall Q s1; Finite s1; ~ Q y; A (s1 @@ y>>s2)|] \
   970 \                         ==> ! n. seq_take n`(f (s1 @@ y>>s2)) \
   970 \                         ==> ! n. seq_take n`(f (s1 @@ y>>s2)) \
   971 \                                = seq_take n`(g (s1 @@ y>>s2)) |] \
   971 \                                = seq_take n`(g (s1 @@ y>>s2)) |] \
   972 \              ==> A x --> (f x)=(g x)";
   972 \              ==> A x --> (f x)=(g x)";
   973 by (case_tac "Forall Q x" 1);
   973 by (case_tac "Forall Q x" 1);
   974 by (auto_tac (!claset addSDs [divide_Seq3],!simpset));
   974 by (auto_tac (claset() addSDs [divide_Seq3],simpset()));
   975 by (resolve_tac seq.take_lemmas 1);
   975 by (resolve_tac seq.take_lemmas 1);
   976 by (Auto_tac());
   976 by (Auto_tac());
   977 qed"take_lemma_principle2";
   977 qed"take_lemma_principle2";
   978 
   978 
   979 
   979 
   999 by (res_inst_tac [("x","x")] spec 1);
   999 by (res_inst_tac [("x","x")] spec 1);
  1000 by (rtac nat_induct 1);
  1000 by (rtac nat_induct 1);
  1001 by (Simp_tac 1);
  1001 by (Simp_tac 1);
  1002 by (rtac allI 1);
  1002 by (rtac allI 1);
  1003 by (case_tac "Forall Q xa" 1);
  1003 by (case_tac "Forall Q xa" 1);
  1004 by (SELECT_GOAL (auto_tac (!claset addSIs [seq_take_lemma RS iffD2 RS spec],
  1004 by (SELECT_GOAL (auto_tac (claset() addSIs [seq_take_lemma RS iffD2 RS spec],
  1005                            !simpset)) 1);
  1005                            simpset())) 1);
  1006 by (auto_tac (!claset addSDs [divide_Seq3],!simpset));
  1006 by (auto_tac (claset() addSDs [divide_Seq3],simpset()));
  1007 qed"take_lemma_induct";
  1007 qed"take_lemma_induct";
  1008 
  1008 
  1009 
  1009 
  1010 goal thy 
  1010 goal thy 
  1011 "!! Q. [|!! s. [| Forall Q s; A s |] ==> (f s) = (g s) ; \
  1011 "!! Q. [|!! s. [| Forall Q s; A s |] ==> (f s) = (g s) ; \
  1020 by (assume_tac 2);
  1020 by (assume_tac 2);
  1021 by (res_inst_tac [("x","x")] spec 1);
  1021 by (res_inst_tac [("x","x")] spec 1);
  1022 by (rtac less_induct 1);
  1022 by (rtac less_induct 1);
  1023 by (rtac allI 1);
  1023 by (rtac allI 1);
  1024 by (case_tac "Forall Q xa" 1);
  1024 by (case_tac "Forall Q xa" 1);
  1025 by (SELECT_GOAL (auto_tac (!claset addSIs [seq_take_lemma RS iffD2 RS spec],
  1025 by (SELECT_GOAL (auto_tac (claset() addSIs [seq_take_lemma RS iffD2 RS spec],
  1026                            !simpset)) 1);
  1026                            simpset())) 1);
  1027 by (auto_tac (!claset addSDs [divide_Seq3],!simpset));
  1027 by (auto_tac (claset() addSDs [divide_Seq3],simpset()));
  1028 qed"take_lemma_less_induct";
  1028 qed"take_lemma_less_induct";
  1029 
  1029 
  1030 
  1030 
  1031 (*
  1031 (*
  1032 local
  1032 local
  1074 by (res_inst_tac [("x","h1a")] spec 1);
  1074 by (res_inst_tac [("x","h1a")] spec 1);
  1075 by (res_inst_tac [("x","x")] spec 1);
  1075 by (res_inst_tac [("x","x")] spec 1);
  1076 by (rtac less_induct 1);
  1076 by (rtac less_induct 1);
  1077 by (rtac allI 1);
  1077 by (rtac allI 1);
  1078 by (case_tac "Forall Q xa" 1);
  1078 by (case_tac "Forall Q xa" 1);
  1079 by (SELECT_GOAL (auto_tac (!claset addSIs [seq_take_lemma RS iffD2 RS spec],
  1079 by (SELECT_GOAL (auto_tac (claset() addSIs [seq_take_lemma RS iffD2 RS spec],
  1080                            !simpset)) 1);
  1080                            simpset())) 1);
  1081 by (auto_tac (!claset addSDs [divide_Seq3],!simpset));
  1081 by (auto_tac (claset() addSDs [divide_Seq3],simpset()));
  1082 qed"take_lemma_less_induct";
  1082 qed"take_lemma_less_induct";
  1083 
  1083 
  1084 
  1084 
  1085 
  1085 
  1086 goal thy 
  1086 goal thy 
  1101 FIX
  1101 FIX
  1102 
  1102 
  1103 by (rtac less_induct 1);
  1103 by (rtac less_induct 1);
  1104 by (rtac allI 1);
  1104 by (rtac allI 1);
  1105 by (case_tac "Forall Q xa" 1);
  1105 by (case_tac "Forall Q xa" 1);
  1106 by (SELECT_GOAL (auto_tac (!claset addSIs [seq_take_lemma RS iffD2 RS spec],
  1106 by (SELECT_GOAL (auto_tac (claset() addSIs [seq_take_lemma RS iffD2 RS spec],
  1107                            !simpset)) 1);
  1107                            simpset())) 1);
  1108 by (auto_tac (!claset addSDs [divide_Seq3],!simpset));
  1108 by (auto_tac (claset() addSDs [divide_Seq3],simpset()));
  1109 qed"take_lemma_less_induct";
  1109 qed"take_lemma_less_induct";
  1110 
  1110 
  1111 
  1111 
  1112 *)
  1112 *)
  1113 
  1113 
  1149 goal thy "Forall (%x.~(P x & Q x)) s \
  1149 goal thy "Forall (%x.~(P x & Q x)) s \
  1150 \         --> Filter P`(Filter Q`s) =\
  1150 \         --> Filter P`(Filter Q`s) =\
  1151 \             Filter (%x. P x & Q x)`s";
  1151 \             Filter (%x. P x & Q x)`s";
  1152 
  1152 
  1153 by (Seq_induct_tac "s" [Forall_def,sforall_def] 1);
  1153 by (Seq_induct_tac "s" [Forall_def,sforall_def] 1);
  1154 by (asm_full_simp_tac (!simpset setloop split_tac [expand_if] ) 1);
  1154 by (asm_full_simp_tac (simpset() setloop split_tac [expand_if] ) 1);
  1155 qed"Filter_lemma1";
  1155 qed"Filter_lemma1";
  1156 
  1156 
  1157 goal thy "!! s. Finite s ==>  \
  1157 goal thy "!! s. Finite s ==>  \
  1158 \         (Forall (%x. (~P x) | (~ Q x)) s  \
  1158 \         (Forall (%x. (~P x) | (~ Q x)) s  \
  1159 \         --> Filter P`(Filter Q`s) = nil)";
  1159 \         --> Filter P`(Filter Q`s) = nil)";
  1160 by (Seq_Finite_induct_tac 1);
  1160 by (Seq_Finite_induct_tac 1);
  1161 by (asm_full_simp_tac (!simpset setloop split_tac [expand_if] ) 1);
  1161 by (asm_full_simp_tac (simpset() setloop split_tac [expand_if] ) 1);
  1162 qed"Filter_lemma2";
  1162 qed"Filter_lemma2";
  1163 
  1163 
  1164 goal thy "!! s. Finite s ==>  \
  1164 goal thy "!! s. Finite s ==>  \
  1165 \         Forall (%x. (~P x) | (~ Q x)) s  \
  1165 \         Forall (%x. (~P x) | (~ Q x)) s  \
  1166 \         --> Filter (%x. P x & Q x)`s = nil";
  1166 \         --> Filter (%x. P x & Q x)`s = nil";
  1167 by (Seq_Finite_induct_tac 1);
  1167 by (Seq_Finite_induct_tac 1);
  1168 by (asm_full_simp_tac (!simpset setloop split_tac [expand_if] ) 1);
  1168 by (asm_full_simp_tac (simpset() setloop split_tac [expand_if] ) 1);
  1169 qed"Filter_lemma3";
  1169 qed"Filter_lemma3";
  1170 
  1170 
  1171 
  1171 
  1172 goal thy "Filter P`(Filter Q`s) = Filter (%x. P x & Q x)`s";
  1172 goal thy "Filter P`(Filter Q`s) = Filter (%x. P x & Q x)`s";
  1173 by (res_inst_tac [("A1","%x. True") 
  1173 by (res_inst_tac [("A1","%x. True") 
  1174                  ,("Q1","%x.~(P x & Q x)"),("x1","s")]
  1174                  ,("Q1","%x.~(P x & Q x)"),("x1","s")]
  1175                  (take_lemma_induct RS mp) 1);
  1175                  (take_lemma_induct RS mp) 1);
  1176 (* FIX: better support for A = %x. True *)
  1176 (* FIX: better support for A = %x. True *)
  1177 by (Fast_tac 3);
  1177 by (Fast_tac 3);
  1178 by (asm_full_simp_tac (!simpset addsimps [Filter_lemma1]) 1);
  1178 by (asm_full_simp_tac (simpset() addsimps [Filter_lemma1]) 1);
  1179 by (asm_full_simp_tac (!simpset addsimps [Filter_lemma2,Filter_lemma3] 
  1179 by (asm_full_simp_tac (simpset() addsimps [Filter_lemma2,Filter_lemma3] 
  1180                                 setloop split_tac [expand_if]) 1);
  1180                                 setloop split_tac [expand_if]) 1);
  1181 qed"FilterPQ_takelemma";
  1181 qed"FilterPQ_takelemma";
  1182 
  1182 
  1183 Addsimps [FilterPQ];
  1183 Addsimps [FilterPQ];
  1184 
  1184