src/HOL/Num.thy
changeset 54489 03ff4d1e6784
parent 54249 ce00f2fef556
child 55415 05f5fdb8d093
equal deleted inserted replaced
54488:b60f1fab408c 54489:03ff4d1e6784
   273 
   273 
   274 declare numeral_One [code_post]
   274 declare numeral_One [code_post]
   275 
   275 
   276 end
   276 end
   277 
   277 
   278 text {* Negative numerals. *}
       
   279 
       
   280 class neg_numeral = numeral + group_add
       
   281 begin
       
   282 
       
   283 definition neg_numeral :: "num \<Rightarrow> 'a" where
       
   284   "neg_numeral k = - numeral k"
       
   285 
       
   286 end
       
   287 
       
   288 text {* Numeral syntax. *}
   278 text {* Numeral syntax. *}
   289 
   279 
   290 syntax
   280 syntax
   291   "_Numeral" :: "num_const \<Rightarrow> 'a"    ("_")
   281   "_Numeral" :: "num_const \<Rightarrow> 'a"    ("_")
   292 
   282 
   297         (case IntInf.quotRem (n, 2) of
   287         (case IntInf.quotRem (n, 2) of
   298           (0, 1) => Syntax.const @{const_name One}
   288           (0, 1) => Syntax.const @{const_name One}
   299         | (n, 0) => Syntax.const @{const_name Bit0} $ num_of_int n
   289         | (n, 0) => Syntax.const @{const_name Bit0} $ num_of_int n
   300         | (n, 1) => Syntax.const @{const_name Bit1} $ num_of_int n)
   290         | (n, 1) => Syntax.const @{const_name Bit1} $ num_of_int n)
   301       else raise Match
   291       else raise Match
   302     val pos = Syntax.const @{const_name numeral}
   292     val numeral = Syntax.const @{const_name numeral}
   303     val neg = Syntax.const @{const_name neg_numeral}
   293     val uminus = Syntax.const @{const_name uminus}
   304     val one = Syntax.const @{const_name Groups.one}
   294     val one = Syntax.const @{const_name Groups.one}
   305     val zero = Syntax.const @{const_name Groups.zero}
   295     val zero = Syntax.const @{const_name Groups.zero}
   306     fun numeral_tr [(c as Const (@{syntax_const "_constrain"}, _)) $ t $ u] =
   296     fun numeral_tr [(c as Const (@{syntax_const "_constrain"}, _)) $ t $ u] =
   307           c $ numeral_tr [t] $ u
   297           c $ numeral_tr [t] $ u
   308       | numeral_tr [Const (num, _)] =
   298       | numeral_tr [Const (num, _)] =
   309           let
   299           let
   310             val {value, ...} = Lexicon.read_xnum num;
   300             val {value, ...} = Lexicon.read_xnum num;
   311           in
   301           in
   312             if value = 0 then zero else
   302             if value = 0 then zero else
   313             if value > 0
   303             if value > 0
   314             then pos $ num_of_int value
   304             then numeral $ num_of_int value
   315             else neg $ num_of_int (~value)
   305             else if value = ~1 then uminus $ one
       
   306             else uminus $ (numeral $ num_of_int (~value))
   316           end
   307           end
   317       | numeral_tr ts = raise TERM ("numeral_tr", ts);
   308       | numeral_tr ts = raise TERM ("numeral_tr", ts);
   318   in [("_Numeral", K numeral_tr)] end
   309   in [("_Numeral", K numeral_tr)] end
   319 *}
   310 *}
   320 
   311 
   321 typed_print_translation {*
   312 typed_print_translation {*
   322   let
   313   let
   323     fun dest_num (Const (@{const_syntax Bit0}, _) $ n) = 2 * dest_num n
   314     fun dest_num (Const (@{const_syntax Bit0}, _) $ n) = 2 * dest_num n
   324       | dest_num (Const (@{const_syntax Bit1}, _) $ n) = 2 * dest_num n + 1
   315       | dest_num (Const (@{const_syntax Bit1}, _) $ n) = 2 * dest_num n + 1
   325       | dest_num (Const (@{const_syntax One}, _)) = 1;
   316       | dest_num (Const (@{const_syntax One}, _)) = 1;
   326     fun num_tr' sign ctxt T [n] =
   317     fun num_tr' ctxt T [n] =
   327       let
   318       let
   328         val k = dest_num n;
   319         val k = dest_num n;
   329         val t' =
   320         val t' =
   330           Syntax.const @{syntax_const "_Numeral"} $
   321           Syntax.const @{syntax_const "_Numeral"} $
   331             Syntax.free (sign ^ string_of_int k);
   322             Syntax.free (string_of_int k);
   332       in
   323       in
   333         (case T of
   324         (case T of
   334           Type (@{type_name fun}, [_, T']) =>
   325           Type (@{type_name fun}, [_, T']) =>
   335             if Printer.type_emphasis ctxt T' then
   326             if Printer.type_emphasis ctxt T' then
   336               Syntax.const @{syntax_const "_constrain"} $ t' $
   327               Syntax.const @{syntax_const "_constrain"} $ t' $
   337                 Syntax_Phases.term_of_typ ctxt T'
   328                 Syntax_Phases.term_of_typ ctxt T'
   338             else t'
   329             else t'
   339         | _ => if T = dummyT then t' else raise Match)
   330         | _ => if T = dummyT then t' else raise Match)
   340       end;
   331       end;
   341   in
   332   in
   342    [(@{const_syntax numeral}, num_tr' ""),
   333    [(@{const_syntax numeral}, num_tr')]
   343     (@{const_syntax neg_numeral}, num_tr' "-")]
       
   344   end
   334   end
   345 *}
   335 *}
   346 
   336 
   347 ML_file "Tools/numeral.ML"
   337 ML_file "Tools/numeral.ML"
   348 
   338 
   381 
   371 
   382 subsubsection {*
   372 subsubsection {*
   383   Structures with negation: class @{text neg_numeral}
   373   Structures with negation: class @{text neg_numeral}
   384 *}
   374 *}
   385 
   375 
   386 context neg_numeral
   376 class neg_numeral = numeral + group_add
   387 begin
   377 begin
       
   378 
       
   379 lemma uminus_numeral_One:
       
   380   "- Numeral1 = - 1"
       
   381   by (simp add: numeral_One)
   388 
   382 
   389 text {* Numerals form an abelian subgroup. *}
   383 text {* Numerals form an abelian subgroup. *}
   390 
   384 
   391 inductive is_num :: "'a \<Rightarrow> bool" where
   385 inductive is_num :: "'a \<Rightarrow> bool" where
   392   "is_num 1" |
   386   "is_num 1" |
   401   apply (induct x rule: is_num.induct)
   395   apply (induct x rule: is_num.induct)
   402   apply (induct y rule: is_num.induct)
   396   apply (induct y rule: is_num.induct)
   403   apply simp
   397   apply simp
   404   apply (rule_tac a=x in add_left_imp_eq)
   398   apply (rule_tac a=x in add_left_imp_eq)
   405   apply (rule_tac a=x in add_right_imp_eq)
   399   apply (rule_tac a=x in add_right_imp_eq)
   406   apply (simp add: add_assoc minus_add_cancel)
   400   apply (simp add: add_assoc)
   407   apply (simp add: add_assoc [symmetric], simp add: add_assoc)
   401   apply (simp add: add_assoc [symmetric], simp add: add_assoc)
   408   apply (rule_tac a=x in add_left_imp_eq)
   402   apply (rule_tac a=x in add_left_imp_eq)
   409   apply (rule_tac a=x in add_right_imp_eq)
   403   apply (rule_tac a=x in add_right_imp_eq)
   410   apply (simp add: add_assoc)
   404   apply (simp add: add_assoc)
   411   apply (simp add: add_assoc, simp add: add_assoc [symmetric])
   405   apply (simp add: add_assoc, simp add: add_assoc [symmetric])
   429 
   423 
   430 lemma numeral_BitM: "numeral (BitM n) = numeral (Bit0 n) - 1"
   424 lemma numeral_BitM: "numeral (BitM n) = numeral (Bit0 n) - 1"
   431   by (simp only: BitM_plus_one [symmetric] numeral_add numeral_One eq_diff_eq)
   425   by (simp only: BitM_plus_one [symmetric] numeral_add numeral_One eq_diff_eq)
   432 
   426 
   433 lemma dbl_simps [simp]:
   427 lemma dbl_simps [simp]:
   434   "dbl (neg_numeral k) = neg_numeral (Bit0 k)"
   428   "dbl (- numeral k) = - dbl (numeral k)"
   435   "dbl 0 = 0"
   429   "dbl 0 = 0"
   436   "dbl 1 = 2"
   430   "dbl 1 = 2"
       
   431   "dbl (- 1) = - 2"
   437   "dbl (numeral k) = numeral (Bit0 k)"
   432   "dbl (numeral k) = numeral (Bit0 k)"
   438   by (simp_all add: dbl_def neg_numeral_def numeral.simps minus_add)
   433   by (simp_all add: dbl_def numeral.simps minus_add)
   439 
   434 
   440 lemma dbl_inc_simps [simp]:
   435 lemma dbl_inc_simps [simp]:
   441   "dbl_inc (neg_numeral k) = neg_numeral (BitM k)"
   436   "dbl_inc (- numeral k) = - dbl_dec (numeral k)"
   442   "dbl_inc 0 = 1"
   437   "dbl_inc 0 = 1"
   443   "dbl_inc 1 = 3"
   438   "dbl_inc 1 = 3"
       
   439   "dbl_inc (- 1) = - 1"
   444   "dbl_inc (numeral k) = numeral (Bit1 k)"
   440   "dbl_inc (numeral k) = numeral (Bit1 k)"
   445   by (simp_all add: dbl_inc_def neg_numeral_def numeral.simps numeral_BitM is_num_normalize algebra_simps del: add_uminus_conv_diff)
   441   by (simp_all add: dbl_inc_def dbl_dec_def numeral.simps numeral_BitM is_num_normalize algebra_simps del: add_uminus_conv_diff)
   446 
   442 
   447 lemma dbl_dec_simps [simp]:
   443 lemma dbl_dec_simps [simp]:
   448   "dbl_dec (neg_numeral k) = neg_numeral (Bit1 k)"
   444   "dbl_dec (- numeral k) = - dbl_inc (numeral k)"
   449   "dbl_dec 0 = -1"
   445   "dbl_dec 0 = - 1"
   450   "dbl_dec 1 = 1"
   446   "dbl_dec 1 = 1"
       
   447   "dbl_dec (- 1) = - 3"
   451   "dbl_dec (numeral k) = numeral (BitM k)"
   448   "dbl_dec (numeral k) = numeral (BitM k)"
   452   by (simp_all add: dbl_dec_def neg_numeral_def numeral.simps numeral_BitM is_num_normalize)
   449   by (simp_all add: dbl_dec_def dbl_inc_def numeral.simps numeral_BitM is_num_normalize)
   453 
   450 
   454 lemma sub_num_simps [simp]:
   451 lemma sub_num_simps [simp]:
   455   "sub One One = 0"
   452   "sub One One = 0"
   456   "sub One (Bit0 l) = neg_numeral (BitM l)"
   453   "sub One (Bit0 l) = - numeral (BitM l)"
   457   "sub One (Bit1 l) = neg_numeral (Bit0 l)"
   454   "sub One (Bit1 l) = - numeral (Bit0 l)"
   458   "sub (Bit0 k) One = numeral (BitM k)"
   455   "sub (Bit0 k) One = numeral (BitM k)"
   459   "sub (Bit1 k) One = numeral (Bit0 k)"
   456   "sub (Bit1 k) One = numeral (Bit0 k)"
   460   "sub (Bit0 k) (Bit0 l) = dbl (sub k l)"
   457   "sub (Bit0 k) (Bit0 l) = dbl (sub k l)"
   461   "sub (Bit0 k) (Bit1 l) = dbl_dec (sub k l)"
   458   "sub (Bit0 k) (Bit1 l) = dbl_dec (sub k l)"
   462   "sub (Bit1 k) (Bit0 l) = dbl_inc (sub k l)"
   459   "sub (Bit1 k) (Bit0 l) = dbl_inc (sub k l)"
   463   "sub (Bit1 k) (Bit1 l) = dbl (sub k l)"
   460   "sub (Bit1 k) (Bit1 l) = dbl (sub k l)"
   464   by (simp_all add: dbl_def dbl_dec_def dbl_inc_def sub_def neg_numeral_def numeral.simps
   461   by (simp_all add: dbl_def dbl_dec_def dbl_inc_def sub_def numeral.simps
   465     numeral_BitM is_num_normalize del: add_uminus_conv_diff add: diff_conv_add_uminus)
   462     numeral_BitM is_num_normalize del: add_uminus_conv_diff add: diff_conv_add_uminus)
   466 
   463 
   467 lemma add_neg_numeral_simps:
   464 lemma add_neg_numeral_simps:
   468   "numeral m + neg_numeral n = sub m n"
   465   "numeral m + - numeral n = sub m n"
   469   "neg_numeral m + numeral n = sub n m"
   466   "- numeral m + numeral n = sub n m"
   470   "neg_numeral m + neg_numeral n = neg_numeral (m + n)"
   467   "- numeral m + - numeral n = - (numeral m + numeral n)"
   471   by (simp_all add: sub_def neg_numeral_def numeral_add numeral.simps is_num_normalize
   468   by (simp_all add: sub_def numeral_add numeral.simps is_num_normalize
   472     del: add_uminus_conv_diff add: diff_conv_add_uminus)
   469     del: add_uminus_conv_diff add: diff_conv_add_uminus)
   473 
   470 
   474 lemma add_neg_numeral_special:
   471 lemma add_neg_numeral_special:
   475   "1 + neg_numeral m = sub One m"
   472   "1 + - numeral m = sub One m"
   476   "neg_numeral m + 1 = sub One m"
   473   "- numeral m + 1 = sub One m"
   477   by (simp_all add: sub_def neg_numeral_def numeral_add numeral.simps is_num_normalize)
   474   "numeral m + - 1 = sub m One"
       
   475   "- 1 + numeral n = sub n One"
       
   476   "- 1 + - numeral n = - numeral (inc n)"
       
   477   "- numeral m + - 1 = - numeral (inc m)"
       
   478   "1 + - 1 = 0"
       
   479   "- 1 + 1 = 0"
       
   480   "- 1 + - 1 = - 2"
       
   481   by (simp_all add: sub_def numeral_add numeral.simps is_num_normalize right_minus numeral_inc
       
   482     del: add_uminus_conv_diff add: diff_conv_add_uminus)
   478 
   483 
   479 lemma diff_numeral_simps:
   484 lemma diff_numeral_simps:
   480   "numeral m - numeral n = sub m n"
   485   "numeral m - numeral n = sub m n"
   481   "numeral m - neg_numeral n = numeral (m + n)"
   486   "numeral m - - numeral n = numeral (m + n)"
   482   "neg_numeral m - numeral n = neg_numeral (m + n)"
   487   "- numeral m - numeral n = - numeral (m + n)"
   483   "neg_numeral m - neg_numeral n = sub n m"
   488   "- numeral m - - numeral n = sub n m"
   484   by (simp_all add: neg_numeral_def sub_def numeral_add numeral.simps is_num_normalize
   489   by (simp_all add: sub_def numeral_add numeral.simps is_num_normalize
   485     del: add_uminus_conv_diff add: diff_conv_add_uminus)
   490     del: add_uminus_conv_diff add: diff_conv_add_uminus)
   486 
   491 
   487 lemma diff_numeral_special:
   492 lemma diff_numeral_special:
   488   "1 - numeral n = sub One n"
   493   "1 - numeral n = sub One n"
   489   "1 - neg_numeral n = numeral (One + n)"
       
   490   "numeral m - 1 = sub m One"
   494   "numeral m - 1 = sub m One"
   491   "neg_numeral m - 1 = neg_numeral (m + One)"
   495   "1 - - numeral n = numeral (One + n)"
   492   by (simp_all add: neg_numeral_def sub_def numeral_add numeral.simps add: is_num_normalize)
   496   "- numeral m - 1 = - numeral (m + One)"
   493 
   497   "- 1 - numeral n = - numeral (inc n)"
   494 lemma minus_one: "- 1 = -1"
   498   "numeral m - - 1 = numeral (inc m)"
   495   unfolding neg_numeral_def numeral.simps ..
   499   "- 1 - - numeral n = sub n One"
   496 
   500   "- numeral m - - 1 = sub One m"
   497 lemma minus_numeral: "- numeral n = neg_numeral n"
   501   "1 - 1 = 0"
   498   unfolding neg_numeral_def ..
   502   "- 1 - 1 = - 2"
   499 
   503   "1 - - 1 = 2"
   500 lemma minus_neg_numeral: "- neg_numeral n = numeral n"
   504   "- 1 - - 1 = 0"
   501   unfolding neg_numeral_def by simp
   505   by (simp_all add: sub_def numeral_add numeral.simps is_num_normalize numeral_inc
   502 
   506     del: add_uminus_conv_diff add: diff_conv_add_uminus)
   503 lemmas minus_numeral_simps [simp] =
       
   504   minus_one minus_numeral minus_neg_numeral
       
   505 
   507 
   506 end
   508 end
   507 
   509 
   508 subsubsection {*
   510 subsubsection {*
   509   Structures with multiplication: class @{text semiring_numeral}
   511   Structures with multiplication: class @{text semiring_numeral}
   673 begin
   675 begin
   674 
   676 
   675 subclass neg_numeral ..
   677 subclass neg_numeral ..
   676 
   678 
   677 lemma mult_neg_numeral_simps:
   679 lemma mult_neg_numeral_simps:
   678   "neg_numeral m * neg_numeral n = numeral (m * n)"
   680   "- numeral m * - numeral n = numeral (m * n)"
   679   "neg_numeral m * numeral n = neg_numeral (m * n)"
   681   "- numeral m * numeral n = - numeral (m * n)"
   680   "numeral m * neg_numeral n = neg_numeral (m * n)"
   682   "numeral m * - numeral n = - numeral (m * n)"
   681   unfolding neg_numeral_def mult_minus_left mult_minus_right
   683   unfolding mult_minus_left mult_minus_right
   682   by (simp_all only: minus_minus numeral_mult)
   684   by (simp_all only: minus_minus numeral_mult)
   683 
   685 
   684 lemma mult_minus1 [simp]: "-1 * z = - z"
   686 lemma mult_minus1 [simp]: "- 1 * z = - z"
   685   unfolding neg_numeral_def numeral.simps mult_minus_left by simp
   687   unfolding numeral.simps mult_minus_left by simp
   686 
   688 
   687 lemma mult_minus1_right [simp]: "z * -1 = - z"
   689 lemma mult_minus1_right [simp]: "z * - 1 = - z"
   688   unfolding neg_numeral_def numeral.simps mult_minus_right by simp
   690   unfolding numeral.simps mult_minus_right by simp
   689 
   691 
   690 end
   692 end
   691 
   693 
   692 subsubsection {*
   694 subsubsection {*
   693   Equality using @{text iszero} for rings with non-zero characteristic
   695   Equality using @{text iszero} for rings with non-zero characteristic
   706   by (simp add: iszero_def)
   708   by (simp add: iszero_def)
   707 
   709 
   708 lemma not_iszero_Numeral1: "\<not> iszero Numeral1"
   710 lemma not_iszero_Numeral1: "\<not> iszero Numeral1"
   709   by (simp add: numeral_One)
   711   by (simp add: numeral_One)
   710 
   712 
       
   713 lemma not_iszero_neg_1 [simp]: "\<not> iszero (- 1)"
       
   714   by (simp add: iszero_def)
       
   715 
       
   716 lemma not_iszero_neg_Numeral1: "\<not> iszero (- Numeral1)"
       
   717   by (simp add: numeral_One)
       
   718 
   711 lemma iszero_neg_numeral [simp]:
   719 lemma iszero_neg_numeral [simp]:
   712   "iszero (neg_numeral w) \<longleftrightarrow> iszero (numeral w)"
   720   "iszero (- numeral w) \<longleftrightarrow> iszero (numeral w)"
   713   unfolding iszero_def neg_numeral_def
   721   unfolding iszero_def
   714   by (rule neg_equal_0_iff_equal)
   722   by (rule neg_equal_0_iff_equal)
   715 
   723 
   716 lemma eq_iff_iszero_diff: "x = y \<longleftrightarrow> iszero (x - y)"
   724 lemma eq_iff_iszero_diff: "x = y \<longleftrightarrow> iszero (x - y)"
   717   unfolding iszero_def by (rule eq_iff_diff_eq_0)
   725   unfolding iszero_def by (rule eq_iff_diff_eq_0)
   718 
   726 
   728 the @{text "ring_char_0"} rules in the simplifier.
   736 the @{text "ring_char_0"} rules in the simplifier.
   729 *}
   737 *}
   730 
   738 
   731 lemma eq_numeral_iff_iszero:
   739 lemma eq_numeral_iff_iszero:
   732   "numeral x = numeral y \<longleftrightarrow> iszero (sub x y)"
   740   "numeral x = numeral y \<longleftrightarrow> iszero (sub x y)"
   733   "numeral x = neg_numeral y \<longleftrightarrow> iszero (numeral (x + y))"
   741   "numeral x = - numeral y \<longleftrightarrow> iszero (numeral (x + y))"
   734   "neg_numeral x = numeral y \<longleftrightarrow> iszero (numeral (x + y))"
   742   "- numeral x = numeral y \<longleftrightarrow> iszero (numeral (x + y))"
   735   "neg_numeral x = neg_numeral y \<longleftrightarrow> iszero (sub y x)"
   743   "- numeral x = - numeral y \<longleftrightarrow> iszero (sub y x)"
   736   "numeral x = 1 \<longleftrightarrow> iszero (sub x One)"
   744   "numeral x = 1 \<longleftrightarrow> iszero (sub x One)"
   737   "1 = numeral y \<longleftrightarrow> iszero (sub One y)"
   745   "1 = numeral y \<longleftrightarrow> iszero (sub One y)"
   738   "neg_numeral x = 1 \<longleftrightarrow> iszero (numeral (x + One))"
   746   "- numeral x = 1 \<longleftrightarrow> iszero (numeral (x + One))"
   739   "1 = neg_numeral y \<longleftrightarrow> iszero (numeral (One + y))"
   747   "1 = - numeral y \<longleftrightarrow> iszero (numeral (One + y))"
   740   "numeral x = 0 \<longleftrightarrow> iszero (numeral x)"
   748   "numeral x = 0 \<longleftrightarrow> iszero (numeral x)"
   741   "0 = numeral y \<longleftrightarrow> iszero (numeral y)"
   749   "0 = numeral y \<longleftrightarrow> iszero (numeral y)"
   742   "neg_numeral x = 0 \<longleftrightarrow> iszero (numeral x)"
   750   "- numeral x = 0 \<longleftrightarrow> iszero (numeral x)"
   743   "0 = neg_numeral y \<longleftrightarrow> iszero (numeral y)"
   751   "0 = - numeral y \<longleftrightarrow> iszero (numeral y)"
   744   unfolding eq_iff_iszero_diff diff_numeral_simps diff_numeral_special
   752   unfolding eq_iff_iszero_diff diff_numeral_simps diff_numeral_special
   745   by simp_all
   753   by simp_all
   746 
   754 
   747 end
   755 end
   748 
   756 
   754 begin
   762 begin
   755 
   763 
   756 lemma not_iszero_numeral [simp]: "\<not> iszero (numeral w)"
   764 lemma not_iszero_numeral [simp]: "\<not> iszero (numeral w)"
   757   by (simp add: iszero_def)
   765   by (simp add: iszero_def)
   758 
   766 
   759 lemma neg_numeral_eq_iff: "neg_numeral m = neg_numeral n \<longleftrightarrow> m = n"
   767 lemma neg_numeral_eq_iff: "- numeral m = - numeral n \<longleftrightarrow> m = n"
   760   by (simp only: neg_numeral_def neg_equal_iff_equal numeral_eq_iff)
   768   by simp
   761 
   769 
   762 lemma numeral_neq_neg_numeral: "numeral m \<noteq> neg_numeral n"
   770 lemma numeral_neq_neg_numeral: "numeral m \<noteq> - numeral n"
   763   unfolding neg_numeral_def eq_neg_iff_add_eq_0
   771   unfolding eq_neg_iff_add_eq_0
   764   by (simp add: numeral_plus_numeral)
   772   by (simp add: numeral_plus_numeral)
   765 
   773 
   766 lemma neg_numeral_neq_numeral: "neg_numeral m \<noteq> numeral n"
   774 lemma neg_numeral_neq_numeral: "- numeral m \<noteq> numeral n"
   767   by (rule numeral_neq_neg_numeral [symmetric])
   775   by (rule numeral_neq_neg_numeral [symmetric])
   768 
   776 
   769 lemma zero_neq_neg_numeral: "0 \<noteq> neg_numeral n"
   777 lemma zero_neq_neg_numeral: "0 \<noteq> - numeral n"
   770   unfolding neg_numeral_def neg_0_equal_iff_equal by simp
   778   unfolding neg_0_equal_iff_equal by simp
   771 
   779 
   772 lemma neg_numeral_neq_zero: "neg_numeral n \<noteq> 0"
   780 lemma neg_numeral_neq_zero: "- numeral n \<noteq> 0"
   773   unfolding neg_numeral_def neg_equal_0_iff_equal by simp
   781   unfolding neg_equal_0_iff_equal by simp
   774 
   782 
   775 lemma one_neq_neg_numeral: "1 \<noteq> neg_numeral n"
   783 lemma one_neq_neg_numeral: "1 \<noteq> - numeral n"
   776   using numeral_neq_neg_numeral [of One n] by (simp add: numeral_One)
   784   using numeral_neq_neg_numeral [of One n] by (simp add: numeral_One)
   777 
   785 
   778 lemma neg_numeral_neq_one: "neg_numeral n \<noteq> 1"
   786 lemma neg_numeral_neq_one: "- numeral n \<noteq> 1"
   779   using neg_numeral_neq_numeral [of n One] by (simp add: numeral_One)
   787   using neg_numeral_neq_numeral [of n One] by (simp add: numeral_One)
       
   788 
       
   789 lemma neg_one_neq_numeral:
       
   790   "- 1 \<noteq> numeral n"
       
   791   using neg_numeral_neq_numeral [of One n] by (simp add: numeral_One)
       
   792 
       
   793 lemma numeral_neq_neg_one:
       
   794   "numeral n \<noteq> - 1"
       
   795   using numeral_neq_neg_numeral [of n One] by (simp add: numeral_One)
       
   796 
       
   797 lemma neg_one_eq_numeral_iff:
       
   798   "- 1 = - numeral n \<longleftrightarrow> n = One"
       
   799   using neg_numeral_eq_iff [of One n] by (auto simp add: numeral_One)
       
   800 
       
   801 lemma numeral_eq_neg_one_iff:
       
   802   "- numeral n = - 1 \<longleftrightarrow> n = One"
       
   803   using neg_numeral_eq_iff [of n One] by (auto simp add: numeral_One)
       
   804 
       
   805 lemma neg_one_neq_zero:
       
   806   "- 1 \<noteq> 0"
       
   807   by simp
       
   808 
       
   809 lemma zero_neq_neg_one:
       
   810   "0 \<noteq> - 1"
       
   811   by simp
       
   812 
       
   813 lemma neg_one_neq_one:
       
   814   "- 1 \<noteq> 1"
       
   815   using neg_numeral_neq_numeral [of One One] by (simp only: numeral_One not_False_eq_True)
       
   816 
       
   817 lemma one_neq_neg_one:
       
   818   "1 \<noteq> - 1"
       
   819   using numeral_neq_neg_numeral [of One One] by (simp only: numeral_One not_False_eq_True)
   780 
   820 
   781 lemmas eq_neg_numeral_simps [simp] =
   821 lemmas eq_neg_numeral_simps [simp] =
   782   neg_numeral_eq_iff
   822   neg_numeral_eq_iff
   783   numeral_neq_neg_numeral neg_numeral_neq_numeral
   823   numeral_neq_neg_numeral neg_numeral_neq_numeral
   784   one_neq_neg_numeral neg_numeral_neq_one
   824   one_neq_neg_numeral neg_numeral_neq_one
   785   zero_neq_neg_numeral neg_numeral_neq_zero
   825   zero_neq_neg_numeral neg_numeral_neq_zero
       
   826   neg_one_neq_numeral numeral_neq_neg_one
       
   827   neg_one_eq_numeral_iff numeral_eq_neg_one_iff
       
   828   neg_one_neq_zero zero_neq_neg_one
       
   829   neg_one_neq_one one_neq_neg_one
   786 
   830 
   787 end
   831 end
   788 
   832 
   789 subsubsection {*
   833 subsubsection {*
   790   Structures with negation and order: class @{text linordered_idom}
   834   Structures with negation and order: class @{text linordered_idom}
   793 context linordered_idom
   837 context linordered_idom
   794 begin
   838 begin
   795 
   839 
   796 subclass ring_char_0 ..
   840 subclass ring_char_0 ..
   797 
   841 
   798 lemma neg_numeral_le_iff: "neg_numeral m \<le> neg_numeral n \<longleftrightarrow> n \<le> m"
   842 lemma neg_numeral_le_iff: "- numeral m \<le> - numeral n \<longleftrightarrow> n \<le> m"
   799   by (simp only: neg_numeral_def neg_le_iff_le numeral_le_iff)
   843   by (simp only: neg_le_iff_le numeral_le_iff)
   800 
   844 
   801 lemma neg_numeral_less_iff: "neg_numeral m < neg_numeral n \<longleftrightarrow> n < m"
   845 lemma neg_numeral_less_iff: "- numeral m < - numeral n \<longleftrightarrow> n < m"
   802   by (simp only: neg_numeral_def neg_less_iff_less numeral_less_iff)
   846   by (simp only: neg_less_iff_less numeral_less_iff)
   803 
   847 
   804 lemma neg_numeral_less_zero: "neg_numeral n < 0"
   848 lemma neg_numeral_less_zero: "- numeral n < 0"
   805   by (simp only: neg_numeral_def neg_less_0_iff_less zero_less_numeral)
   849   by (simp only: neg_less_0_iff_less zero_less_numeral)
   806 
   850 
   807 lemma neg_numeral_le_zero: "neg_numeral n \<le> 0"
   851 lemma neg_numeral_le_zero: "- numeral n \<le> 0"
   808   by (simp only: neg_numeral_def neg_le_0_iff_le zero_le_numeral)
   852   by (simp only: neg_le_0_iff_le zero_le_numeral)
   809 
   853 
   810 lemma not_zero_less_neg_numeral: "\<not> 0 < neg_numeral n"
   854 lemma not_zero_less_neg_numeral: "\<not> 0 < - numeral n"
   811   by (simp only: not_less neg_numeral_le_zero)
   855   by (simp only: not_less neg_numeral_le_zero)
   812 
   856 
   813 lemma not_zero_le_neg_numeral: "\<not> 0 \<le> neg_numeral n"
   857 lemma not_zero_le_neg_numeral: "\<not> 0 \<le> - numeral n"
   814   by (simp only: not_le neg_numeral_less_zero)
   858   by (simp only: not_le neg_numeral_less_zero)
   815 
   859 
   816 lemma neg_numeral_less_numeral: "neg_numeral m < numeral n"
   860 lemma neg_numeral_less_numeral: "- numeral m < numeral n"
   817   using neg_numeral_less_zero zero_less_numeral by (rule less_trans)
   861   using neg_numeral_less_zero zero_less_numeral by (rule less_trans)
   818 
   862 
   819 lemma neg_numeral_le_numeral: "neg_numeral m \<le> numeral n"
   863 lemma neg_numeral_le_numeral: "- numeral m \<le> numeral n"
   820   by (simp only: less_imp_le neg_numeral_less_numeral)
   864   by (simp only: less_imp_le neg_numeral_less_numeral)
   821 
   865 
   822 lemma not_numeral_less_neg_numeral: "\<not> numeral m < neg_numeral n"
   866 lemma not_numeral_less_neg_numeral: "\<not> numeral m < - numeral n"
   823   by (simp only: not_less neg_numeral_le_numeral)
   867   by (simp only: not_less neg_numeral_le_numeral)
   824 
   868 
   825 lemma not_numeral_le_neg_numeral: "\<not> numeral m \<le> neg_numeral n"
   869 lemma not_numeral_le_neg_numeral: "\<not> numeral m \<le> - numeral n"
   826   by (simp only: not_le neg_numeral_less_numeral)
   870   by (simp only: not_le neg_numeral_less_numeral)
   827   
   871   
   828 lemma neg_numeral_less_one: "neg_numeral m < 1"
   872 lemma neg_numeral_less_one: "- numeral m < 1"
   829   by (rule neg_numeral_less_numeral [of m One, unfolded numeral_One])
   873   by (rule neg_numeral_less_numeral [of m One, unfolded numeral_One])
   830 
   874 
   831 lemma neg_numeral_le_one: "neg_numeral m \<le> 1"
   875 lemma neg_numeral_le_one: "- numeral m \<le> 1"
   832   by (rule neg_numeral_le_numeral [of m One, unfolded numeral_One])
   876   by (rule neg_numeral_le_numeral [of m One, unfolded numeral_One])
   833 
   877 
   834 lemma not_one_less_neg_numeral: "\<not> 1 < neg_numeral m"
   878 lemma not_one_less_neg_numeral: "\<not> 1 < - numeral m"
   835   by (simp only: not_less neg_numeral_le_one)
   879   by (simp only: not_less neg_numeral_le_one)
   836 
   880 
   837 lemma not_one_le_neg_numeral: "\<not> 1 \<le> neg_numeral m"
   881 lemma not_one_le_neg_numeral: "\<not> 1 \<le> - numeral m"
   838   by (simp only: not_le neg_numeral_less_one)
   882   by (simp only: not_le neg_numeral_less_one)
       
   883 
       
   884 lemma not_numeral_less_neg_one: "\<not> numeral m < - 1"
       
   885   using not_numeral_less_neg_numeral [of m One] by (simp add: numeral_One)
       
   886 
       
   887 lemma not_numeral_le_neg_one: "\<not> numeral m \<le> - 1"
       
   888   using not_numeral_le_neg_numeral [of m One] by (simp add: numeral_One)
       
   889 
       
   890 lemma neg_one_less_numeral: "- 1 < numeral m"
       
   891   using neg_numeral_less_numeral [of One m] by (simp add: numeral_One)
       
   892 
       
   893 lemma neg_one_le_numeral: "- 1 \<le> numeral m"
       
   894   using neg_numeral_le_numeral [of One m] by (simp add: numeral_One)
       
   895 
       
   896 lemma neg_numeral_less_neg_one_iff: "- numeral m < - 1 \<longleftrightarrow> m \<noteq> One"
       
   897   by (cases m) simp_all
       
   898 
       
   899 lemma neg_numeral_le_neg_one: "- numeral m \<le> - 1"
       
   900   by simp
       
   901 
       
   902 lemma not_neg_one_less_neg_numeral: "\<not> - 1 < - numeral m"
       
   903   by simp
       
   904 
       
   905 lemma not_neg_one_le_neg_numeral_iff: "\<not> - 1 \<le> - numeral m \<longleftrightarrow> m \<noteq> One"
       
   906   by (cases m) simp_all
   839 
   907 
   840 lemma sub_non_negative:
   908 lemma sub_non_negative:
   841   "sub n m \<ge> 0 \<longleftrightarrow> n \<ge> m"
   909   "sub n m \<ge> 0 \<longleftrightarrow> n \<ge> m"
   842   by (simp only: sub_def le_diff_eq) simp
   910   by (simp only: sub_def le_diff_eq) simp
   843 
   911 
   856 lemmas le_neg_numeral_simps [simp] =
   924 lemmas le_neg_numeral_simps [simp] =
   857   neg_numeral_le_iff
   925   neg_numeral_le_iff
   858   neg_numeral_le_numeral not_numeral_le_neg_numeral
   926   neg_numeral_le_numeral not_numeral_le_neg_numeral
   859   neg_numeral_le_zero not_zero_le_neg_numeral
   927   neg_numeral_le_zero not_zero_le_neg_numeral
   860   neg_numeral_le_one not_one_le_neg_numeral
   928   neg_numeral_le_one not_one_le_neg_numeral
       
   929   neg_one_le_numeral not_numeral_le_neg_one
       
   930   neg_numeral_le_neg_one not_neg_one_le_neg_numeral_iff
       
   931 
       
   932 lemma le_minus_one_simps [simp]:
       
   933   "- 1 \<le> 0"
       
   934   "- 1 \<le> 1"
       
   935   "\<not> 0 \<le> - 1"
       
   936   "\<not> 1 \<le> - 1"
       
   937   by simp_all
   861 
   938 
   862 lemmas less_neg_numeral_simps [simp] =
   939 lemmas less_neg_numeral_simps [simp] =
   863   neg_numeral_less_iff
   940   neg_numeral_less_iff
   864   neg_numeral_less_numeral not_numeral_less_neg_numeral
   941   neg_numeral_less_numeral not_numeral_less_neg_numeral
   865   neg_numeral_less_zero not_zero_less_neg_numeral
   942   neg_numeral_less_zero not_zero_less_neg_numeral
   866   neg_numeral_less_one not_one_less_neg_numeral
   943   neg_numeral_less_one not_one_less_neg_numeral
       
   944   neg_one_less_numeral not_numeral_less_neg_one
       
   945   neg_numeral_less_neg_one_iff not_neg_one_less_neg_numeral
       
   946 
       
   947 lemma less_minus_one_simps [simp]:
       
   948   "- 1 < 0"
       
   949   "- 1 < 1"
       
   950   "\<not> 0 < - 1"
       
   951   "\<not> 1 < - 1"
       
   952   by (simp_all add: less_le)
   867 
   953 
   868 lemma abs_numeral [simp]: "abs (numeral n) = numeral n"
   954 lemma abs_numeral [simp]: "abs (numeral n) = numeral n"
   869   by simp
   955   by simp
   870 
   956 
   871 lemma abs_neg_numeral [simp]: "abs (neg_numeral n) = numeral n"
   957 lemma abs_neg_numeral [simp]: "abs (- numeral n) = numeral n"
   872   by (simp only: neg_numeral_def abs_minus_cancel abs_numeral)
   958   by (simp only: abs_minus_cancel abs_numeral)
       
   959 
       
   960 lemma abs_neg_one [simp]:
       
   961   "abs (- 1) = 1"
       
   962   by simp
   873 
   963 
   874 end
   964 end
   875 
   965 
   876 subsubsection {*
   966 subsubsection {*
   877   Natural numbers
   967   Natural numbers
  1030   by simp
  1120   by simp
  1031 
  1121 
  1032 text{*Theorem lists for the cancellation simprocs. The use of a binary
  1122 text{*Theorem lists for the cancellation simprocs. The use of a binary
  1033 numeral for 1 reduces the number of special cases.*}
  1123 numeral for 1 reduces the number of special cases.*}
  1034 
  1124 
  1035 lemmas mult_1s =
  1125 lemma mult_1s:
  1036   mult_numeral_1 mult_numeral_1_right 
  1126   fixes a :: "'a::semiring_numeral"
  1037   mult_minus1 mult_minus1_right
  1127     and b :: "'b::ring_1"
       
  1128   shows "Numeral1 * a = a"
       
  1129     "a * Numeral1 = a"
       
  1130     "- Numeral1 * b = - b"
       
  1131     "b * - Numeral1 = - b"
       
  1132   by simp_all
  1038 
  1133 
  1039 setup {*
  1134 setup {*
  1040   Reorient_Proc.add
  1135   Reorient_Proc.add
  1041     (fn Const (@{const_name numeral}, _) $ _ => true
  1136     (fn Const (@{const_name numeral}, _) $ _ => true
  1042     | Const (@{const_name neg_numeral}, _) $ _ => true
  1137     | Const (@{const_name uminus}, _) $ (Const (@{const_name numeral}, _) $ _) => true
  1043     | _ => false)
  1138     | _ => false)
  1044 *}
  1139 *}
  1045 
  1140 
  1046 simproc_setup reorient_numeral
  1141 simproc_setup reorient_numeral
  1047   ("numeral w = x" | "neg_numeral w = y") = Reorient_Proc.proc
  1142   ("numeral w = x" | "- numeral w = y") = Reorient_Proc.proc
  1048 
  1143 
  1049 
  1144 
  1050 subsubsection {* Simplification of arithmetic operations on integer constants. *}
  1145 subsubsection {* Simplification of arithmetic operations on integer constants. *}
  1051 
  1146 
  1052 lemmas arith_special = (* already declared simp above *)
  1147 lemmas arith_special = (* already declared simp above *)
  1053   add_numeral_special add_neg_numeral_special
  1148   add_numeral_special add_neg_numeral_special
  1054   diff_numeral_special minus_one
  1149   diff_numeral_special
  1055 
  1150 
  1056 (* rules already in simpset *)
  1151 (* rules already in simpset *)
  1057 lemmas arith_extra_simps =
  1152 lemmas arith_extra_simps =
  1058   numeral_plus_numeral add_neg_numeral_simps add_0_left add_0_right
  1153   numeral_plus_numeral add_neg_numeral_simps add_0_left add_0_right
  1059   minus_numeral minus_neg_numeral minus_zero minus_one
  1154   minus_zero
  1060   diff_numeral_simps diff_0 diff_0_right
  1155   diff_numeral_simps diff_0 diff_0_right
  1061   numeral_times_numeral mult_neg_numeral_simps
  1156   numeral_times_numeral mult_neg_numeral_simps
  1062   mult_zero_left mult_zero_right
  1157   mult_zero_left mult_zero_right
  1063   abs_numeral abs_neg_numeral
  1158   abs_numeral abs_neg_numeral
  1064 
  1159 
  1087 lemmas eq_numeral_extra =
  1182 lemmas eq_numeral_extra =
  1088   zero_neq_one one_neq_zero
  1183   zero_neq_one one_neq_zero
  1089 
  1184 
  1090 lemmas rel_simps =
  1185 lemmas rel_simps =
  1091   le_num_simps less_num_simps eq_num_simps
  1186   le_num_simps less_num_simps eq_num_simps
  1092   le_numeral_simps le_neg_numeral_simps le_numeral_extra
  1187   le_numeral_simps le_neg_numeral_simps le_minus_one_simps le_numeral_extra
  1093   less_numeral_simps less_neg_numeral_simps less_numeral_extra
  1188   less_numeral_simps less_neg_numeral_simps less_minus_one_simps less_numeral_extra
  1094   eq_numeral_simps eq_neg_numeral_simps eq_numeral_extra
  1189   eq_numeral_simps eq_neg_numeral_simps eq_numeral_extra
  1095 
  1190 
  1096 lemma Let_numeral [simp]: "Let (numeral v) f = f (numeral v)"
  1191 lemma Let_numeral [simp]: "Let (numeral v) f = f (numeral v)"
  1097   -- {* Unfold all @{text let}s involving constants *}
  1192   -- {* Unfold all @{text let}s involving constants *}
  1098   unfolding Let_def ..
  1193   unfolding Let_def ..
  1099 
  1194 
  1100 lemma Let_neg_numeral [simp]: "Let (neg_numeral v) f = f (neg_numeral v)"
  1195 lemma Let_neg_numeral [simp]: "Let (- numeral v) f = f (- numeral v)"
  1101   -- {* Unfold all @{text let}s involving constants *}
  1196   -- {* Unfold all @{text let}s involving constants *}
  1102   unfolding Let_def ..
  1197   unfolding Let_def ..
  1103 
  1198 
  1104 declaration {*
  1199 declaration {*
  1105 let 
  1200 let 
  1131 lemma add_numeral_left [simp]:
  1226 lemma add_numeral_left [simp]:
  1132   "numeral v + (numeral w + z) = (numeral(v + w) + z)"
  1227   "numeral v + (numeral w + z) = (numeral(v + w) + z)"
  1133   by (simp_all add: add_assoc [symmetric])
  1228   by (simp_all add: add_assoc [symmetric])
  1134 
  1229 
  1135 lemma add_neg_numeral_left [simp]:
  1230 lemma add_neg_numeral_left [simp]:
  1136   "numeral v + (neg_numeral w + y) = (sub v w + y)"
  1231   "numeral v + (- numeral w + y) = (sub v w + y)"
  1137   "neg_numeral v + (numeral w + y) = (sub w v + y)"
  1232   "- numeral v + (numeral w + y) = (sub w v + y)"
  1138   "neg_numeral v + (neg_numeral w + y) = (neg_numeral(v + w) + y)"
  1233   "- numeral v + (- numeral w + y) = (- numeral(v + w) + y)"
  1139   by (simp_all add: add_assoc [symmetric])
  1234   by (simp_all add: add_assoc [symmetric])
  1140 
  1235 
  1141 lemma mult_numeral_left [simp]:
  1236 lemma mult_numeral_left [simp]:
  1142   "numeral v * (numeral w * z) = (numeral(v * w) * z :: 'a::semiring_numeral)"
  1237   "numeral v * (numeral w * z) = (numeral(v * w) * z :: 'a::semiring_numeral)"
  1143   "neg_numeral v * (numeral w * y) = (neg_numeral(v * w) * y :: 'b::ring_1)"
  1238   "- numeral v * (numeral w * y) = (- numeral(v * w) * y :: 'b::ring_1)"
  1144   "numeral v * (neg_numeral w * y) = (neg_numeral(v * w) * y :: 'b::ring_1)"
  1239   "numeral v * (- numeral w * y) = (- numeral(v * w) * y :: 'b::ring_1)"
  1145   "neg_numeral v * (neg_numeral w * y) = (numeral(v * w) * y :: 'b::ring_1)"
  1240   "- numeral v * (- numeral w * y) = (numeral(v * w) * y :: 'b::ring_1)"
  1146   by (simp_all add: mult_assoc [symmetric])
  1241   by (simp_all add: mult_assoc [symmetric])
  1147 
  1242 
  1148 hide_const (open) One Bit0 Bit1 BitM inc pow sqr sub dbl dbl_inc dbl_dec
  1243 hide_const (open) One Bit0 Bit1 BitM inc pow sqr sub dbl dbl_inc dbl_dec
  1149 
  1244 
  1150 
  1245