src/HOL/Library/positivstellensatz.ML
changeset 60801 7664e0916eec
parent 60642 48dd1cefb4ae
child 60949 ccbf9379e355
equal deleted inserted replaced
60799:57dd0b45fc21 60801:7664e0916eec
   315     _$_ => (find_cterm p (Thm.dest_fun t) handle CTERM _ => find_cterm p (Thm.dest_arg t))
   315     _$_ => (find_cterm p (Thm.dest_fun t) handle CTERM _ => find_cterm p (Thm.dest_arg t))
   316   | Abs (_,_,_) => find_cterm p (Thm.dest_abs NONE t |> snd)
   316   | Abs (_,_,_) => find_cterm p (Thm.dest_abs NONE t |> snd)
   317   | _ => raise CTERM ("find_cterm",[t]);
   317   | _ => raise CTERM ("find_cterm",[t]);
   318 
   318 
   319     (* Some conversions-related stuff which has been forbidden entrance into Pure/conv.ML*)
   319     (* Some conversions-related stuff which has been forbidden entrance into Pure/conv.ML*)
   320 fun instantiate_cterm' ty tms = Drule.cterm_rule (Drule.instantiate' ty tms)
   320 fun instantiate_cterm' ty tms = Drule.cterm_rule (Thm.instantiate' ty tms)
   321 fun is_comb t = (case Thm.term_of t of _ $ _ => true | _ => false);
   321 fun is_comb t = (case Thm.term_of t of _ $ _ => true | _ => false);
   322 
   322 
   323 fun is_binop ct ct' = ct aconvc (Thm.dest_fun (Thm.dest_fun ct'))
   323 fun is_binop ct ct' = ct aconvc (Thm.dest_fun (Thm.dest_fun ct'))
   324   handle CTERM _ => false;
   324   handle CTERM _ => false;
   325 
   325 
   394     fun mul_rule th th' = fconv_rule (arg_conv (oprconv poly_mul_conv))
   394     fun mul_rule th th' = fconv_rule (arg_conv (oprconv poly_mul_conv))
   395          (match_mp_rule pth_mul [th, th'])
   395          (match_mp_rule pth_mul [th, th'])
   396     fun add_rule th th' = fconv_rule (arg_conv (oprconv poly_add_conv))
   396     fun add_rule th th' = fconv_rule (arg_conv (oprconv poly_add_conv))
   397          (match_mp_rule pth_add [th, th'])
   397          (match_mp_rule pth_add [th, th'])
   398     fun emul_rule ct th = fconv_rule (arg_conv (oprconv poly_mul_conv))
   398     fun emul_rule ct th = fconv_rule (arg_conv (oprconv poly_mul_conv))
   399        (instantiate' [] [SOME ct] (th RS pth_emul))
   399        (Thm.instantiate' [] [SOME ct] (th RS pth_emul))
   400     fun square_rule t = fconv_rule (arg_conv (oprconv poly_conv))
   400     fun square_rule t = fconv_rule (arg_conv (oprconv poly_conv))
   401        (instantiate' [] [SOME t] pth_square)
   401        (Thm.instantiate' [] [SOME t] pth_square)
   402 
   402 
   403     fun hol_of_positivstellensatz(eqs,les,lts) proof =
   403     fun hol_of_positivstellensatz(eqs,les,lts) proof =
   404       let
   404       let
   405         fun translate prf =
   405         fun translate prf =
   406           case prf of
   406           case prf of
   442         val c = concl th1
   442         val c = concl th1
   443         val _ =
   443         val _ =
   444           if c aconvc (concl th2) then ()
   444           if c aconvc (concl th2) then ()
   445           else error "disj_cases : conclusions not alpha convertible"
   445           else error "disj_cases : conclusions not alpha convertible"
   446       in Thm.implies_elim (Thm.implies_elim
   446       in Thm.implies_elim (Thm.implies_elim
   447           (Thm.implies_elim (instantiate' [] (map SOME [p,q,c]) @{thm disjE}) th)
   447           (Thm.implies_elim (Thm.instantiate' [] (map SOME [p,q,c]) @{thm disjE}) th)
   448           (Thm.implies_intr (Thm.apply @{cterm Trueprop} p) th1))
   448           (Thm.implies_intr (Thm.apply @{cterm Trueprop} p) th1))
   449         (Thm.implies_intr (Thm.apply @{cterm Trueprop} q) th2)
   449         (Thm.implies_intr (Thm.apply @{cterm Trueprop} q) th2)
   450       end
   450       end
   451     fun overall cert_choice dun ths =
   451     fun overall cert_choice dun ths =
   452       case ths of
   452       case ths of
   516     fun mk_forall x th =
   516     fun mk_forall x th =
   517       Drule.arg_cong_rule
   517       Drule.arg_cong_rule
   518         (instantiate_cterm' [SOME (Thm.ctyp_of_cterm x)] [] @{cpat "All :: (?'a => bool) => _" })
   518         (instantiate_cterm' [SOME (Thm.ctyp_of_cterm x)] [] @{cpat "All :: (?'a => bool) => _" })
   519         (Thm.abstract_rule (name_of x) x th)
   519         (Thm.abstract_rule (name_of x) x th)
   520 
   520 
   521     val specl = fold_rev (fn x => fn th => instantiate' [] [SOME x] (th RS spec));
   521     val specl = fold_rev (fn x => fn th => Thm.instantiate' [] [SOME x] (th RS spec));
   522 
   522 
   523     fun ext T = Drule.cterm_rule (instantiate' [SOME T] []) @{cpat Ex}
   523     fun ext T = Drule.cterm_rule (Thm.instantiate' [SOME T] []) @{cpat Ex}
   524     fun mk_ex v t = Thm.apply (ext (Thm.ctyp_of_cterm v)) (Thm.lambda v t)
   524     fun mk_ex v t = Thm.apply (ext (Thm.ctyp_of_cterm v)) (Thm.lambda v t)
   525 
   525 
   526     fun choose v th th' =
   526     fun choose v th th' =
   527       case Thm.concl_of th of
   527       case Thm.concl_of th of
   528         @{term Trueprop} $ (Const(@{const_name Ex},_)$_) =>
   528         @{term Trueprop} $ (Const(@{const_name Ex},_)$_) =>
   529         let
   529         let
   530           val p = (funpow 2 Thm.dest_arg o Thm.cprop_of) th
   530           val p = (funpow 2 Thm.dest_arg o Thm.cprop_of) th
   531           val T = (hd o Thm.dest_ctyp o Thm.ctyp_of_cterm) p
   531           val T = (hd o Thm.dest_ctyp o Thm.ctyp_of_cterm) p
   532           val th0 = fconv_rule (Thm.beta_conversion true)
   532           val th0 = fconv_rule (Thm.beta_conversion true)
   533             (instantiate' [SOME T] [SOME p, (SOME o Thm.dest_arg o Thm.cprop_of) th'] exE)
   533             (Thm.instantiate' [SOME T] [SOME p, (SOME o Thm.dest_arg o Thm.cprop_of) th'] exE)
   534           val pv = (Thm.rhs_of o Thm.beta_conversion true)
   534           val pv = (Thm.rhs_of o Thm.beta_conversion true)
   535             (Thm.apply @{cterm Trueprop} (Thm.apply p v))
   535             (Thm.apply @{cterm Trueprop} (Thm.apply p v))
   536           val th1 = Thm.forall_intr v (Thm.implies_intr pv th')
   536           val th1 = Thm.forall_intr v (Thm.implies_intr pv th')
   537         in Thm.implies_elim (Thm.implies_elim th0 th) th1  end
   537         in Thm.implies_elim (Thm.implies_elim th0 th) th1  end
   538       | _ => raise THM ("choose",0,[th, th'])
   538       | _ => raise THM ("choose",0,[th, th'])
   577             val th3 =
   577             val th3 =
   578               fold simple_choose evs
   578               fold simple_choose evs
   579                 (prove_hyp (Thm.equal_elim th1 (Thm.assume (Thm.apply @{cterm Trueprop} bod))) th2)
   579                 (prove_hyp (Thm.equal_elim th1 (Thm.assume (Thm.apply @{cterm Trueprop} bod))) th2)
   580           in (Drule.implies_intr_hyps (prove_hyp (Thm.equal_elim th0 (Thm.assume nct)) th3), certs)
   580           in (Drule.implies_intr_hyps (prove_hyp (Thm.equal_elim th0 (Thm.assume nct)) th3), certs)
   581           end
   581           end
   582       in (Thm.implies_elim (instantiate' [] [SOME ct] pth_final) th, certificates)
   582       in (Thm.implies_elim (Thm.instantiate' [] [SOME ct] pth_final) th, certificates)
   583       end
   583       end
   584   in f
   584   in f
   585   end;
   585   end;
   586 
   586 
   587 (* A linear arithmetic prover *)
   587 (* A linear arithmetic prover *)
   708     val aliens = filter is_alien
   708     val aliens = filter is_alien
   709       (fold_rev (union (op aconvc) o FuncUtil.Ctermfunc.dom)
   709       (fold_rev (union (op aconvc) o FuncUtil.Ctermfunc.dom)
   710                 (eq_pols @ le_pols @ lt_pols) [])
   710                 (eq_pols @ le_pols @ lt_pols) [])
   711     val le_pols' = le_pols @ map (fn v => FuncUtil.Ctermfunc.onefunc (v,Rat.one)) aliens
   711     val le_pols' = le_pols @ map (fn v => FuncUtil.Ctermfunc.onefunc (v,Rat.one)) aliens
   712     val (_,proof) = linear_prover (eq_pols,le_pols',lt_pols)
   712     val (_,proof) = linear_prover (eq_pols,le_pols',lt_pols)
   713     val le' = le @ map (fn a => instantiate' [] [SOME (Thm.dest_arg a)] @{thm real_of_nat_ge_zero}) aliens
   713     val le' = le @ map (fn a => Thm.instantiate' [] [SOME (Thm.dest_arg a)] @{thm real_of_nat_ge_zero}) aliens
   714   in ((translator (eq,le',lt) proof), Trivial)
   714   in ((translator (eq,le',lt) proof), Trivial)
   715   end
   715   end
   716 end;
   716 end;
   717 
   717 
   718 (* A less general generic arithmetic prover dealing with abs,max and min*)
   718 (* A less general generic arithmetic prover dealing with abs,max and min*)
   723   fun absmaxmin_elim_conv1 ctxt =
   723   fun absmaxmin_elim_conv1 ctxt =
   724     Simplifier.rewrite (put_simpset absmaxmin_elim_ss1 ctxt)
   724     Simplifier.rewrite (put_simpset absmaxmin_elim_ss1 ctxt)
   725 
   725 
   726   val absmaxmin_elim_conv2 =
   726   val absmaxmin_elim_conv2 =
   727     let
   727     let
   728       val pth_abs = instantiate' [SOME @{ctyp real}] [] abs_split'
   728       val pth_abs = Thm.instantiate' [SOME @{ctyp real}] [] abs_split'
   729       val pth_max = instantiate' [SOME @{ctyp real}] [] max_split
   729       val pth_max = Thm.instantiate' [SOME @{ctyp real}] [] max_split
   730       val pth_min = instantiate' [SOME @{ctyp real}] [] min_split
   730       val pth_min = Thm.instantiate' [SOME @{ctyp real}] [] min_split
   731       val abs_tm = @{cterm "abs :: real => _"}
   731       val abs_tm = @{cterm "abs :: real => _"}
   732       val p_v = (("P", 0), @{typ "real \<Rightarrow> bool"})
   732       val p_v = (("P", 0), @{typ "real \<Rightarrow> bool"})
   733       val x_v = (("x", 0), @{typ real})
   733       val x_v = (("x", 0), @{typ real})
   734       val y_v = (("y", 0), @{typ real})
   734       val y_v = (("y", 0), @{typ real})
   735       val is_max = is_binop @{cterm "max :: real => _"}
   735       val is_max = is_binop @{cterm "max :: real => _"}