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 |