src/HOL/Tools/lin_arith.ML
changeset 25919 8b1c0d434824
parent 25015 1a84a9ae9d58
child 26061 59de52bec3ec
equal deleted inserted replaced
25918:82dd239e0f65 25919:8b1c0d434824
   201     | demult (Const (@{const_name HOL.one}, _), m) = (NONE, m)
   201     | demult (Const (@{const_name HOL.one}, _), m) = (NONE, m)
   202     (*Warning: in rare cases number_of encloses a non-numeral,
   202     (*Warning: in rare cases number_of encloses a non-numeral,
   203       in which case dest_numeral raises TERM; hence all the handles below.
   203       in which case dest_numeral raises TERM; hence all the handles below.
   204       Same for Suc-terms that turn out not to be numerals -
   204       Same for Suc-terms that turn out not to be numerals -
   205       although the simplifier should eliminate those anyway ...*)
   205       although the simplifier should eliminate those anyway ...*)
   206     | demult (t as Const ("Numeral.number_class.number_of", _) $ n, m) =
   206     | demult (t as Const ("Int.number_class.number_of", _) $ n, m) =
   207       ((NONE, Rat.mult m (Rat.rat_of_int (HOLogic.dest_numeral n)))
   207       ((NONE, Rat.mult m (Rat.rat_of_int (HOLogic.dest_numeral n)))
   208         handle TERM _ => (SOME t, m))
   208         handle TERM _ => (SOME t, m))
   209     | demult (t as Const (@{const_name Suc}, _) $ _, m) =
   209     | demult (t as Const (@{const_name Suc}, _) $ _, m) =
   210       ((NONE, Rat.mult m (Rat.rat_of_int (HOLogic.dest_nat t)))
   210       ((NONE, Rat.mult m (Rat.rat_of_int (HOLogic.dest_nat t)))
   211         handle TERM _ => (SOME t, m))
   211         handle TERM _ => (SOME t, m))
   240          | (SOME u, m') => add_atom u m' pi)
   240          | (SOME u, m') => add_atom u m' pi)
   241     | poly (all as Const (@{const_name HOL.divide}, _) $ _ $ _, m, pi as (p, i)) =
   241     | poly (all as Const (@{const_name HOL.divide}, _) $ _ $ _, m, pi as (p, i)) =
   242         (case demult inj_consts (all, m) of
   242         (case demult inj_consts (all, m) of
   243            (NONE,   m') => (p, Rat.add i m')
   243            (NONE,   m') => (p, Rat.add i m')
   244          | (SOME u, m') => add_atom u m' pi)
   244          | (SOME u, m') => add_atom u m' pi)
   245     | poly (all as Const ("Numeral.number_class.number_of", Type(_,[_,T])) $ t, m, pi as (p, i)) =
   245     | poly (all as Const ("Int.number_class.number_of", Type(_,[_,T])) $ t, m, pi as (p, i)) =
   246         (let val k = HOLogic.dest_numeral t
   246         (let val k = HOLogic.dest_numeral t
   247             val k2 = if k < 0 andalso T = HOLogic.natT then 0 else k
   247             val k2 = if k < 0 andalso T = HOLogic.natT then 0 else k
   248         in (p, Rat.add i (Rat.mult m (Rat.rat_of_int k2))) end
   248         in (p, Rat.add i (Rat.mult m (Rat.rat_of_int k2))) end
   249         handle TERM _ => add_atom all m pi)
   249         handle TERM _ => add_atom all m pi)
   250     | poly (all as Const f $ x, m, pi) =
   250     | poly (all as Const f $ x, m, pi) =
   322     case head_of lhs of
   322     case head_of lhs of
   323       Const (a, _) => member (op =) [@{const_name Orderings.max},
   323       Const (a, _) => member (op =) [@{const_name Orderings.max},
   324                                     @{const_name Orderings.min},
   324                                     @{const_name Orderings.min},
   325                                     @{const_name HOL.abs},
   325                                     @{const_name HOL.abs},
   326                                     @{const_name HOL.minus},
   326                                     @{const_name HOL.minus},
   327                                     "IntDef.nat",
   327                                     "Int.nat",
   328                                     "Divides.div_class.mod",
   328                                     "Divides.div_class.mod",
   329                                     "Divides.div_class.div"] a
   329                                     "Divides.div_class.div"] a
   330     | _            => (warning ("Lin. Arith.: wrong format for split rule " ^
   330     | _            => (warning ("Lin. Arith.: wrong format for split rule " ^
   331                                  Display.string_of_thm thm);
   331                                  Display.string_of_thm thm);
   332                        false))
   332                        false))
   460         val subgoal2        = (HOLogic.mk_Trueprop t1_eq_t2_plus_d) :: terms2 @ [not_false]
   460         val subgoal2        = (HOLogic.mk_Trueprop t1_eq_t2_plus_d) :: terms2 @ [not_false]
   461       in
   461       in
   462         SOME [(Ts, subgoal1), (split_type :: Ts, subgoal2)]
   462         SOME [(Ts, subgoal1), (split_type :: Ts, subgoal2)]
   463       end
   463       end
   464     (* ?P (nat ?i) = ((ALL n. ?i = int n --> ?P n) & (?i < 0 --> ?P 0)) *)
   464     (* ?P (nat ?i) = ((ALL n. ?i = int n --> ?P n) & (?i < 0 --> ?P 0)) *)
   465     | (Const ("IntDef.nat", _), [t1]) =>
   465     | (Const ("Int.nat", _), [t1]) =>
   466       let
   466       let
   467         val rev_terms   = rev terms
   467         val rev_terms   = rev terms
   468         val zero_int    = Const (@{const_name HOL.zero}, HOLogic.intT)
   468         val zero_int    = Const (@{const_name HOL.zero}, HOLogic.intT)
   469         val zero_nat    = Const (@{const_name HOL.zero}, HOLogic.natT)
   469         val zero_nat    = Const (@{const_name HOL.zero}, HOLogic.natT)
   470         val n           = Bound 0
   470         val n           = Bound 0
   551           (neg (number_of (uminus ?k)) -->
   551           (neg (number_of (uminus ?k)) -->
   552             (ALL i j. 0 <= j & j < number_of ?k & ?n = number_of ?k * i + j --> ?P j)) &
   552             (ALL i j. 0 <= j & j < number_of ?k & ?n = number_of ?k * i + j --> ?P j)) &
   553           (neg (number_of ?k) -->
   553           (neg (number_of ?k) -->
   554             (ALL i j. number_of ?k < j & j <= 0 & ?n = number_of ?k * i + j --> ?P j))) *)
   554             (ALL i j. number_of ?k < j & j <= 0 & ?n = number_of ?k * i + j --> ?P j))) *)
   555     | (Const ("Divides.div_class.mod",
   555     | (Const ("Divides.div_class.mod",
   556         Type ("fun", [Type ("IntDef.int", []), _])), [t1, t2 as (number_of $ k)]) =>
   556         Type ("fun", [Type ("Int.int", []), _])), [t1, t2 as (number_of $ k)]) =>
   557       let
   557       let
   558         val rev_terms               = rev terms
   558         val rev_terms               = rev terms
   559         val zero                    = Const (@{const_name HOL.zero}, split_type)
   559         val zero                    = Const (@{const_name HOL.zero}, split_type)
   560         val i                       = Bound 1
   560         val i                       = Bound 1
   561         val j                       = Bound 0
   561         val j                       = Bound 0
   562         val terms1                  = map (subst_term [(split_term, t1)]) rev_terms
   562         val terms1                  = map (subst_term [(split_term, t1)]) rev_terms
   563         val terms2_3                = map (subst_term [(incr_boundvars 2 split_term, j)])
   563         val terms2_3                = map (subst_term [(incr_boundvars 2 split_term, j)])
   564                                         (map (incr_boundvars 2) rev_terms)
   564                                         (map (incr_boundvars 2) rev_terms)
   565         val t1'                     = incr_boundvars 2 t1
   565         val t1'                     = incr_boundvars 2 t1
   566         val (t2' as (_ $ k'))       = incr_boundvars 2 t2
   566         val (t2' as (_ $ k'))       = incr_boundvars 2 t2
   567         val iszero_t2               = Const ("IntDef.iszero", split_type --> HOLogic.boolT) $ t2
   567         val iszero_t2               = Const ("Int.iszero", split_type --> HOLogic.boolT) $ t2
   568         val neg_minus_k             = Const ("IntDef.neg", split_type --> HOLogic.boolT) $
   568         val neg_minus_k             = Const ("Int.neg", split_type --> HOLogic.boolT) $
   569                                         (number_of $
   569                                         (number_of $
   570                                           (Const (@{const_name HOL.uminus},
   570                                           (Const (@{const_name HOL.uminus},
   571                                             HOLogic.intT --> HOLogic.intT) $ k'))
   571                                             HOLogic.intT --> HOLogic.intT) $ k'))
   572         val zero_leq_j              = Const (@{const_name HOL.less_eq},
   572         val zero_leq_j              = Const (@{const_name HOL.less_eq},
   573                                         split_type --> split_type --> HOLogic.boolT) $ zero $ j
   573                                         split_type --> split_type --> HOLogic.boolT) $ zero $ j
   575                                         split_type --> split_type--> HOLogic.boolT) $ j $ t2'
   575                                         split_type --> split_type--> HOLogic.boolT) $ j $ t2'
   576         val t1_eq_t2_times_i_plus_j = Const ("op =", split_type --> split_type --> HOLogic.boolT) $ t1' $
   576         val t1_eq_t2_times_i_plus_j = Const ("op =", split_type --> split_type --> HOLogic.boolT) $ t1' $
   577                                        (Const (@{const_name HOL.plus}, split_type --> split_type --> split_type) $
   577                                        (Const (@{const_name HOL.plus}, split_type --> split_type --> split_type) $
   578                                          (Const (@{const_name HOL.times},
   578                                          (Const (@{const_name HOL.times},
   579                                            split_type --> split_type --> split_type) $ t2' $ i) $ j)
   579                                            split_type --> split_type --> split_type) $ t2' $ i) $ j)
   580         val neg_t2                  = Const ("IntDef.neg", split_type --> HOLogic.boolT) $ t2'
   580         val neg_t2                  = Const ("Int.neg", split_type --> HOLogic.boolT) $ t2'
   581         val t2_lt_j                 = Const (@{const_name HOL.less},
   581         val t2_lt_j                 = Const (@{const_name HOL.less},
   582                                         split_type --> split_type--> HOLogic.boolT) $ t2' $ j
   582                                         split_type --> split_type--> HOLogic.boolT) $ t2' $ j
   583         val j_leq_zero              = Const (@{const_name HOL.less_eq},
   583         val j_leq_zero              = Const (@{const_name HOL.less_eq},
   584                                         split_type --> split_type --> HOLogic.boolT) $ j $ zero
   584                                         split_type --> split_type --> HOLogic.boolT) $ j $ zero
   585         val not_false               = HOLogic.mk_Trueprop (HOLogic.Not $ HOLogic.false_const)
   585         val not_false               = HOLogic.mk_Trueprop (HOLogic.Not $ HOLogic.false_const)
   603           (neg (number_of (uminus ?k)) -->
   603           (neg (number_of (uminus ?k)) -->
   604             (ALL i. (EX j. 0 <= j & j < number_of ?k & ?n = number_of ?k * i + j) --> ?P i)) &
   604             (ALL i. (EX j. 0 <= j & j < number_of ?k & ?n = number_of ?k * i + j) --> ?P i)) &
   605           (neg (number_of ?k) -->
   605           (neg (number_of ?k) -->
   606             (ALL i. (EX j. number_of ?k < j & j <= 0 & ?n = number_of ?k * i + j) --> ?P i))) *)
   606             (ALL i. (EX j. number_of ?k < j & j <= 0 & ?n = number_of ?k * i + j) --> ?P i))) *)
   607     | (Const ("Divides.div_class.div",
   607     | (Const ("Divides.div_class.div",
   608         Type ("fun", [Type ("IntDef.int", []), _])), [t1, t2 as (number_of $ k)]) =>
   608         Type ("fun", [Type ("Int.int", []), _])), [t1, t2 as (number_of $ k)]) =>
   609       let
   609       let
   610         val rev_terms               = rev terms
   610         val rev_terms               = rev terms
   611         val zero                    = Const (@{const_name HOL.zero}, split_type)
   611         val zero                    = Const (@{const_name HOL.zero}, split_type)
   612         val i                       = Bound 1
   612         val i                       = Bound 1
   613         val j                       = Bound 0
   613         val j                       = Bound 0
   614         val terms1                  = map (subst_term [(split_term, zero)]) rev_terms
   614         val terms1                  = map (subst_term [(split_term, zero)]) rev_terms
   615         val terms2_3                = map (subst_term [(incr_boundvars 2 split_term, i)])
   615         val terms2_3                = map (subst_term [(incr_boundvars 2 split_term, i)])
   616                                         (map (incr_boundvars 2) rev_terms)
   616                                         (map (incr_boundvars 2) rev_terms)
   617         val t1'                     = incr_boundvars 2 t1
   617         val t1'                     = incr_boundvars 2 t1
   618         val (t2' as (_ $ k'))       = incr_boundvars 2 t2
   618         val (t2' as (_ $ k'))       = incr_boundvars 2 t2
   619         val iszero_t2               = Const ("IntDef.iszero", split_type --> HOLogic.boolT) $ t2
   619         val iszero_t2               = Const ("Int.iszero", split_type --> HOLogic.boolT) $ t2
   620         val neg_minus_k             = Const ("IntDef.neg", split_type --> HOLogic.boolT) $
   620         val neg_minus_k             = Const ("Int.neg", split_type --> HOLogic.boolT) $
   621                                         (number_of $
   621                                         (number_of $
   622                                           (Const (@{const_name HOL.uminus},
   622                                           (Const (@{const_name HOL.uminus},
   623                                             HOLogic.intT --> HOLogic.intT) $ k'))
   623                                             HOLogic.intT --> HOLogic.intT) $ k'))
   624         val zero_leq_j              = Const (@{const_name HOL.less_eq},
   624         val zero_leq_j              = Const (@{const_name HOL.less_eq},
   625                                         split_type --> split_type --> HOLogic.boolT) $ zero $ j
   625                                         split_type --> split_type --> HOLogic.boolT) $ zero $ j
   628         val t1_eq_t2_times_i_plus_j = Const ("op =",
   628         val t1_eq_t2_times_i_plus_j = Const ("op =",
   629                                         split_type --> split_type --> HOLogic.boolT) $ t1' $
   629                                         split_type --> split_type --> HOLogic.boolT) $ t1' $
   630                                        (Const (@{const_name HOL.plus}, split_type --> split_type --> split_type) $
   630                                        (Const (@{const_name HOL.plus}, split_type --> split_type --> split_type) $
   631                                          (Const (@{const_name HOL.times},
   631                                          (Const (@{const_name HOL.times},
   632                                            split_type --> split_type --> split_type) $ t2' $ i) $ j)
   632                                            split_type --> split_type --> split_type) $ t2' $ i) $ j)
   633         val neg_t2                  = Const ("IntDef.neg", split_type --> HOLogic.boolT) $ t2'
   633         val neg_t2                  = Const ("Int.neg", split_type --> HOLogic.boolT) $ t2'
   634         val t2_lt_j                 = Const (@{const_name HOL.less},
   634         val t2_lt_j                 = Const (@{const_name HOL.less},
   635                                         split_type --> split_type--> HOLogic.boolT) $ t2' $ j
   635                                         split_type --> split_type--> HOLogic.boolT) $ t2' $ j
   636         val j_leq_zero              = Const (@{const_name HOL.less_eq},
   636         val j_leq_zero              = Const (@{const_name HOL.less_eq},
   637                                         split_type --> split_type --> HOLogic.boolT) $ j $ zero
   637                                         split_type --> split_type --> HOLogic.boolT) $ j $ zero
   638         val not_false               = HOLogic.mk_Trueprop (HOLogic.Not $ HOLogic.false_const)
   638         val not_false               = HOLogic.mk_Trueprop (HOLogic.Not $ HOLogic.false_const)