src/HOLCF/IOA/meta_theory/Sequence.ML
changeset 4477 b3e5857d8d99
parent 4098 71e05eb27fb6
child 4681 a331c1f5a23e
equal deleted inserted replaced
4476:fbdc87f8ac7e 4477:b3e5857d8d99
   430 goal thy "Finite(x@@y) = (Finite (x::'a Seq) & Finite y)";
   430 goal thy "Finite(x@@y) = (Finite (x::'a Seq) & Finite y)";
   431 by (rtac iffI 1);
   431 by (rtac iffI 1);
   432 by (etac (FiniteConc_2 RS spec RS spec RS mp) 1);
   432 by (etac (FiniteConc_2 RS spec RS spec RS mp) 1);
   433 by (rtac refl 1);
   433 by (rtac refl 1);
   434 by (rtac (FiniteConc_1 RS mp) 1);
   434 by (rtac (FiniteConc_1 RS mp) 1);
   435 by (Auto_tac());
   435 by Auto_tac;
   436 qed"FiniteConc";
   436 qed"FiniteConc";
   437 
   437 
   438 Addsimps [FiniteConc];
   438 Addsimps [FiniteConc];
   439 
   439 
   440 
   440 
   446 by (Seq_Finite_induct_tac 1);
   446 by (Seq_Finite_induct_tac 1);
   447 by (strip_tac 1);
   447 by (strip_tac 1);
   448 by (Seq_case_simp_tac "t" 1);
   448 by (Seq_case_simp_tac "t" 1);
   449 by (Asm_full_simp_tac 1);
   449 by (Asm_full_simp_tac 1);
   450 (* main case *)
   450 (* main case *)
   451 by (Auto_tac());
   451 by Auto_tac;
   452 by (Seq_case_simp_tac "t" 1);
   452 by (Seq_case_simp_tac "t" 1);
   453 by (Asm_full_simp_tac 1);
   453 by (Asm_full_simp_tac 1);
   454 qed"FiniteMap2";
   454 qed"FiniteMap2";
   455 
   455 
   456 goal thy "Finite (Map f`s) = Finite s";
   456 goal thy "Finite (Map f`s) = Finite s";
   457 by (Auto_tac());
   457 by Auto_tac;
   458 by (etac (FiniteMap2 RS spec RS mp) 1);
   458 by (etac (FiniteMap2 RS spec RS mp) 1);
   459 by (rtac refl 1);
   459 by (rtac refl 1);
   460 by (etac FiniteMap1 1);
   460 by (etac FiniteMap1 1);
   461 qed"Map2Finite";
   461 qed"Map2Finite";
   462 
   462 
   480 by (Seq_Finite_induct_tac 1);
   480 by (Seq_Finite_induct_tac 1);
   481 by (strip_tac 1);
   481 by (strip_tac 1);
   482 by (etac conjE 1);
   482 by (etac conjE 1);
   483 by (etac nil_less_is_nil 1);
   483 by (etac nil_less_is_nil 1);
   484 (* main case *)
   484 (* main case *)
   485 by (Auto_tac());
   485 by Auto_tac;
   486 by (Seq_case_simp_tac "y" 1);
   486 by (Seq_case_simp_tac "y" 1);
   487 by (Auto_tac());
   487 by Auto_tac;
   488 qed_spec_mp"Finite_flat";
   488 qed_spec_mp"Finite_flat";
   489 
   489 
   490 
   490 
   491 goal thy "adm(%(x:: 'a Seq).Finite x)";
   491 goal thy "adm(%(x:: 'a Seq).Finite x)";
   492 by (rtac admI2 1);
   492 by (rtac admI2 1);
   497 by (res_inst_tac [("x","0")] allE 1);
   497 by (res_inst_tac [("x","0")] allE 1);
   498 by (assume_tac 1);
   498 by (assume_tac 1);
   499 by (eres_inst_tac [("x","j")] allE 1);
   499 by (eres_inst_tac [("x","j")] allE 1);
   500 by (cut_inst_tac [("x","Y 0"),("y","Y j")] Finite_flat 1);
   500 by (cut_inst_tac [("x","Y 0"),("y","Y j")] Finite_flat 1);
   501 (* Generates a contradiction in subgoal 3 *)
   501 (* Generates a contradiction in subgoal 3 *)
   502 by (Auto_tac());
   502 by Auto_tac;
   503 qed"adm_Finite";
   503 qed"adm_Finite";
   504 
   504 
   505 Addsimps [adm_Finite];
   505 Addsimps [adm_Finite];
   506 
   506 
   507 
   507 
   528 Addsimps [nilConc];
   528 Addsimps [nilConc];
   529 
   529 
   530 (* FIX: should be same as nil_is_Conc2 when all nils are turned to right side !! *)
   530 (* FIX: should be same as nil_is_Conc2 when all nils are turned to right side !! *)
   531 goal thy "(nil = x @@ y) = ((x::'a Seq)= nil & y = nil)";
   531 goal thy "(nil = x @@ y) = ((x::'a Seq)= nil & y = nil)";
   532 by (Seq_case_simp_tac "x" 1);
   532 by (Seq_case_simp_tac "x" 1);
   533 by (Auto_tac());
   533 by Auto_tac;
   534 qed"nil_is_Conc";
   534 qed"nil_is_Conc";
   535 
   535 
   536 goal thy "(x @@ y = nil) = ((x::'a Seq)= nil & y = nil)";
   536 goal thy "(x @@ y = nil) = ((x::'a Seq)= nil & y = nil)";
   537 by (Seq_case_simp_tac "x" 1);
   537 by (Seq_case_simp_tac "x" 1);
   538 by (Auto_tac());
   538 by Auto_tac;
   539 qed"nil_is_Conc2";
   539 qed"nil_is_Conc2";
   540 
   540 
   541 
   541 
   542 (* ------------------------------------------------------------------------------------ *)
   542 (* ------------------------------------------------------------------------------------ *)
   543 
   543 
   640 goal thy "! s. Forall P s --> t<<s --> Forall P t";
   640 goal thy "! s. Forall P s --> t<<s --> Forall P t";
   641 by (Seq_induct_tac "t" [Forall_def,sforall_def] 1);
   641 by (Seq_induct_tac "t" [Forall_def,sforall_def] 1);
   642 by (strip_tac 1); 
   642 by (strip_tac 1); 
   643 by (Seq_case_simp_tac "sa" 1);
   643 by (Seq_case_simp_tac "sa" 1);
   644 by (Asm_full_simp_tac 1);
   644 by (Asm_full_simp_tac 1);
   645 by (Auto_tac());
   645 by Auto_tac;
   646 qed"Forall_prefix";
   646 qed"Forall_prefix";
   647  
   647  
   648 bind_thm ("Forall_prefixclosed",Forall_prefix RS spec RS mp RS mp);
   648 bind_thm ("Forall_prefixclosed",Forall_prefix RS spec RS mp RS mp);
   649 
   649 
   650 
   650 
   651 goal thy "!! h. [| Finite h; Forall P s; s= h @@ t |] ==> Forall P t";
   651 goal thy "!! h. [| Finite h; Forall P s; s= h @@ t |] ==> Forall P t";
   652 by (Auto_tac());
   652 by Auto_tac;
   653 qed"Forall_postfixclosed";
   653 qed"Forall_postfixclosed";
   654 
   654 
   655 
   655 
   656 goal thy "((! x. P x --> (Q x = R x)) & Forall P tr) --> Filter Q`tr = Filter R`tr";
   656 goal thy "((! x. P x --> (Q x = R x)) & Forall P tr) --> Filter Q`tr = Filter R`tr";
   657 by (Seq_induct_tac "tr" [Forall_def,sforall_def] 1);
   657 by (Seq_induct_tac "tr" [Forall_def,sforall_def] 1);
   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";
   738 by (etac ForallnPFilterPnil 1);
   738 by (etac ForallnPFilterPnil 1);
   739 by (etac ForallPForallQ 1);
   739 by (etac ForallPForallQ 1);
   740 by (Auto_tac());
   740 by Auto_tac;
   741 qed"ForallQFilterPnil";
   741 qed"ForallQFilterPnil";
   742 
   742 
   743 goal thy "!! Q P. [| ~Finite ys; Forall Q ys;  !!x. Q x ==> ~P x|] \
   743 goal thy "!! Q P. [| ~Finite ys; Forall Q ys;  !!x. Q x ==> ~P x|] \
   744 \   ==> Filter P`ys = UU ";
   744 \   ==> Filter P`ys = UU ";
   745 by (etac ForallnPFilterPUU 1);
   745 by (etac ForallnPFilterPUU 1);
   746 by (etac ForallPForallQ 1);
   746 by (etac ForallPForallQ 1);
   747 by (Auto_tac());
   747 by Auto_tac;
   748 qed"ForallQFilterPUU";
   748 qed"ForallQFilterPUU";
   749 
   749 
   750 
   750 
   751 
   751 
   752 (* ------------------------------------------------------------------------------------- *)
   752 (* ------------------------------------------------------------------------------------- *)
   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);
   764 by (rtac ForallPTakewhileP 1);
   764 by (rtac ForallPTakewhileP 1);
   765 by (Auto_tac());
   765 by Auto_tac;
   766 qed"ForallPTakewhileQ";
   766 qed"ForallPTakewhileQ";
   767 
   767 
   768 
   768 
   769 goal thy  "!! Q P.[| Finite (Takewhile Q`ys); !!x. Q x ==> ~P x |] \
   769 goal thy  "!! Q P.[| Finite (Takewhile Q`ys); !!x. Q x ==> ~P x |] \
   770 \   ==> Filter P`(Takewhile Q`ys) = nil";
   770 \   ==> Filter P`(Takewhile Q`ys) = nil";
   771 by (etac ForallnPFilterPnil 1);
   771 by (etac ForallnPFilterPnil 1);
   772 by (rtac ForallPForallQ 1);
   772 by (rtac ForallPForallQ 1);
   773 by (rtac ForallPTakewhileP 1);
   773 by (rtac ForallPTakewhileP 1);
   774 by (Auto_tac());
   774 by Auto_tac;
   775 qed"FilterPTakewhileQnil";
   775 qed"FilterPTakewhileQnil";
   776 
   776 
   777 goal thy "!! Q P. [| !!x. Q x ==> P x |] ==> \
   777 goal thy "!! Q P. [| !!x. Q x ==> P x |] ==> \
   778 \            Filter P`(Takewhile Q`ys) = (Takewhile Q`ys)";
   778 \            Filter P`(Takewhile Q`ys) = (Takewhile Q`ys)";
   779 by (rtac ForallPFilterPid 1);
   779 by (rtac ForallPFilterPid 1);
   780 by (rtac ForallPForallQ 1);
   780 by (rtac ForallPForallQ 1);
   781 by (rtac ForallPTakewhileP 1);
   781 by (rtac ForallPTakewhileP 1);
   782 by (Auto_tac());
   782 by Auto_tac;
   783 qed"FilterPTakewhileQid";
   783 qed"FilterPTakewhileQid";
   784 
   784 
   785 Addsimps [ForallPTakewhileP,ForallPTakewhileQ,
   785 Addsimps [ForallPTakewhileP,ForallPTakewhileQ,
   786           FilterPTakewhileQnil,FilterPTakewhileQid];
   786           FilterPTakewhileQnil,FilterPTakewhileQid];
   787 
   787 
   862 \      Finite (Takewhile P`y) & (~ P x)";
   862 \      Finite (Takewhile P`y) & (~ P x)";
   863 by (dtac (nForall_HDFilter RS mp) 1);
   863 by (dtac (nForall_HDFilter RS mp) 1);
   864 by (safe_tac set_cs);
   864 by (safe_tac set_cs);
   865 by (res_inst_tac [("x","x")] exI 1);
   865 by (res_inst_tac [("x","x")] exI 1);
   866 by (cut_inst_tac [("P1","%x. ~ P x")] (divide_Seq_lemma RS mp) 1);
   866 by (cut_inst_tac [("P1","%x. ~ P x")] (divide_Seq_lemma RS mp) 1);
   867 by (Auto_tac());
   867 by Auto_tac;
   868 qed"divide_Seq2";
   868 qed"divide_Seq2";
   869 
   869 
   870 
   870 
   871 goal thy  "!! y. ~Forall P y \
   871 goal thy  "!! y. ~Forall P y \
   872 \  ==> ? x bs rs. y= (bs @@ (x>>rs)) & Finite bs & Forall P bs & (~ P x)";
   872 \  ==> ? x bs rs. y= (bs @@ (x>>rs)) & Finite bs & Forall P bs & (~ P x)";
   873 by (cut_inst_tac [] divide_Seq2 1);
   873 by (cut_inst_tac [] divide_Seq2 1);
   874 by (Auto_tac());
   874 (*Auto_tac no longer proves it*)
       
   875 by (REPEAT (fast_tac (claset() addss (simpset())) 1));
   875 qed"divide_Seq3";
   876 qed"divide_Seq3";
   876 
   877 
   877 Addsimps [FilterPQ,FilterConc,Conc_cong];
   878 Addsimps [FilterPQ,FilterConc,Conc_cong];
   878 
   879 
   879 
   880 
   883 section "take_lemma";
   884 section "take_lemma";
   884 
   885 
   885 goal thy "(!n. seq_take n`x = seq_take n`x') = (x = x')";
   886 goal thy "(!n. seq_take n`x = seq_take n`x') = (x = x')";
   886 by (rtac iffI 1);
   887 by (rtac iffI 1);
   887 by (resolve_tac seq.take_lemmas 1);
   888 by (resolve_tac seq.take_lemmas 1);
   888 by (Auto_tac());
   889 by Auto_tac;
   889 qed"seq_take_lemma";
   890 qed"seq_take_lemma";
   890 
   891 
   891 goal thy 
   892 goal thy 
   892 "  ! n. ((! k. k < n --> seq_take k`y1 = seq_take k`y2) \
   893 "  ! n. ((! k. k < n --> seq_take k`y1 = seq_take k`y2) \
   893 \   --> seq_take n`(x @@ (t>>y1)) =  seq_take n`(x @@ (t>>y2)))";
   894 \   --> seq_take n`(x @@ (t>>y1)) =  seq_take n`(x @@ (t>>y2)))";
   894 by (Seq_induct_tac "x" [] 1);
   895 by (Seq_induct_tac "x" [] 1);
   895 by (strip_tac 1);
   896 by (strip_tac 1);
   896 by (res_inst_tac [("n","n")] natE 1);
   897 by (res_inst_tac [("n","n")] natE 1);
   897 by (Auto_tac());
   898 by Auto_tac;
   898 by (res_inst_tac [("n","n")] natE 1);
   899 by (res_inst_tac [("n","n")] natE 1);
   899 by (Auto_tac());
   900 by Auto_tac;
   900 qed"take_reduction1";
   901 qed"take_reduction1";
   901 
   902 
   902 
   903 
   903 goal thy "!! n.[| x=y; s=t;!! k. k<n ==> seq_take k`y1 = seq_take k`y2|] \
   904 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))";
   905 \ ==> seq_take n`(x @@ (s>>y1)) =  seq_take n`(y @@ (t>>y2))";
   914 "  ! n. ((! k. k < n --> seq_take k`y1 << seq_take k`y2) \
   915 "  ! n. ((! k. k < n --> seq_take k`y1 << seq_take k`y2) \
   915 \   --> seq_take n`(x @@ (t>>y1)) <<  seq_take n`(x @@ (t>>y2)))";
   916 \   --> seq_take n`(x @@ (t>>y1)) <<  seq_take n`(x @@ (t>>y2)))";
   916 by (Seq_induct_tac "x" [] 1);
   917 by (Seq_induct_tac "x" [] 1);
   917 by (strip_tac 1);
   918 by (strip_tac 1);
   918 by (res_inst_tac [("n","n")] natE 1);
   919 by (res_inst_tac [("n","n")] natE 1);
   919 by (Auto_tac());
   920 by Auto_tac;
   920 by (res_inst_tac [("n","n")] natE 1);
   921 by (res_inst_tac [("n","n")] natE 1);
   921 by (Auto_tac());
   922 by Auto_tac;
   922 qed"take_reduction_less1";
   923 qed"take_reduction_less1";
   923 
   924 
   924 
   925 
   925 goal thy "!! n.[| x=y; s=t;!! k. k<n ==> seq_take k`y1 << seq_take k`y2|] \
   926 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))";
   927 \ ==> seq_take n`(x @@ (s>>y1)) <<  seq_take n`(y @@ (t>>y2))";
   947 
   948 
   948 
   949 
   949 goal thy "(!n. seq_take n`x << seq_take n`x') = (x << x')";
   950 goal thy "(!n. seq_take n`x << seq_take n`x') = (x << x')";
   950 by (rtac iffI 1);
   951 by (rtac iffI 1);
   951 by (rtac take_lemma_less1 1);
   952 by (rtac take_lemma_less1 1);
   952 by (Auto_tac());
   953 by Auto_tac;
   953 by (etac monofun_cfun_arg 1);
   954 by (etac monofun_cfun_arg 1);
   954 qed"take_lemma_less";
   955 qed"take_lemma_less";
   955 
   956 
   956 (* ------------------------------------------------------------------
   957 (* ------------------------------------------------------------------
   957           take-lemma proof principles
   958           take-lemma proof principles
   971 \                                = seq_take n`(g (s1 @@ y>>s2)) |] \
   972 \                                = seq_take n`(g (s1 @@ y>>s2)) |] \
   972 \              ==> A x --> (f x)=(g x)";
   973 \              ==> A x --> (f x)=(g x)";
   973 by (case_tac "Forall Q x" 1);
   974 by (case_tac "Forall Q x" 1);
   974 by (auto_tac (claset() addSDs [divide_Seq3],simpset()));
   975 by (auto_tac (claset() addSDs [divide_Seq3],simpset()));
   975 by (resolve_tac seq.take_lemmas 1);
   976 by (resolve_tac seq.take_lemmas 1);
   976 by (Auto_tac());
   977 by Auto_tac;
   977 qed"take_lemma_principle2";
   978 qed"take_lemma_principle2";
   978 
   979 
   979 
   980 
   980 (* Note: in the following proofs the ordering of proof steps is very 
   981 (* Note: in the following proofs the ordering of proof steps is very 
   981          important, as otherwise either (Forall Q s1) would be in the IH as
   982          important, as otherwise either (Forall Q s1) would be in the IH as
  1188 (* --------------------------------------------------------------- *)
  1189 (* --------------------------------------------------------------- *)
  1189 
  1190 
  1190 
  1191 
  1191 
  1192 
  1192 goal thy "Map f`(x@@y) = (Map f`x) @@ (Map f`y)";
  1193 goal thy "Map f`(x@@y) = (Map f`x) @@ (Map f`y)";
  1193 by (res_inst_tac [("A1","%x. True"),("x1","x")] (take_lemma_in_eq_out RS mp) 1);
  1194 by (res_inst_tac [("A1","%x. True"), ("x1","x")]
  1194 by (Auto_tac());
  1195     (take_lemma_in_eq_out RS mp) 1);
       
  1196 by Auto_tac;
  1195 qed"MapConc_takelemma";
  1197 qed"MapConc_takelemma";
  1196 
  1198 
  1197 
  1199