345 goal Arith.thy |
345 goal Arith.thy |
346 "!!m n. [| 0<n; m:nat; n:nat |] ==> \ |
346 "!!m n. [| 0<n; m:nat; n:nat |] ==> \ |
347 \ succ(m) mod n = if(succ(m mod n) = n, 0, succ(m mod n))"; |
347 \ succ(m) mod n = if(succ(m mod n) = n, 0, succ(m mod n))"; |
348 by (etac complete_induct 1); |
348 by (etac complete_induct 1); |
349 by (excluded_middle_tac "succ(x)<n" 1); |
349 by (excluded_middle_tac "succ(x)<n" 1); |
350 (*case x<n*) |
350 (* case succ(x) < n *) |
351 by (asm_simp_tac (arith_ss addsimps [mod_less, nat_le_refl RS lt_trans, |
351 by (asm_simp_tac (arith_ss addsimps [mod_less, nat_le_refl RS lt_trans, |
352 succ_neq_self]) 2); |
352 succ_neq_self]) 2); |
353 by (asm_simp_tac (arith_ss addsimps [ltD RS mem_imp_not_eq]) 2); |
353 by (asm_simp_tac (arith_ss addsimps [ltD RS mem_imp_not_eq]) 2); |
354 (*case n le x*) |
354 (* case n le succ(x) *) |
355 by (asm_full_simp_tac |
355 by (asm_full_simp_tac |
356 (arith_ss addsimps [not_lt_iff_le, nat_into_Ord, mod_geq]) 1); |
356 (arith_ss addsimps [not_lt_iff_le, nat_into_Ord, mod_geq]) 1); |
357 be leE 1; |
357 by (etac leE 1); |
358 by (asm_simp_tac (arith_ss addsimps [div_termination RS ltD, diff_succ, |
358 by (asm_simp_tac (arith_ss addsimps [div_termination RS ltD, diff_succ, |
359 mod_geq]) 1); |
359 mod_geq]) 1); |
360 by (asm_simp_tac (arith_ss addsimps [mod_less, diff_self_eq_0]) 1); |
360 by (asm_simp_tac (arith_ss addsimps [mod_less, diff_self_eq_0]) 1); |
361 qed "mod_succ"; |
361 qed "mod_succ"; |
362 |
362 |
363 goal Arith.thy "!!m n. [| 0<n; m:nat; n:nat |] ==> m mod n < n"; |
363 goal Arith.thy "!!m n. [| 0<n; m:nat; n:nat |] ==> m mod n < n"; |
364 by (etac complete_induct 1); |
364 by (etac complete_induct 1); |
374 |
374 |
375 goal Arith.thy |
375 goal Arith.thy |
376 "!!k b. [| k: nat; b<2 |] ==> k mod 2 = b | k mod 2 = if(b=1,0,1)"; |
376 "!!k b. [| k: nat; b<2 |] ==> k mod 2 = b | k mod 2 = if(b=1,0,1)"; |
377 by (subgoal_tac "k mod 2: 2" 1); |
377 by (subgoal_tac "k mod 2: 2" 1); |
378 by (asm_simp_tac (arith_ss addsimps [mod_less_divisor RS ltD]) 2); |
378 by (asm_simp_tac (arith_ss addsimps [mod_less_divisor RS ltD]) 2); |
379 by (dresolve_tac [ltD] 1); |
379 by (dtac ltD 1); |
380 by (asm_simp_tac (ZF_ss setloop split_tac [expand_if]) 1); |
380 by (asm_simp_tac (ZF_ss setloop split_tac [expand_if]) 1); |
381 by (fast_tac ZF_cs 1); |
381 by (fast_tac ZF_cs 1); |
382 qed "mod2_cases"; |
382 qed "mod2_cases"; |
383 |
383 |
384 goal Arith.thy "!!m. m:nat ==> succ(succ(m)) mod 2 = m mod 2"; |
384 goal Arith.thy "!!m. m:nat ==> succ(succ(m)) mod 2 = m mod 2"; |
386 by (asm_simp_tac (arith_ss addsimps [mod_less_divisor RS ltD]) 2); |
386 by (asm_simp_tac (arith_ss addsimps [mod_less_divisor RS ltD]) 2); |
387 by (asm_simp_tac (arith_ss addsimps [mod_succ] setloop step_tac ZF_cs) 1); |
387 by (asm_simp_tac (arith_ss addsimps [mod_succ] setloop step_tac ZF_cs) 1); |
388 qed "mod2_succ_succ"; |
388 qed "mod2_succ_succ"; |
389 |
389 |
390 goal Arith.thy "!!m. m:nat ==> (m#+m) mod 2 = 0"; |
390 goal Arith.thy "!!m. m:nat ==> (m#+m) mod 2 = 0"; |
391 by (eresolve_tac [nat_induct] 1); |
391 by (etac nat_induct 1); |
392 by (simp_tac (arith_ss addsimps [mod_less]) 1); |
392 by (simp_tac (arith_ss addsimps [mod_less]) 1); |
393 by (asm_simp_tac (arith_ss addsimps [mod2_succ_succ, add_succ_right]) 1); |
393 by (asm_simp_tac (arith_ss addsimps [mod2_succ_succ, add_succ_right]) 1); |
394 qed "mod2_add_self"; |
394 qed "mod2_add_self"; |
395 |
395 |
396 |
396 |
454 by (REPEAT (eresolve_tac [asm_rl, lt_nat_in_nat, nat_succI] 1)); |
454 by (REPEAT (eresolve_tac [asm_rl, lt_nat_in_nat, nat_succI] 1)); |
455 qed "add_le_mono"; |
455 qed "add_le_mono"; |
456 |
456 |
457 val arith_ss0 = arith_ss |
457 val arith_ss0 = arith_ss |
458 and arith_ss = arith_ss addsimps [add_0_right, add_succ_right, |
458 and arith_ss = arith_ss addsimps [add_0_right, add_succ_right, |
459 mult_0_right, mult_succ_right, |
459 mult_0_right, mult_succ_right, |
460 mod_less, mod_geq, div_less, div_geq]; |
460 mod_less, mod_geq, div_less, div_geq]; |