src/FOL/ex/Classical.thy
changeset 62020 5d208fd2507d
parent 61490 7c9c54eb9658
child 69590 e65314985426
equal deleted inserted replaced
62019:9de1eb745aeb 62020:5d208fd2507d
   319   "(\<forall>x. \<forall>y. q(x,y) \<longleftrightarrow> (\<forall>z. p(z,x) \<longleftrightarrow> p(z,y)))
   319   "(\<forall>x. \<forall>y. q(x,y) \<longleftrightarrow> (\<forall>z. p(z,x) \<longleftrightarrow> p(z,y)))
   320     \<longrightarrow> (\<forall>x. \<forall>y. q(x,y) \<longleftrightarrow> q(y,x))"
   320     \<longrightarrow> (\<forall>x. \<forall>y. q(x,y) \<longleftrightarrow> q(y,x))"
   321   by blast
   321   by blast
   322 
   322 
   323 text \<open>
   323 text \<open>
   324   Other proofs: Can use @{text auto}, which cheats by using rewriting!
   324   Other proofs: Can use \<open>auto\<close>, which cheats by using rewriting!
   325   @{text Deepen_tac} alone requires 253 secs.  Or
   325   \<open>Deepen_tac\<close> alone requires 253 secs.  Or
   326   @{text \<open>by (mini_tac 1 THEN Deepen_tac 5 1)\<close>}.
   326   \<open>by (mini_tac 1 THEN Deepen_tac 5 1)\<close>.
   327 \<close>
   327 \<close>
   328 
   328 
   329 text\<open>44\<close>
   329 text\<open>44\<close>
   330 lemma
   330 lemma
   331   "(\<forall>x. f(x) \<longrightarrow> (\<exists>y. g(y) \<and> h(x,y) \<and> (\<exists>y. g(y) \<and> \<not> h(x,y)))) \<and>
   331   "(\<forall>x. f(x) \<longrightarrow> (\<exists>y. g(y) \<and> h(x,y) \<and> (\<exists>y. g(y) \<and> \<not> h(x,y)))) \<and>
   364 lemma
   364 lemma
   365   "(\<exists>x y::'a. \<forall>z. z = x \<or> z = y) \<and> P(a) \<and> P(b) \<and> a \<noteq> b \<longrightarrow> (\<forall>u::'a. P(u))"
   365   "(\<exists>x y::'a. \<forall>z. z = x \<or> z = y) \<and> P(a) \<and> P(b) \<and> a \<noteq> b \<longrightarrow> (\<forall>u::'a. P(u))"
   366   apply safe
   366   apply safe
   367   apply (rule_tac x = a in allE, assumption)
   367   apply (rule_tac x = a in allE, assumption)
   368   apply (rule_tac x = b in allE, assumption)
   368   apply (rule_tac x = b in allE, assumption)
   369   apply fast  -- \<open>blast's treatment of equality can't do it\<close>
   369   apply fast  \<comment> \<open>blast's treatment of equality can't do it\<close>
   370   done
   370   done
   371 
   371 
   372 text\<open>50. (What has this to do with equality?)\<close>
   372 text\<open>50. (What has this to do with equality?)\<close>
   373 lemma "(\<forall>x. P(a,x) \<or> (\<forall>y. P(x,y))) \<longrightarrow> (\<exists>x. \<forall>y. P(x,y))"
   373 lemma "(\<forall>x. P(a,x) \<or> (\<forall>y. P(x,y))) \<longrightarrow> (\<exists>x. \<forall>y. P(x,y))"
   374   by blast
   374   by blast
   397    (hates(agatha,agatha) \<and> hates(agatha,charles)) \<and>
   397    (hates(agatha,agatha) \<and> hates(agatha,charles)) \<and>
   398    (\<forall>x. lives(x) \<and> \<not> richer(x,agatha) \<longrightarrow> hates(butler,x)) \<and>
   398    (\<forall>x. lives(x) \<and> \<not> richer(x,agatha) \<longrightarrow> hates(butler,x)) \<and>
   399    (\<forall>x. hates(agatha,x) \<longrightarrow> hates(butler,x)) \<and>
   399    (\<forall>x. hates(agatha,x) \<longrightarrow> hates(butler,x)) \<and>
   400    (\<forall>x. \<not> hates(x,agatha) \<or> \<not> hates(x,butler) \<or> \<not> hates(x,charles)) \<longrightarrow>
   400    (\<forall>x. \<not> hates(x,agatha) \<or> \<not> hates(x,butler) \<or> \<not> hates(x,charles)) \<longrightarrow>
   401     killed(?who,agatha)"
   401     killed(?who,agatha)"
   402   by fast  -- \<open>MUCH faster than blast\<close>
   402   by fast  \<comment> \<open>MUCH faster than blast\<close>
   403 
   403 
   404 
   404 
   405 text\<open>56\<close>
   405 text\<open>56\<close>
   406 lemma "(\<forall>x. (\<exists>y. P(y) \<and> x = f(y)) \<longrightarrow> P(x)) \<longleftrightarrow> (\<forall>x. P(x) \<longrightarrow> P(f(x)))"
   406 lemma "(\<forall>x. (\<exists>y. P(y) \<and> x = f(y)) \<longrightarrow> P(x)) \<longleftrightarrow> (\<forall>x. P(x) \<longrightarrow> P(f(x)))"
   407   by blast
   407   by blast
   466       (\<exists>v. C(v) \<and>
   466       (\<exists>v. C(v) \<and>
   467             (\<forall>y. ((C(y) \<and> Q(w,y,y)) \<and> OO(w,g) \<longrightarrow> \<not> P(v,y)) \<and>
   467             (\<forall>y. ((C(y) \<and> Q(w,y,y)) \<and> OO(w,g) \<longrightarrow> \<not> P(v,y)) \<and>
   468                     ((C(y) \<and> Q(w,y,y)) \<and> OO(w,b) \<longrightarrow> P(v,y) \<and> OO(v,b)))))
   468                     ((C(y) \<and> Q(w,y,y)) \<and> OO(w,b) \<longrightarrow> P(v,y) \<and> OO(v,b)))))
   469      \<longrightarrow> \<not> (\<exists>x. A(x) \<and> (\<forall>y. C(y) \<longrightarrow> (\<forall>z. D(x,y,z))))"
   469      \<longrightarrow> \<not> (\<exists>x. A(x) \<and> (\<forall>y. C(y) \<longrightarrow> (\<forall>z. D(x,y,z))))"
   470   by (blast 12)
   470   by (blast 12)
   471     -- \<open>Needed because the search for depths below 12 is very slow.\<close>
   471     \<comment> \<open>Needed because the search for depths below 12 is very slow.\<close>
   472 
   472 
   473 
   473 
   474 text \<open>
   474 text \<open>
   475   Halting problem II: credited to M. Bruschi by Li Dafa in JAR 18(1),
   475   Halting problem II: credited to M. Bruschi by Li Dafa in JAR 18(1),
   476   p. 105.
   476   p. 105.