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); |