src/HOL/Integ/Bin.ML
changeset 5069 3ea049f7979d
parent 4686 74a12e86b20b
child 5184 9b8547a9496a
equal deleted inserted replaced
5068:fb28eaa07e01 5069:3ea049f7979d
   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();