src/HOL/Integ/NatSimprocs.ML
changeset 11704 3c50a2cd6f00
parent 11701 3d51fbf81c17
child 11868 56db9f3a6b3e
equal deleted inserted replaced
11703:6e5de8d4290a 11704:3c50a2cd6f00
    90 *)
    90 *)
    91 
    91 
    92 
    92 
    93 (** Evens and Odds, for Mutilated Chess Board **)
    93 (** Evens and Odds, for Mutilated Chess Board **)
    94 
    94 
    95 (*Case analysis on b<# 2*)
    95 (*Case analysis on b<2*)
    96 Goal "(n::nat) < # 2 ==> n = Numeral0 | n = Numeral1";
    96 Goal "(n::nat) < 2 ==> n = Numeral0 | n = Numeral1";
    97 by (arith_tac 1);
    97 by (arith_tac 1);
    98 qed "less_2_cases";
    98 qed "less_2_cases";
    99 
    99 
   100 Goal "Suc(Suc(m)) mod # 2 = m mod # 2";
   100 Goal "Suc(Suc(m)) mod 2 = m mod 2";
   101 by (subgoal_tac "m mod # 2 < # 2" 1);
   101 by (subgoal_tac "m mod 2 < 2" 1);
   102 by (Asm_simp_tac 2);
   102 by (Asm_simp_tac 2);
   103 be (less_2_cases RS disjE) 1;
   103 be (less_2_cases RS disjE) 1;
   104 by (ALLGOALS (asm_simp_tac (simpset() addsimps [mod_Suc])));
   104 by (ALLGOALS (asm_simp_tac (simpset() addsimps [mod_Suc])));
   105 qed "mod2_Suc_Suc";
   105 qed "mod2_Suc_Suc";
   106 Addsimps [mod2_Suc_Suc];
   106 Addsimps [mod2_Suc_Suc];
   107 
   107 
   108 Goal "!!m::nat. (0 < m mod # 2) = (m mod # 2 = Numeral1)";
   108 Goal "!!m::nat. (0 < m mod 2) = (m mod 2 = Numeral1)";
   109 by (subgoal_tac "m mod # 2 < # 2" 1);
   109 by (subgoal_tac "m mod 2 < 2" 1);
   110 by (Asm_simp_tac 2);
   110 by (Asm_simp_tac 2);
   111 by (auto_tac (claset(), simpset() delsimps [mod_less_divisor]));
   111 by (auto_tac (claset(), simpset() delsimps [mod_less_divisor]));
   112 qed "mod2_gr_0";
   112 qed "mod2_gr_0";
   113 Addsimps [mod2_gr_0, rename_numerals mod2_gr_0];
   113 Addsimps [mod2_gr_0, rename_numerals mod2_gr_0];
   114 
   114 
   115 (** Removal of small numerals: Numeral0, Numeral1 and (in additive positions) # 2 **)
   115 (** Removal of small numerals: Numeral0, Numeral1 and (in additive positions) 2 **)
   116 
   116 
   117 Goal "# 2 + n = Suc (Suc n)";
   117 Goal "2 + n = Suc (Suc n)";
   118 by (Simp_tac 1);
   118 by (Simp_tac 1);
   119 qed "add_2_eq_Suc";
   119 qed "add_2_eq_Suc";
   120 
   120 
   121 Goal "n + # 2 = Suc (Suc n)";
   121 Goal "n + 2 = Suc (Suc n)";
   122 by (Simp_tac 1);
   122 by (Simp_tac 1);
   123 qed "add_2_eq_Suc'";
   123 qed "add_2_eq_Suc'";
   124 
   124 
   125 Addsimps [numeral_0_eq_0, numeral_1_eq_1, add_2_eq_Suc, add_2_eq_Suc'];
   125 Addsimps [numeral_0_eq_0, numeral_1_eq_1, add_2_eq_Suc, add_2_eq_Suc'];
   126 
   126 
   127 (*Can be used to eliminate long strings of Sucs, but not by default*)
   127 (*Can be used to eliminate long strings of Sucs, but not by default*)
   128 Goal "Suc (Suc (Suc n)) = # 3 + n";
   128 Goal "Suc (Suc (Suc n)) = 3 + n";
   129 by (Simp_tac 1);
   129 by (Simp_tac 1);
   130 qed "Suc3_eq_add_3";
   130 qed "Suc3_eq_add_3";
   131 
   131 
   132 
   132 
   133 (** To collapse some needless occurrences of Suc 
   133 (** To collapse some needless occurrences of Suc 
   134     At least three Sucs, since two and fewer are rewritten back to Suc again!
   134     At least three Sucs, since two and fewer are rewritten back to Suc again!
   135 
   135 
   136     We already have some rules to simplify operands smaller than 3.
   136     We already have some rules to simplify operands smaller than 3.
   137 **)
   137 **)
   138 
   138 
   139 Goal "m div (Suc (Suc (Suc n))) = m div (# 3+n)";
   139 Goal "m div (Suc (Suc (Suc n))) = m div (3+n)";
   140 by (simp_tac (simpset() addsimps [Suc3_eq_add_3]) 1);
   140 by (simp_tac (simpset() addsimps [Suc3_eq_add_3]) 1);
   141 qed "div_Suc_eq_div_add3";
   141 qed "div_Suc_eq_div_add3";
   142 
   142 
   143 Goal "m mod (Suc (Suc (Suc n))) = m mod (# 3+n)";
   143 Goal "m mod (Suc (Suc (Suc n))) = m mod (3+n)";
   144 by (simp_tac (simpset() addsimps [Suc3_eq_add_3]) 1);
   144 by (simp_tac (simpset() addsimps [Suc3_eq_add_3]) 1);
   145 qed "mod_Suc_eq_mod_add3";
   145 qed "mod_Suc_eq_mod_add3";
   146 
   146 
   147 Addsimps [div_Suc_eq_div_add3, mod_Suc_eq_mod_add3];
   147 Addsimps [div_Suc_eq_div_add3, mod_Suc_eq_mod_add3];
   148 
   148 
   149 Goal "(Suc (Suc (Suc m))) div n = (# 3+m) div n";
   149 Goal "(Suc (Suc (Suc m))) div n = (3+m) div n";
   150 by (simp_tac (simpset() addsimps [Suc3_eq_add_3]) 1);
   150 by (simp_tac (simpset() addsimps [Suc3_eq_add_3]) 1);
   151 qed "Suc_div_eq_add3_div";
   151 qed "Suc_div_eq_add3_div";
   152 
   152 
   153 Goal "(Suc (Suc (Suc m))) mod n = (# 3+m) mod n";
   153 Goal "(Suc (Suc (Suc m))) mod n = (3+m) mod n";
   154 by (simp_tac (simpset() addsimps [Suc3_eq_add_3]) 1);
   154 by (simp_tac (simpset() addsimps [Suc3_eq_add_3]) 1);
   155 qed "Suc_mod_eq_add3_mod";
   155 qed "Suc_mod_eq_add3_mod";
   156 
   156 
   157 Addsimps [inst "n" "number_of ?v" Suc_div_eq_add3_div,
   157 Addsimps [inst "n" "number_of ?v" Suc_div_eq_add3_div,
   158 	  inst "n" "number_of ?v" Suc_mod_eq_add3_mod];
   158 	  inst "n" "number_of ?v" Suc_mod_eq_add3_mod];