65 |
65 |
66 lemma below_0: "below 0 = {}"; |
66 lemma below_0: "below 0 = {}"; |
67 by (simp add: below_def); |
67 by (simp add: below_def); |
68 |
68 |
69 lemma Sigma_Suc1: |
69 lemma Sigma_Suc1: |
70 "below (Suc n) Times B = ({n} Times B) Un (below n Times B)"; |
70 "below (Suc n) <*> B = ({n} <*> B) Un (below n <*> B)"; |
71 by (simp add: below_def less_Suc_eq) blast; |
71 by (simp add: below_def less_Suc_eq) blast; |
72 |
72 |
73 lemma Sigma_Suc2: |
73 lemma Sigma_Suc2: |
74 "A Times below (Suc n) = (A Times {n}) Un (A Times (below n))"; |
74 "A <*> below (Suc n) = (A <*> {n}) Un (A <*> (below n))"; |
75 by (simp add: below_def less_Suc_eq) blast; |
75 by (simp add: below_def less_Suc_eq) blast; |
76 |
76 |
77 lemmas Sigma_Suc = Sigma_Suc1 Sigma_Suc2; |
77 lemmas Sigma_Suc = Sigma_Suc1 Sigma_Suc2; |
78 |
78 |
79 |
79 |
120 intrs |
120 intrs |
121 horiz: "{(i, j), (i, j + 1)} : domino" |
121 horiz: "{(i, j), (i, j + 1)} : domino" |
122 vertl: "{(i, j), (i + 1, j)} : domino"; |
122 vertl: "{(i, j), (i + 1, j)} : domino"; |
123 |
123 |
124 lemma dominoes_tile_row: |
124 lemma dominoes_tile_row: |
125 "{i} Times below (2 * n) : tiling domino" |
125 "{i} <*> below (2 * n) : tiling domino" |
126 (is "?P n" is "?B n : ?T"); |
126 (is "?P n" is "?B n : ?T"); |
127 proof (induct n); |
127 proof (induct n); |
128 show "?P 0"; by (simp add: below_0 tiling.empty); |
128 show "?P 0"; by (simp add: below_0 tiling.empty); |
129 |
129 |
130 fix n; assume hyp: "?P n"; |
130 fix n; assume hyp: "?P n"; |
131 let ?a = "{i} Times {2 * n + 1} Un {i} Times {2 * n}"; |
131 let ?a = "{i} <*> {2 * n + 1} Un {i} <*> {2 * n}"; |
132 |
132 |
133 have "?B (Suc n) = ?a Un ?B n"; by (simp add: Sigma_Suc Un_assoc); |
133 have "?B (Suc n) = ?a Un ?B n"; by (simp add: Sigma_Suc Un_assoc); |
134 also; have "... : ?T"; |
134 also; have "... : ?T"; |
135 proof (rule tiling.Un); |
135 proof (rule tiling.Un); |
136 have "{(i, 2 * n), (i, 2 * n + 1)} : domino"; |
136 have "{(i, 2 * n), (i, 2 * n + 1)} : domino"; |
142 qed; |
142 qed; |
143 finally; show "?P (Suc n)"; .; |
143 finally; show "?P (Suc n)"; .; |
144 qed; |
144 qed; |
145 |
145 |
146 lemma dominoes_tile_matrix: |
146 lemma dominoes_tile_matrix: |
147 "below m Times below (2 * n) : tiling domino" |
147 "below m <*> below (2 * n) : tiling domino" |
148 (is "?P m" is "?B m : ?T"); |
148 (is "?P m" is "?B m : ?T"); |
149 proof (induct m); |
149 proof (induct m); |
150 show "?P 0"; by (simp add: below_0 tiling.empty); |
150 show "?P 0"; by (simp add: below_0 tiling.empty); |
151 |
151 |
152 fix m; assume hyp: "?P m"; |
152 fix m; assume hyp: "?P m"; |
153 let ?t = "{m} Times below (2 * n)"; |
153 let ?t = "{m} <*> below (2 * n)"; |
154 |
154 |
155 have "?B (Suc m) = ?t Un ?B m"; by (simp add: Sigma_Suc); |
155 have "?B (Suc m) = ?t Un ?B m"; by (simp add: Sigma_Suc); |
156 also; have "... : ?T"; |
156 also; have "... : ?T"; |
157 proof (rule tiling_Un [rulify]); |
157 proof (rule tiling_Un [rulify]); |
158 show "?t : ?T"; by (rule dominoes_tile_row); |
158 show "?t : ?T"; by (rule dominoes_tile_row); |
247 subsection {* Main theorem *}; |
247 subsection {* Main theorem *}; |
248 |
248 |
249 constdefs |
249 constdefs |
250 mutilated_board :: "nat => nat => (nat * nat) set" |
250 mutilated_board :: "nat => nat => (nat * nat) set" |
251 "mutilated_board m n == |
251 "mutilated_board m n == |
252 below (2 * (m + 1)) Times below (2 * (n + 1)) |
252 below (2 * (m + 1)) <*> below (2 * (n + 1)) |
253 - {(0, 0)} - {(2 * m + 1, 2 * n + 1)}"; |
253 - {(0, 0)} - {(2 * m + 1, 2 * n + 1)}"; |
254 |
254 |
255 theorem mutil_not_tiling: "mutilated_board m n ~: tiling domino"; |
255 theorem mutil_not_tiling: "mutilated_board m n ~: tiling domino"; |
256 proof (unfold mutilated_board_def); |
256 proof (unfold mutilated_board_def); |
257 let ?T = "tiling domino"; |
257 let ?T = "tiling domino"; |
258 let ?t = "below (2 * (m + 1)) Times below (2 * (n + 1))"; |
258 let ?t = "below (2 * (m + 1)) <*> below (2 * (n + 1))"; |
259 let ?t' = "?t - {(0, 0)}"; |
259 let ?t' = "?t - {(0, 0)}"; |
260 let ?t'' = "?t' - {(2 * m + 1, 2 * n + 1)}"; |
260 let ?t'' = "?t' - {(2 * m + 1, 2 * n + 1)}"; |
261 |
261 |
262 show "?t'' ~: ?T"; |
262 show "?t'' ~: ?T"; |
263 proof; |
263 proof; |