src/HOL/Integ/nat_simprocs.ML
changeset 11701 3d51fbf81c17
parent 11377 0f16ad464c62
child 11704 3c50a2cd6f00
equal deleted inserted replaced
11700:a0e6bda62b7b 11701:3d51fbf81c17
    64 qed "nat_le_add_iff2";
    64 qed "nat_le_add_iff2";
    65 
    65 
    66 
    66 
    67 (** For cancel_numeral_factors **)
    67 (** For cancel_numeral_factors **)
    68 
    68 
    69 Goal "(#0::nat) < k ==> (k*m <= k*n) = (m<=n)";
    69 Goal "(Numeral0::nat) < k ==> (k*m <= k*n) = (m<=n)";
    70 by Auto_tac;  
    70 by Auto_tac;  
    71 qed "nat_mult_le_cancel1";
    71 qed "nat_mult_le_cancel1";
    72 
    72 
    73 Goal "(#0::nat) < k ==> (k*m < k*n) = (m<n)";
    73 Goal "(Numeral0::nat) < k ==> (k*m < k*n) = (m<n)";
    74 by Auto_tac;  
    74 by Auto_tac;  
    75 qed "nat_mult_less_cancel1";
    75 qed "nat_mult_less_cancel1";
    76 
    76 
    77 Goal "(#0::nat) < k ==> (k*m = k*n) = (m=n)";
    77 Goal "(Numeral0::nat) < k ==> (k*m = k*n) = (m=n)";
    78 by Auto_tac;  
    78 by Auto_tac;  
    79 qed "nat_mult_eq_cancel1";
    79 qed "nat_mult_eq_cancel1";
    80 
    80 
    81 Goal "(#0::nat) < k ==> (k*m) div (k*n) = (m div n)";
    81 Goal "(Numeral0::nat) < k ==> (k*m) div (k*n) = (m div n)";
    82 by Auto_tac;  
    82 by Auto_tac;  
    83 qed "nat_mult_div_cancel1";
    83 qed "nat_mult_div_cancel1";
    84 
    84 
    85 
    85 
    86 (** For cancel_factor **)
    86 (** For cancel_factor **)
   123   | find_first_numeral past [] = raise TERM("find_first_numeral", []);
   123   | find_first_numeral past [] = raise TERM("find_first_numeral", []);
   124 
   124 
   125 val zero = mk_numeral 0;
   125 val zero = mk_numeral 0;
   126 val mk_plus = HOLogic.mk_binop "op +";
   126 val mk_plus = HOLogic.mk_binop "op +";
   127 
   127 
   128 (*Thus mk_sum[t] yields t+#0; longer sums don't have a trailing zero*)
   128 (*Thus mk_sum[t] yields t+Numeral0; longer sums don't have a trailing zero*)
   129 fun mk_sum []        = zero
   129 fun mk_sum []        = zero
   130   | mk_sum [t,u]     = mk_plus (t, u)
   130   | mk_sum [t,u]     = mk_plus (t, u)
   131   | mk_sum (t :: ts) = mk_plus (t, mk_sum ts);
   131   | mk_sum (t :: ts) = mk_plus (t, mk_sum ts);
   132 
   132 
   133 (*this version ALWAYS includes a trailing zero*)
   133 (*this version ALWAYS includes a trailing zero*)
   156 val prove_conv = Int_Numeral_Simprocs.prove_conv;
   156 val prove_conv = Int_Numeral_Simprocs.prove_conv;
   157 
   157 
   158 val bin_simps = [add_nat_number_of, nat_number_of_add_left,
   158 val bin_simps = [add_nat_number_of, nat_number_of_add_left,
   159                  diff_nat_number_of, le_nat_number_of_eq_not_less,
   159                  diff_nat_number_of, le_nat_number_of_eq_not_less,
   160                  less_nat_number_of, mult_nat_number_of, 
   160                  less_nat_number_of, mult_nat_number_of, 
   161                  Let_number_of, nat_number_of] @
   161                  thm "Let_number_of", nat_number_of] @
   162                 bin_arith_simps @ bin_rel_simps;
   162                 bin_arith_simps @ bin_rel_simps;
   163 
   163 
   164 fun prep_simproc (name, pats, proc) = Simplifier.mk_simproc name pats proc;
   164 fun prep_simproc (name, pats, proc) = Simplifier.mk_simproc name pats proc;
   165 fun prep_pat s = Thm.read_cterm (Theory.sign_of (the_context ()))
   165 fun prep_pat s = Thm.read_cterm (Theory.sign_of (the_context ()))
   166                                 (s, HOLogic.termT);
   166                                 (s, HOLogic.termT);
   202                           else find_first_coeff (t::past) u terms
   202                           else find_first_coeff (t::past) u terms
   203         end
   203         end
   204         handle TERM _ => find_first_coeff (t::past) u terms;
   204         handle TERM _ => find_first_coeff (t::past) u terms;
   205 
   205 
   206 
   206 
   207 (*Simplify #1*n and n*#1 to n*)
   207 (*Simplify Numeral1*n and n*Numeral1 to n*)
   208 val add_0s = map rename_numerals [add_0, add_0_right];
   208 val add_0s = map rename_numerals [add_0, add_0_right];
   209 val mult_1s = map rename_numerals [mult_1, mult_1_right];
   209 val mult_1s = map rename_numerals [mult_1, mult_1_right];
   210 
   210 
   211 (*Final simplification: cancel + and *; replace #0 by 0 and #1 by 1*)
   211 (*Final simplification: cancel + and *; replace Numeral0 by 0 and Numeral1 by 1*)
   212 val simplify_meta_eq =
   212 val simplify_meta_eq =
   213     Int_Numeral_Simprocs.simplify_meta_eq
   213     Int_Numeral_Simprocs.simplify_meta_eq
   214          [numeral_0_eq_0, numeral_1_eq_1, add_0, add_0_right,
   214          [numeral_0_eq_0, numeral_1_eq_1, add_0, add_0_right,
   215          mult_0, mult_0_right, mult_1, mult_1_right];
   215          mult_0, mult_0_right, mult_1, mult_1_right];
   216 
   216 
   317 (*** Applying CombineNumeralsFun ***)
   317 (*** Applying CombineNumeralsFun ***)
   318 
   318 
   319 structure CombineNumeralsData =
   319 structure CombineNumeralsData =
   320   struct
   320   struct
   321   val add		= op + : int*int -> int 
   321   val add		= op + : int*int -> int 
   322   val mk_sum            = long_mk_sum    (*to work for e.g. #2*x + #3*x *)
   322   val mk_sum            = long_mk_sum    (*to work for e.g. # 2*x + # 3*x *)
   323   val dest_sum          = restricted_dest_Sucs_sum
   323   val dest_sum          = restricted_dest_Sucs_sum
   324   val mk_coeff          = mk_coeff
   324   val mk_coeff          = mk_coeff
   325   val dest_coeff        = dest_coeff
   325   val dest_coeff        = dest_coeff
   326   val left_distrib      = left_add_mult_distrib RS trans
   326   val left_distrib      = left_add_mult_distrib RS trans
   327   val prove_conv = 
   327   val prove_conv = 
   502 set timing;
   502 set timing;
   503 set trace_simp;
   503 set trace_simp;
   504 fun test s = (Goal s; by (Simp_tac 1));
   504 fun test s = (Goal s; by (Simp_tac 1));
   505 
   505 
   506 (*cancel_numerals*)
   506 (*cancel_numerals*)
   507 test "l +( #2) + (#2) + #2 + (l + #2) + (oo  + #2) = (uu::nat)";
   507 test "l +( # 2) + (# 2) + # 2 + (l + # 2) + (oo  + # 2) = (uu::nat)";
   508 test "(#2*length xs < #2*length xs + j)";
   508 test "(# 2*length xs < # 2*length xs + j)";
   509 test "(#2*length xs < length xs * #2 + j)";
   509 test "(# 2*length xs < length xs * # 2 + j)";
   510 test "#2*u = (u::nat)";
   510 test "# 2*u = (u::nat)";
   511 test "#2*u = Suc (u)";
   511 test "# 2*u = Suc (u)";
   512 test "(i + j + #12 + (k::nat)) - #15 = y";
   512 test "(i + j + # 12 + (k::nat)) - # 15 = y";
   513 test "(i + j + #12 + (k::nat)) - #5 = y";
   513 test "(i + j + # 12 + (k::nat)) - # 5 = y";
   514 test "Suc u - #2 = y";
   514 test "Suc u - # 2 = y";
   515 test "Suc (Suc (Suc u)) - #2 = y";
   515 test "Suc (Suc (Suc u)) - # 2 = y";
   516 test "(i + j + #2 + (k::nat)) - 1 = y";
   516 test "(i + j + # 2 + (k::nat)) - 1 = y";
   517 test "(i + j + #1 + (k::nat)) - 2 = y";
   517 test "(i + j + Numeral1 + (k::nat)) - 2 = y";
   518 
   518 
   519 test "(#2*x + (u*v) + y) - v*#3*u = (w::nat)";
   519 test "(# 2*x + (u*v) + y) - v*# 3*u = (w::nat)";
   520 test "(#2*x*u*v + #5 + (u*v)*#4 + y) - v*u*#4 = (w::nat)";
   520 test "(# 2*x*u*v + # 5 + (u*v)*# 4 + y) - v*u*# 4 = (w::nat)";
   521 test "(#2*x*u*v + (u*v)*#4 + y) - v*u = (w::nat)";
   521 test "(# 2*x*u*v + (u*v)*# 4 + y) - v*u = (w::nat)";
   522 test "Suc (Suc (#2*x*u*v + u*#4 + y)) - u = w";
   522 test "Suc (Suc (# 2*x*u*v + u*# 4 + y)) - u = w";
   523 test "Suc ((u*v)*#4) - v*#3*u = w";
   523 test "Suc ((u*v)*# 4) - v*# 3*u = w";
   524 test "Suc (Suc ((u*v)*#3)) - v*#3*u = w";
   524 test "Suc (Suc ((u*v)*# 3)) - v*# 3*u = w";
   525 
   525 
   526 test "(i + j + #12 + (k::nat)) = u + #15 + y";
   526 test "(i + j + # 12 + (k::nat)) = u + # 15 + y";
   527 test "(i + j + #32 + (k::nat)) - (u + #15 + y) = zz";
   527 test "(i + j + # 32 + (k::nat)) - (u + # 15 + y) = zz";
   528 test "(i + j + #12 + (k::nat)) = u + #5 + y";
   528 test "(i + j + # 12 + (k::nat)) = u + # 5 + y";
   529 (*Suc*)
   529 (*Suc*)
   530 test "(i + j + #12 + k) = Suc (u + y)";
   530 test "(i + j + # 12 + k) = Suc (u + y)";
   531 test "Suc (Suc (Suc (Suc (Suc (u + y))))) <= ((i + j) + #41 + k)";
   531 test "Suc (Suc (Suc (Suc (Suc (u + y))))) <= ((i + j) + # 41 + k)";
   532 test "(i + j + #5 + k) < Suc (Suc (Suc (Suc (Suc (u + y)))))";
   532 test "(i + j + # 5 + k) < Suc (Suc (Suc (Suc (Suc (u + y)))))";
   533 test "Suc (Suc (Suc (Suc (Suc (u + y))))) - #5 = v";
   533 test "Suc (Suc (Suc (Suc (Suc (u + y))))) - # 5 = v";
   534 test "(i + j + #5 + k) = Suc (Suc (Suc (Suc (Suc (Suc (Suc (u + y)))))))";
   534 test "(i + j + # 5 + k) = Suc (Suc (Suc (Suc (Suc (Suc (Suc (u + y)))))))";
   535 test "#2*y + #3*z + #2*u = Suc (u)";
   535 test "# 2*y + # 3*z + # 2*u = Suc (u)";
   536 test "#2*y + #3*z + #6*w + #2*y + #3*z + #2*u = Suc (u)";
   536 test "# 2*y + # 3*z + # 6*w + # 2*y + # 3*z + # 2*u = Suc (u)";
   537 test "#2*y + #3*z + #6*w + #2*y + #3*z + #2*u = #2*y' + #3*z' + #6*w' + #2*y' + #3*z' + u + (vv::nat)";
   537 test "# 2*y + # 3*z + # 6*w + # 2*y + # 3*z + # 2*u = # 2*y' + # 3*z' + # 6*w' + # 2*y' + # 3*z' + u + (vv::nat)";
   538 test "#6 + #2*y + #3*z + #4*u = Suc (vv + #2*u + z)";
   538 test "# 6 + # 2*y + # 3*z + # 4*u = Suc (vv + # 2*u + z)";
   539 test "(#2*n*m) < (#3*(m*n)) + (u::nat)";
   539 test "(# 2*n*m) < (# 3*(m*n)) + (u::nat)";
   540 
   540 
   541 (*negative numerals: FAIL*)
   541 (*negative numerals: FAIL*)
   542 test "(i + j + #-23 + (k::nat)) < u + #15 + y";
   542 test "(i + j + # -23 + (k::nat)) < u + # 15 + y";
   543 test "(i + j + #3 + (k::nat)) < u + #-15 + y";
   543 test "(i + j + # 3 + (k::nat)) < u + # -15 + y";
   544 test "(i + j + #-12 + (k::nat)) - #15 = y";
   544 test "(i + j + # -12 + (k::nat)) - # 15 = y";
   545 test "(i + j + #12 + (k::nat)) - #-15 = y";
   545 test "(i + j + # 12 + (k::nat)) - # -15 = y";
   546 test "(i + j + #-12 + (k::nat)) - #-15 = y";
   546 test "(i + j + # -12 + (k::nat)) - # -15 = y";
   547 
   547 
   548 (*combine_numerals*)
   548 (*combine_numerals*)
   549 test "k + #3*k = (u::nat)";
   549 test "k + # 3*k = (u::nat)";
   550 test "Suc (i + #3) = u";
   550 test "Suc (i + # 3) = u";
   551 test "Suc (i + j + #3 + k) = u";
   551 test "Suc (i + j + # 3 + k) = u";
   552 test "k + j + #3*k + j = (u::nat)";
   552 test "k + j + # 3*k + j = (u::nat)";
   553 test "Suc (j*i + i + k + #5 + #3*k + i*j*#4) = (u::nat)";
   553 test "Suc (j*i + i + k + # 5 + # 3*k + i*j*# 4) = (u::nat)";
   554 test "(#2*n*m) + (#3*(m*n)) = (u::nat)";
   554 test "(# 2*n*m) + (# 3*(m*n)) = (u::nat)";
   555 (*negative numerals: FAIL*)
   555 (*negative numerals: FAIL*)
   556 test "Suc (i + j + #-3 + k) = u";
   556 test "Suc (i + j + # -3 + k) = u";
   557 
   557 
   558 (*cancel_numeral_factors*)
   558 (*cancel_numeral_factors*)
   559 test "#9*x = #12 * (y::nat)";
   559 test "# 9*x = # 12 * (y::nat)";
   560 test "(#9*x) div (#12 * (y::nat)) = z";
   560 test "(# 9*x) div (# 12 * (y::nat)) = z";
   561 test "#9*x < #12 * (y::nat)";
   561 test "# 9*x < # 12 * (y::nat)";
   562 test "#9*x <= #12 * (y::nat)";
   562 test "# 9*x <= # 12 * (y::nat)";
   563 
   563 
   564 (*cancel_factor*)
   564 (*cancel_factor*)
   565 test "x*k = k*(y::nat)";
   565 test "x*k = k*(y::nat)";
   566 test "k = k*(y::nat)"; 
   566 test "k = k*(y::nat)"; 
   567 test "a*(b*c) = (b::nat)";
   567 test "a*(b*c) = (b::nat)";
   595    le_Suc_number_of,le_number_of_Suc,
   595    le_Suc_number_of,le_number_of_Suc,
   596    less_Suc_number_of,less_number_of_Suc,
   596    less_Suc_number_of,less_number_of_Suc,
   597    Suc_eq_number_of,eq_number_of_Suc,
   597    Suc_eq_number_of,eq_number_of_Suc,
   598    mult_0, mult_0_right, mult_Suc, mult_Suc_right,
   598    mult_0, mult_0_right, mult_Suc, mult_Suc_right,
   599    eq_number_of_0, eq_0_number_of, less_0_number_of,
   599    eq_number_of_0, eq_0_number_of, less_0_number_of,
   600    nat_number_of, Let_number_of, if_True, if_False];
   600    nat_number_of, thm "Let_number_of", if_True, if_False];
   601 
   601 
   602 val simprocs = [Nat_Times_Assoc.conv,
   602 val simprocs = [Nat_Times_Assoc.conv,
   603                 Nat_Numeral_Simprocs.combine_numerals]@
   603                 Nat_Numeral_Simprocs.combine_numerals]@
   604                 Nat_Numeral_Simprocs.cancel_numerals;
   604                 Nat_Numeral_Simprocs.cancel_numerals;
   605 
   605