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 |