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 *) |
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); |
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"; |
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 |
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 |