src/HOL/Integ/Bin.ML
changeset 11701 3d51fbf81c17
parent 11655 923e4d0d36d5
child 11704 3c50a2cd6f00
equal deleted inserted replaced
11700:a0e6bda62b7b 11701:3d51fbf81c17
   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 
   337 (** Equals (=) **)
   337 (** Equals (=) **)
   338 
   338 
   339 Goalw [iszero_def]
   339 Goalw [iszero_def]
   340   "((number_of x::int) = number_of y) = \
   340   "((number_of x::int) = number_of y) = \
   341 \  iszero (number_of (bin_add x (bin_minus y)))"; 
   341 \  iszero (number_of (bin_add x (bin_minus y)))"; 
   342 by (simp_tac (simpset() delsimps [number_of_reorient] 
   342 by (simp_tac (simpset() delsimps [thm "number_of_reorient"] 
   343                  addsimps zcompare_rls @ [number_of_add, number_of_minus]) 1); 
   343                  addsimps zcompare_rls @ [number_of_add, number_of_minus]) 1); 
   344 qed "eq_number_of_eq"; 
   344 qed "eq_number_of_eq"; 
   345 
   345 
   346 Goalw [iszero_def] "iszero ((number_of Pls)::int)"; 
   346 Goalw [iszero_def] "iszero ((number_of Pls)::int)"; 
   347 by (Simp_tac 1); 
   347 by (Simp_tac 1);