src/Provers/Arith/fast_lin_arith.ML
changeset 7582 2650c9c2ab7f
parent 7570 a9391550eea1
child 8263 699d4ad2ced3
equal deleted inserted replaced
7581:18070ae7a84c 7582:2650c9c2ab7f
    14     lin_arith_prover: Sign.sg -> thm list -> term -> thm option
    14     lin_arith_prover: Sign.sg -> thm list -> term -> thm option
    15 
    15 
    16 Only take premises and conclusions into account that are already (negated)
    16 Only take premises and conclusions into account that are already (negated)
    17 (in)equations. lin_arith_prover tries to prove or disprove the term.
    17 (in)equations. lin_arith_prover tries to prove or disprove the term.
    18 *)
    18 *)
       
    19 
       
    20 (* Debugging: (*? -> (*?*), !*) -> (*!*) *)
    19 
    21 
    20 (*** Data needed for setting up the linear arithmetic package ***)
    22 (*** Data needed for setting up the linear arithmetic package ***)
    21 
    23 
    22 signature LIN_ARITH_LOGIC =
    24 signature LIN_ARITH_LOGIC =
    23 sig
    25 sig
    52 sig
    54 sig
    53   val add_mono_thms:    thm list ref
    55   val add_mono_thms:    thm list ref
    54                             (* [| i rel1 j; m rel2 n |] ==> i + m rel3 j + n *)
    56                             (* [| i rel1 j; m rel2 n |] ==> i + m rel3 j + n *)
    55   val lessD:            thm list ref (* m < n ==> m+1 <= n *)
    57   val lessD:            thm list ref (* m < n ==> m+1 <= n *)
    56   val decomp:
    58   val decomp:
    57     term ->
    59     term -> ((term*int)list * int * string * (term*int)list * int * bool)option
    58       ((term * int)list * int * string * (term * int)list * int * bool)option
    60   val ss_ref: simpset ref
    59   val simp: (thm -> thm) ref
       
    60 end;
    61 end;
    61 (*
    62 (*
    62 decomp(`x Rel y') should yield (p,i,Rel,q,j,d)
    63 decomp(`x Rel y') should yield (p,i,Rel,q,j,d)
    63    where Rel is one of "<", "~<", "<=", "~<=" and "=" and
    64    where Rel is one of "<", "~<", "<=", "~<=" and "=" and
    64          p/q is the decomposition of the sum terms x/y into a list
    65          p/q is the decomposition of the sum terms x/y into a list
    65          of summand * multiplicity pairs and a constant summand and
    66          of summand * multiplicity pairs and a constant summand and
    66          d indicates if the domain is discrete.
    67          d indicates if the domain is discrete.
    67 
    68 
    68 simp must reduce contradictory <= to False.
    69 ss_ref must reduce contradictory <= to False.
    69    It should also cancel common summands to keep <= reduced;
    70    It should also cancel common summands to keep <= reduced;
    70    otherwise <= can grow to massive proportions.
    71    otherwise <= can grow to massive proportions.
    71 *)
    72 *)
    72 
    73 
    73 signature FAST_LIN_ARITH =
    74 signature FAST_LIN_ARITH =
   200    (case t of Eq => " =  " | Lt=> " <  " | Le => " <= ") ^
   201    (case t of Eq => " =  " | Lt=> " <  " | Le => " <= ") ^
   201    commas(map string_of_int l)) ineqs));
   202    commas(map string_of_int l)) ineqs));
   202 
   203 
   203 
   204 
   204 fun elim ineqs =
   205 fun elim ineqs =
   205   let (*val dummy = print_ineqs ineqs;*)
   206   let (*?val dummy = print_ineqs ineqs;!*)
   206       val (triv,nontriv) = partition is_trivial ineqs in
   207       val (triv,nontriv) = partition is_trivial ineqs in
   207   if not(null triv)
   208   if not(null triv)
   208   then case find_first is_answer triv of
   209   then case find_first is_answer triv of
   209          None => elim nontriv | some => some
   210          None => elim nontriv | some => some
   210   else
   211   else
   266       fun multn(n,thm) =
   267       fun multn(n,thm) =
   267         let fun mul(i,th) = if i=1 then th else mul(i-1, addthms thm th)
   268         let fun mul(i,th) = if i=1 then th else mul(i-1, addthms thm th)
   268         in if n < 0 then mul(~n,thm) RS LA_Logic.sym else mul(n,thm) end;
   269         in if n < 0 then mul(~n,thm) RS LA_Logic.sym else mul(n,thm) end;
   269 
   270 
   270       fun simp thm =
   271       fun simp thm =
   271         let val thm' = !LA_Data.simp thm
   272         let val thm' = simplify (!LA_Data.ss_ref) thm
   272         in if LA_Logic.is_False thm' then raise FalseE thm' else thm' end
   273         in if LA_Logic.is_False thm' then raise FalseE thm' else thm' end
   273 
   274 
   274       fun mk(Asm i) = ((*writeln"Asm";prth*)(nth_elem(i,asms)))
   275       fun mk(Asm i) = ((*?writeln"Asm";prth!*)(nth_elem(i,asms)))
   275         | mk(Nat(i)) = ((*writeln"N";*)LA_Logic.mk_nat_thm sg (nth_elem(i,atoms)))
   276         | mk(Nat(i)) = ((*?writeln"Nat";!*)LA_Logic.mk_nat_thm sg (nth_elem(i,atoms)))
   276         | mk(LessD(j)) = ((*writeln"L";prth*)(hd([mk j] RL !LA_Data.lessD)))
   277         | mk(LessD(j)) = ((*?writeln"L";prth!*)(hd([mk j] RL !LA_Data.lessD)))
   277         | mk(NotLeD(j)) = ((*writeln"NLe";prth*)(mk j RS LA_Logic.not_leD))
   278         | mk(NotLeD(j)) = ((*?writeln"NLe";prth!*)(mk j RS LA_Logic.not_leD))
   278         | mk(NotLeDD(j)) = ((*writeln"NLeD";prth*)(hd([mk j RS LA_Logic.not_leD] RL !LA_Data.lessD)))
   279         | mk(NotLeDD(j)) = ((*?writeln"NLeD";prth!*)(hd([mk j RS LA_Logic.not_leD] RL !LA_Data.lessD)))
   279         | mk(NotLessD(j)) = ((*writeln"NL";prth*)(mk j RS LA_Logic.not_lessD))
   280         | mk(NotLessD(j)) = ((*?writeln"NL";prth!*)(mk j RS LA_Logic.not_lessD))
   280         | mk(Added(j1,j2)) = ((*writeln"+";prth*)(simp((*prth*)(addthms (mk j1) (mk j2)))))
   281         | mk(Added(j1,j2)) = ((*?writeln"+";prth!*)(simp((*?prth!*)(addthms (mk j1) (mk j2)))))
   281         | mk(Multiplied(n,j)) = ((*writeln"*";*)multn(n,mk j))
   282         | mk(Multiplied(n,j)) = ((*?writeln"*";!*)multn(n,mk j))
   282 
   283 
   283   in (*writeln"mkthm";*)!LA_Data.simp(mk just) handle FalseE thm => thm end
   284   in (*?writeln"mkthm";!*)
       
   285      simplify (!LA_Data.ss_ref) (mk just) handle FalseE thm => thm end
   284 end;
   286 end;
   285 
   287 
   286 fun coeff poly atom = case assoc(poly,atom) of None => 0 | Some i => i;
   288 fun coeff poly atom = case assoc(poly,atom) of None => 0 | Some i => i;
   287 
   289 
   288 fun mklineq atoms =
   290 fun mklineq atoms =