src/HOL/Arith.ML
changeset 1660 8cb42cd97579
parent 1655 5be64540f275
child 1713 79b4ef7832b5
equal deleted inserted replaced
1659:41e37e5211f2 1660:8cb42cd97579
   155 
   155 
   156 (*Addition is the inverse of subtraction: if n<=m then n+(m-n) = m. *)
   156 (*Addition is the inverse of subtraction: if n<=m then n+(m-n) = m. *)
   157 val [prem] = goal Arith.thy "[| ~ m<n |] ==> n+(m-n) = (m::nat)";
   157 val [prem] = goal Arith.thy "[| ~ m<n |] ==> n+(m-n) = (m::nat)";
   158 by (rtac (prem RS rev_mp) 1);
   158 by (rtac (prem RS rev_mp) 1);
   159 by (res_inst_tac [("m","m"),("n","n")] diff_induct 1);
   159 by (res_inst_tac [("m","m"),("n","n")] diff_induct 1);
   160 by (ALLGOALS Asm_simp_tac);
   160 by (ALLGOALS (Asm_simp_tac));
   161 qed "add_diff_inverse";
   161 qed "add_diff_inverse";
   162 
   162 
   163 
   163 
   164 (*** Remainder ***)
   164 (*** Remainder ***)
   165 
   165 
   166 goal Arith.thy "m - n < Suc(m)";
   166 goal Arith.thy "m - n < Suc(m)";
   167 by (res_inst_tac [("m","m"),("n","n")] diff_induct 1);
   167 by (res_inst_tac [("m","m"),("n","n")] diff_induct 1);
   168 by (etac less_SucE 3);
   168 by (etac less_SucE 3);
   169 by (ALLGOALS Asm_simp_tac);
   169 by (ALLGOALS (asm_simp_tac (!simpset addsimps [less_Suc_eq])));
   170 qed "diff_less_Suc";
   170 qed "diff_less_Suc";
   171 
   171 
   172 goal Arith.thy "!!m::nat. m - n <= m";
   172 goal Arith.thy "!!m::nat. m - n <= m";
   173 by (res_inst_tac [("m","m"), ("n","n")] diff_induct 1);
   173 by (res_inst_tac [("m","m"), ("n","n")] diff_induct 1);
   174 by (ALLGOALS Asm_simp_tac);
   174 by (ALLGOALS Asm_simp_tac);
   234 (*Main Result about quotient and remainder.*)
   234 (*Main Result about quotient and remainder.*)
   235 goal Arith.thy "!!m. 0<n ==> (m div n)*n + m mod n = m";
   235 goal Arith.thy "!!m. 0<n ==> (m div n)*n + m mod n = m";
   236 by (res_inst_tac [("n","m")] less_induct 1);
   236 by (res_inst_tac [("n","m")] less_induct 1);
   237 by (rename_tac "k" 1);    (*Variable name used in line below*)
   237 by (rename_tac "k" 1);    (*Variable name used in line below*)
   238 by (case_tac "k<n" 1);
   238 by (case_tac "k<n" 1);
   239 by (ALLGOALS (asm_simp_tac(!simpset addsimps (add_ac @
   239 by (ALLGOALS (asm_simp_tac(!simpset addsimps ([add_assoc] @
   240                        [mod_less, mod_geq, div_less, div_geq,
   240                        [mod_less, mod_geq, div_less, div_geq,
   241                         add_diff_inverse, diff_less]))));
   241                         add_diff_inverse, diff_less]))));
   242 qed "mod_div_equality";
   242 qed "mod_div_equality";
   243 
   243 
   244 
   244 
   245 (*** More results about difference ***)
   245 (*** More results about difference ***)
   246 
   246 
   247 val [prem] = goal Arith.thy "m < Suc(n) ==> m-n = 0";
   247 val [prem] = goal Arith.thy "m < Suc(n) ==> m-n = 0";
   248 by (rtac (prem RS rev_mp) 1);
   248 by (rtac (prem RS rev_mp) 1);
   249 by (res_inst_tac [("m","m"),("n","n")] diff_induct 1);
   249 by (res_inst_tac [("m","m"),("n","n")] diff_induct 1);
   250 by (ALLGOALS Asm_simp_tac);
   250 by (asm_simp_tac (!simpset addsimps [less_Suc_eq]) 1);
       
   251 by (ALLGOALS (Asm_simp_tac));
   251 qed "less_imp_diff_is_0";
   252 qed "less_imp_diff_is_0";
   252 
   253 
   253 val prems = goal Arith.thy "m-n = 0  -->  n-m = 0  -->  m=n";
   254 val prems = goal Arith.thy "m-n = 0  -->  n-m = 0  -->  m=n";
   254 by (res_inst_tac [("m","m"),("n","n")] diff_induct 1);
   255 by (res_inst_tac [("m","m"),("n","n")] diff_induct 1);
   255 by (REPEAT(Simp_tac 1 THEN TRY(atac 1)));
   256 by (REPEAT(Simp_tac 1 THEN TRY(atac 1)));
   256 qed_spec_mp "diffs0_imp_equal";
   257 qed_spec_mp "diffs0_imp_equal";
   257 
   258 
   258 val [prem] = goal Arith.thy "m<n ==> 0<n-m";
   259 val [prem] = goal Arith.thy "m<n ==> 0<n-m";
   259 by (rtac (prem RS rev_mp) 1);
   260 by (rtac (prem RS rev_mp) 1);
   260 by (res_inst_tac [("m","m"),("n","n")] diff_induct 1);
   261 by (res_inst_tac [("m","m"),("n","n")] diff_induct 1);
   261 by (ALLGOALS Asm_simp_tac);
   262 by (ALLGOALS (Asm_simp_tac));
   262 qed "less_imp_diff_positive";
   263 qed "less_imp_diff_positive";
   263 
   264 
   264 val [prem] = goal Arith.thy "n < Suc(m) ==> Suc(m)-n = Suc(m-n)";
   265 val [prem] = goal Arith.thy "n < Suc(m) ==> Suc(m)-n = Suc(m-n)";
   265 by (rtac (prem RS rev_mp) 1);
   266 by (rtac (prem RS rev_mp) 1);
   266 by (res_inst_tac [("m","m"),("n","n")] diff_induct 1);
   267 by (res_inst_tac [("m","m"),("n","n")] diff_induct 1);
   267 by (ALLGOALS Asm_simp_tac);
   268 by (ALLGOALS (Asm_simp_tac));
   268 qed "Suc_diff_n";
   269 qed "Suc_diff_n";
   269 
   270 
   270 goal Arith.thy "Suc(m)-n = (if m<n then 0 else Suc(m-n))";
   271 goal Arith.thy "Suc(m)-n = (if m<n then 0 else Suc(m-n))";
   271 by (simp_tac (!simpset addsimps [less_imp_diff_is_0, not_less_eq, Suc_diff_n]
   272 by (simp_tac (!simpset addsimps [less_imp_diff_is_0, not_less_eq, Suc_diff_n]
   272                     setloop (split_tac [expand_if])) 1);
   273                     setloop (split_tac [expand_if])) 1);
   344 
   345 
   345 (**** Additional theorems about "less than" ****)
   346 (**** Additional theorems about "less than" ****)
   346 
   347 
   347 goal Arith.thy "!!m. m<n --> (? k. n=Suc(m+k))";
   348 goal Arith.thy "!!m. m<n --> (? k. n=Suc(m+k))";
   348 by (nat_ind_tac "n" 1);
   349 by (nat_ind_tac "n" 1);
   349 by (ALLGOALS(Simp_tac));
   350 by (Simp_tac 1);
       
   351 by (simp_tac (!simpset addsimps [less_Suc_eq]) 1);
   350 by (REPEAT_FIRST (ares_tac [conjI, impI]));
   352 by (REPEAT_FIRST (ares_tac [conjI, impI]));
   351 by (res_inst_tac [("x","0")] exI 2);
   353 by (res_inst_tac [("x","0")] exI 2);
   352 by (Simp_tac 2);
   354 by (Simp_tac 2);
   353 by (safe_tac HOL_cs);
   355 by (safe_tac HOL_cs);
   354 by (res_inst_tac [("x","Suc(k)")] exI 1);
   356 by (res_inst_tac [("x","Suc(k)")] exI 1);