src/HOL/Isar_examples/MutilatedCheckerboard.thy
changeset 26813 6a4d5ca6d2e5
parent 23746 a455e69c31cc
equal deleted inserted replaced
26812:c0fa62fa0e5b 26813:6a4d5ca6d2e5
   132 next
   132 next
   133   case (Suc n)
   133   case (Suc n)
   134   let ?a = "{i} <*> {2 * n + 1} Un {i} <*> {2 * n}"
   134   let ?a = "{i} <*> {2 * n + 1} Un {i} <*> {2 * n}"
   135   have "?B (Suc n) = ?a Un ?B n"
   135   have "?B (Suc n) = ?a Un ?B n"
   136     by (auto simp add: Sigma_Suc Un_assoc)
   136     by (auto simp add: Sigma_Suc Un_assoc)
   137   also have "... : ?T"
   137   moreover have "... : ?T"
   138   proof (rule tiling.Un)
   138   proof (rule tiling.Un)
   139     have "{(i, 2 * n), (i, 2 * n + 1)} : domino"
   139     have "{(i, 2 * n), (i, 2 * n + 1)} : domino"
   140       by (rule domino.horiz)
   140       by (rule domino.horiz)
   141     also have "{(i, 2 * n), (i, 2 * n + 1)} = ?a" by blast
   141     also have "{(i, 2 * n), (i, 2 * n + 1)} = ?a" by blast
   142     finally show "... : domino" .
   142     finally show "... : domino" .
   143     show "?B n : ?T" by (rule Suc)
   143     show "?B n : ?T" by (rule Suc)
   144     show "?a <= - ?B n" by blast
   144     show "?a <= - ?B n" by blast
   145   qed
   145   qed
   146   finally show ?case .
   146   ultimately show ?case by simp
   147 qed
   147 qed
   148 
   148 
   149 lemma dominoes_tile_matrix:
   149 lemma dominoes_tile_matrix:
   150   "below m <*> below (2 * n) : tiling domino"
   150   "below m <*> below (2 * n) : tiling domino"
   151   (is "?B m : ?T")
   151   (is "?B m : ?T")
   154   show ?case by (simp add: below_0 tiling.empty)
   154   show ?case by (simp add: below_0 tiling.empty)
   155 next
   155 next
   156   case (Suc m)
   156   case (Suc m)
   157   let ?t = "{m} <*> below (2 * n)"
   157   let ?t = "{m} <*> below (2 * n)"
   158   have "?B (Suc m) = ?t Un ?B m" by (simp add: Sigma_Suc)
   158   have "?B (Suc m) = ?t Un ?B m" by (simp add: Sigma_Suc)
   159   also have "... : ?T"
   159   moreover have "... : ?T"
   160   proof (rule tiling_Un)
   160   proof (rule tiling_Un)
   161     show "?t : ?T" by (rule dominoes_tile_row)
   161     show "?t : ?T" by (rule dominoes_tile_row)
   162     show "?B m : ?T" by (rule Suc)
   162     show "?B m : ?T" by (rule Suc)
   163     show "?t Int ?B m = {}" by blast
   163     show "?t Int ?B m = {}" by blast
   164   qed
   164   qed
   165   finally show ?case .
   165   ultimately show ?case by simp
   166 qed
   166 qed
   167 
   167 
   168 lemma domino_singleton:
   168 lemma domino_singleton:
   169   assumes d: "d : domino" and "b < 2"
   169   assumes d: "d : domino" and "b < 2"
   170   shows "EX i j. evnodd d b = {(i, j)}"  (is "?P d")
   170   shows "EX i j. evnodd d b = {(i, j)}"  (is "?P d")
   222     proof -
   222     proof -
   223       from `a \<in> domino` and `b < 2`
   223       from `a \<in> domino` and `b < 2`
   224       have "EX i j. ?e a b = {(i, j)}" by (rule domino_singleton)
   224       have "EX i j. ?e a b = {(i, j)}" by (rule domino_singleton)
   225       then show ?thesis by (blast intro: that)
   225       then show ?thesis by (blast intro: that)
   226     qed
   226     qed
   227     also have "... Un ?e t b = insert (i, j) (?e t b)" by simp
   227     moreover have "... Un ?e t b = insert (i, j) (?e t b)" by simp
   228     also have "card ... = Suc (card (?e t b))"
   228     moreover have "card ... = Suc (card (?e t b))"
   229     proof (rule card_insert_disjoint)
   229     proof (rule card_insert_disjoint)
   230       from `t \<in> tiling domino` have "finite t"
   230       from `t \<in> tiling domino` have "finite t"
   231 	by (rule tiling_domino_finite)
   231 	by (rule tiling_domino_finite)
   232       then show "finite (?e t b)"
   232       then show "finite (?e t b)"
   233         by (rule evnodd_finite)
   233         by (rule evnodd_finite)
   234       from e have "(i, j) : ?e a b" by simp
   234       from e have "(i, j) : ?e a b" by simp
   235       with at show "(i, j) ~: ?e t b" by (blast dest: evnoddD)
   235       with at show "(i, j) ~: ?e t b" by (blast dest: evnoddD)
   236     qed
   236     qed
   237     finally show "?thesis b" .
   237     ultimately show "?thesis b" by simp
   238   qed
   238   qed
   239   then have "card (?e (a Un t) 0) = Suc (card (?e t 0))" by simp
   239   then have "card (?e (a Un t) 0) = Suc (card (?e t 0))" by simp
   240   also from hyp have "card (?e t 0) = card (?e t 1)" .
   240   also from hyp have "card (?e t 0) = card (?e t 1)" .
   241   also from card_suc have "Suc ... = card (?e (a Un t) 1)"
   241   also from card_suc have "Suc ... = card (?e (a Un t) 1)"
   242     by simp
   242     by simp