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 |