src/HOL/Tools/lin_arith.ML
changeset 75879 24b17460ee60
parent 75878 fcd118d9242f
child 78800 0b3700d31758
equal deleted inserted replaced
75878:fcd118d9242f 75879:24b17460ee60
   101    discrete = discrete});
   101    discrete = discrete});
   102 
   102 
   103 val split_limit = Attrib.setup_config_int \<^binding>\<open>linarith_split_limit\<close> (K 9);
   103 val split_limit = Attrib.setup_config_int \<^binding>\<open>linarith_split_limit\<close> (K 9);
   104 val neq_limit = Attrib.setup_config_int \<^binding>\<open>linarith_neq_limit\<close> (K 9);
   104 val neq_limit = Attrib.setup_config_int \<^binding>\<open>linarith_neq_limit\<close> (K 9);
   105 val trace = Attrib.setup_config_bool \<^binding>\<open>linarith_trace\<close> (K false);
   105 val trace = Attrib.setup_config_bool \<^binding>\<open>linarith_trace\<close> (K false);
       
   106 
       
   107 fun nnf_simpset ctxt =
       
   108   (empty_simpset ctxt
       
   109     |> Simplifier.set_mkeqTrue mk_eq_True
       
   110     |> Simplifier.set_mksimps (mksimps mksimps_pairs))
       
   111   addsimps @{thms imp_conv_disj iff_conv_conj_imp de_Morgan_disj
       
   112     de_Morgan_conj not_all not_ex not_not}
       
   113 
       
   114 fun prem_nnf_tac ctxt = full_simp_tac (nnf_simpset ctxt)
   106 
   115 
   107 
   116 
   108 structure LA_Data: LIN_ARITH_DATA =
   117 structure LA_Data: LIN_ARITH_DATA =
   109 struct
   118 struct
   110 
   119 
   762     val result = filter_out (negated_term_occurs_positively o snd) beta_eta_norm
   771     val result = filter_out (negated_term_occurs_positively o snd) beta_eta_norm
   763   in
   772   in
   764     result
   773     result
   765   end;
   774   end;
   766 
   775 
       
   776 
   767 (* takes the i-th subgoal  [| A1; ...; An |] ==> B  to                       *)
   777 (* takes the i-th subgoal  [| A1; ...; An |] ==> B  to                       *)
   768 (* An --> ... --> A1 --> B,  performs splitting with the given 'split_thms'  *)
   778 (* An --> ... --> A1 --> B,  performs splitting with the given 'split_thms'  *)
   769 (* (resulting in a different subgoal P), takes  P  to  ~P ==> False,         *)
   779 (* (resulting in a different subgoal P), takes  P  to  ~P ==> False,         *)
   770 (* performs NNF-normalization of ~P, and eliminates conjunctions,            *)
   780 (* performs NNF-normalization of ~P, and eliminates conjunctions,            *)
   771 (* disjunctions and existential quantifiers from the premises, possibly (in  *)
   781 (* disjunctions and existential quantifiers from the premises, possibly (in  *)
   772 (* the case of disjunctions) resulting in several new subgoals, each of the  *)
   782 (* the case of disjunctions) resulting in several new subgoals, each of the  *)
   773 (* general form  [| Q1; ...; Qm |] ==> False.  Fails if more than            *)
   783 (* general form  [| Q1; ...; Qm |] ==> False.  Fails if more than            *)
   774 (* !split_limit splits are possible.                              *)
   784 (* !split_limit splits are possible.                              *)
   775 
       
   776 local
       
   777   fun nnf_simpset ctxt =
       
   778     (empty_simpset ctxt
       
   779       |> Simplifier.set_mkeqTrue mk_eq_True
       
   780       |> Simplifier.set_mksimps (mksimps mksimps_pairs))
       
   781     addsimps [@{thm imp_conv_disj}, @{thm iff_conv_conj_imp}, @{thm de_Morgan_disj},
       
   782       @{thm de_Morgan_conj}, not_all, not_ex, not_not]
       
   783   fun prem_nnf_tac ctxt = full_simp_tac (nnf_simpset ctxt)
       
   784 in
       
   785 
   785 
   786 fun split_once_tac ctxt split_thms =
   786 fun split_once_tac ctxt split_thms =
   787   let
   787   let
   788     val thy = Proof_Context.theory_of ctxt
   788     val thy = Proof_Context.theory_of ctxt
   789     val cond_split_tac = SUBGOAL (fn (subgoal, i) =>
   789     val cond_split_tac = SUBGOAL (fn (subgoal, i) =>
   811       TRY o REPEAT_ALL_NEW
   811       TRY o REPEAT_ALL_NEW
   812         (DETERM o (eresolve_tac ctxt [conjE, exE] ORELSE' eresolve_tac ctxt [disjE]))
   812         (DETERM o (eresolve_tac ctxt [conjE, exE] ORELSE' eresolve_tac ctxt [disjE]))
   813     ]
   813     ]
   814   end;
   814   end;
   815 
   815 
   816 end;  (* local *)
       
   817 
       
   818 (* remove irrelevant premises, then split the i-th subgoal (and all new      *)
   816 (* remove irrelevant premises, then split the i-th subgoal (and all new      *)
   819 (* subgoals) by using 'split_once_tac' repeatedly.  Beta-eta-normalize new   *)
   817 (* subgoals) by using 'split_once_tac' repeatedly.  Beta-eta-normalize new   *)
   820 (* subgoals and finally attempt to solve them by finding an immediate        *)
   818 (* subgoals and finally attempt to solve them by finding an immediate        *)
   821 (* contradiction (i.e., a term and its negation) in their premises.          *)
   819 (* contradiction (i.e., a term and its negation) in their premises.          *)
   822 
   820 
   895    the actual refutation tactic. Should be able to deal with goals
   893    the actual refutation tactic. Should be able to deal with goals
   896    [| A1; ...; An |] ==> False
   894    [| A1; ...; An |] ==> False
   897    where the Ai are atomic, i.e. no top-level &, | or EX
   895    where the Ai are atomic, i.e. no top-level &, | or EX
   898 *)
   896 *)
   899 
   897 
   900 local
       
   901   fun nnf_simpset ctxt =
       
   902     (empty_simpset ctxt
       
   903       |> Simplifier.set_mkeqTrue mk_eq_True
       
   904       |> Simplifier.set_mksimps (mksimps mksimps_pairs))
       
   905     addsimps [@{thm imp_conv_disj}, @{thm iff_conv_conj_imp}, @{thm de_Morgan_disj},
       
   906       @{thm de_Morgan_conj}, @{thm not_all}, @{thm not_ex}, @{thm not_not}];
       
   907   fun prem_nnf_tac ctxt = full_simp_tac (nnf_simpset ctxt);
       
   908 in
       
   909 
       
   910 fun refute_tac ctxt test prep_tac ref_tac =
   898 fun refute_tac ctxt test prep_tac ref_tac =
   911   let val refute_prems_tac =
   899   let val refute_prems_tac =
   912         REPEAT_DETERM
   900         REPEAT_DETERM
   913               (eresolve_tac ctxt [@{thm conjE}, @{thm exE}] 1 ORELSE
   901               (eresolve_tac ctxt [@{thm conjE}, @{thm exE}] 1 ORELSE
   914                filter_prems_tac ctxt test 1 ORELSE
   902                filter_prems_tac ctxt test 1 ORELSE
   918   in EVERY'[TRY o filter_prems_tac ctxt test,
   906   in EVERY'[TRY o filter_prems_tac ctxt test,
   919             REPEAT_DETERM o eresolve_tac ctxt @{thms rev_mp}, prep_tac,
   907             REPEAT_DETERM o eresolve_tac ctxt @{thms rev_mp}, prep_tac,
   920               resolve_tac ctxt @{thms ccontr}, prem_nnf_tac ctxt,
   908               resolve_tac ctxt @{thms ccontr}, prem_nnf_tac ctxt,
   921             SELECT_GOAL (DEPTH_SOLVE refute_prems_tac)]
   909             SELECT_GOAL (DEPTH_SOLVE refute_prems_tac)]
   922   end;
   910   end;
   923 
       
   924 end;
       
   925 
   911 
   926 
   912 
   927 (* arith proof method *)
   913 (* arith proof method *)
   928 
   914 
   929 local
   915 local