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 = |