136 bin_add_Bcons_Minus,bin_add_Bcons_Bcons, |
136 bin_add_Bcons_Minus,bin_add_Bcons_Bcons, |
137 integ_of_bin_succ, integ_of_bin_pred, |
137 integ_of_bin_succ, integ_of_bin_pred, |
138 integ_of_bin_norm_Bcons]; |
138 integ_of_bin_norm_Bcons]; |
139 val bin_simps = [iob_Plus,iob_Minus,iob_Bcons]; |
139 val bin_simps = [iob_Plus,iob_Minus,iob_Bcons]; |
140 |
140 |
141 goal Bin.thy |
141 Goal |
142 "! w. integ_of_bin(bin_add v w) = integ_of_bin v + integ_of_bin w"; |
142 "! w. integ_of_bin(bin_add v w) = integ_of_bin v + integ_of_bin w"; |
143 by (bin.induct_tac "v" 1); |
143 by (bin.induct_tac "v" 1); |
144 by (simp_tac (simpset() addsimps bin_add_simps) 1); |
144 by (simp_tac (simpset() addsimps bin_add_simps) 1); |
145 by (simp_tac (simpset() addsimps bin_add_simps) 1); |
145 by (simp_tac (simpset() addsimps bin_add_simps) 1); |
146 by (rtac allI 1); |
146 by (rtac allI 1); |
151 by (etac disjE 1); |
151 by (etac disjE 1); |
152 by (asm_simp_tac (simpset() addsimps (bin_add_simps @ zadd_ac)) 1); |
152 by (asm_simp_tac (simpset() addsimps (bin_add_simps @ zadd_ac)) 1); |
153 by (asm_simp_tac (simpset() addsimps (bin_add_simps @ zadd_ac)) 1); |
153 by (asm_simp_tac (simpset() addsimps (bin_add_simps @ zadd_ac)) 1); |
154 val integ_of_bin_add_lemma = result(); |
154 val integ_of_bin_add_lemma = result(); |
155 |
155 |
156 goal Bin.thy "integ_of_bin(bin_add v w) = integ_of_bin v + integ_of_bin w"; |
156 Goal "integ_of_bin(bin_add v w) = integ_of_bin v + integ_of_bin w"; |
157 by (cut_facts_tac [integ_of_bin_add_lemma] 1); |
157 by (cut_facts_tac [integ_of_bin_add_lemma] 1); |
158 by (Fast_tac 1); |
158 by (Fast_tac 1); |
159 qed "integ_of_bin_add"; |
159 qed "integ_of_bin_add"; |
160 |
160 |
161 val bin_mult_simps = [integ_of_bin_minus, integ_of_bin_add, |
161 val bin_mult_simps = [integ_of_bin_minus, integ_of_bin_add, |
162 integ_of_bin_norm_Bcons]; |
162 integ_of_bin_norm_Bcons]; |
163 |
163 |
164 goal Bin.thy "integ_of_bin(bin_mult v w) = integ_of_bin v * integ_of_bin w"; |
164 Goal "integ_of_bin(bin_mult v w) = integ_of_bin v * integ_of_bin w"; |
165 by (bin.induct_tac "v" 1); |
165 by (bin.induct_tac "v" 1); |
166 by (simp_tac (simpset() addsimps bin_mult_simps) 1); |
166 by (simp_tac (simpset() addsimps bin_mult_simps) 1); |
167 by (simp_tac (simpset() addsimps bin_mult_simps) 1); |
167 by (simp_tac (simpset() addsimps bin_mult_simps) 1); |
168 by (cut_inst_tac [("P","bool")] True_or_False 1); |
168 by (cut_inst_tac [("P","bool")] True_or_False 1); |
169 by (etac disjE 1); |
169 by (etac disjE 1); |
193 |
193 |
194 (** Simplification rules for comparison of binary numbers (Norbert Voelker) **) |
194 (** Simplification rules for comparison of binary numbers (Norbert Voelker) **) |
195 |
195 |
196 Addsimps [zadd_assoc]; |
196 Addsimps [zadd_assoc]; |
197 |
197 |
198 goal Bin.thy |
198 Goal |
199 "(integ_of_bin x = integ_of_bin y) \ |
199 "(integ_of_bin x = integ_of_bin y) \ |
200 \ = (integ_of_bin (bin_add x (bin_minus y)) = $# 0)"; |
200 \ = (integ_of_bin (bin_add x (bin_minus y)) = $# 0)"; |
201 by (simp_tac (HOL_ss addsimps |
201 by (simp_tac (HOL_ss addsimps |
202 [integ_of_bin_add, integ_of_bin_minus,zdiff_def]) 1); |
202 [integ_of_bin_add, integ_of_bin_minus,zdiff_def]) 1); |
203 by (rtac iffI 1); |
203 by (rtac iffI 1); |
207 by (asm_full_simp_tac |
207 by (asm_full_simp_tac |
208 (HOL_ss addsimps[zadd_assoc,zadd_0,zadd_0_right, |
208 (HOL_ss addsimps[zadd_assoc,zadd_0,zadd_0_right, |
209 zadd_zminus_inverse2]) 1); |
209 zadd_zminus_inverse2]) 1); |
210 val iob_eq_eq_diff_0 = result(); |
210 val iob_eq_eq_diff_0 = result(); |
211 |
211 |
212 goal Bin.thy "(integ_of_bin PlusSign = $# 0) = True"; |
212 Goal "(integ_of_bin PlusSign = $# 0) = True"; |
213 by (stac iob_Plus 1); by (Simp_tac 1); |
213 by (stac iob_Plus 1); by (Simp_tac 1); |
214 val iob_Plus_eq_0 = result(); |
214 val iob_Plus_eq_0 = result(); |
215 |
215 |
216 goal Bin.thy "(integ_of_bin MinusSign = $# 0) = False"; |
216 Goal "(integ_of_bin MinusSign = $# 0) = False"; |
217 by (stac iob_Minus 1); |
217 by (stac iob_Minus 1); |
218 by (Simp_tac 1); |
218 by (Simp_tac 1); |
219 val iob_Minus_not_eq_0 = result(); |
219 val iob_Minus_not_eq_0 = result(); |
220 |
220 |
221 goal Bin.thy |
221 Goal |
222 "(integ_of_bin (Bcons w x) = $# 0) = (~x & integ_of_bin w = $# 0)"; |
222 "(integ_of_bin (Bcons w x) = $# 0) = (~x & integ_of_bin w = $# 0)"; |
223 by (stac iob_Bcons 1); |
223 by (stac iob_Bcons 1); |
224 by (case_tac "x" 1); |
224 by (case_tac "x" 1); |
225 by (ALLGOALS Asm_simp_tac); |
225 by (ALLGOALS Asm_simp_tac); |
226 by (ALLGOALS(asm_simp_tac (HOL_ss addsimps [integ_of_bin_add]))); |
226 by (ALLGOALS(asm_simp_tac (HOL_ss addsimps [integ_of_bin_add]))); |
231 by (rtac notI 1); |
231 by (rtac notI 1); |
232 by (dres_inst_tac [("f","(% z. z + $# Suc (Suc (n + n)))")] arg_cong 1); |
232 by (dres_inst_tac [("f","(% z. z + $# Suc (Suc (n + n)))")] arg_cong 1); |
233 by (Asm_full_simp_tac 1); |
233 by (Asm_full_simp_tac 1); |
234 val iob_Bcons_eq_0 = result(); |
234 val iob_Bcons_eq_0 = result(); |
235 |
235 |
236 goalw Bin.thy [zless_def,zdiff_def] |
236 Goalw [zless_def,zdiff_def] |
237 "integ_of_bin x < integ_of_bin y \ |
237 "integ_of_bin x < integ_of_bin y \ |
238 \ = (integ_of_bin (bin_add x (bin_minus y)) < $# 0)"; |
238 \ = (integ_of_bin (bin_add x (bin_minus y)) < $# 0)"; |
239 by (Simp_tac 1); |
239 by (Simp_tac 1); |
240 val iob_less_eq_diff_lt_0 = result(); |
240 val iob_less_eq_diff_lt_0 = result(); |
241 |
241 |
242 goal Bin.thy "(integ_of_bin PlusSign < $# 0) = False"; |
242 Goal "(integ_of_bin PlusSign < $# 0) = False"; |
243 by (stac iob_Plus 1); by (Simp_tac 1); |
243 by (stac iob_Plus 1); by (Simp_tac 1); |
244 val iob_Plus_not_lt_0 = result(); |
244 val iob_Plus_not_lt_0 = result(); |
245 |
245 |
246 goal Bin.thy "(integ_of_bin MinusSign < $# 0) = True"; |
246 Goal "(integ_of_bin MinusSign < $# 0) = True"; |
247 by (stac iob_Minus 1); by (Simp_tac 1); |
247 by (stac iob_Minus 1); by (Simp_tac 1); |
248 val iob_Minus_lt_0 = result(); |
248 val iob_Minus_lt_0 = result(); |
249 |
249 |
250 goal Bin.thy |
250 Goal |
251 "(integ_of_bin (Bcons w x) < $# 0) = (integ_of_bin w < $# 0)"; |
251 "(integ_of_bin (Bcons w x) < $# 0) = (integ_of_bin w < $# 0)"; |
252 by (stac iob_Bcons 1); |
252 by (stac iob_Bcons 1); |
253 by (case_tac "x" 1); |
253 by (case_tac "x" 1); |
254 by (ALLGOALS Asm_simp_tac); |
254 by (ALLGOALS Asm_simp_tac); |
255 by (ALLGOALS(asm_simp_tac (HOL_ss addsimps [integ_of_bin_add]))); |
255 by (ALLGOALS(asm_simp_tac (HOL_ss addsimps [integ_of_bin_add]))); |
260 by (stac (zadd_zminus_inverse RS sym) 1); |
260 by (stac (zadd_zminus_inverse RS sym) 1); |
261 by (rtac zadd_zless_mono1 1); |
261 by (rtac zadd_zless_mono1 1); |
262 by (Simp_tac 1); |
262 by (Simp_tac 1); |
263 val iob_Bcons_lt_0 = result(); |
263 val iob_Bcons_lt_0 = result(); |
264 |
264 |
265 goal Bin.thy |
265 Goal |
266 "integ_of_bin x <= integ_of_bin y \ |
266 "integ_of_bin x <= integ_of_bin y \ |
267 \ = ( integ_of_bin (bin_add x (bin_minus y)) < $# 0 \ |
267 \ = ( integ_of_bin (bin_add x (bin_minus y)) < $# 0 \ |
268 \ | integ_of_bin (bin_add x (bin_minus y)) = $# 0)"; |
268 \ | integ_of_bin (bin_add x (bin_minus y)) = $# 0)"; |
269 by (simp_tac (HOL_ss addsimps |
269 by (simp_tac (HOL_ss addsimps |
270 [zle_eq_zless_or_eq,iob_less_eq_diff_lt_0,zdiff_def |
270 [zle_eq_zless_or_eq,iob_less_eq_diff_lt_0,zdiff_def |
281 iob_Bcons_eq_0, iob_Plus_not_lt_0, iob_Minus_lt_0, iob_Bcons_lt_0]; |
281 iob_Bcons_eq_0, iob_Plus_not_lt_0, iob_Minus_lt_0, iob_Bcons_lt_0]; |
282 |
282 |
283 |
283 |
284 (*** Examples of performing binary arithmetic by simplification ***) |
284 (*** Examples of performing binary arithmetic by simplification ***) |
285 |
285 |
286 goal Bin.thy "#13 + #19 = #32"; |
286 Goal "#13 + #19 = #32"; |
287 by (Simp_tac 1); |
287 by (Simp_tac 1); |
288 result(); |
288 result(); |
289 |
289 |
290 goal Bin.thy "#1234 + #5678 = #6912"; |
290 Goal "#1234 + #5678 = #6912"; |
291 by (Simp_tac 1); |
291 by (Simp_tac 1); |
292 result(); |
292 result(); |
293 |
293 |
294 goal Bin.thy "#1359 + #~2468 = #~1109"; |
294 Goal "#1359 + #~2468 = #~1109"; |
295 by (Simp_tac 1); |
295 by (Simp_tac 1); |
296 result(); |
296 result(); |
297 |
297 |
298 goal Bin.thy "#93746 + #~46375 = #47371"; |
298 Goal "#93746 + #~46375 = #47371"; |
299 by (Simp_tac 1); |
299 by (Simp_tac 1); |
300 result(); |
300 result(); |
301 |
301 |
302 goal Bin.thy "$~ #65745 = #~65745"; |
302 Goal "$~ #65745 = #~65745"; |
303 by (Simp_tac 1); |
303 by (Simp_tac 1); |
304 result(); |
304 result(); |
305 |
305 |
306 goal Bin.thy "$~ #~54321 = #54321"; |
306 Goal "$~ #~54321 = #54321"; |
307 by (Simp_tac 1); |
307 by (Simp_tac 1); |
308 result(); |
308 result(); |
309 |
309 |
310 goal Bin.thy "#13 * #19 = #247"; |
310 Goal "#13 * #19 = #247"; |
311 by (Simp_tac 1); |
311 by (Simp_tac 1); |
312 result(); |
312 result(); |
313 |
313 |
314 goal Bin.thy "#~84 * #51 = #~4284"; |
314 Goal "#~84 * #51 = #~4284"; |
315 by (Simp_tac 1); |
315 by (Simp_tac 1); |
316 result(); |
316 result(); |
317 |
317 |
318 goal Bin.thy "#255 * #255 = #65025"; |
318 Goal "#255 * #255 = #65025"; |
319 by (Simp_tac 1); |
319 by (Simp_tac 1); |
320 result(); |
320 result(); |
321 |
321 |
322 goal Bin.thy "#1359 * #~2468 = #~3354012"; |
322 Goal "#1359 * #~2468 = #~3354012"; |
323 by (Simp_tac 1); |
323 by (Simp_tac 1); |
324 result(); |
324 result(); |
325 |
325 |
326 goal Bin.thy "#89 * #10 ~= #889"; |
326 Goal "#89 * #10 ~= #889"; |
327 by (Simp_tac 1); |
327 by (Simp_tac 1); |
328 result(); |
328 result(); |
329 |
329 |
330 goal Bin.thy "#13 < #18 - #4"; |
330 Goal "#13 < #18 - #4"; |
331 by (Simp_tac 1); |
331 by (Simp_tac 1); |
332 result(); |
332 result(); |
333 |
333 |
334 goal Bin.thy "#~345 < #~242 + #~100"; |
334 Goal "#~345 < #~242 + #~100"; |
335 by (Simp_tac 1); |
335 by (Simp_tac 1); |
336 result(); |
336 result(); |
337 |
337 |
338 goal Bin.thy "#13557456 < #18678654"; |
338 Goal "#13557456 < #18678654"; |
339 by (Simp_tac 1); |
339 by (Simp_tac 1); |
340 result(); |
340 result(); |
341 |
341 |
342 goal Bin.thy "#999999 <= (#1000001 + #1)-#2"; |
342 Goal "#999999 <= (#1000001 + #1)-#2"; |
343 by (Simp_tac 1); |
343 by (Simp_tac 1); |
344 result(); |
344 result(); |
345 |
345 |
346 goal Bin.thy "#1234567 <= #1234567"; |
346 Goal "#1234567 <= #1234567"; |
347 by (Simp_tac 1); |
347 by (Simp_tac 1); |
348 result(); |
348 result(); |