32 goal Transition.thy |
32 goal Transition.thy |
33 "!s t u c d. (c,s) -n-> (SKIP,t) --> (d,t) -*-> (SKIP,u) --> \ |
33 "!s t u c d. (c,s) -n-> (SKIP,t) --> (d,t) -*-> (SKIP,u) --> \ |
34 \ (c;d, s) -*-> (SKIP, u)"; |
34 \ (c;d, s) -*-> (SKIP, u)"; |
35 by (nat_ind_tac "n" 1); |
35 by (nat_ind_tac "n" 1); |
36 (* case n = 0 *) |
36 (* case n = 0 *) |
37 by (fast_tac (!claset addIs [rtrancl_into_rtrancl2])1); |
37 by (fast_tac (claset() addIs [rtrancl_into_rtrancl2])1); |
38 (* induction step *) |
38 (* induction step *) |
39 by (safe_tac (!claset addSDs [rel_pow_Suc_D2])); |
39 by (safe_tac (claset() addSDs [rel_pow_Suc_D2])); |
40 by (split_all_tac 1); |
40 by (split_all_tac 1); |
41 by (fast_tac (!claset addIs [rtrancl_into_rtrancl2]) 1); |
41 by (fast_tac (claset() addIs [rtrancl_into_rtrancl2]) 1); |
42 qed_spec_mp "lemma1"; |
42 qed_spec_mp "lemma1"; |
43 |
43 |
44 |
44 |
45 goal Transition.thy "!!c s s1. <c,s> -c-> s1 ==> (c,s) -*-> (SKIP,s1)"; |
45 goal Transition.thy "!!c s s1. <c,s> -c-> s1 ==> (c,s) -*-> (SKIP,s1)"; |
46 by (etac evalc.induct 1); |
46 by (etac evalc.induct 1); |
47 |
47 |
48 (* SKIP *) |
48 (* SKIP *) |
49 by (rtac rtrancl_refl 1); |
49 by (rtac rtrancl_refl 1); |
50 |
50 |
51 (* ASSIGN *) |
51 (* ASSIGN *) |
52 by (fast_tac (!claset addSIs [r_into_rtrancl]) 1); |
52 by (fast_tac (claset() addSIs [r_into_rtrancl]) 1); |
53 |
53 |
54 (* SEMI *) |
54 (* SEMI *) |
55 by (fast_tac (!claset addDs [rtrancl_imp_UN_rel_pow] addIs [lemma1]) 1); |
55 by (fast_tac (claset() addDs [rtrancl_imp_UN_rel_pow] addIs [lemma1]) 1); |
56 |
56 |
57 (* IF *) |
57 (* IF *) |
58 by (fast_tac (!claset addIs [rtrancl_into_rtrancl2]) 1); |
58 by (fast_tac (claset() addIs [rtrancl_into_rtrancl2]) 1); |
59 by (fast_tac (!claset addIs [rtrancl_into_rtrancl2]) 1); |
59 by (fast_tac (claset() addIs [rtrancl_into_rtrancl2]) 1); |
60 |
60 |
61 (* WHILE *) |
61 (* WHILE *) |
62 by (fast_tac (!claset addSIs [r_into_rtrancl]) 1); |
62 by (fast_tac (claset() addSIs [r_into_rtrancl]) 1); |
63 by (fast_tac (!claset addDs [rtrancl_imp_UN_rel_pow] |
63 by (fast_tac (claset() addDs [rtrancl_imp_UN_rel_pow] |
64 addIs [rtrancl_into_rtrancl2,lemma1]) 1); |
64 addIs [rtrancl_into_rtrancl2,lemma1]) 1); |
65 |
65 |
66 qed "evalc_impl_evalc1"; |
66 qed "evalc_impl_evalc1"; |
67 |
67 |
68 |
68 |
69 goal Transition.thy |
69 goal Transition.thy |
70 "!c d s u. (c;d,s) -n-> (SKIP,u) --> \ |
70 "!c d s u. (c;d,s) -n-> (SKIP,u) --> \ |
71 \ (? t m. (c,s) -*-> (SKIP,t) & (d,t) -m-> (SKIP,u) & m <= n)"; |
71 \ (? t m. (c,s) -*-> (SKIP,t) & (d,t) -m-> (SKIP,u) & m <= n)"; |
72 by (nat_ind_tac "n" 1); |
72 by (nat_ind_tac "n" 1); |
73 (* case n = 0 *) |
73 (* case n = 0 *) |
74 by (fast_tac (!claset addss !simpset) 1); |
74 by (fast_tac (claset() addss simpset()) 1); |
75 (* induction step *) |
75 (* induction step *) |
76 by (fast_tac (!claset addSIs [le_SucI,le_refl] |
76 by (fast_tac (claset() addSIs [le_SucI,le_refl] |
77 addSDs [rel_pow_Suc_D2] |
77 addSDs [rel_pow_Suc_D2] |
78 addSEs [rel_pow_imp_rtrancl,rtrancl_into_rtrancl2]) 1); |
78 addSEs [rel_pow_imp_rtrancl,rtrancl_into_rtrancl2]) 1); |
79 qed_spec_mp "lemma2"; |
79 qed_spec_mp "lemma2"; |
80 |
80 |
81 goal Transition.thy "!s t. (c,s) -*-> (SKIP,t) --> <c,s> -c-> t"; |
81 goal Transition.thy "!s t. (c,s) -*-> (SKIP,t) --> <c,s> -c-> t"; |
82 by (com.induct_tac "c" 1); |
82 by (com.induct_tac "c" 1); |
83 by (safe_tac (!claset addSDs [rtrancl_imp_UN_rel_pow])); |
83 by (safe_tac (claset() addSDs [rtrancl_imp_UN_rel_pow])); |
84 |
84 |
85 (* SKIP *) |
85 (* SKIP *) |
86 by (fast_tac (!claset addSEs [rel_pow_E2]) 1); |
86 by (fast_tac (claset() addSEs [rel_pow_E2]) 1); |
87 |
87 |
88 (* ASSIGN *) |
88 (* ASSIGN *) |
89 by (fast_tac (!claset addSDs [hlemma] addSEs [rel_pow_E2] |
89 by (fast_tac (claset() addSDs [hlemma] addSEs [rel_pow_E2] |
90 addss !simpset) 1); |
90 addss simpset()) 1); |
91 |
91 |
92 (* SEMI *) |
92 (* SEMI *) |
93 by (fast_tac (!claset addSDs [lemma2,rel_pow_imp_rtrancl]) 1); |
93 by (fast_tac (claset() addSDs [lemma2,rel_pow_imp_rtrancl]) 1); |
94 |
94 |
95 (* IF *) |
95 (* IF *) |
96 by (etac rel_pow_E2 1); |
96 by (etac rel_pow_E2 1); |
97 by (Asm_full_simp_tac 1); |
97 by (Asm_full_simp_tac 1); |
98 by (fast_tac (!claset addSDs [rel_pow_imp_rtrancl]) 1); |
98 by (fast_tac (claset() addSDs [rel_pow_imp_rtrancl]) 1); |
99 |
99 |
100 (* WHILE, induction on the length of the computation *) |
100 (* WHILE, induction on the length of the computation *) |
101 by (rotate_tac 1 1); |
101 by (rotate_tac 1 1); |
102 by (etac rev_mp 1); |
102 by (etac rev_mp 1); |
103 by (res_inst_tac [("x","s")] spec 1); |
103 by (res_inst_tac [("x","s")] spec 1); |
127 |
127 |
128 goal Transition.thy |
128 goal Transition.thy |
129 "!!c1. (c1,s1) -*-> (SKIP,s2) ==> \ |
129 "!!c1. (c1,s1) -*-> (SKIP,s2) ==> \ |
130 \ (c2,s2) -*-> cs3 --> (c1;c2,s1) -*-> cs3"; |
130 \ (c2,s2) -*-> cs3 --> (c1;c2,s1) -*-> cs3"; |
131 by (etac inverse_rtrancl_induct2 1); |
131 by (etac inverse_rtrancl_induct2 1); |
132 by (fast_tac (!claset addIs [rtrancl_into_rtrancl2]) 1); |
132 by (fast_tac (claset() addIs [rtrancl_into_rtrancl2]) 1); |
133 by (fast_tac (!claset addIs [rtrancl_into_rtrancl2]) 1); |
133 by (fast_tac (claset() addIs [rtrancl_into_rtrancl2]) 1); |
134 qed_spec_mp "my_lemma1"; |
134 qed_spec_mp "my_lemma1"; |
135 |
135 |
136 |
136 |
137 goal Transition.thy "!!c s s1. <c,s> -c-> s1 ==> (c,s) -*-> (SKIP,s1)"; |
137 goal Transition.thy "!!c s s1. <c,s> -c-> s1 ==> (c,s) -*-> (SKIP,s1)"; |
138 by (etac evalc.induct 1); |
138 by (etac evalc.induct 1); |
139 |
139 |
140 (* SKIP *) |
140 (* SKIP *) |
141 by (rtac rtrancl_refl 1); |
141 by (rtac rtrancl_refl 1); |
142 |
142 |
143 (* ASSIGN *) |
143 (* ASSIGN *) |
144 by (fast_tac (!claset addSIs [r_into_rtrancl]) 1); |
144 by (fast_tac (claset() addSIs [r_into_rtrancl]) 1); |
145 |
145 |
146 (* SEMI *) |
146 (* SEMI *) |
147 by (fast_tac (!claset addIs [my_lemma1]) 1); |
147 by (fast_tac (claset() addIs [my_lemma1]) 1); |
148 |
148 |
149 (* IF *) |
149 (* IF *) |
150 by (fast_tac (!claset addIs [rtrancl_into_rtrancl2]) 1); |
150 by (fast_tac (claset() addIs [rtrancl_into_rtrancl2]) 1); |
151 by (fast_tac (!claset addIs [rtrancl_into_rtrancl2]) 1); |
151 by (fast_tac (claset() addIs [rtrancl_into_rtrancl2]) 1); |
152 |
152 |
153 (* WHILE *) |
153 (* WHILE *) |
154 by (fast_tac (!claset addSIs [r_into_rtrancl]) 1); |
154 by (fast_tac (claset() addSIs [r_into_rtrancl]) 1); |
155 by (fast_tac (!claset addIs [rtrancl_into_rtrancl2,my_lemma1]) 1); |
155 by (fast_tac (claset() addIs [rtrancl_into_rtrancl2,my_lemma1]) 1); |
156 |
156 |
157 qed "evalc_impl_evalc1"; |
157 qed "evalc_impl_evalc1"; |
158 |
158 |
159 (* The opposite direction is based on a Coq proof done by Ranan Fraer and |
159 (* The opposite direction is based on a Coq proof done by Ranan Fraer and |
160 Yves Bertot. The following sketch is from an email by Ranan Fraer. |
160 Yves Bertot. The following sketch is from an email by Ranan Fraer. |
199 |
199 |
200 val [major] = goal Transition.thy |
200 val [major] = goal Transition.thy |
201 "(c,s) -*-> (c',s') ==> <c',s'> -c-> t --> <c,s> -c-> t"; |
201 "(c,s) -*-> (c',s') ==> <c',s'> -c-> t --> <c,s> -c-> t"; |
202 by (rtac (major RS rtrancl_induct2) 1); |
202 by (rtac (major RS rtrancl_induct2) 1); |
203 by (Fast_tac 1); |
203 by (Fast_tac 1); |
204 by (fast_tac (!claset addIs [FB_lemma3] addbefore split_all_tac) 1); |
204 by (fast_tac (claset() addIs [FB_lemma3] addbefore split_all_tac) 1); |
205 qed_spec_mp "FB_lemma2"; |
205 qed_spec_mp "FB_lemma2"; |
206 |
206 |
207 goal Transition.thy "!!c. (c,s) -*-> (SKIP,t) ==> <c,s> -c-> t"; |
207 goal Transition.thy "!!c. (c,s) -*-> (SKIP,t) ==> <c,s> -c-> t"; |
208 by (fast_tac (!claset addEs [FB_lemma2]) 1); |
208 by (fast_tac (claset() addEs [FB_lemma2]) 1); |
209 qed "evalc1_impl_evalc"; |
209 qed "evalc1_impl_evalc"; |