src/HOL/Nat_Numeral.thy
changeset 35216 7641e8d831d2
parent 35047 1b2bae06c796
child 35631 0b8a5fd339ab
equal deleted inserted replaced
35215:a03462cbf86f 35216:7641e8d831d2
   209 
   209 
   210 lemma zero_le_even_power'[simp]:
   210 lemma zero_le_even_power'[simp]:
   211   "0 \<le> a ^ (2*n)"
   211   "0 \<le> a ^ (2*n)"
   212 proof (induct n)
   212 proof (induct n)
   213   case 0
   213   case 0
   214     show ?case by (simp add: zero_le_one)
   214     show ?case by simp
   215 next
   215 next
   216   case (Suc n)
   216   case (Suc n)
   217     have "a ^ (2 * Suc n) = (a*a) * a ^ (2*n)" 
   217     have "a ^ (2 * Suc n) = (a*a) * a ^ (2*n)" 
   218       by (simp add: mult_ac power_add power2_eq_square)
   218       by (simp add: mult_ac power_add power2_eq_square)
   219     thus ?case
   219     thus ?case
   260 
   260 
   261 lemma not_neg_int [simp]: "~ neg (of_nat n)"
   261 lemma not_neg_int [simp]: "~ neg (of_nat n)"
   262 by (simp add: neg_def)
   262 by (simp add: neg_def)
   263 
   263 
   264 lemma neg_zminus_int [simp]: "neg (- (of_nat (Suc n)))"
   264 lemma neg_zminus_int [simp]: "neg (- (of_nat (Suc n)))"
   265 by (simp add: neg_def neg_less_0_iff_less del: of_nat_Suc)
   265 by (simp add: neg_def del: of_nat_Suc)
   266 
   266 
   267 lemmas neg_eq_less_0 = neg_def
   267 lemmas neg_eq_less_0 = neg_def
   268 
   268 
   269 lemma not_neg_eq_ge_0: "(~neg x) = (0 \<le> x)"
   269 lemma not_neg_eq_ge_0: "(~neg x) = (0 \<le> x)"
   270 by (simp add: neg_def linorder_not_less)
   270 by (simp add: neg_def linorder_not_less)
   273 
   273 
   274 lemma not_neg_0: "~ neg 0"
   274 lemma not_neg_0: "~ neg 0"
   275 by (simp add: One_int_def neg_def)
   275 by (simp add: One_int_def neg_def)
   276 
   276 
   277 lemma not_neg_1: "~ neg 1"
   277 lemma not_neg_1: "~ neg 1"
   278 by (simp add: neg_def linorder_not_less zero_le_one)
   278 by (simp add: neg_def linorder_not_less)
   279 
   279 
   280 lemma neg_nat: "neg z ==> nat z = 0"
   280 lemma neg_nat: "neg z ==> nat z = 0"
   281 by (simp add: neg_def order_less_imp_le) 
   281 by (simp add: neg_def order_less_imp_le) 
   282 
   282 
   283 lemma not_neg_nat: "~ neg z ==> of_nat (nat z) = z"
   283 lemma not_neg_nat: "~ neg z ==> of_nat (nat z) = z"
   308   neg_number_of_Bit0 neg_number_of_Bit1
   308   neg_number_of_Bit0 neg_number_of_Bit1
   309 
   309 
   310 
   310 
   311 subsection{*Function @{term nat}: Coercion from Type @{typ int} to @{typ nat}*}
   311 subsection{*Function @{term nat}: Coercion from Type @{typ int} to @{typ nat}*}
   312 
   312 
   313 declare nat_0 [simp] nat_1 [simp]
   313 declare nat_1 [simp]
   314 
   314 
   315 lemma nat_number_of [simp]: "nat (number_of w) = number_of w"
   315 lemma nat_number_of [simp]: "nat (number_of w) = number_of w"
   316 by (simp add: nat_number_of_def)
   316 by (simp add: nat_number_of_def)
   317 
   317 
   318 lemma nat_numeral_0_eq_0 [simp, code_post]: "Numeral0 = (0::nat)"
   318 lemma nat_numeral_0_eq_0 [simp, code_post]: "Numeral0 = (0::nat)"
   319 by (simp add: nat_number_of_def)
   319 by (simp add: nat_number_of_def)
   320 
   320 
   321 lemma nat_numeral_1_eq_1 [simp]: "Numeral1 = (1::nat)"
   321 lemma nat_numeral_1_eq_1 [simp]: "Numeral1 = (1::nat)"
   322 by (simp add: nat_1 nat_number_of_def)
   322 by (simp add: nat_number_of_def)
   323 
   323 
   324 lemma numeral_1_eq_Suc_0 [code_post]: "Numeral1 = Suc 0"
   324 lemma numeral_1_eq_Suc_0 [code_post]: "Numeral1 = Suc 0"
   325 by (simp add: nat_numeral_1_eq_1)
   325 by (simp only: nat_numeral_1_eq_1 One_nat_def)
   326 
   326 
   327 
   327 
   328 subsection{*Function @{term int}: Coercion from Type @{typ nat} to @{typ int}*}
   328 subsection{*Function @{term int}: Coercion from Type @{typ nat} to @{typ int}*}
   329 
   329 
   330 lemma int_nat_number_of [simp]:
   330 lemma int_nat_number_of [simp]:
   467     zero_le_power2 power2_less_0
   467     zero_le_power2 power2_less_0
   468 
   468 
   469 subsubsection{*Nat *}
   469 subsubsection{*Nat *}
   470 
   470 
   471 lemma Suc_pred': "0 < n ==> n = Suc(n - 1)"
   471 lemma Suc_pred': "0 < n ==> n = Suc(n - 1)"
   472 by (simp add: numerals)
   472 by simp
   473 
   473 
   474 (*Expresses a natural number constant as the Suc of another one.
   474 (*Expresses a natural number constant as the Suc of another one.
   475   NOT suitable for rewriting because n recurs in the condition.*)
   475   NOT suitable for rewriting because n recurs in the condition.*)
   476 lemmas expand_Suc = Suc_pred' [of "number_of v", standard]
   476 lemmas expand_Suc = Suc_pred' [of "number_of v", standard]
   477 
   477 
   478 subsubsection{*Arith *}
   478 subsubsection{*Arith *}
   479 
   479 
   480 lemma Suc_eq_plus1: "Suc n = n + 1"
   480 lemma Suc_eq_plus1: "Suc n = n + 1"
   481 by (simp add: numerals)
   481   unfolding One_nat_def by simp
   482 
   482 
   483 lemma Suc_eq_plus1_left: "Suc n = 1 + n"
   483 lemma Suc_eq_plus1_left: "Suc n = 1 + n"
   484 by (simp add: numerals)
   484   unfolding One_nat_def by simp
   485 
   485 
   486 (* These two can be useful when m = number_of... *)
   486 (* These two can be useful when m = number_of... *)
   487 
   487 
   488 lemma add_eq_if: "(m::nat) + n = (if m=0 then n else Suc ((m - 1) + n))"
   488 lemma add_eq_if: "(m::nat) + n = (if m=0 then n else Suc ((m - 1) + n))"
   489   unfolding One_nat_def by (cases m) simp_all
   489   unfolding One_nat_def by (cases m) simp_all
   561 
   561 
   562 lemma le_number_of_Suc [simp]:
   562 lemma le_number_of_Suc [simp]:
   563      "(number_of v <= Suc n) =  
   563      "(number_of v <= Suc n) =  
   564         (let pv = number_of (Int.pred v) in  
   564         (let pv = number_of (Int.pred v) in  
   565          if neg pv then True else nat pv <= n)"
   565          if neg pv then True else nat pv <= n)"
   566 by (simp add: Let_def less_Suc_number_of linorder_not_less [symmetric])
   566 by (simp add: Let_def linorder_not_less [symmetric])
   567 
   567 
   568 lemma le_Suc_number_of [simp]:
   568 lemma le_Suc_number_of [simp]:
   569      "(Suc n <= number_of v) =  
   569      "(Suc n <= number_of v) =  
   570         (let pv = number_of (Int.pred v) in  
   570         (let pv = number_of (Int.pred v) in  
   571          if neg pv then False else n <= nat pv)"
   571          if neg pv then False else n <= nat pv)"
   572 by (simp add: Let_def less_number_of_Suc linorder_not_less [symmetric])
   572 by (simp add: Let_def linorder_not_less [symmetric])
   573 
   573 
   574 
   574 
   575 lemma eq_number_of_Pls_Min: "(Numeral0 ::int) ~= number_of Int.Min"
   575 lemma eq_number_of_Pls_Min: "(Numeral0 ::int) ~= number_of Int.Min"
   576 by auto
   576 by auto
   577 
   577 
   658 
   658 
   659 lemmas power_number_of_odd_number_of [simp] =
   659 lemmas power_number_of_odd_number_of [simp] =
   660     power_number_of_odd [of "number_of v", standard]
   660     power_number_of_odd [of "number_of v", standard]
   661 
   661 
   662 lemma nat_number_of_Pls: "Numeral0 = (0::nat)"
   662 lemma nat_number_of_Pls: "Numeral0 = (0::nat)"
   663   by (simp add: number_of_Pls nat_number_of_def)
   663   by (simp add: nat_number_of_def)
   664 
   664 
   665 lemma nat_number_of_Min: "number_of Int.Min = (0::nat)"
   665 lemma nat_number_of_Min: "number_of Int.Min = (0::nat)"
   666   apply (simp only: number_of_Min nat_number_of_def nat_zminus_int)
   666   apply (simp only: number_of_Min nat_number_of_def nat_zminus_int)
   667   done
   667   done
   668 
   668 
   682 
   682 
   683 lemmas nat_number =
   683 lemmas nat_number =
   684   nat_number_of_Pls nat_number_of_Min
   684   nat_number_of_Pls nat_number_of_Min
   685   nat_number_of_Bit0 nat_number_of_Bit1
   685   nat_number_of_Bit0 nat_number_of_Bit1
   686 
   686 
       
   687 lemmas nat_number' =
       
   688   nat_number_of_Bit0 nat_number_of_Bit1
       
   689 
   687 lemma Let_Suc [simp]: "Let (Suc n) f == f (Suc n)"
   690 lemma Let_Suc [simp]: "Let (Suc n) f == f (Suc n)"
   688   by (fact Let_def)
   691   by (fact Let_def)
   689 
   692 
   690 lemma power_m1_even: "(-1) ^ (2*n) = (1::'a::{number_ring})"
   693 lemma power_m1_even: "(-1) ^ (2*n) = (1::'a::{number_ring})"
   691   by (simp only: number_of_Min power_minus1_even)
   694   by (simp only: number_of_Min power_minus1_even)
   734 subsubsection{*For simplifying @{term "Suc m - K"} and  @{term "K - Suc m"}*}
   737 subsubsection{*For simplifying @{term "Suc m - K"} and  @{term "K - Suc m"}*}
   735 
   738 
   736 text{*Where K above is a literal*}
   739 text{*Where K above is a literal*}
   737 
   740 
   738 lemma Suc_diff_eq_diff_pred: "Numeral0 < n ==> Suc m - n = m - (n - Numeral1)"
   741 lemma Suc_diff_eq_diff_pred: "Numeral0 < n ==> Suc m - n = m - (n - Numeral1)"
   739 by (simp add: numeral_0_eq_0 numeral_1_eq_1 split add: nat_diff_split)
   742 by (simp split: nat_diff_split)
   740 
   743 
   741 text {*Now just instantiating @{text n} to @{text "number_of v"} does
   744 text {*Now just instantiating @{text n} to @{text "number_of v"} does
   742   the right simplification, but with some redundant inequality
   745   the right simplification, but with some redundant inequality
   743   tests.*}
   746   tests.*}
   744 lemma neg_number_of_pred_iff_0:
   747 lemma neg_number_of_pred_iff_0:
   759 apply (auto simp only: diff_nat_number_of less_0_number_of [symmetric]
   762 apply (auto simp only: diff_nat_number_of less_0_number_of [symmetric]
   760                         neg_number_of_pred_iff_0)
   763                         neg_number_of_pred_iff_0)
   761 done
   764 done
   762 
   765 
   763 lemma diff_Suc_eq_diff_pred: "m - Suc n = (m - 1) - n"
   766 lemma diff_Suc_eq_diff_pred: "m - Suc n = (m - 1) - n"
   764 by (simp add: numerals split add: nat_diff_split)
   767 by (simp split: nat_diff_split)
   765 
   768 
   766 
   769 
   767 subsubsection{*For @{term nat_case} and @{term nat_rec}*}
   770 subsubsection{*For @{term nat_case} and @{term nat_rec}*}
   768 
   771 
   769 lemma nat_case_number_of [simp]:
   772 lemma nat_case_number_of [simp]: