src/HOL/Tools/lin_arith.ML
changeset 47108 2a1953f0d20d
parent 46709 65a9b30bff00
child 48556 62a3fbf9d35b
equal deleted inserted replaced
47107:35807a5d8dc2 47108:2a1953f0d20d
   172       (case demult (t, Rat.one) of
   172       (case demult (t, Rat.one) of
   173         (SOME _, _) => (SOME (mC $ s $ t), m)
   173         (SOME _, _) => (SOME (mC $ s $ t), m)
   174       | (NONE,  m') => apsnd (Rat.mult (Rat.inv m')) (demult (s, m)))
   174       | (NONE,  m') => apsnd (Rat.mult (Rat.inv m')) (demult (s, m)))
   175     (* terms that evaluate to numeric constants *)
   175     (* terms that evaluate to numeric constants *)
   176     | demult (Const (@{const_name Groups.uminus}, _) $ t, m) = demult (t, Rat.neg m)
   176     | demult (Const (@{const_name Groups.uminus}, _) $ t, m) = demult (t, Rat.neg m)
   177     | demult (Const (@{const_name Groups.zero}, _), m) = (NONE, Rat.zero)
   177     | demult (Const (@{const_name Groups.zero}, _), _) = (NONE, Rat.zero)
   178     | demult (Const (@{const_name Groups.one}, _), m) = (NONE, m)
   178     | demult (Const (@{const_name Groups.one}, _), m) = (NONE, m)
   179     (*Warning: in rare cases number_of encloses a non-numeral,
   179     (*Warning: in rare cases (neg_)numeral encloses a non-numeral,
   180       in which case dest_numeral raises TERM; hence all the handles below.
   180       in which case dest_num raises TERM; hence all the handles below.
   181       Same for Suc-terms that turn out not to be numerals -
   181       Same for Suc-terms that turn out not to be numerals -
   182       although the simplifier should eliminate those anyway ...*)
   182       although the simplifier should eliminate those anyway ...*)
   183     | demult (t as Const ("Int.number_class.number_of", _) $ n, m) =
   183     | demult (t as Const ("Num.numeral_class.numeral", _) $ n, m) =
   184       ((NONE, Rat.mult m (Rat.rat_of_int (HOLogic.dest_numeral n)))
   184       ((NONE, Rat.mult m (Rat.rat_of_int (HOLogic.dest_num n)))
       
   185         handle TERM _ => (SOME t, m))
       
   186     | demult (t as Const ("Num.neg_numeral_class.neg_numeral", _) $ n, m) =
       
   187       ((NONE, Rat.mult m (Rat.rat_of_int (~ (HOLogic.dest_num n))))
   185         handle TERM _ => (SOME t, m))
   188         handle TERM _ => (SOME t, m))
   186     | demult (t as Const (@{const_name Suc}, _) $ _, m) =
   189     | demult (t as Const (@{const_name Suc}, _) $ _, m) =
   187       ((NONE, Rat.mult m (Rat.rat_of_int (HOLogic.dest_nat t)))
   190       ((NONE, Rat.mult m (Rat.rat_of_int (HOLogic.dest_nat t)))
   188         handle TERM _ => (SOME t, m))
   191         handle TERM _ => (SOME t, m))
   189     (* injection constants are ignored *)
   192     (* injection constants are ignored *)
   217          | (SOME u, m') => add_atom u m' pi)
   220          | (SOME u, m') => add_atom u m' pi)
   218     | poly (all as Const (@{const_name Fields.divide}, _) $ _ $ _, m, pi as (p, i)) =
   221     | poly (all as Const (@{const_name Fields.divide}, _) $ _ $ _, m, pi as (p, i)) =
   219         (case demult inj_consts (all, m) of
   222         (case demult inj_consts (all, m) of
   220            (NONE,   m') => (p, Rat.add i m')
   223            (NONE,   m') => (p, Rat.add i m')
   221          | (SOME u, m') => add_atom u m' pi)
   224          | (SOME u, m') => add_atom u m' pi)
   222     | poly (all as Const ("Int.number_class.number_of", Type(_,[_,T])) $ t, m, pi as (p, i)) =
   225     | poly (all as Const ("Num.numeral_class.numeral", Type(_,[_,_])) $ t, m, pi as (p, i)) =
   223         (let val k = HOLogic.dest_numeral t
   226         (let val k = HOLogic.dest_num t
   224             val k2 = if k < 0 andalso T = HOLogic.natT then 0 else k
   227         in (p, Rat.add i (Rat.mult m (Rat.rat_of_int k))) end
   225         in (p, Rat.add i (Rat.mult m (Rat.rat_of_int k2))) end
   228         handle TERM _ => add_atom all m pi)
       
   229     | poly (all as Const ("Num.neg_numeral_class.neg_numeral", Type(_,[_,_])) $ t, m, pi as (p, i)) =
       
   230         (let val k = HOLogic.dest_num t
       
   231         in (p, Rat.add i (Rat.mult m (Rat.rat_of_int (~ k)))) end
   226         handle TERM _ => add_atom all m pi)
   232         handle TERM _ => add_atom all m pi)
   227     | poly (all as Const f $ x, m, pi) =
   233     | poly (all as Const f $ x, m, pi) =
   228         if member (op =) inj_consts f then poly (x, m, pi) else add_atom all m pi
   234         if member (op =) inj_consts f then poly (x, m, pi) else add_atom all m pi
   229     | poly (all, m, pi) =
   235     | poly (all, m, pi) =
   230         add_atom all m pi
   236         add_atom all m pi
   462         val subgoal1    = (HOLogic.mk_Trueprop t1_eq_nat_n) :: terms1 @ [not_false]
   468         val subgoal1    = (HOLogic.mk_Trueprop t1_eq_nat_n) :: terms1 @ [not_false]
   463         val subgoal2    = (HOLogic.mk_Trueprop t1_lt_zero) :: terms2 @ [not_false]
   469         val subgoal2    = (HOLogic.mk_Trueprop t1_lt_zero) :: terms2 @ [not_false]
   464       in
   470       in
   465         SOME [(HOLogic.natT :: Ts, subgoal1), (Ts, subgoal2)]
   471         SOME [(HOLogic.natT :: Ts, subgoal1), (Ts, subgoal2)]
   466       end
   472       end
   467     (* ?P ((?n::nat) mod (number_of ?k)) =
   473     (* ?P ((?n::nat) mod (numeral ?k)) =
   468          ((number_of ?k = 0 --> ?P ?n) & (~ (number_of ?k = 0) -->
   474          ((numeral ?k = 0 --> ?P ?n) & (~ (numeral ?k = 0) -->
   469            (ALL i j. j < number_of ?k --> ?n = number_of ?k * i + j --> ?P j))) *)
   475            (ALL i j. j < numeral ?k --> ?n = numeral ?k * i + j --> ?P j))) *)
   470     | (Const ("Divides.div_class.mod", Type ("fun", [@{typ nat}, _])), [t1, t2]) =>
   476     | (Const ("Divides.div_class.mod", Type ("fun", [@{typ nat}, _])), [t1, t2]) =>
   471       let
   477       let
   472         val rev_terms               = rev terms
   478         val rev_terms               = rev terms
   473         val zero                    = Const (@{const_name Groups.zero}, split_type)
   479         val zero                    = Const (@{const_name Groups.zero}, split_type)
   474         val i                       = Bound 1
   480         val i                       = Bound 1
   494                                         [t2_neq_zero, j_lt_t2, t1_eq_t2_times_i_plus_j])
   500                                         [t2_neq_zero, j_lt_t2, t1_eq_t2_times_i_plus_j])
   495                                           @ terms2 @ [not_false]
   501                                           @ terms2 @ [not_false]
   496       in
   502       in
   497         SOME [(Ts, subgoal1), (split_type :: split_type :: Ts, subgoal2)]
   503         SOME [(Ts, subgoal1), (split_type :: split_type :: Ts, subgoal2)]
   498       end
   504       end
   499     (* ?P ((?n::nat) div (number_of ?k)) =
   505     (* ?P ((?n::nat) div (numeral ?k)) =
   500          ((number_of ?k = 0 --> ?P 0) & (~ (number_of ?k = 0) -->
   506          ((numeral ?k = 0 --> ?P 0) & (~ (numeral ?k = 0) -->
   501            (ALL i j. j < number_of ?k --> ?n = number_of ?k * i + j --> ?P i))) *)
   507            (ALL i j. j < numeral ?k --> ?n = numeral ?k * i + j --> ?P i))) *)
   502     | (Const ("Divides.div_class.div", Type ("fun", [@{typ nat}, _])), [t1, t2]) =>
   508     | (Const ("Divides.div_class.div", Type ("fun", [@{typ nat}, _])), [t1, t2]) =>
   503       let
   509       let
   504         val rev_terms               = rev terms
   510         val rev_terms               = rev terms
   505         val zero                    = Const (@{const_name Groups.zero}, split_type)
   511         val zero                    = Const (@{const_name Groups.zero}, split_type)
   506         val i                       = Bound 1
   512         val i                       = Bound 1
   526                                         [t2_neq_zero, j_lt_t2, t1_eq_t2_times_i_plus_j])
   532                                         [t2_neq_zero, j_lt_t2, t1_eq_t2_times_i_plus_j])
   527                                           @ terms2 @ [not_false]
   533                                           @ terms2 @ [not_false]
   528       in
   534       in
   529         SOME [(Ts, subgoal1), (split_type :: split_type :: Ts, subgoal2)]
   535         SOME [(Ts, subgoal1), (split_type :: split_type :: Ts, subgoal2)]
   530       end
   536       end
   531     (* ?P ((?n::int) mod (number_of ?k)) =
   537     (* ?P ((?n::int) mod (numeral ?k)) =
   532          ((number_of ?k = 0 --> ?P ?n) &
   538          ((numeral ?k = 0 --> ?P ?n) &
   533           (0 < number_of ?k -->
   539           (0 < numeral ?k -->
   534             (ALL i j.
   540             (ALL i j.
   535               0 <= j & j < number_of ?k & ?n = number_of ?k * i + j --> ?P j)) &
   541               0 <= j & j < numeral ?k & ?n = numeral ?k * i + j --> ?P j)) &
   536           (number_of ?k < 0 -->
   542           (numeral ?k < 0 -->
   537             (ALL i j.
   543             (ALL i j.
   538               number_of ?k < j & j <= 0 & ?n = number_of ?k * i + j --> ?P j))) *)
   544               numeral ?k < j & j <= 0 & ?n = numeral ?k * i + j --> ?P j))) *)
   539     | (Const ("Divides.div_class.mod",
   545     | (Const ("Divides.div_class.mod",
   540         Type ("fun", [Type ("Int.int", []), _])), [t1, t2]) =>
   546         Type ("fun", [Type ("Int.int", []), _])), [t1, t2]) =>
   541       let
   547       let
   542         val rev_terms               = rev terms
   548         val rev_terms               = rev terms
   543         val zero                    = Const (@{const_name Groups.zero}, split_type)
   549         val zero                    = Const (@{const_name Groups.zero}, split_type)
   580                                         @ (if tl terms2_3 = [] then [] else tl terms2_3 @ [not_false])
   586                                         @ (if tl terms2_3 = [] then [] else tl terms2_3 @ [not_false])
   581         val Ts'                     = split_type :: split_type :: Ts
   587         val Ts'                     = split_type :: split_type :: Ts
   582       in
   588       in
   583         SOME [(Ts, subgoal1), (Ts', subgoal2), (Ts', subgoal3)]
   589         SOME [(Ts, subgoal1), (Ts', subgoal2), (Ts', subgoal3)]
   584       end
   590       end
   585     (* ?P ((?n::int) div (number_of ?k)) =
   591     (* ?P ((?n::int) div (numeral ?k)) =
   586          ((number_of ?k = 0 --> ?P 0) &
   592          ((numeral ?k = 0 --> ?P 0) &
   587           (0 < number_of ?k -->
   593           (0 < numeral ?k -->
   588             (ALL i j.
   594             (ALL i j.
   589               0 <= j & j < number_of ?k & ?n = number_of ?k * i + j --> ?P i)) &
   595               0 <= j & j < numeral ?k & ?n = numeral ?k * i + j --> ?P i)) &
   590           (number_of ?k < 0 -->
   596           (numeral ?k < 0 -->
   591             (ALL i j.
   597             (ALL i j.
   592               number_of ?k < j & j <= 0 & ?n = number_of ?k * i + j --> ?P i))) *)
   598               numeral ?k < j & j <= 0 & ?n = numeral ?k * i + j --> ?P i))) *)
   593     | (Const ("Divides.div_class.div",
   599     | (Const ("Divides.div_class.div",
   594         Type ("fun", [Type ("Int.int", []), _])), [t1, t2]) =>
   600         Type ("fun", [Type ("Int.int", []), _])), [t1, t2]) =>
   595       let
   601       let
   596         val rev_terms               = rev terms
   602         val rev_terms               = rev terms
   597         val zero                    = Const (@{const_name Groups.zero}, split_type)
   603         val zero                    = Const (@{const_name Groups.zero}, split_type)