src/HOL/Library/positivstellensatz.ML
changeset 67399 eab6ce8368fa
parent 67271 48ef58c6cf4c
child 67559 833d154ab189
equal deleted inserted replaced
67398:5eb932e604a2 67399:eab6ce8368fa
   288 fun cterm_of_rat x =
   288 fun cterm_of_rat x =
   289   let
   289   let
   290     val (a, b) = Rat.dest x
   290     val (a, b) = Rat.dest x
   291   in
   291   in
   292     if b = 1 then Numeral.mk_cnumber \<^ctyp>\<open>real\<close> a
   292     if b = 1 then Numeral.mk_cnumber \<^ctyp>\<open>real\<close> a
   293     else Thm.apply (Thm.apply \<^cterm>\<open>op / :: real \<Rightarrow> _\<close>
   293     else Thm.apply (Thm.apply \<^cterm>\<open>(/) :: real \<Rightarrow> _\<close>
   294       (Numeral.mk_cnumber \<^ctyp>\<open>real\<close> a))
   294       (Numeral.mk_cnumber \<^ctyp>\<open>real\<close> a))
   295       (Numeral.mk_cnumber \<^ctyp>\<open>real\<close> b)
   295       (Numeral.mk_cnumber \<^ctyp>\<open>real\<close> b)
   296   end;
   296   end;
   297 
   297 
   298 fun dest_ratconst t =
   298 fun dest_ratconst t =
   322   handle CTERM _ => false;
   322   handle CTERM _ => false;
   323 
   323 
   324 
   324 
   325 (* Map back polynomials to HOL.                         *)
   325 (* Map back polynomials to HOL.                         *)
   326 
   326 
   327 fun cterm_of_varpow x k = if k = 1 then x else Thm.apply (Thm.apply \<^cterm>\<open>op ^ :: real \<Rightarrow> _\<close> x)
   327 fun cterm_of_varpow x k = if k = 1 then x else Thm.apply (Thm.apply \<^cterm>\<open>(^) :: real \<Rightarrow> _\<close> x)
   328   (Numeral.mk_cnumber \<^ctyp>\<open>nat\<close> k)
   328   (Numeral.mk_cnumber \<^ctyp>\<open>nat\<close> k)
   329 
   329 
   330 fun cterm_of_monomial m =
   330 fun cterm_of_monomial m =
   331   if FuncUtil.Ctermfunc.is_empty m then \<^cterm>\<open>1::real\<close>
   331   if FuncUtil.Ctermfunc.is_empty m then \<^cterm>\<open>1::real\<close>
   332   else
   332   else
   333     let
   333     let
   334       val m' = FuncUtil.dest_monomial m
   334       val m' = FuncUtil.dest_monomial m
   335       val vps = fold_rev (fn (x,k) => cons (cterm_of_varpow x k)) m' []
   335       val vps = fold_rev (fn (x,k) => cons (cterm_of_varpow x k)) m' []
   336     in foldr1 (fn (s, t) => Thm.apply (Thm.apply \<^cterm>\<open>op * :: real \<Rightarrow> _\<close> s) t) vps
   336     in foldr1 (fn (s, t) => Thm.apply (Thm.apply \<^cterm>\<open>( * ) :: real \<Rightarrow> _\<close> s) t) vps
   337     end
   337     end
   338 
   338 
   339 fun cterm_of_cmonomial (m,c) =
   339 fun cterm_of_cmonomial (m,c) =
   340   if FuncUtil.Ctermfunc.is_empty m then cterm_of_rat c
   340   if FuncUtil.Ctermfunc.is_empty m then cterm_of_rat c
   341   else if c = @1 then cterm_of_monomial m
   341   else if c = @1 then cterm_of_monomial m
   342   else Thm.apply (Thm.apply \<^cterm>\<open>op *::real \<Rightarrow> _\<close> (cterm_of_rat c)) (cterm_of_monomial m);
   342   else Thm.apply (Thm.apply \<^cterm>\<open>( * )::real \<Rightarrow> _\<close> (cterm_of_rat c)) (cterm_of_monomial m);
   343 
   343 
   344 fun cterm_of_poly p =
   344 fun cterm_of_poly p =
   345   if FuncUtil.Monomialfunc.is_empty p then \<^cterm>\<open>0::real\<close>
   345   if FuncUtil.Monomialfunc.is_empty p then \<^cterm>\<open>0::real\<close>
   346   else
   346   else
   347     let
   347     let
   348       val cms = map cterm_of_cmonomial
   348       val cms = map cterm_of_cmonomial
   349         (sort (prod_ord FuncUtil.monomial_order (K EQUAL)) (FuncUtil.Monomialfunc.dest p))
   349         (sort (prod_ord FuncUtil.monomial_order (K EQUAL)) (FuncUtil.Monomialfunc.dest p))
   350     in foldr1 (fn (t1, t2) => Thm.apply(Thm.apply \<^cterm>\<open>op + :: real \<Rightarrow> _\<close> t1) t2) cms
   350     in foldr1 (fn (t1, t2) => Thm.apply(Thm.apply \<^cterm>\<open>(+) :: real \<Rightarrow> _\<close> t1) t2) cms
   351     end;
   351     end;
   352 
   352 
   353 (* A general real arithmetic prover *)
   353 (* A general real arithmetic prover *)
   354 
   354 
   355 fun gen_gen_real_arith ctxt (mk_numeric,
   355 fun gen_gen_real_arith ctxt (mk_numeric,
   368     val weak_dnf_ss = put_simpset HOL_basic_ss ctxt addsimps weak_dnf_simps
   368     val weak_dnf_ss = put_simpset HOL_basic_ss ctxt addsimps weak_dnf_simps
   369     val weak_dnf_conv = Simplifier.rewrite weak_dnf_ss
   369     val weak_dnf_conv = Simplifier.rewrite weak_dnf_ss
   370     fun eqT_elim th = Thm.equal_elim (Thm.symmetric th) @{thm TrueI}
   370     fun eqT_elim th = Thm.equal_elim (Thm.symmetric th) @{thm TrueI}
   371     fun oprconv cv ct =
   371     fun oprconv cv ct =
   372       let val g = Thm.dest_fun2 ct
   372       let val g = Thm.dest_fun2 ct
   373       in if g aconvc \<^cterm>\<open>(op \<le>) :: real \<Rightarrow> _\<close>
   373       in if g aconvc \<^cterm>\<open>((\<le>)) :: real \<Rightarrow> _\<close>
   374             orelse g aconvc \<^cterm>\<open>(op <) :: real \<Rightarrow> _\<close>
   374             orelse g aconvc \<^cterm>\<open>((<)) :: real \<Rightarrow> _\<close>
   375          then arg_conv cv ct else arg1_conv cv ct
   375          then arg_conv cv ct else arg1_conv cv ct
   376       end
   376       end
   377 
   377 
   378     fun real_ineq_conv th ct =
   378     fun real_ineq_conv th ct =
   379       let
   379       let
   404           case prf of
   404           case prf of
   405             Axiom_eq n => nth eqs n
   405             Axiom_eq n => nth eqs n
   406           | Axiom_le n => nth les n
   406           | Axiom_le n => nth les n
   407           | Axiom_lt n => nth lts n
   407           | Axiom_lt n => nth lts n
   408           | Rational_eq x => eqT_elim(numeric_eq_conv(Thm.apply \<^cterm>\<open>Trueprop\<close>
   408           | Rational_eq x => eqT_elim(numeric_eq_conv(Thm.apply \<^cterm>\<open>Trueprop\<close>
   409                           (Thm.apply (Thm.apply \<^cterm>\<open>(op =)::real \<Rightarrow> _\<close> (mk_numeric x))
   409                           (Thm.apply (Thm.apply \<^cterm>\<open>((=))::real \<Rightarrow> _\<close> (mk_numeric x))
   410                                \<^cterm>\<open>0::real\<close>)))
   410                                \<^cterm>\<open>0::real\<close>)))
   411           | Rational_le x => eqT_elim(numeric_ge_conv(Thm.apply \<^cterm>\<open>Trueprop\<close>
   411           | Rational_le x => eqT_elim(numeric_ge_conv(Thm.apply \<^cterm>\<open>Trueprop\<close>
   412                           (Thm.apply (Thm.apply \<^cterm>\<open>(op \<le>)::real \<Rightarrow> _\<close>
   412                           (Thm.apply (Thm.apply \<^cterm>\<open>((\<le>))::real \<Rightarrow> _\<close>
   413                                      \<^cterm>\<open>0::real\<close>) (mk_numeric x))))
   413                                      \<^cterm>\<open>0::real\<close>) (mk_numeric x))))
   414           | Rational_lt x => eqT_elim(numeric_gt_conv(Thm.apply \<^cterm>\<open>Trueprop\<close>
   414           | Rational_lt x => eqT_elim(numeric_gt_conv(Thm.apply \<^cterm>\<open>Trueprop\<close>
   415                       (Thm.apply (Thm.apply \<^cterm>\<open>(op <)::real \<Rightarrow> _\<close> \<^cterm>\<open>0::real\<close>)
   415                       (Thm.apply (Thm.apply \<^cterm>\<open>((<))::real \<Rightarrow> _\<close> \<^cterm>\<open>0::real\<close>)
   416                         (mk_numeric x))))
   416                         (mk_numeric x))))
   417           | Square pt => square_rule (cterm_of_poly pt)
   417           | Square pt => square_rule (cterm_of_poly pt)
   418           | Eqmul(pt,p) => emul_rule (cterm_of_poly pt) (translate p)
   418           | Eqmul(pt,p) => emul_rule (cterm_of_poly pt) (translate p)
   419           | Sum(p1,p2) => add_rule (translate p1) (translate p2)
   419           | Sum(p1,p2) => add_rule (translate p1) (translate p2)
   420           | Product(p1,p2) => mul_rule (translate p1) (translate p2)
   420           | Product(p1,p2) => mul_rule (translate p1) (translate p2)
   426         nnf_conv ctxt then_conv skolemize_conv then_conv prenex_conv then_conv
   426         nnf_conv ctxt then_conv skolemize_conv then_conv prenex_conv then_conv
   427         weak_dnf_conv
   427         weak_dnf_conv
   428 
   428 
   429     val concl = Thm.dest_arg o Thm.cprop_of
   429     val concl = Thm.dest_arg o Thm.cprop_of
   430     fun is_binop opr ct = (Thm.dest_fun2 ct aconvc opr handle CTERM _ => false)
   430     fun is_binop opr ct = (Thm.dest_fun2 ct aconvc opr handle CTERM _ => false)
   431     val is_req = is_binop \<^cterm>\<open>(op =):: real \<Rightarrow> _\<close>
   431     val is_req = is_binop \<^cterm>\<open>((=)):: real \<Rightarrow> _\<close>
   432     val is_ge = is_binop \<^cterm>\<open>(op \<le>):: real \<Rightarrow> _\<close>
   432     val is_ge = is_binop \<^cterm>\<open>((\<le>)):: real \<Rightarrow> _\<close>
   433     val is_gt = is_binop \<^cterm>\<open>(op <):: real \<Rightarrow> _\<close>
   433     val is_gt = is_binop \<^cterm>\<open>((<)):: real \<Rightarrow> _\<close>
   434     val is_conj = is_binop \<^cterm>\<open>HOL.conj\<close>
   434     val is_conj = is_binop \<^cterm>\<open>HOL.conj\<close>
   435     val is_disj = is_binop \<^cterm>\<open>HOL.disj\<close>
   435     val is_disj = is_binop \<^cterm>\<open>HOL.disj\<close>
   436     fun conj_pair th = (th RS @{thm conjunct1}, th RS @{thm conjunct2})
   436     fun conj_pair th = (th RS @{thm conjunct1}, th RS @{thm conjunct2})
   437     fun disj_cases th th1 th2 =
   437     fun disj_cases th th1 th2 =
   438       let
   438       let
   474           else overall cert_choice (th::dun) oths
   474           else overall cert_choice (th::dun) oths
   475         end
   475         end
   476     fun dest_binary b ct =
   476     fun dest_binary b ct =
   477         if is_binop b ct then Thm.dest_binop ct
   477         if is_binop b ct then Thm.dest_binop ct
   478         else raise CTERM ("dest_binary",[b,ct])
   478         else raise CTERM ("dest_binary",[b,ct])
   479     val dest_eq = dest_binary \<^cterm>\<open>(op =) :: real \<Rightarrow> _\<close>
   479     val dest_eq = dest_binary \<^cterm>\<open>((=)) :: real \<Rightarrow> _\<close>
   480     val neq_th = nth pth 5
   480     val neq_th = nth pth 5
   481     fun real_not_eq_conv ct =
   481     fun real_not_eq_conv ct =
   482       let
   482       let
   483         val (l,r) = dest_eq (Thm.dest_arg ct)
   483         val (l,r) = dest_eq (Thm.dest_arg ct)
   484         val th = Thm.instantiate ([],[((("x", 0), \<^typ>\<open>real\<close>),l),((("y", 0), \<^typ>\<open>real\<close>),r)]) neq_th
   484         val th = Thm.instantiate ([],[((("x", 0), \<^typ>\<open>real\<close>),l),((("y", 0), \<^typ>\<open>real\<close>),r)]) neq_th
   485         val th_p = poly_conv(Thm.dest_arg(Thm.dest_arg1(Thm.rhs_of th)))
   485         val th_p = poly_conv(Thm.dest_arg(Thm.dest_arg1(Thm.rhs_of th)))
   486         val th_x = Drule.arg_cong_rule \<^cterm>\<open>uminus :: real \<Rightarrow> _\<close> th_p
   486         val th_x = Drule.arg_cong_rule \<^cterm>\<open>uminus :: real \<Rightarrow> _\<close> th_p
   487         val th_n = fconv_rule (arg_conv poly_neg_conv) th_x
   487         val th_n = fconv_rule (arg_conv poly_neg_conv) th_x
   488         val th' = Drule.binop_cong_rule \<^cterm>\<open>HOL.disj\<close>
   488         val th' = Drule.binop_cong_rule \<^cterm>\<open>HOL.disj\<close>
   489           (Drule.arg_cong_rule (Thm.apply \<^cterm>\<open>(op <)::real \<Rightarrow> _\<close> \<^cterm>\<open>0::real\<close>) th_p)
   489           (Drule.arg_cong_rule (Thm.apply \<^cterm>\<open>((<))::real \<Rightarrow> _\<close> \<^cterm>\<open>0::real\<close>) th_p)
   490           (Drule.arg_cong_rule (Thm.apply \<^cterm>\<open>(op <)::real \<Rightarrow> _\<close> \<^cterm>\<open>0::real\<close>) th_n)
   490           (Drule.arg_cong_rule (Thm.apply \<^cterm>\<open>((<))::real \<Rightarrow> _\<close> \<^cterm>\<open>0::real\<close>) th_n)
   491       in Thm.transitive th th'
   491       in Thm.transitive th th'
   492       end
   492       end
   493     fun equal_implies_1_rule PQ =
   493     fun equal_implies_1_rule PQ =
   494       let
   494       let
   495         val P = Thm.lhs_of PQ
   495         val P = Thm.lhs_of PQ
   681       in
   681       in
   682         if not (is_comb lop) then FuncUtil.Ctermfunc.onefunc (ct, @1)
   682         if not (is_comb lop) then FuncUtil.Ctermfunc.onefunc (ct, @1)
   683         else
   683         else
   684           let val (opr,l) = Thm.dest_comb lop
   684           let val (opr,l) = Thm.dest_comb lop
   685           in
   685           in
   686             if opr aconvc \<^cterm>\<open>op + :: real \<Rightarrow> _\<close>
   686             if opr aconvc \<^cterm>\<open>(+) :: real \<Rightarrow> _\<close>
   687             then linear_add (lin_of_hol l) (lin_of_hol r)
   687             then linear_add (lin_of_hol l) (lin_of_hol r)
   688             else if opr aconvc \<^cterm>\<open>op * :: real \<Rightarrow> _\<close>
   688             else if opr aconvc \<^cterm>\<open>( * ) :: real \<Rightarrow> _\<close>
   689                     andalso is_ratconst l then FuncUtil.Ctermfunc.onefunc (r, dest_ratconst l)
   689                     andalso is_ratconst l then FuncUtil.Ctermfunc.onefunc (r, dest_ratconst l)
   690             else FuncUtil.Ctermfunc.onefunc (ct, @1)
   690             else FuncUtil.Ctermfunc.onefunc (ct, @1)
   691           end
   691           end
   692       end
   692       end
   693 
   693