src/HOL/Tools/groebner.ML
changeset 46497 89ccf66aa73d
parent 42793 88bee9f6eec7
child 47432 e1576d13e933
equal deleted inserted replaced
46496:b8920f3fd259 46497:89ccf66aa73d
   393     (refute_disj rfn (Thm.dest_arg tm), 2,
   393     (refute_disj rfn (Thm.dest_arg tm), 2,
   394       Drule.compose_single (refute_disj rfn (Thm.dest_arg1 tm), 2, disjE))
   394       Drule.compose_single (refute_disj rfn (Thm.dest_arg1 tm), 2, disjE))
   395   | _ => rfn tm ;
   395   | _ => rfn tm ;
   396 
   396 
   397 val notnotD = @{thm notnotD};
   397 val notnotD = @{thm notnotD};
   398 fun mk_binop ct x y = Thm.capply (Thm.capply ct x) y
   398 fun mk_binop ct x y = Thm.apply (Thm.apply ct x) y
   399 
   399 
   400 fun is_neg t =
   400 fun is_neg t =
   401     case term_of t of
   401     case term_of t of
   402       (Const(@{const_name Not},_)$p) => true
   402       (Const(@{const_name Not},_)$p) => true
   403     | _  => false;
   403     | _  => false;
   449 val specl = fold_rev (fn x => fn th => instantiate' [] [SOME x] (th RS spec));
   449 val specl = fold_rev (fn x => fn th => instantiate' [] [SOME x] (th RS spec));
   450 
   450 
   451 val cTrp = @{cterm "Trueprop"};
   451 val cTrp = @{cterm "Trueprop"};
   452 val cConj = @{cterm HOL.conj};
   452 val cConj = @{cterm HOL.conj};
   453 val (cNot,false_tm) = (@{cterm "Not"}, @{cterm "False"});
   453 val (cNot,false_tm) = (@{cterm "Not"}, @{cterm "False"});
   454 val assume_Trueprop = Thm.capply cTrp #> Thm.assume;
   454 val assume_Trueprop = Thm.apply cTrp #> Thm.assume;
   455 val list_mk_conj = list_mk_binop cConj;
   455 val list_mk_conj = list_mk_binop cConj;
   456 val conjs = list_dest_binop cConj;
   456 val conjs = list_dest_binop cConj;
   457 val mk_neg = Thm.capply cNot;
   457 val mk_neg = Thm.apply cNot;
   458 
   458 
   459 fun striplist dest =
   459 fun striplist dest =
   460  let
   460  let
   461   fun h acc x = case try dest x of
   461   fun h acc x = case try dest x of
   462     SOME (a,b) => h (h acc b) a
   462     SOME (a,b) => h (h acc b) a
   463   | NONE => x::acc
   463   | NONE => x::acc
   464  in h [] end;
   464  in h [] end;
   465 fun list_mk_binop b = foldr1 (fn (s,t) => Thm.capply (Thm.capply b s) t);
   465 fun list_mk_binop b = foldr1 (fn (s,t) => Thm.apply (Thm.apply b s) t);
   466 
   466 
   467 val eq_commute = mk_meta_eq @{thm eq_commute};
   467 val eq_commute = mk_meta_eq @{thm eq_commute};
   468 
   468 
   469 fun sym_conv eq =
   469 fun sym_conv eq =
   470  let val (l,r) = Thm.dest_binop eq
   470  let val (l,r) = Thm.dest_binop eq
   477   @{term HOL.conj}$_$_ => (Thm.dest_arg1 ct)::(conjuncts (Thm.dest_arg ct))
   477   @{term HOL.conj}$_$_ => (Thm.dest_arg1 ct)::(conjuncts (Thm.dest_arg ct))
   478 | _ => [ct];
   478 | _ => [ct];
   479 
   479 
   480 fun fold1 f = foldr1 (uncurry f);
   480 fun fold1 f = foldr1 (uncurry f);
   481 
   481 
   482 val list_conj = fold1 (fn c => fn c' => Thm.capply (Thm.capply @{cterm HOL.conj} c) c') ;
   482 val list_conj = fold1 (fn c => fn c' => Thm.apply (Thm.apply @{cterm HOL.conj} c) c') ;
   483 
   483 
   484 fun mk_conj_tab th =
   484 fun mk_conj_tab th =
   485  let fun h acc th =
   485  let fun h acc th =
   486    case prop_of th of
   486    case prop_of th of
   487    @{term "Trueprop"}$(@{term HOL.conj}$p$q) =>
   487    @{term "Trueprop"}$(@{term HOL.conj}$p$q) =>
   498  | c::cs => conjI OF [prove_conj tab [c], prove_conj tab cs];
   498  | c::cs => conjI OF [prove_conj tab [c], prove_conj tab cs];
   499 
   499 
   500 fun conj_ac_rule eq =
   500 fun conj_ac_rule eq =
   501  let
   501  let
   502   val (l,r) = Thm.dest_equals eq
   502   val (l,r) = Thm.dest_equals eq
   503   val ctabl = mk_conj_tab (Thm.assume (Thm.capply @{cterm Trueprop} l))
   503   val ctabl = mk_conj_tab (Thm.assume (Thm.apply @{cterm Trueprop} l))
   504   val ctabr = mk_conj_tab (Thm.assume (Thm.capply @{cterm Trueprop} r))
   504   val ctabr = mk_conj_tab (Thm.assume (Thm.apply @{cterm Trueprop} r))
   505   fun tabl c = the (Termtab.lookup ctabl (term_of c))
   505   fun tabl c = the (Termtab.lookup ctabl (term_of c))
   506   fun tabr c = the (Termtab.lookup ctabr (term_of c))
   506   fun tabr c = the (Termtab.lookup ctabr (term_of c))
   507   val thl  = prove_conj tabl (conjuncts r) |> implies_intr_hyps
   507   val thl  = prove_conj tabl (conjuncts r) |> implies_intr_hyps
   508   val thr  = prove_conj tabr (conjuncts l) |> implies_intr_hyps
   508   val thr  = prove_conj tabr (conjuncts l) |> implies_intr_hyps
   509   val eqI = instantiate' [] [SOME l, SOME r] @{thm iffI}
   509   val eqI = instantiate' [] [SOME l, SOME r] @{thm iffI}
   512  (* END FIXME.*)
   512  (* END FIXME.*)
   513 
   513 
   514    (* Conversion for the equivalence of existential statements where
   514    (* Conversion for the equivalence of existential statements where
   515       EX quantifiers are rearranged differently *)
   515       EX quantifiers are rearranged differently *)
   516  fun ext T = Drule.cterm_rule (instantiate' [SOME T] []) @{cpat Ex}
   516  fun ext T = Drule.cterm_rule (instantiate' [SOME T] []) @{cpat Ex}
   517  fun mk_ex v t = Thm.capply (ext (ctyp_of_term v)) (Thm.cabs v t)
   517  fun mk_ex v t = Thm.apply (ext (ctyp_of_term v)) (Thm.lambda v t)
   518 
   518 
   519 fun choose v th th' = case concl_of th of
   519 fun choose v th th' = case concl_of th of
   520   @{term Trueprop} $ (Const(@{const_name Ex},_)$_) =>
   520   @{term Trueprop} $ (Const(@{const_name Ex},_)$_) =>
   521    let
   521    let
   522     val p = (funpow 2 Thm.dest_arg o cprop_of) th
   522     val p = (funpow 2 Thm.dest_arg o cprop_of) th
   523     val T = (hd o Thm.dest_ctyp o ctyp_of_term) p
   523     val T = (hd o Thm.dest_ctyp o ctyp_of_term) p
   524     val th0 = Conv.fconv_rule (Thm.beta_conversion true)
   524     val th0 = Conv.fconv_rule (Thm.beta_conversion true)
   525         (instantiate' [SOME T] [SOME p, (SOME o Thm.dest_arg o cprop_of) th'] exE)
   525         (instantiate' [SOME T] [SOME p, (SOME o Thm.dest_arg o cprop_of) th'] exE)
   526     val pv = (Thm.rhs_of o Thm.beta_conversion true)
   526     val pv = (Thm.rhs_of o Thm.beta_conversion true)
   527           (Thm.capply @{cterm Trueprop} (Thm.capply p v))
   527           (Thm.apply @{cterm Trueprop} (Thm.apply p v))
   528     val th1 = Thm.forall_intr v (Thm.implies_intr pv th')
   528     val th1 = Thm.forall_intr v (Thm.implies_intr pv th')
   529    in Thm.implies_elim (Thm.implies_elim th0 th) th1  end
   529    in Thm.implies_elim (Thm.implies_elim th0 th) th1  end
   530 | _ => error ""  (* FIXME ? *)
   530 | _ => error ""  (* FIXME ? *)
   531 
   531 
   532 fun simple_choose v th =
   532 fun simple_choose v th =
   533    choose v (Thm.assume ((Thm.capply @{cterm Trueprop} o mk_ex v)
   533    choose v (Thm.assume ((Thm.apply @{cterm Trueprop} o mk_ex v)
   534     ((Thm.dest_arg o hd o #hyps o Thm.crep_thm) th))) th
   534     ((Thm.dest_arg o hd o #hyps o Thm.crep_thm) th))) th
   535 
   535 
   536 
   536 
   537  fun mkexi v th =
   537  fun mkexi v th =
   538   let
   538   let
   539    val p = Thm.cabs v (Thm.dest_arg (Thm.cprop_of th))
   539    val p = Thm.lambda v (Thm.dest_arg (Thm.cprop_of th))
   540   in Thm.implies_elim
   540   in Thm.implies_elim
   541     (Conv.fconv_rule (Thm.beta_conversion true)
   541     (Conv.fconv_rule (Thm.beta_conversion true)
   542       (instantiate' [SOME (ctyp_of_term v)] [SOME p, SOME v] @{thm exI}))
   542       (instantiate' [SOME (ctyp_of_term v)] [SOME p, SOME v] @{thm exI}))
   543       th
   543       th
   544   end
   544   end
   545  fun ex_eq_conv t =
   545  fun ex_eq_conv t =
   546   let
   546   let
   547   val (p0,q0) = Thm.dest_binop t
   547   val (p0,q0) = Thm.dest_binop t
   548   val (vs',P) = strip_exists p0
   548   val (vs',P) = strip_exists p0
   549   val (vs,_) = strip_exists q0
   549   val (vs,_) = strip_exists q0
   550    val th = Thm.assume (Thm.capply @{cterm Trueprop} P)
   550    val th = Thm.assume (Thm.apply @{cterm Trueprop} P)
   551    val th1 = implies_intr_hyps (fold simple_choose vs' (fold mkexi vs th))
   551    val th1 = implies_intr_hyps (fold simple_choose vs' (fold mkexi vs th))
   552    val th2 = implies_intr_hyps (fold simple_choose vs (fold mkexi vs' th))
   552    val th2 = implies_intr_hyps (fold simple_choose vs (fold mkexi vs' th))
   553    val p = (Thm.dest_arg o Thm.dest_arg1 o cprop_of) th1
   553    val p = (Thm.dest_arg o Thm.dest_arg1 o cprop_of) th1
   554    val q = (Thm.dest_arg o Thm.dest_arg o cprop_of) th1
   554    val q = (Thm.dest_arg o Thm.dest_arg o cprop_of) th1
   555   in Thm.implies_elim (Thm.implies_elim (instantiate' [] [SOME p, SOME q] iffI) th1) th2
   555   in Thm.implies_elim (Thm.implies_elim (instantiate' [] [SOME p, SOME q] iffI) th1) th2
   559 
   559 
   560  fun getname v = case term_of v of
   560  fun getname v = case term_of v of
   561   Free(s,_) => s
   561   Free(s,_) => s
   562  | Var ((s,_),_) => s
   562  | Var ((s,_),_) => s
   563  | _ => "x"
   563  | _ => "x"
   564  fun mk_eq s t = Thm.capply (Thm.capply @{cterm "op == :: bool => _"} s) t
   564  fun mk_eq s t = Thm.apply (Thm.apply @{cterm "op == :: bool => _"} s) t
   565  fun mkeq s t = Thm.capply @{cterm Trueprop} (Thm.capply (Thm.capply @{cterm "op = :: bool => _"} s) t)
   565  fun mkeq s t = Thm.apply @{cterm Trueprop} (Thm.apply (Thm.apply @{cterm "op = :: bool => _"} s) t)
   566  fun mk_exists v th = Drule.arg_cong_rule (ext (ctyp_of_term v))
   566  fun mk_exists v th = Drule.arg_cong_rule (ext (ctyp_of_term v))
   567    (Thm.abstract_rule (getname v) v th)
   567    (Thm.abstract_rule (getname v) v th)
   568  val simp_ex_conv =
   568  val simp_ex_conv =
   569      Simplifier.rewrite (HOL_basic_ss addsimps @{thms simp_thms(39)})
   569      Simplifier.rewrite (HOL_basic_ss addsimps @{thms simp_thms(39)})
   570 
   570 
   571 fun frees t = Thm.add_cterm_frees t [];
   571 fun frees t = Thm.add_cterm_frees t [];
   572 fun free_in v t = member op aconvc (frees t) v;
   572 fun free_in v t = member op aconvc (frees t) v;
   573 
   573 
   574 val vsubst = let
   574 val vsubst = let
   575  fun vsubst (t,v) tm =
   575  fun vsubst (t,v) tm =
   576    (Thm.rhs_of o Thm.beta_conversion false) (Thm.capply (Thm.cabs v tm) t)
   576    (Thm.rhs_of o Thm.beta_conversion false) (Thm.apply (Thm.lambda v tm) t)
   577 in fold vsubst end;
   577 in fold vsubst end;
   578 
   578 
   579 
   579 
   580 (** main **)
   580 (** main **)
   581 
   581 
   605     let val (l,r) = Thm.dest_comb t
   605     let val (l,r) = Thm.dest_comb t
   606     in if Term.could_unify(term_of l,term_of ring_neg_tm) then r
   606     in if Term.could_unify(term_of l,term_of ring_neg_tm) then r
   607        else raise CTERM ("ring_dest_neg", [t])
   607        else raise CTERM ("ring_dest_neg", [t])
   608     end
   608     end
   609 
   609 
   610  val ring_mk_neg = fn tm => Thm.capply (ring_neg_tm) (tm);
   610  val ring_mk_neg = fn tm => Thm.apply (ring_neg_tm) (tm);
   611  fun field_dest_inv t =
   611  fun field_dest_inv t =
   612     let val (l,r) = Thm.dest_comb t in
   612     let val (l,r) = Thm.dest_comb t in
   613         if Term.could_unify(term_of l, term_of field_inv_tm) then r
   613         if Term.could_unify(term_of l, term_of field_inv_tm) then r
   614         else raise CTERM ("field_dest_inv", [t])
   614         else raise CTERM ("field_dest_inv", [t])
   615     end
   615     end
   725       val th2 =
   725       val th2 =
   726         Conv.fconv_rule
   726         Conv.fconv_rule
   727           ((Conv.arg_conv #> Conv.arg_conv) (Conv.binop_conv ring_normalize_conv)) th1
   727           ((Conv.arg_conv #> Conv.arg_conv) (Conv.binop_conv ring_normalize_conv)) th1
   728       val conc = th2 |> concl |> Thm.dest_arg
   728       val conc = th2 |> concl |> Thm.dest_arg
   729       val (l,r) = conc |> dest_eq
   729       val (l,r) = conc |> dest_eq
   730     in Thm.implies_intr (Thm.capply cTrp tm)
   730     in Thm.implies_intr (Thm.apply cTrp tm)
   731                     (Thm.equal_elim (Drule.arg_cong_rule cTrp (eqF_intr th2))
   731                     (Thm.equal_elim (Drule.arg_cong_rule cTrp (eqF_intr th2))
   732                            (Thm.reflexive l |> mk_object_eq))
   732                            (Thm.reflexive l |> mk_object_eq))
   733     end
   733     end
   734    else
   734    else
   735    let
   735    let
   756     val  herts_pos = map (fn (i,p) => (i,holify_polynomial vars p)) cert_pos
   756     val  herts_pos = map (fn (i,p) => (i,holify_polynomial vars p)) cert_pos
   757     val  herts_neg = map (fn (i,p) => (i,holify_polynomial vars p)) cert_neg
   757     val  herts_neg = map (fn (i,p) => (i,holify_polynomial vars p)) cert_neg
   758     fun thm_fn pols =
   758     fun thm_fn pols =
   759         if null pols then Thm.reflexive(mk_const rat_0) else
   759         if null pols then Thm.reflexive(mk_const rat_0) else
   760         end_itlist mk_add
   760         end_itlist mk_add
   761             (map (fn (i,p) => Drule.arg_cong_rule (Thm.capply ring_mul_tm p)
   761             (map (fn (i,p) => Drule.arg_cong_rule (Thm.apply ring_mul_tm p)
   762               (nth eths i |> mk_meta_eq)) pols)
   762               (nth eths i |> mk_meta_eq)) pols)
   763     val th1 = thm_fn herts_pos
   763     val th1 = thm_fn herts_pos
   764     val th2 = thm_fn herts_neg
   764     val th2 = thm_fn herts_neg
   765     val th3 = HOLogic.conj_intr(mk_add (Thm.symmetric th1) th2 |> mk_object_eq) noteqth
   765     val th3 = HOLogic.conj_intr(mk_add (Thm.symmetric th1) th2 |> mk_object_eq) noteqth
   766     val th4 =
   766     val th4 =
   767       Conv.fconv_rule ((Conv.arg_conv o Conv.arg_conv o Conv.binop_conv) ring_normalize_conv)
   767       Conv.fconv_rule ((Conv.arg_conv o Conv.arg_conv o Conv.binop_conv) ring_normalize_conv)
   768         (neq_rule l th3)
   768         (neq_rule l th3)
   769     val (l,r) = dest_eq(Thm.dest_arg(concl th4))
   769     val (l,r) = dest_eq(Thm.dest_arg(concl th4))
   770    in Thm.implies_intr (Thm.capply cTrp tm)
   770    in Thm.implies_intr (Thm.apply cTrp tm)
   771                         (Thm.equal_elim (Drule.arg_cong_rule cTrp (eqF_intr th4))
   771                         (Thm.equal_elim (Drule.arg_cong_rule cTrp (eqF_intr th4))
   772                    (Thm.reflexive l |> mk_object_eq))
   772                    (Thm.reflexive l |> mk_object_eq))
   773    end
   773    end
   774   end) handle ERROR _ => raise CTERM ("Groebner-refute: unable to refute",[tm]))
   774   end) handle ERROR _ => raise CTERM ("Groebner-refute: unable to refute",[tm]))
   775 
   775 
   776 fun ring tm =
   776 fun ring tm =
   777  let
   777  let
   778   fun mk_forall x p =
   778   fun mk_forall x p =
   779     Thm.capply
   779     Thm.apply
   780       (Drule.cterm_rule (instantiate' [SOME (ctyp_of_term x)] [])
   780       (Drule.cterm_rule (instantiate' [SOME (ctyp_of_term x)] [])
   781         @{cpat "All:: (?'a => bool) => _"}) (Thm.cabs x p)
   781         @{cpat "All:: (?'a => bool) => _"}) (Thm.lambda x p)
   782   val avs = Thm.add_cterm_frees tm []
   782   val avs = Thm.add_cterm_frees tm []
   783   val P' = fold mk_forall avs tm
   783   val P' = fold mk_forall avs tm
   784   val th1 = initial_conv(mk_neg P')
   784   val th1 = initial_conv(mk_neg P')
   785   val (evs,bod) = strip_exists(concl th1) in
   785   val (evs,bod) = strip_exists(concl th1) in
   786    if is_forall bod then raise CTERM("ring: non-universal formula",[tm])
   786    if is_forall bod then raise CTERM("ring: non-universal formula",[tm])
   890   val (cmons,vmons) =
   890   val (cmons,vmons) =
   891     List.partition (fn m => null (inter (op aconvc) vars (frees m)))
   891     List.partition (fn m => null (inter (op aconvc) vars (frees m)))
   892                    (striplist ring_dest_add tm)
   892                    (striplist ring_dest_add tm)
   893   val cofactors = map (fn v => find_multipliers v vmons) vars
   893   val cofactors = map (fn v => find_multipliers v vmons) vars
   894   val cnc = if null cmons then zero_tm
   894   val cnc = if null cmons then zero_tm
   895              else Thm.capply ring_neg_tm
   895              else Thm.apply ring_neg_tm
   896                     (list_mk_binop ring_add_tm cmons)
   896                     (list_mk_binop ring_add_tm cmons)
   897   in (cofactors,cnc)
   897   in (cofactors,cnc)
   898   end;
   898   end;
   899 
   899 
   900 fun isolate_variables evs ps eq =
   900 fun isolate_variables evs ps eq =