3 Author: Tobias Nipkow |
3 Author: Tobias Nipkow |
4 Copyright 1998 TU Muenchen |
4 Copyright 1998 TU Muenchen |
5 *) |
5 *) |
6 |
6 |
7 Goalw [step1_def] "step1(r^-1) = (step1 r)^-1"; |
7 Goalw [step1_def] "step1(r^-1) = (step1 r)^-1"; |
8 by(Blast_tac 1); |
8 by (Blast_tac 1); |
9 qed "step1_converse"; |
9 qed "step1_converse"; |
10 Addsimps [step1_converse]; |
10 Addsimps [step1_converse]; |
11 |
11 |
12 Goal "(p : step1(r^-1)) = (p : (step1 r)^-1)"; |
12 Goal "(p : step1(r^-1)) = (p : (step1 r)^-1)"; |
13 by(Auto_tac); |
13 by (Auto_tac); |
14 qed "in_step1_converse"; |
14 qed "in_step1_converse"; |
15 AddIffs [in_step1_converse]; |
15 AddIffs [in_step1_converse]; |
16 |
16 |
17 Goalw [step1_def] "([],xs) ~: step1 r"; |
17 Goalw [step1_def] "([],xs) ~: step1 r"; |
18 by(Blast_tac 1); |
18 by (Blast_tac 1); |
19 qed "not_Nil_step1"; |
19 qed "not_Nil_step1"; |
20 AddIffs [not_Nil_step1]; |
20 AddIffs [not_Nil_step1]; |
21 |
21 |
22 Goalw [step1_def] "(xs,[]) ~: step1 r"; |
22 Goalw [step1_def] "(xs,[]) ~: step1 r"; |
23 by(Blast_tac 1); |
23 by (Blast_tac 1); |
24 qed "not_step1_Nil"; |
24 qed "not_step1_Nil"; |
25 AddIffs [not_step1_Nil]; |
25 AddIffs [not_step1_Nil]; |
26 |
26 |
27 Goalw [step1_def] |
27 Goalw [step1_def] |
28 "((y#ys,x#xs) : step1 r) = ((y,x):r & xs=ys | x=y & (ys,xs) : step1 r)"; |
28 "((y#ys,x#xs) : step1 r) = ((y,x):r & xs=ys | x=y & (ys,xs) : step1 r)"; |
29 by(Asm_full_simp_tac 1); |
29 by (Asm_full_simp_tac 1); |
30 br iffI 1; |
30 by (rtac iffI 1); |
31 be exE 1; |
31 by (etac exE 1); |
32 by(rename_tac "ts" 1); |
32 by (rename_tac "ts" 1); |
33 by(exhaust_tac "ts" 1); |
33 by (exhaust_tac "ts" 1); |
34 by(Force_tac 1); |
34 by (Force_tac 1); |
35 by(Force_tac 1); |
35 by (Force_tac 1); |
36 be disjE 1; |
36 by (etac disjE 1); |
37 by(Blast_tac 1); |
37 by (Blast_tac 1); |
38 by(blast_tac (claset() addIs [Cons_eq_appendI]) 1); |
38 by (blast_tac (claset() addIs [Cons_eq_appendI]) 1); |
39 qed "Cons_step1_Cons"; |
39 qed "Cons_step1_Cons"; |
40 AddIffs [Cons_step1_Cons]; |
40 AddIffs [Cons_step1_Cons]; |
41 |
41 |
42 Goalw [step1_def] |
42 Goalw [step1_def] |
43 "(ys,xs) : step1 r & vs=us | ys=xs & (vs,us) : step1 r \ |
43 "(ys,xs) : step1 r & vs=us | ys=xs & (vs,us) : step1 r \ |
44 \ ==> (ys@vs,xs@us) : step1 r"; |
44 \ ==> (ys@vs,xs@us) : step1 r"; |
45 by(Auto_tac); |
45 by (Auto_tac); |
46 by(Force_tac 1); |
46 by (Force_tac 1); |
47 by(blast_tac (claset() addIs [append_eq_appendI]) 1); |
47 by (blast_tac (claset() addIs [append_eq_appendI]) 1); |
48 qed "append_step1I"; |
48 qed "append_step1I"; |
49 |
49 |
50 Goal "[| (ys,x#xs) : step1 r; \ |
50 Goal "[| (ys,x#xs) : step1 r; \ |
51 \ !y. ys = y#xs --> (y,x) : r --> R; \ |
51 \ !y. ys = y#xs --> (y,x) : r --> R; \ |
52 \ !zs. ys = x#zs --> (zs,xs) : step1 r --> R \ |
52 \ !zs. ys = x#zs --> (zs,xs) : step1 r --> R \ |
53 \ |] ==> R"; |
53 \ |] ==> R"; |
54 by(exhaust_tac "ys" 1); |
54 by (exhaust_tac "ys" 1); |
55 by(asm_full_simp_tac (simpset() addsimps [step1_def]) 1); |
55 by (asm_full_simp_tac (simpset() addsimps [step1_def]) 1); |
56 by(Blast_tac 1); |
56 by (Blast_tac 1); |
57 val lemma = result(); |
57 val lemma = result(); |
58 bind_thm("Cons_step1E", |
58 bind_thm("Cons_step1E", |
59 impI RSN (3,impI RSN (3,allI RSN (3,impI RSN (2, |
59 impI RSN (3,impI RSN (3,allI RSN (3,impI RSN (2, |
60 impI RSN (2,allI RSN (2,lemma))))))); |
60 impI RSN (2,allI RSN (2,lemma))))))); |
61 AddSEs [Cons_step1E]; |
61 AddSEs [Cons_step1E]; |
62 |
62 |
63 Goalw [step1_def] |
63 Goalw [step1_def] |
64 "(ys@[y],xs@[x]) : step1 r ==> ((ys,xs) : step1 r & y=x | ys=xs & (y,x) : r)"; |
64 "(ys@[y],xs@[x]) : step1 r ==> ((ys,xs) : step1 r & y=x | ys=xs & (y,x) : r)"; |
65 by(Asm_full_simp_tac 1); |
65 by (Asm_full_simp_tac 1); |
66 by(clarify_tac (claset() delrules [disjCI]) 1); |
66 by (clarify_tac (claset() delrules [disjCI]) 1); |
67 by(rename_tac "vs" 1); |
67 by (rename_tac "vs" 1); |
68 by(res_inst_tac [("xs","vs")]rev_exhaust 1); |
68 by (res_inst_tac [("xs","vs")]rev_exhaust 1); |
69 by(Force_tac 1); |
69 by (Force_tac 1); |
70 by(Asm_full_simp_tac 1); |
70 by (Asm_full_simp_tac 1); |
71 by(Blast_tac 1); |
71 by (Blast_tac 1); |
72 qed "Snoc_step1_SnocD"; |
72 qed "Snoc_step1_SnocD"; |
73 |
73 |
74 Goal "x : acc r ==> !xs. xs : acc(step1 r) --> x#xs : acc(step1 r)"; |
74 Goal "x : acc r ==> !xs. xs : acc(step1 r) --> x#xs : acc(step1 r)"; |
75 be acc_induct 1; |
75 by (etac acc_induct 1); |
76 be thin_rl 1; |
76 by (etac thin_rl 1); |
77 by(Clarify_tac 1); |
77 by (Clarify_tac 1); |
78 be acc_induct 1; |
78 by (etac acc_induct 1); |
79 br accI 1; |
79 by (rtac accI 1); |
80 by(Blast_tac 1); |
80 by (Blast_tac 1); |
81 val lemma = result(); |
81 val lemma = result(); |
82 qed_spec_mp "Cons_acc_step1I"; |
82 qed_spec_mp "Cons_acc_step1I"; |
83 AddSIs [Cons_acc_step1I]; |
83 AddSIs [Cons_acc_step1I]; |
84 |
84 |
85 Goal "xs : lists(acc r) ==> xs : acc(step1 r)"; |
85 Goal "xs : lists(acc r) ==> xs : acc(step1 r)"; |
86 be lists.induct 1; |
86 be lists.induct 1; |
87 br accI 1; |
87 by (rtac accI 1); |
88 by(asm_full_simp_tac (simpset() addsimps [step1_def]) 1); |
88 by (asm_full_simp_tac (simpset() addsimps [step1_def]) 1); |
89 br accI 1; |
89 by (rtac accI 1); |
90 by(fast_tac (claset() addDs [acc_downward]) 1); |
90 by (fast_tac (claset() addDs [acc_downward]) 1); |
91 qed "lists_accD"; |
91 qed "lists_accD"; |
92 |
92 |
93 Goalw [step1_def] |
93 Goalw [step1_def] |
94 "[| x : set xs; (y,x) : r |] ==> ? ys. (ys,xs) : step1 r & y : set ys"; |
94 "[| x : set xs; (y,x) : r |] ==> ? ys. (ys,xs) : step1 r & y : set ys"; |
95 bd (in_set_conv_decomp RS iffD1) 1; |
95 by (dtac (in_set_conv_decomp RS iffD1) 1); |
96 by(Force_tac 1); |
96 by (Force_tac 1); |
97 qed "ex_step1I"; |
97 qed "ex_step1I"; |
98 |
98 |
99 Goal "xs : acc(step1 r) ==> xs : lists(acc r)"; |
99 Goal "xs : acc(step1 r) ==> xs : lists(acc r)"; |
100 be acc_induct 1; |
100 by (etac acc_induct 1); |
101 by(Clarify_tac 1); |
101 by (Clarify_tac 1); |
102 br accI 1; |
102 by (rtac accI 1); |
103 by(EVERY1[dtac ex_step1I, atac]); |
103 by (EVERY1[dtac ex_step1I, atac]); |
104 by(Blast_tac 1); |
104 by (Blast_tac 1); |
105 qed "lists_accI"; |
105 qed "lists_accI"; |