42 |
42 |
43 Addsimps [evnodd_cons, evnodd_0]; |
43 Addsimps [evnodd_cons, evnodd_0]; |
44 |
44 |
45 (*** Dominoes ***) |
45 (*** Dominoes ***) |
46 |
46 |
47 Goal "d:domino ==> Finite(d)"; |
47 Goal "d \\<in> domino ==> Finite(d)"; |
48 by (blast_tac (claset() addSIs [Finite_cons, Finite_0] addEs [domino.elim]) 1); |
48 by (blast_tac (claset() addSIs [Finite_cons, Finite_0] addEs [domino.elim]) 1); |
49 qed "domino_Finite"; |
49 qed "domino_Finite"; |
50 |
50 |
51 Goal "[| d:domino; b<2 |] ==> EX i' j'. evnodd(d,b) = {<i',j'>}"; |
51 Goal "[| d \\<in> domino; b<2 |] ==> \\<exists>i' j'. evnodd(d,b) = {<i',j'>}"; |
52 by (eresolve_tac [domino.elim] 1); |
52 by (eresolve_tac [domino.elim] 1); |
53 by (res_inst_tac [("k1", "i#+j")] (mod2_cases RS disjE) 2); |
53 by (res_inst_tac [("k1", "i#+j")] (mod2_cases RS disjE) 2); |
54 by (res_inst_tac [("k1", "i#+j")] (mod2_cases RS disjE) 1); |
54 by (res_inst_tac [("k1", "i#+j")] (mod2_cases RS disjE) 1); |
55 by (REPEAT_FIRST (ares_tac [add_type])); |
55 by (REPEAT_FIRST (ares_tac [add_type])); |
56 (*Four similar cases: case (i#+j) mod 2 = b, 2#-b, ...*) |
56 (*Four similar cases: case (i#+j) mod 2 = b, 2#-b, ...*) |
61 |
61 |
62 (*** Tilings ***) |
62 (*** Tilings ***) |
63 |
63 |
64 (** The union of two disjoint tilings is a tiling **) |
64 (** The union of two disjoint tilings is a tiling **) |
65 |
65 |
66 Goal "t: tiling(A) ==> \ |
66 Goal "t \\<in> tiling(A) ==> \ |
67 \ u: tiling(A) --> t Int u = 0 --> t Un u : tiling(A)"; |
67 \ u \\<in> tiling(A) --> t Int u = 0 --> t Un u \\<in> tiling(A)"; |
68 by (etac tiling.induct 1); |
68 by (etac tiling.induct 1); |
69 by (simp_tac (simpset() addsimps tiling.intrs) 1); |
69 by (simp_tac (simpset() addsimps tiling.intrs) 1); |
70 by (asm_full_simp_tac (simpset() addsimps [Un_assoc, |
70 by (asm_full_simp_tac (simpset() addsimps [Un_assoc, |
71 subset_empty_iff RS iff_sym]) 1); |
71 subset_empty_iff RS iff_sym]) 1); |
72 by (blast_tac (claset() addIs tiling.intrs) 1); |
72 by (blast_tac (claset() addIs tiling.intrs) 1); |
73 qed_spec_mp "tiling_UnI"; |
73 qed_spec_mp "tiling_UnI"; |
74 |
74 |
75 Goal "t:tiling(domino) ==> Finite(t)"; |
75 Goal "t \\<in> tiling(domino) ==> Finite(t)"; |
76 by (eresolve_tac [tiling.induct] 1); |
76 by (eresolve_tac [tiling.induct] 1); |
77 by (rtac Finite_0 1); |
77 by (rtac Finite_0 1); |
78 by (blast_tac (claset() addSIs [Finite_Un] addIs [domino_Finite]) 1); |
78 by (blast_tac (claset() addSIs [Finite_Un] addIs [domino_Finite]) 1); |
79 qed "tiling_domino_Finite"; |
79 qed "tiling_domino_Finite"; |
80 |
80 |
81 Goal "t: tiling(domino) ==> |evnodd(t,0)| = |evnodd(t,1)|"; |
81 Goal "t \\<in> tiling(domino) ==> |evnodd(t,0)| = |evnodd(t,1)|"; |
82 by (eresolve_tac [tiling.induct] 1); |
82 by (eresolve_tac [tiling.induct] 1); |
83 by (simp_tac (simpset() addsimps [evnodd_def]) 1); |
83 by (simp_tac (simpset() addsimps [evnodd_def]) 1); |
84 by (res_inst_tac [("b1","0")] (domino_singleton RS exE) 1); |
84 by (res_inst_tac [("b1","0")] (domino_singleton RS exE) 1); |
85 by (Simp_tac 2 THEN assume_tac 1); |
85 by (Simp_tac 2 THEN assume_tac 1); |
86 by (res_inst_tac [("b1","1")] (domino_singleton RS exE) 1); |
86 by (res_inst_tac [("b1","1")] (domino_singleton RS exE) 1); |
87 by (Simp_tac 2 THEN assume_tac 1); |
87 by (Simp_tac 2 THEN assume_tac 1); |
88 by Safe_tac; |
88 by Safe_tac; |
89 by (subgoal_tac "ALL p b. p:evnodd(a,b) --> p~:evnodd(t,b)" 1); |
89 by (subgoal_tac "\\<forall>p b. p \\<in> evnodd(a,b) --> p\\<notin>evnodd(t,b)" 1); |
90 by (asm_simp_tac |
90 by (asm_simp_tac |
91 (simpset() addsimps [evnodd_Un, Un_cons, tiling_domino_Finite, |
91 (simpset() addsimps [evnodd_Un, Un_cons, tiling_domino_Finite, |
92 evnodd_subset RS subset_Finite, |
92 evnodd_subset RS subset_Finite, |
93 Finite_imp_cardinal_cons]) 1); |
93 Finite_imp_cardinal_cons]) 1); |
94 by (blast_tac (claset() addSDs [evnodd_subset RS subsetD] |
94 by (blast_tac (claset() addSDs [evnodd_subset RS subsetD] |
95 addEs [equalityE]) 1); |
95 addEs [equalityE]) 1); |
96 qed "tiling_domino_0_1"; |
96 qed "tiling_domino_0_1"; |
97 |
97 |
98 Goal "[| i: nat; n: nat |] ==> {i} * (n #+ n) : tiling(domino)"; |
98 Goal "[| i \\<in> nat; n \\<in> nat |] ==> {i} * (n #+ n) \\<in> tiling(domino)"; |
99 by (induct_tac "n" 1); |
99 by (induct_tac "n" 1); |
100 by (simp_tac (simpset() addsimps tiling.intrs) 1); |
100 by (simp_tac (simpset() addsimps tiling.intrs) 1); |
101 by (asm_simp_tac (simpset() addsimps [Un_assoc RS sym, Sigma_succ2]) 1); |
101 by (asm_simp_tac (simpset() addsimps [Un_assoc RS sym, Sigma_succ2]) 1); |
102 by (resolve_tac tiling.intrs 1); |
102 by (resolve_tac tiling.intrs 1); |
103 by (assume_tac 2); |
103 by (assume_tac 2); |
107 by (Blast_tac 2); |
107 by (Blast_tac 2); |
108 by (asm_simp_tac (simpset() addsimps [domino.horiz]) 1); |
108 by (asm_simp_tac (simpset() addsimps [domino.horiz]) 1); |
109 by (blast_tac (claset() addEs [mem_irrefl, mem_asym]) 1); |
109 by (blast_tac (claset() addEs [mem_irrefl, mem_asym]) 1); |
110 qed "dominoes_tile_row"; |
110 qed "dominoes_tile_row"; |
111 |
111 |
112 Goal "[| m: nat; n: nat |] ==> m * (n #+ n) : tiling(domino)"; |
112 Goal "[| m \\<in> nat; n \\<in> nat |] ==> m * (n #+ n) \\<in> tiling(domino)"; |
113 by (induct_tac "m" 1); |
113 by (induct_tac "m" 1); |
114 by (simp_tac (simpset() addsimps tiling.intrs) 1); |
114 by (simp_tac (simpset() addsimps tiling.intrs) 1); |
115 by (asm_simp_tac (simpset() addsimps [Sigma_succ1]) 1); |
115 by (asm_simp_tac (simpset() addsimps [Sigma_succ1]) 1); |
116 by (blast_tac (claset() addIs [tiling_UnI, dominoes_tile_row] |
116 by (blast_tac (claset() addIs [tiling_UnI, dominoes_tile_row] |
117 addEs [mem_irrefl]) 1); |
117 addEs [mem_irrefl]) 1); |
119 |
119 |
120 Goal "[| x=y; x<y |] ==> P"; |
120 Goal "[| x=y; x<y |] ==> P"; |
121 by Auto_tac; |
121 by Auto_tac; |
122 qed "eq_lt_E"; |
122 qed "eq_lt_E"; |
123 |
123 |
124 Goal "[| m: nat; n: nat; \ |
124 Goal "[| m \\<in> nat; n \\<in> nat; \ |
125 \ t = (succ(m)#+succ(m))*(succ(n)#+succ(n)); \ |
125 \ t = (succ(m)#+succ(m))*(succ(n)#+succ(n)); \ |
126 \ t' = t - {<0,0>} - {<succ(m#+m), succ(n#+n)>} |] \ |
126 \ t' = t - {<0,0>} - {<succ(m#+m), succ(n#+n)>} |] \ |
127 \ ==> t' ~: tiling(domino)"; |
127 \ ==> t' \\<notin> tiling(domino)"; |
128 by (rtac notI 1); |
128 by (rtac notI 1); |
129 by (dtac tiling_domino_0_1 1); |
129 by (dtac tiling_domino_0_1 1); |
130 by (eres_inst_tac [("x", "|?A|")] eq_lt_E 1); |
130 by (eres_inst_tac [("x", "|?A|")] eq_lt_E 1); |
131 by (subgoal_tac "t : tiling(domino)" 1); |
131 by (subgoal_tac "t \\<in> tiling(domino)" 1); |
132 (*Requires a small simpset that won't move the succ applications*) |
132 (*Requires a small simpset that won't move the succ applications*) |
133 by (asm_simp_tac (ZF_ss addsimps [nat_succI, add_type, |
133 by (asm_simp_tac (ZF_ss addsimps [nat_succI, add_type, |
134 dominoes_tile_matrix]) 2); |
134 dominoes_tile_matrix]) 2); |
135 by (asm_full_simp_tac |
135 by (asm_full_simp_tac |
136 (simpset() addsimps [evnodd_Diff, mod2_add_self, |
136 (simpset() addsimps [evnodd_Diff, mod2_add_self, |