src/HOL/ex/Meson_Test.thy
changeset 69597 ff784d5a5bfb
parent 67443 3abf6a722518
child 70166 538919322852
equal deleted inserted replaced
69596:c8a2755bf220 69597:ff784d5a5bfb
    22 
    22 
    23 lemma problem_25:
    23 lemma problem_25:
    24   "(\<exists>x. P x) & (\<forall>x. L x --> ~ (M x & R x)) & (\<forall>x. P x --> (M x & L x)) & ((\<forall>x. P x --> Q x) | (\<exists>x. P x & R x)) --> (\<exists>x. Q x & P x)"
    24   "(\<exists>x. P x) & (\<forall>x. L x --> ~ (M x & R x)) & (\<forall>x. P x --> (M x & L x)) & ((\<forall>x. P x --> Q x) | (\<exists>x. P x & R x)) --> (\<exists>x. Q x & P x)"
    25   apply (rule ccontr)
    25   apply (rule ccontr)
    26   ML_prf \<open>
    26   ML_prf \<open>
    27     val ctxt = @{context};
    27     val ctxt = \<^context>;
    28     val prem25 = Thm.assume @{cprop "\<not> ?thesis"};
    28     val prem25 = Thm.assume \<^cprop>\<open>\<not> ?thesis\<close>;
    29     val nnf25 = Meson.make_nnf ctxt prem25;
    29     val nnf25 = Meson.make_nnf ctxt prem25;
    30     val xsko25 = Meson.skolemize ctxt nnf25;
    30     val xsko25 = Meson.skolemize ctxt nnf25;
    31 \<close>
    31 \<close>
    32   apply (tactic \<open>cut_tac xsko25 1 THEN REPEAT (eresolve_tac @{context} [exE] 1)\<close>)
    32   apply (tactic \<open>cut_tac xsko25 1 THEN REPEAT (eresolve_tac \<^context> [exE] 1)\<close>)
    33   ML_val \<open>
    33   ML_val \<open>
    34     val ctxt = @{context};
    34     val ctxt = \<^context>;
    35     val [_, sko25] = #prems (#1 (Subgoal.focus ctxt 1 NONE (#goal @{Isar.goal})));
    35     val [_, sko25] = #prems (#1 (Subgoal.focus ctxt 1 NONE (#goal @{Isar.goal})));
    36     val clauses25 = Meson.make_clauses ctxt [sko25];   (*7 clauses*)
    36     val clauses25 = Meson.make_clauses ctxt [sko25];   (*7 clauses*)
    37     val horns25 = Meson.make_horns clauses25;     (*16 Horn clauses*)
    37     val horns25 = Meson.make_horns clauses25;     (*16 Horn clauses*)
    38     val go25 :: _ = Meson.gocls clauses25;
    38     val go25 :: _ = Meson.gocls clauses25;
    39 
    39 
    40     val ctxt' = fold Thm.declare_hyps (maps Thm.chyps_of (go25 :: horns25)) ctxt;
    40     val ctxt' = fold Thm.declare_hyps (maps Thm.chyps_of (go25 :: horns25)) ctxt;
    41     Goal.prove ctxt' [] [] @{prop False} (fn _ =>
    41     Goal.prove ctxt' [] [] \<^prop>\<open>False\<close> (fn _ =>
    42       resolve_tac ctxt' [go25] 1 THEN
    42       resolve_tac ctxt' [go25] 1 THEN
    43       Meson.depth_prolog_tac ctxt' horns25);
    43       Meson.depth_prolog_tac ctxt' horns25);
    44 \<close>
    44 \<close>
    45   oops
    45   oops
    46 
    46 
    47 lemma problem_26:
    47 lemma problem_26:
    48   "((\<exists>x. p x) = (\<exists>x. q x)) & (\<forall>x. \<forall>y. p x & q y --> (r x = s y)) --> ((\<forall>x. p x --> r x) = (\<forall>x. q x --> s x))"
    48   "((\<exists>x. p x) = (\<exists>x. q x)) & (\<forall>x. \<forall>y. p x & q y --> (r x = s y)) --> ((\<forall>x. p x --> r x) = (\<forall>x. q x --> s x))"
    49   apply (rule ccontr)
    49   apply (rule ccontr)
    50   ML_prf \<open>
    50   ML_prf \<open>
    51     val ctxt = @{context};
    51     val ctxt = \<^context>;
    52     val prem26 = Thm.assume @{cprop "\<not> ?thesis"}
    52     val prem26 = Thm.assume \<^cprop>\<open>\<not> ?thesis\<close>
    53     val nnf26 = Meson.make_nnf ctxt prem26;
    53     val nnf26 = Meson.make_nnf ctxt prem26;
    54     val xsko26 = Meson.skolemize ctxt nnf26;
    54     val xsko26 = Meson.skolemize ctxt nnf26;
    55 \<close>
    55 \<close>
    56   apply (tactic \<open>cut_tac xsko26 1 THEN REPEAT (eresolve_tac @{context} [exE] 1)\<close>)
    56   apply (tactic \<open>cut_tac xsko26 1 THEN REPEAT (eresolve_tac \<^context> [exE] 1)\<close>)
    57   ML_val \<open>
    57   ML_val \<open>
    58     val ctxt = @{context};
    58     val ctxt = \<^context>;
    59     val [_, sko26] = #prems (#1 (Subgoal.focus ctxt 1 NONE (#goal @{Isar.goal})));
    59     val [_, sko26] = #prems (#1 (Subgoal.focus ctxt 1 NONE (#goal @{Isar.goal})));
    60     val clauses26 = Meson.make_clauses ctxt [sko26];
    60     val clauses26 = Meson.make_clauses ctxt [sko26];
    61     val _ = @{assert} (length clauses26 = 9);
    61     val _ = \<^assert> (length clauses26 = 9);
    62     val horns26 = Meson.make_horns clauses26;
    62     val horns26 = Meson.make_horns clauses26;
    63     val _ = @{assert} (length horns26 = 24);
    63     val _ = \<^assert> (length horns26 = 24);
    64     val go26 :: _ = Meson.gocls clauses26;
    64     val go26 :: _ = Meson.gocls clauses26;
    65 
    65 
    66     val ctxt' = fold Thm.declare_hyps (maps Thm.chyps_of (go26 :: horns26)) ctxt;
    66     val ctxt' = fold Thm.declare_hyps (maps Thm.chyps_of (go26 :: horns26)) ctxt;
    67     Goal.prove ctxt' [] [] @{prop False} (fn _ =>
    67     Goal.prove ctxt' [] [] \<^prop>\<open>False\<close> (fn _ =>
    68       resolve_tac ctxt' [go26] 1 THEN
    68       resolve_tac ctxt' [go26] 1 THEN
    69       Meson.depth_prolog_tac ctxt' horns26);  (*7 ms*)
    69       Meson.depth_prolog_tac ctxt' horns26);  (*7 ms*)
    70     (*Proof is of length 107!!*)
    70     (*Proof is of length 107!!*)
    71 \<close>
    71 \<close>
    72   oops
    72   oops
    73 
    73 
    74 lemma problem_43:  \<comment> \<open>NOW PROVED AUTOMATICALLY!!\<close>  (*16 Horn clauses*)
    74 lemma problem_43:  \<comment> \<open>NOW PROVED AUTOMATICALLY!!\<close>  (*16 Horn clauses*)
    75   "(\<forall>x. \<forall>y. q x y = (\<forall>z. p z x = (p z y::bool))) --> (\<forall>x. (\<forall>y. q x y = (q y x::bool)))"
    75   "(\<forall>x. \<forall>y. q x y = (\<forall>z. p z x = (p z y::bool))) --> (\<forall>x. (\<forall>y. q x y = (q y x::bool)))"
    76   apply (rule ccontr)
    76   apply (rule ccontr)
    77   ML_prf \<open>
    77   ML_prf \<open>
    78     val ctxt = @{context};
    78     val ctxt = \<^context>;
    79     val prem43 = Thm.assume @{cprop "\<not> ?thesis"};
    79     val prem43 = Thm.assume \<^cprop>\<open>\<not> ?thesis\<close>;
    80     val nnf43 = Meson.make_nnf ctxt prem43;
    80     val nnf43 = Meson.make_nnf ctxt prem43;
    81     val xsko43 = Meson.skolemize ctxt nnf43;
    81     val xsko43 = Meson.skolemize ctxt nnf43;
    82 \<close>
    82 \<close>
    83   apply (tactic \<open>cut_tac xsko43 1 THEN REPEAT (eresolve_tac @{context} [exE] 1)\<close>)
    83   apply (tactic \<open>cut_tac xsko43 1 THEN REPEAT (eresolve_tac \<^context> [exE] 1)\<close>)
    84   ML_val \<open>
    84   ML_val \<open>
    85     val ctxt = @{context};
    85     val ctxt = \<^context>;
    86     val [_, sko43] = #prems (#1 (Subgoal.focus ctxt 1 NONE (#goal @{Isar.goal})));
    86     val [_, sko43] = #prems (#1 (Subgoal.focus ctxt 1 NONE (#goal @{Isar.goal})));
    87     val clauses43 = Meson.make_clauses ctxt [sko43];
    87     val clauses43 = Meson.make_clauses ctxt [sko43];
    88     val _ = @{assert} (length clauses43 = 6);
    88     val _ = \<^assert> (length clauses43 = 6);
    89     val horns43 = Meson.make_horns clauses43;
    89     val horns43 = Meson.make_horns clauses43;
    90     val _ = @{assert} (length horns43 = 16);
    90     val _ = \<^assert> (length horns43 = 16);
    91     val go43 :: _ = Meson.gocls clauses43;
    91     val go43 :: _ = Meson.gocls clauses43;
    92 
    92 
    93     val ctxt' = fold Thm.declare_hyps (maps Thm.chyps_of (go43 :: horns43)) ctxt;
    93     val ctxt' = fold Thm.declare_hyps (maps Thm.chyps_of (go43 :: horns43)) ctxt;
    94     Goal.prove ctxt' [] [] @{prop False} (fn _ =>
    94     Goal.prove ctxt' [] [] \<^prop>\<open>False\<close> (fn _ =>
    95       resolve_tac ctxt' [go43] 1 THEN
    95       resolve_tac ctxt' [go43] 1 THEN
    96       Meson.best_prolog_tac ctxt' Meson.size_of_subgoals horns43);   (*7ms*)
    96       Meson.best_prolog_tac ctxt' Meson.size_of_subgoals horns43);   (*7ms*)
    97 \<close>
    97 \<close>
    98   oops
    98   oops
    99 
    99