158 qed "number_of_mult"; |
158 qed "number_of_mult"; |
159 |
159 |
160 |
160 |
161 (*The correctness of shifting. But it doesn't seem to give a measurable |
161 (*The correctness of shifting. But it doesn't seem to give a measurable |
162 speed-up.*) |
162 speed-up.*) |
163 Goal "(#2::int) * number_of w = number_of (w BIT False)"; |
163 Goal "(# 2::int) * number_of w = number_of (w BIT False)"; |
164 by (induct_tac "w" 1); |
164 by (induct_tac "w" 1); |
165 by (ALLGOALS (asm_simp_tac |
165 by (ALLGOALS (asm_simp_tac |
166 (simpset() addsimps bin_mult_simps @ [zadd_zmult_distrib] @ zadd_ac))); |
166 (simpset() addsimps bin_mult_simps @ [zadd_zmult_distrib] @ zadd_ac))); |
167 qed "double_number_of_BIT"; |
167 qed "double_number_of_BIT"; |
168 |
168 |
169 |
169 |
170 (** Simplification rules with integer constants **) |
170 (** Simplification rules with integer constants **) |
171 |
171 |
172 Goal "#0 + z = (z::int)"; |
172 Goal "Numeral0 + z = (z::int)"; |
173 by (Simp_tac 1); |
173 by (Simp_tac 1); |
174 qed "zadd_0"; |
174 qed "zadd_0"; |
175 |
175 |
176 Goal "z + #0 = (z::int)"; |
176 Goal "z + Numeral0 = (z::int)"; |
177 by (Simp_tac 1); |
177 by (Simp_tac 1); |
178 qed "zadd_0_right"; |
178 qed "zadd_0_right"; |
179 |
179 |
180 Addsimps [zadd_0, zadd_0_right]; |
180 Addsimps [zadd_0, zadd_0_right]; |
181 |
181 |
182 |
182 |
183 (** Converting simple cases of (int n) to numerals **) |
183 (** Converting simple cases of (int n) to numerals **) |
184 |
184 |
185 (*int 0 = #0 *) |
185 (*int 0 = Numeral0 *) |
186 bind_thm ("int_0", number_of_Pls RS sym); |
186 bind_thm ("int_0", number_of_Pls RS sym); |
187 |
187 |
188 Goal "int (Suc n) = #1 + int n"; |
188 Goal "int (Suc n) = Numeral1 + int n"; |
189 by (simp_tac (simpset() addsimps [zadd_int]) 1); |
189 by (simp_tac (simpset() addsimps [zadd_int]) 1); |
190 qed "int_Suc"; |
190 qed "int_Suc"; |
191 |
191 |
192 Goal "- (#0) = (#0::int)"; |
192 Goal "- (Numeral0) = (Numeral0::int)"; |
193 by (Simp_tac 1); |
193 by (Simp_tac 1); |
194 qed "zminus_0"; |
194 qed "zminus_0"; |
195 |
195 |
196 Addsimps [zminus_0]; |
196 Addsimps [zminus_0]; |
197 |
197 |
198 |
198 |
199 Goal "(#0::int) - x = -x"; |
199 Goal "(Numeral0::int) - x = -x"; |
200 by (simp_tac (simpset() addsimps [zdiff_def]) 1); |
200 by (simp_tac (simpset() addsimps [zdiff_def]) 1); |
201 qed "zdiff0"; |
201 qed "zdiff0"; |
202 |
202 |
203 Goal "x - (#0::int) = x"; |
203 Goal "x - (Numeral0::int) = x"; |
204 by (simp_tac (simpset() addsimps [zdiff_def]) 1); |
204 by (simp_tac (simpset() addsimps [zdiff_def]) 1); |
205 qed "zdiff0_right"; |
205 qed "zdiff0_right"; |
206 |
206 |
207 Goal "x - x = (#0::int)"; |
207 Goal "x - x = (Numeral0::int)"; |
208 by (simp_tac (simpset() addsimps [zdiff_def]) 1); |
208 by (simp_tac (simpset() addsimps [zdiff_def]) 1); |
209 qed "zdiff_self"; |
209 qed "zdiff_self"; |
210 |
210 |
211 Addsimps [zdiff0, zdiff0_right, zdiff_self]; |
211 Addsimps [zdiff0, zdiff0_right, zdiff_self]; |
212 |
212 |
232 zmult_zle_cancel1, zmult_zle_cancel2]); |
232 zmult_zle_cancel1, zmult_zle_cancel2]); |
233 |
233 |
234 |
234 |
235 (** Special-case simplification for small constants **) |
235 (** Special-case simplification for small constants **) |
236 |
236 |
237 Goal "#0 * z = (#0::int)"; |
237 Goal "Numeral0 * z = (Numeral0::int)"; |
238 by (Simp_tac 1); |
238 by (Simp_tac 1); |
239 qed "zmult_0"; |
239 qed "zmult_0"; |
240 |
240 |
241 Goal "z * #0 = (#0::int)"; |
241 Goal "z * Numeral0 = (Numeral0::int)"; |
242 by (Simp_tac 1); |
242 by (Simp_tac 1); |
243 qed "zmult_0_right"; |
243 qed "zmult_0_right"; |
244 |
244 |
245 Goal "#1 * z = (z::int)"; |
245 Goal "Numeral1 * z = (z::int)"; |
246 by (Simp_tac 1); |
246 by (Simp_tac 1); |
247 qed "zmult_1"; |
247 qed "zmult_1"; |
248 |
248 |
249 Goal "z * #1 = (z::int)"; |
249 Goal "z * Numeral1 = (z::int)"; |
250 by (Simp_tac 1); |
250 by (Simp_tac 1); |
251 qed "zmult_1_right"; |
251 qed "zmult_1_right"; |
252 |
252 |
253 Goal "#-1 * z = -(z::int)"; |
253 Goal "# -1 * z = -(z::int)"; |
254 by (simp_tac (simpset() addsimps zcompare_rls@[zmult_zminus]) 1); |
254 by (simp_tac (simpset() addsimps zcompare_rls@[zmult_zminus]) 1); |
255 qed "zmult_minus1"; |
255 qed "zmult_minus1"; |
256 |
256 |
257 Goal "z * #-1 = -(z::int)"; |
257 Goal "z * # -1 = -(z::int)"; |
258 by (simp_tac (simpset() addsimps zcompare_rls@[zmult_zminus_right]) 1); |
258 by (simp_tac (simpset() addsimps zcompare_rls@[zmult_zminus_right]) 1); |
259 qed "zmult_minus1_right"; |
259 qed "zmult_minus1_right"; |
260 |
260 |
261 Addsimps [zmult_0, zmult_0_right, |
261 Addsimps [zmult_0, zmult_0_right, |
262 zmult_1, zmult_1_right, |
262 zmult_1, zmult_1_right, |
270 Addsimps [zminus_number_of_zmult]; |
270 Addsimps [zminus_number_of_zmult]; |
271 |
271 |
272 |
272 |
273 (** Inequality reasoning **) |
273 (** Inequality reasoning **) |
274 |
274 |
275 Goal "(m*n = (#0::int)) = (m = #0 | n = #0)"; |
275 Goal "(m*n = (Numeral0::int)) = (m = Numeral0 | n = Numeral0)"; |
276 by (stac (int_0 RS sym) 1 THEN rtac zmult_eq_int0_iff 1); |
276 by (stac (int_0 RS sym) 1 THEN rtac zmult_eq_int0_iff 1); |
277 qed "zmult_eq_0_iff"; |
277 qed "zmult_eq_0_iff"; |
278 AddIffs [zmult_eq_0_iff]; |
278 AddIffs [zmult_eq_0_iff]; |
279 |
279 |
280 Goal "(w < z + (#1::int)) = (w<z | w=z)"; |
280 Goal "(w < z + (Numeral1::int)) = (w<z | w=z)"; |
281 by (simp_tac (simpset() addsimps [zless_add_int_Suc_eq]) 1); |
281 by (simp_tac (simpset() addsimps [zless_add_int_Suc_eq]) 1); |
282 qed "zless_add1_eq"; |
282 qed "zless_add1_eq"; |
283 |
283 |
284 Goal "(w + (#1::int) <= z) = (w<z)"; |
284 Goal "(w + (Numeral1::int) <= z) = (w<z)"; |
285 by (simp_tac (simpset() addsimps [add_int_Suc_zle_eq]) 1); |
285 by (simp_tac (simpset() addsimps [add_int_Suc_zle_eq]) 1); |
286 qed "add1_zle_eq"; |
286 qed "add1_zle_eq"; |
287 |
287 |
288 Goal "((#1::int) + w <= z) = (w<z)"; |
288 Goal "((Numeral1::int) + w <= z) = (w<z)"; |
289 by (stac zadd_commute 1); |
289 by (stac zadd_commute 1); |
290 by (rtac add1_zle_eq 1); |
290 by (rtac add1_zle_eq 1); |
291 qed "add1_left_zle_eq"; |
291 qed "add1_left_zle_eq"; |
292 |
292 |
293 Goal "neg x = (x < #0)"; |
293 Goal "neg x = (x < Numeral0)"; |
294 by (simp_tac (simpset() addsimps [neg_eq_less_int0]) 1); |
294 by (simp_tac (simpset() addsimps [neg_eq_less_int0]) 1); |
295 qed "neg_eq_less_0"; |
295 qed "neg_eq_less_0"; |
296 |
296 |
297 Goal "(~neg x) = (#0 <= x)"; |
297 Goal "(~neg x) = (Numeral0 <= x)"; |
298 by (simp_tac (simpset() addsimps [not_neg_eq_ge_int0]) 1); |
298 by (simp_tac (simpset() addsimps [not_neg_eq_ge_int0]) 1); |
299 qed "not_neg_eq_ge_0"; |
299 qed "not_neg_eq_ge_0"; |
300 |
300 |
301 Goal "#0 <= int m"; |
301 Goal "Numeral0 <= int m"; |
302 by (Simp_tac 1); |
302 by (Simp_tac 1); |
303 qed "zero_zle_int"; |
303 qed "zero_zle_int"; |
304 AddIffs [zero_zle_int]; |
304 AddIffs [zero_zle_int]; |
305 |
305 |
306 |
306 |
307 (** Needed because (int 0) rewrites to #0. |
307 (** Needed because (int 0) rewrites to Numeral0. (* FIXME !? *) |
308 Can these be generalized without evaluating large numbers?**) |
308 Can these be generalized without evaluating large numbers?**) |
309 |
309 |
310 Goal "~ (int k < #0)"; |
310 Goal "~ (int k < Numeral0)"; |
311 by (Simp_tac 1); |
311 by (Simp_tac 1); |
312 qed "int_less_0_conv"; |
312 qed "int_less_0_conv"; |
313 |
313 |
314 Goal "(int k <= #0) = (k=0)"; |
314 Goal "(int k <= Numeral0) = (k=0)"; |
315 by (Simp_tac 1); |
315 by (Simp_tac 1); |
316 qed "int_le_0_conv"; |
316 qed "int_le_0_conv"; |
317 |
317 |
318 Goal "(int k = #0) = (k=0)"; |
318 Goal "(int k = Numeral0) = (k=0)"; |
319 by (Simp_tac 1); |
319 by (Simp_tac 1); |
320 qed "int_eq_0_conv"; |
320 qed "int_eq_0_conv"; |
321 |
321 |
322 Goal "(#0 < int k) = (0<k)"; |
322 Goal "(Numeral0 < int k) = (0<k)"; |
323 by (Simp_tac 1); |
323 by (Simp_tac 1); |
324 qed "zero_less_int_conv"; |
324 qed "zero_less_int_conv"; |
325 |
325 |
326 Addsimps [int_less_0_conv, int_le_0_conv, int_eq_0_conv, zero_less_int_conv]; |
326 Addsimps [int_less_0_conv, int_le_0_conv, int_eq_0_conv, zero_less_int_conv]; |
327 |
327 |
328 Goal "(0 < nat z) = (#0 < z)"; |
328 Goal "(0 < nat z) = (Numeral0 < z)"; |
329 by (cut_inst_tac [("w","#0")] zless_nat_conj 1); |
329 by (cut_inst_tac [("w","Numeral0")] zless_nat_conj 1); |
330 by Auto_tac; |
330 by Auto_tac; |
331 qed "zero_less_nat_eq"; |
331 qed "zero_less_nat_eq"; |
332 Addsimps [zero_less_nat_eq]; |
332 Addsimps [zero_less_nat_eq]; |
333 |
333 |
334 |
334 |