src/HOL/Arith.ML
changeset 2031 03a843f0f447
parent 2007 968f78b52540
child 2099 c5f004bfcbab
equal deleted inserted replaced
2030:474b3f208789 2031:03a843f0f447
   162            ALLGOALS(asm_simp_tac (!simpset addsimps add_ac))]);
   162            ALLGOALS(asm_simp_tac (!simpset addsimps add_ac))]);
   163 
   163 
   164 (*Associative law for multiplication*)
   164 (*Associative law for multiplication*)
   165 qed_goal "mult_assoc" Arith.thy "(m * n) * k = m * ((n * k)::nat)"
   165 qed_goal "mult_assoc" Arith.thy "(m * n) * k = m * ((n * k)::nat)"
   166   (fn _ => [nat_ind_tac "m" 1, 
   166   (fn _ => [nat_ind_tac "m" 1, 
   167 	    ALLGOALS (asm_simp_tac (!simpset addsimps [add_mult_distrib]))]);
   167             ALLGOALS (asm_simp_tac (!simpset addsimps [add_mult_distrib]))]);
   168 
   168 
   169 qed_goal "mult_left_commute" Arith.thy "x*(y*z) = y*((x*z)::nat)"
   169 qed_goal "mult_left_commute" Arith.thy "x*(y*z) = y*((x*z)::nat)"
   170  (fn _ => [rtac trans 1, rtac mult_commute 1, rtac trans 1,
   170  (fn _ => [rtac trans 1, rtac mult_commute 1, rtac trans 1,
   171            rtac mult_assoc 1, rtac (mult_commute RS arg_cong) 1]);
   171            rtac mult_assoc 1, rtac (mult_commute RS arg_cong) 1]);
   172 
   172 
   537 by (simp_tac (!simpset addsimps [mult_commute]) 1);
   537 by (simp_tac (!simpset addsimps [mult_commute]) 1);
   538 qed "mult_le_mono";
   538 qed "mult_le_mono";
   539 
   539 
   540 (*strict, in 1st argument; proof is by induction on k>0*)
   540 (*strict, in 1st argument; proof is by induction on k>0*)
   541 goal Arith.thy "!!i::nat. [| i<j; 0<k |] ==> k*i < k*j";
   541 goal Arith.thy "!!i::nat. [| i<j; 0<k |] ==> k*i < k*j";
   542 be zero_less_natE 1;
   542 by (etac zero_less_natE 1);
   543 by (Asm_simp_tac 1);
   543 by (Asm_simp_tac 1);
   544 by (nat_ind_tac "x" 1);
   544 by (nat_ind_tac "x" 1);
   545 by (ALLGOALS (asm_simp_tac (!simpset addsimps [add_less_mono])));
   545 by (ALLGOALS (asm_simp_tac (!simpset addsimps [add_less_mono])));
   546 qed "mult_less_mono2";
   546 qed "mult_less_mono2";
   547 
   547 
   562 (*Cancellation law for division*)
   562 (*Cancellation law for division*)
   563 goal Arith.thy "!!k. [| 0<n; 0<k |] ==> (k*m) div (k*n) = m div n";
   563 goal Arith.thy "!!k. [| 0<n; 0<k |] ==> (k*m) div (k*n) = m div n";
   564 by (res_inst_tac [("n","m")] less_induct 1);
   564 by (res_inst_tac [("n","m")] less_induct 1);
   565 by (case_tac "na<n" 1);
   565 by (case_tac "na<n" 1);
   566 by (asm_simp_tac (!simpset addsimps [div_less, zero_less_mult_iff, 
   566 by (asm_simp_tac (!simpset addsimps [div_less, zero_less_mult_iff, 
   567 				     mult_less_mono2]) 1);
   567                                      mult_less_mono2]) 1);
   568 by (subgoal_tac "~ k*na < k*n" 1);
   568 by (subgoal_tac "~ k*na < k*n" 1);
   569 by (asm_simp_tac
   569 by (asm_simp_tac
   570      (!simpset addsimps [zero_less_mult_iff, div_geq,
   570      (!simpset addsimps [zero_less_mult_iff, div_geq,
   571 			 diff_mult_distrib2 RS sym, diff_less]) 1);
   571                          diff_mult_distrib2 RS sym, diff_less]) 1);
   572 by (asm_full_simp_tac (!simpset addsimps [not_less_iff_le, 
   572 by (asm_full_simp_tac (!simpset addsimps [not_less_iff_le, 
   573 					  le_refl RS mult_le_mono]) 1);
   573                                           le_refl RS mult_le_mono]) 1);
   574 qed "div_cancel";
   574 qed "div_cancel";
   575 
   575 
   576 goal Arith.thy "!!k. [| 0<n; 0<k |] ==> (k*m) mod (k*n) = k * (m mod n)";
   576 goal Arith.thy "!!k. [| 0<n; 0<k |] ==> (k*m) mod (k*n) = k * (m mod n)";
   577 by (res_inst_tac [("n","m")] less_induct 1);
   577 by (res_inst_tac [("n","m")] less_induct 1);
   578 by (case_tac "na<n" 1);
   578 by (case_tac "na<n" 1);
   579 by (asm_simp_tac (!simpset addsimps [mod_less, zero_less_mult_iff, 
   579 by (asm_simp_tac (!simpset addsimps [mod_less, zero_less_mult_iff, 
   580 				     mult_less_mono2]) 1);
   580                                      mult_less_mono2]) 1);
   581 by (subgoal_tac "~ k*na < k*n" 1);
   581 by (subgoal_tac "~ k*na < k*n" 1);
   582 by (asm_simp_tac
   582 by (asm_simp_tac
   583      (!simpset addsimps [zero_less_mult_iff, mod_geq,
   583      (!simpset addsimps [zero_less_mult_iff, mod_geq,
   584 			 diff_mult_distrib2 RS sym, diff_less]) 1);
   584                          diff_mult_distrib2 RS sym, diff_less]) 1);
   585 by (asm_full_simp_tac (!simpset addsimps [not_less_iff_le, 
   585 by (asm_full_simp_tac (!simpset addsimps [not_less_iff_le, 
   586 					  le_refl RS mult_le_mono]) 1);
   586                                           le_refl RS mult_le_mono]) 1);
   587 qed "mult_mod_distrib";
   587 qed "mult_mod_distrib";
   588 
   588 
   589 
   589 
   590 (** Lemma for gcd **)
   590 (** Lemma for gcd **)
   591 
   591