equal
deleted
inserted
replaced
26 qed "length_induct"; |
26 qed "length_induct"; |
27 |
27 |
28 |
28 |
29 (** "lists": the list-forming operator over sets **) |
29 (** "lists": the list-forming operator over sets **) |
30 |
30 |
31 Goalw lists.defs "!!A B. A<=B ==> lists A <= lists B"; |
31 Goalw lists.defs "A<=B ==> lists A <= lists B"; |
32 by (rtac lfp_mono 1); |
32 by (rtac lfp_mono 1); |
33 by (REPEAT (ares_tac basic_monos 1)); |
33 by (REPEAT (ares_tac basic_monos 1)); |
34 qed "lists_mono"; |
34 qed "lists_mono"; |
35 |
35 |
36 val listsE = lists.mk_cases list.simps "x#l : lists A"; |
36 val listsE = lists.mk_cases list.simps "x#l : lists A"; |
37 AddSEs [listsE]; |
37 AddSEs [listsE]; |
38 AddSIs lists.intrs; |
38 AddSIs lists.intrs; |
39 |
39 |
40 Goal "!!l. l: lists A ==> l: lists B --> l: lists (A Int B)"; |
40 Goal "l: lists A ==> l: lists B --> l: lists (A Int B)"; |
41 by (etac lists.induct 1); |
41 by (etac lists.induct 1); |
42 by (ALLGOALS Blast_tac); |
42 by (ALLGOALS Blast_tac); |
43 qed_spec_mp "lists_IntI"; |
43 qed_spec_mp "lists_IntI"; |
44 |
44 |
45 Goal "lists (A Int B) = lists A Int lists B"; |
45 Goal "lists (A Int B) = lists A Int lists B"; |
86 by (induct_tac "xs" 1); |
86 by (induct_tac "xs" 1); |
87 by (ALLGOALS Asm_simp_tac); |
87 by (ALLGOALS Asm_simp_tac); |
88 qed "length_rev"; |
88 qed "length_rev"; |
89 Addsimps [length_rev]; |
89 Addsimps [length_rev]; |
90 |
90 |
91 Goal "!!xs. xs ~= [] ==> length(tl xs) = (length xs) - 1"; |
91 Goal "xs ~= [] ==> length(tl xs) = (length xs) - 1"; |
92 by (exhaust_tac "xs" 1); |
92 by (exhaust_tac "xs" 1); |
93 by (ALLGOALS Asm_full_simp_tac); |
93 by (ALLGOALS Asm_full_simp_tac); |
94 qed "length_tl"; |
94 qed "length_tl"; |
95 Addsimps [length_tl]; |
95 Addsimps [length_tl]; |
96 |
96 |
207 Goal "hd(xs@ys) = (if xs=[] then hd ys else hd xs)"; |
207 Goal "hd(xs@ys) = (if xs=[] then hd ys else hd xs)"; |
208 by (induct_tac "xs" 1); |
208 by (induct_tac "xs" 1); |
209 by (ALLGOALS Asm_simp_tac); |
209 by (ALLGOALS Asm_simp_tac); |
210 qed "hd_append"; |
210 qed "hd_append"; |
211 |
211 |
212 Goal "!!xs. xs ~= [] ==> hd(xs @ ys) = hd xs"; |
212 Goal "xs ~= [] ==> hd(xs @ ys) = hd xs"; |
213 by (asm_simp_tac (simpset() addsimps [hd_append] |
213 by (asm_simp_tac (simpset() addsimps [hd_append] |
214 addsplits [split_list_case]) 1); |
214 addsplits [split_list_case]) 1); |
215 qed "hd_append2"; |
215 qed "hd_append2"; |
216 Addsimps [hd_append2]; |
216 Addsimps [hd_append2]; |
217 |
217 |
218 Goal "tl(xs@ys) = (case xs of [] => tl(ys) | z#zs => zs@ys)"; |
218 Goal "tl(xs@ys) = (case xs of [] => tl(ys) | z#zs => zs@ys)"; |
219 by (simp_tac (simpset() addsplits [split_list_case]) 1); |
219 by (simp_tac (simpset() addsplits [split_list_case]) 1); |
220 qed "tl_append"; |
220 qed "tl_append"; |
221 |
221 |
222 Goal "!!xs. xs ~= [] ==> tl(xs @ ys) = (tl xs) @ ys"; |
222 Goal "xs ~= [] ==> tl(xs @ ys) = (tl xs) @ ys"; |
223 by (asm_simp_tac (simpset() addsimps [tl_append] |
223 by (asm_simp_tac (simpset() addsimps [tl_append] |
224 addsplits [split_list_case]) 1); |
224 addsplits [split_list_case]) 1); |
225 qed "tl_append2"; |
225 qed "tl_append2"; |
226 Addsimps [tl_append2]; |
226 Addsimps [tl_append2]; |
227 |
227 |
566 Goal "x:set(butlast xs) --> x:set xs"; |
566 Goal "x:set(butlast xs) --> x:set xs"; |
567 by (induct_tac "xs" 1); |
567 by (induct_tac "xs" 1); |
568 by (ALLGOALS Asm_simp_tac); |
568 by (ALLGOALS Asm_simp_tac); |
569 qed_spec_mp "in_set_butlastD"; |
569 qed_spec_mp "in_set_butlastD"; |
570 |
570 |
571 Goal "!!xs. x:set(butlast xs) ==> x:set(butlast(xs@ys))"; |
571 Goal "x:set(butlast xs) ==> x:set(butlast(xs@ys))"; |
572 by (asm_simp_tac (simpset() addsimps [butlast_append]) 1); |
572 by (asm_simp_tac (simpset() addsimps [butlast_append]) 1); |
573 by (blast_tac (claset() addDs [in_set_butlastD]) 1); |
573 by (blast_tac (claset() addDs [in_set_butlastD]) 1); |
574 qed "in_set_butlast_appendI1"; |
574 qed "in_set_butlast_appendI1"; |
575 |
575 |
576 Goal "!!xs. x:set(butlast ys) ==> x:set(butlast(xs@ys))"; |
576 Goal "x:set(butlast ys) ==> x:set(butlast(xs@ys))"; |
577 by (asm_simp_tac (simpset() addsimps [butlast_append]) 1); |
577 by (asm_simp_tac (simpset() addsimps [butlast_append]) 1); |
578 by (Clarify_tac 1); |
578 by (Clarify_tac 1); |
579 by (Full_simp_tac 1); |
579 by (Full_simp_tac 1); |
580 qed "in_set_butlast_appendI2"; |
580 qed "in_set_butlast_appendI2"; |
581 |
581 |
790 Goal "set(replicate (Suc n) x) = {x}"; |
790 Goal "set(replicate (Suc n) x) = {x}"; |
791 by (induct_tac "n" 1); |
791 by (induct_tac "n" 1); |
792 by (ALLGOALS Asm_full_simp_tac); |
792 by (ALLGOALS Asm_full_simp_tac); |
793 val lemma = result(); |
793 val lemma = result(); |
794 |
794 |
795 Goal "!!n. n ~= 0 ==> set(replicate n x) = {x}"; |
795 Goal "n ~= 0 ==> set(replicate n x) = {x}"; |
796 by (fast_tac (claset() addSDs [not0_implies_Suc] addSIs [lemma]) 1); |
796 by (fast_tac (claset() addSDs [not0_implies_Suc] addSIs [lemma]) 1); |
797 qed "set_replicate"; |
797 qed "set_replicate"; |
798 Addsimps [set_replicate]; |
798 Addsimps [set_replicate]; |