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