equal
deleted
inserted
replaced
21 tiling :: "'a set set => 'a set set"; |
21 tiling :: "'a set set => 'a set set"; |
22 |
22 |
23 inductive "tiling A" |
23 inductive "tiling A" |
24 intrs |
24 intrs |
25 empty: "{} : tiling A" |
25 empty: "{} : tiling A" |
26 Un: "[| a : A; t : tiling A; a <= - t |] ==> a Un t : tiling A"; |
26 Un: "[| a : A; t : tiling A; a <= - t |] |
27 |
27 ==> a Un t : tiling A"; |
28 |
28 |
29 text "The union of two disjoint tilings is a tiling"; |
29 |
|
30 text "The union of two disjoint tilings is a tiling."; |
30 |
31 |
31 lemma tiling_Un: |
32 lemma tiling_Un: |
32 "t : tiling A --> u : tiling A --> t Int u = {} --> t Un u : tiling A"; |
33 "t : tiling A --> u : tiling A --> t Int u = {} |
|
34 --> t Un u : tiling A"; |
33 proof; |
35 proof; |
34 assume "t : tiling A" (is "_ : ?T"); |
36 assume "t : tiling A" (is "_ : ?T"); |
35 thus "u : ?T --> t Int u = {} --> t Un u : ?T" (is "?P t"); |
37 thus "u : ?T --> t Int u = {} --> t Un u : ?T" (is "?P t"); |
36 proof (induct t set: tiling); |
38 proof (induct t set: tiling); |
37 show "?P {}"; by simp; |
39 show "?P {}"; by simp; |
117 inductive domino |
119 inductive domino |
118 intrs |
120 intrs |
119 horiz: "{(i, j), (i, j + 1)} : domino" |
121 horiz: "{(i, j), (i, j + 1)} : domino" |
120 vertl: "{(i, j), (i + 1, j)} : domino"; |
122 vertl: "{(i, j), (i + 1, j)} : domino"; |
121 |
123 |
122 lemma dominoes_tile_row: "{i} Times below (2 * n) : tiling domino" |
124 lemma dominoes_tile_row: |
|
125 "{i} Times below (2 * n) : tiling domino" |
123 (is "?P n" is "?B n : ?T"); |
126 (is "?P n" is "?B n : ?T"); |
124 proof (induct n); |
127 proof (induct n); |
125 show "?P 0"; by (simp add: below_0 tiling.empty); |
128 show "?P 0"; by (simp add: below_0 tiling.empty); |
126 |
129 |
127 fix n; assume hyp: "?P n"; |
130 fix n; assume hyp: "?P n"; |
266 by (rule evnodd_finite, rule tiling_domino_finite, rule t); |
269 by (rule evnodd_finite, rule tiling_domino_finite, rule t); |
267 |
270 |
268 note [simp] = evnodd_iff evnodd_empty evnodd_insert evnodd_Diff; |
271 note [simp] = evnodd_iff evnodd_empty evnodd_insert evnodd_Diff; |
269 have "card (?e ?t'' 0) < card (?e ?t' 0)"; |
272 have "card (?e ?t'' 0) < card (?e ?t' 0)"; |
270 proof -; |
273 proof -; |
271 have "card (?e ?t' 0 - {(2 * m + 1, 2 * n + 1)}) < card (?e ?t' 0)"; |
274 have "card (?e ?t' 0 - {(2 * m + 1, 2 * n + 1)}) |
|
275 < card (?e ?t' 0)"; |
272 proof (rule card_Diff1_less); |
276 proof (rule card_Diff1_less); |
273 show "finite (?e ?t' 0)"; by (rule finite_subset, rule fin) force; |
277 show "finite (?e ?t' 0)"; |
|
278 by (rule finite_subset, rule fin) force; |
274 show "(2 * m + 1, 2 * n + 1) : ?e ?t' 0"; by simp; |
279 show "(2 * m + 1, 2 * n + 1) : ?e ?t' 0"; by simp; |
275 qed; |
280 qed; |
276 thus ?thesis; by simp; |
281 thus ?thesis; by simp; |
277 qed; |
282 qed; |
278 also; have "... < card (?e ?t 0)"; |
283 also; have "... < card (?e ?t 0)"; |
280 have "(0, 0) : ?e ?t 0"; by simp; |
285 have "(0, 0) : ?e ?t 0"; by simp; |
281 with fin; have "card (?e ?t 0 - {(0, 0)}) < card (?e ?t 0)"; |
286 with fin; have "card (?e ?t 0 - {(0, 0)}) < card (?e ?t 0)"; |
282 by (rule card_Diff1_less); |
287 by (rule card_Diff1_less); |
283 thus ?thesis; by simp; |
288 thus ?thesis; by simp; |
284 qed; |
289 qed; |
285 also; from t; have "... = card (?e ?t 1)"; by (rule tiling_domino_01); |
290 also; from t; have "... = card (?e ?t 1)"; |
|
291 by (rule tiling_domino_01); |
286 also; have "?e ?t 1 = ?e ?t'' 1"; by simp; |
292 also; have "?e ?t 1 = ?e ?t'' 1"; by simp; |
287 also; from t''; have "card ... = card (?e ?t'' 0)"; |
293 also; from t''; have "card ... = card (?e ?t'' 0)"; |
288 by (rule tiling_domino_01 [RS sym]); |
294 by (rule tiling_domino_01 [RS sym]); |
289 finally; show False; ..; |
295 finally; show False; ..; |
290 qed; |
296 qed; |