src/HOL/Isar_examples/MutilatedCheckerboard.thy
changeset 7800 8ee919e42174
parent 7761 7fab9592384f
child 7874 180364256231
equal deleted inserted replaced
7799:4c69318e6a6d 7800:8ee919e42174
    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;