src/HOL/Isar_examples/MutilatedCheckerboard.thy
changeset 8703 816d8f6513be
parent 8674 ac6c028e0249
child 8814 0a5edcbe0695
equal deleted inserted replaced
8702:78b7010db847 8703:816d8f6513be
    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;