src/HOL/ex/Refute_Examples.thy
changeset 14489 3676def6b8b9
parent 14465 8cc21ed7ef41
child 14809 eaa5d6987ba2
equal deleted inserted replaced
14488:863258b0cdca 14489:3676def6b8b9
    24     -- {* here 'refute 3' would cause an exception, since we only have 2 subgoals *}
    24     -- {* here 'refute 3' would cause an exception, since we only have 2 subgoals *}
    25   refute [maxsize=5]           -- {* we can override parameters ... *}
    25   refute [maxsize=5]           -- {* we can override parameters ... *}
    26   refute [satsolver="dpll"] 2  -- {* ... and specify a subgoal at the same time *}
    26   refute [satsolver="dpll"] 2  -- {* ... and specify a subgoal at the same time *}
    27 oops
    27 oops
    28 
    28 
    29 refute_params
    29 refute_params [satsolver="dpll"]
    30 
    30 
    31 section {* Examples and Test Cases *}
    31 section {* Examples and Test Cases *}
    32 
    32 
    33 subsection {* Propositional logic *}
    33 subsection {* Propositional logic *}
    34 
    34 
   153 oops
   153 oops
   154 
   154 
   155 text {* A true statement (also testing names of free and bound variables being identical) *}
   155 text {* A true statement (also testing names of free and bound variables being identical) *}
   156 
   156 
   157 lemma "(\<forall>x y. P x y \<longrightarrow> P y x) \<longrightarrow> (\<forall>x. P x y) \<longrightarrow> P y x"
   157 lemma "(\<forall>x y. P x y \<longrightarrow> P y x) \<longrightarrow> (\<forall>x. P x y) \<longrightarrow> P y x"
   158   refute [maxsize=2]  (* [maxsize=5] works well with ZChaff *)
   158   refute
   159   apply fast
   159   apply fast
   160 done
   160 done
   161 
   161 
   162 text {* "A type has at most 3 elements." *}
   162 text {* "A type has at most 3 elements." *}
   163 
   163 
   170 oops
   170 oops
   171 
   171 
   172 text {* "Every reflexive and symmetric relation is transitive." *}
   172 text {* "Every reflexive and symmetric relation is transitive." *}
   173 
   173 
   174 lemma "\<lbrakk> \<forall>x. P x x; \<forall>x y. P x y \<longrightarrow> P y x \<rbrakk> \<Longrightarrow> P x y \<longrightarrow> P y z \<longrightarrow> P x z"
   174 lemma "\<lbrakk> \<forall>x. P x x; \<forall>x y. P x y \<longrightarrow> P y x \<rbrakk> \<Longrightarrow> P x y \<longrightarrow> P y z \<longrightarrow> P x z"
   175   (* refute -- works well with ZChaff, but the internal solver is too slow *)
   175   refute
   176 oops
   176 oops
   177 
   177 
   178 text {* The "Drinker's theorem" ... *}
   178 text {* The "Drinker's theorem" ... *}
   179 
   179 
   180 lemma "\<exists>x. f x = g x \<longrightarrow> f = g"
   180 lemma "\<exists>x. f x = g x \<longrightarrow> f = g"
   181   refute [maxsize=4]  (* [maxsize=6] works well with ZChaff *)
   181   refute
   182   apply (auto simp add: ext)
   182   apply (auto simp add: ext)
   183 done
   183 done
   184 
   184 
   185 text {* ... and an incorrect version of it *}
   185 text {* ... and an incorrect version of it *}
   186 
   186 
   260 
   260 
   261 lemma "(\<forall>x y. (P x y | R x y) \<longrightarrow> T x y) \<longrightarrow> trans T \<longrightarrow> (\<forall>Q. (\<forall>x y. (P x y | R x y) \<longrightarrow> Q x y) \<longrightarrow> trans Q \<longrightarrow> subset T Q)
   261 lemma "(\<forall>x y. (P x y | R x y) \<longrightarrow> T x y) \<longrightarrow> trans T \<longrightarrow> (\<forall>Q. (\<forall>x y. (P x y | R x y) \<longrightarrow> Q x y) \<longrightarrow> trans Q \<longrightarrow> subset T Q)
   262         \<longrightarrow> trans_closure TP P
   262         \<longrightarrow> trans_closure TP P
   263         \<longrightarrow> trans_closure TR R
   263         \<longrightarrow> trans_closure TR R
   264         \<longrightarrow> (T x y = (TP x y | TR x y))"
   264         \<longrightarrow> (T x y = (TP x y | TR x y))"
   265   (* refute -- works well with ZChaff, but the internal solver is too slow *)
   265   refute
   266 oops
   266 oops
   267 
   267 
   268 text {* "Every surjective function is invertible." *}
   268 text {* "Every surjective function is invertible." *}
   269 
   269 
   270 lemma "(\<forall>y. \<exists>x. y = f x) \<longrightarrow> (\<exists>g. \<forall>x. g (f x) = x)"
   270 lemma "(\<forall>y. \<exists>x. y = f x) \<longrightarrow> (\<exists>g. \<forall>x. g (f x) = x)"
   278 oops
   278 oops
   279 
   279 
   280 text {* Every point is a fixed point of some function. *}
   280 text {* Every point is a fixed point of some function. *}
   281 
   281 
   282 lemma "\<exists>f. f x = x"
   282 lemma "\<exists>f. f x = x"
   283   refute [maxsize=4]
   283   refute [maxsize=5]
   284   apply (rule_tac x="\<lambda>x. x" in exI)
   284   apply (rule_tac x="\<lambda>x. x" in exI)
   285   apply simp
   285   apply simp
   286 done
   286 done
   287 
   287 
   288 text {* Axiom of Choice: first an incorrect version ... *}
   288 text {* Axiom of Choice: first an incorrect version ... *}
   292 oops
   292 oops
   293 
   293 
   294 text {* ... and now two correct ones *}
   294 text {* ... and now two correct ones *}
   295 
   295 
   296 lemma "(\<forall>x. \<exists>y. P x y) \<longrightarrow> (\<exists>f. \<forall>x. P x (f x))"
   296 lemma "(\<forall>x. \<exists>y. P x y) \<longrightarrow> (\<exists>f. \<forall>x. P x (f x))"
   297   refute [maxsize=5]
   297   refute
   298   apply (simp add: choice)
   298   apply (simp add: choice)
   299 done
   299 done
   300 
   300 
   301 lemma "(\<forall>x. EX!y. P x y) \<longrightarrow> (EX!f. \<forall>x. P x (f x))"
   301 lemma "(\<forall>x. EX!y. P x y) \<longrightarrow> (EX!f. \<forall>x. P x (f x))"
   302   refute [maxsize=3]  (* [maxsize=4] works well with ZChaff *)
   302   refute
   303   apply auto
   303   apply auto
   304     apply (simp add: ex1_implies_ex choice)
   304     apply (simp add: ex1_implies_ex choice)
   305   apply (fast intro: ext)
   305   apply (fast intro: ext)
   306 done
   306 done
   307 
   307 
   359 lemma "P (A::'a set set)"
   359 lemma "P (A::'a set set)"
   360   refute
   360   refute
   361 oops
   361 oops
   362 
   362 
   363 lemma "{x. P x} = {y. P y}"
   363 lemma "{x. P x} = {y. P y}"
   364   refute [maxsize=2]  (* [maxsize=8] works well with ZChaff *)
   364   refute
   365   apply simp
   365   apply simp
   366 done
   366 done
   367 
   367 
   368 lemma "x : {x. P x}"
   368 lemma "x : {x. P x}"
   369   refute
   369   refute
   428 lemma "(THE x. x=y) = z"
   428 lemma "(THE x. x=y) = z"
   429   refute
   429   refute
   430 oops
   430 oops
   431 
   431 
   432 lemma "Ex P \<longrightarrow> P (The P)"
   432 lemma "Ex P \<longrightarrow> P (The P)"
   433   (* refute -- works well with ZChaff, but the internal solver is too slow *)
   433   refute
   434 oops
   434 oops
   435 
   435 
   436 subsection {* Eps *}
   436 subsection {* Eps *}
   437 
   437 
   438 lemma "Eps P"
   438 lemma "Eps P"
   450 lemma "(SOME x. x=y) = z"
   450 lemma "(SOME x. x=y) = z"
   451   refute
   451   refute
   452 oops
   452 oops
   453 
   453 
   454 lemma "Ex P \<longrightarrow> P (Eps P)"
   454 lemma "Ex P \<longrightarrow> P (Eps P)"
   455   refute [maxsize=2]  (* [maxsize=3] works well with ZChaff *)
   455   refute [maxsize=3]
   456   apply (auto simp add: someI)
   456   apply (auto simp add: someI)
   457 done
   457 done
   458 
   458 
   459 subsection {* Inductive datatypes *}
   459 subsection {* Inductive datatypes *}
   460 
   460