author | nipkow |
Tue, 10 Mar 1998 19:02:53 +0100 | |
changeset 4723 | 9e2609b1bfb1 |
parent 4152 | 451104c223e2 |
child 5068 | fb28eaa07e01 |
permissions | -rw-r--r-- |
1606 | 1 |
(* Title: ZF/ex/Mutil |
2 |
ID: $Id$ |
|
3 |
Author: Lawrence C Paulson, Cambridge University Computer Laboratory |
|
4 |
Copyright 1996 University of Cambridge |
|
5 |
||
6 |
The Mutilated Checkerboard Problem, formalized inductively |
|
7 |
*) |
|
8 |
||
9 |
open Mutil; |
|
10 |
||
11 |
||
12 |
(** Basic properties of evnodd **) |
|
13 |
||
1624 | 14 |
goalw thy [evnodd_def] "<i,j>: evnodd(A,b) <-> <i,j>: A & (i#+j) mod 2 = b"; |
2875 | 15 |
by (Blast_tac 1); |
1624 | 16 |
qed "evnodd_iff"; |
1606 | 17 |
|
18 |
goalw thy [evnodd_def] "evnodd(A, b) <= A"; |
|
2875 | 19 |
by (Blast_tac 1); |
1606 | 20 |
qed "evnodd_subset"; |
21 |
||
22 |
(* Finite(X) ==> Finite(evnodd(X,b)) *) |
|
23 |
bind_thm("Finite_evnodd", evnodd_subset RS subset_imp_lepoll RS lepoll_Finite); |
|
24 |
||
25 |
goalw thy [evnodd_def] "evnodd(A Un B, b) = evnodd(A,b) Un evnodd(B,b)"; |
|
4091 | 26 |
by (simp_tac (simpset() addsimps [Collect_Un]) 1); |
1606 | 27 |
qed "evnodd_Un"; |
28 |
||
29 |
goalw thy [evnodd_def] "evnodd(A - B, b) = evnodd(A,b) - evnodd(B,b)"; |
|
4091 | 30 |
by (simp_tac (simpset() addsimps [Collect_Diff]) 1); |
1606 | 31 |
qed "evnodd_Diff"; |
32 |
||
33 |
goalw thy [evnodd_def] |
|
34 |
"evnodd(cons(<i,j>,C), b) = \ |
|
35 |
\ if((i#+j) mod 2 = b, cons(<i,j>, evnodd(C,b)), evnodd(C,b))"; |
|
4091 | 36 |
by (asm_simp_tac (simpset() addsimps [evnodd_def, Collect_cons] |
1606 | 37 |
setloop split_tac [expand_if]) 1); |
38 |
qed "evnodd_cons"; |
|
39 |
||
40 |
goalw thy [evnodd_def] "evnodd(0, b) = 0"; |
|
4091 | 41 |
by (simp_tac (simpset() addsimps [evnodd_def]) 1); |
1606 | 42 |
qed "evnodd_0"; |
43 |
||
2469 | 44 |
Addsimps [evnodd_cons, evnodd_0]; |
1606 | 45 |
|
46 |
(*** Dominoes ***) |
|
47 |
||
48 |
goal thy "!!d. d:domino ==> Finite(d)"; |
|
4091 | 49 |
by (blast_tac (claset() addSIs [Finite_cons, Finite_0] addEs [domino.elim]) 1); |
1606 | 50 |
qed "domino_Finite"; |
51 |
||
52 |
goal thy "!!d. [| d:domino; b<2 |] ==> EX i' j'. evnodd(d,b) = {<i',j'>}"; |
|
53 |
by (eresolve_tac [domino.elim] 1); |
|
54 |
by (res_inst_tac [("k1", "i#+j")] (mod2_cases RS disjE) 2); |
|
55 |
by (res_inst_tac [("k1", "i#+j")] (mod2_cases RS disjE) 1); |
|
56 |
by (REPEAT_FIRST (ares_tac [add_type])); |
|
57 |
(*Four similar cases: case (i#+j) mod 2 = b, 2#-b, ...*) |
|
4091 | 58 |
by (REPEAT (asm_simp_tac (simpset() addsimps [mod_succ, succ_neq_self] |
1606 | 59 |
setloop split_tac [expand_if]) 1 |
4091 | 60 |
THEN blast_tac (claset() addDs [ltD]) 1)); |
1606 | 61 |
qed "domino_singleton"; |
62 |
||
63 |
||
64 |
(*** Tilings ***) |
|
65 |
||
66 |
(** The union of two disjoint tilings is a tiling **) |
|
67 |
||
68 |
goal thy "!!t. t: tiling(A) ==> \ |
|
1630 | 69 |
\ u: tiling(A) --> t Int u = 0 --> t Un u : tiling(A)"; |
1606 | 70 |
by (etac tiling.induct 1); |
4091 | 71 |
by (simp_tac (simpset() addsimps tiling.intrs) 1); |
72 |
by (asm_full_simp_tac (simpset() addsimps [Un_assoc, |
|
2875 | 73 |
subset_empty_iff RS iff_sym]) 1); |
4091 | 74 |
by (blast_tac (claset() addIs tiling.intrs) 1); |
3732 | 75 |
qed_spec_mp "tiling_UnI"; |
1606 | 76 |
|
77 |
goal thy "!!t. t:tiling(domino) ==> Finite(t)"; |
|
78 |
by (eresolve_tac [tiling.induct] 1); |
|
4152 | 79 |
by (rtac Finite_0 1); |
4091 | 80 |
by (blast_tac (claset() addSIs [Finite_Un] addIs [domino_Finite]) 1); |
1606 | 81 |
qed "tiling_domino_Finite"; |
82 |
||
83 |
goal thy "!!t. t: tiling(domino) ==> |evnodd(t,0)| = |evnodd(t,1)|"; |
|
84 |
by (eresolve_tac [tiling.induct] 1); |
|
4091 | 85 |
by (simp_tac (simpset() addsimps [evnodd_def]) 1); |
1624 | 86 |
by (res_inst_tac [("b1","0")] (domino_singleton RS exE) 1); |
2469 | 87 |
by (Simp_tac 2 THEN assume_tac 1); |
1624 | 88 |
by (res_inst_tac [("b1","1")] (domino_singleton RS exE) 1); |
2469 | 89 |
by (Simp_tac 2 THEN assume_tac 1); |
2896 | 90 |
by (Step_tac 1); |
1624 | 91 |
by (subgoal_tac "ALL p b. p:evnodd(a,b) --> p~:evnodd(ta,b)" 1); |
4091 | 92 |
by (asm_simp_tac (simpset() addsimps [evnodd_Un, Un_cons, tiling_domino_Finite, |
2469 | 93 |
evnodd_subset RS subset_Finite, |
94 |
Finite_imp_cardinal_cons]) 1); |
|
4091 | 95 |
by (blast_tac (claset() addSDs [evnodd_subset RS subsetD] addEs [equalityE]) 1); |
1606 | 96 |
qed "tiling_domino_0_1"; |
97 |
||
98 |
goal thy "!!i n. [| i: nat; n: nat |] ==> {i} * (n #+ n) : tiling(domino)"; |
|
99 |
by (nat_ind_tac "n" [] 1); |
|
4091 | 100 |
by (simp_tac (simpset() addsimps tiling.intrs) 1); |
101 |
by (asm_simp_tac (simpset() addsimps [Un_assoc RS sym, Sigma_succ2]) 1); |
|
1606 | 102 |
by (resolve_tac tiling.intrs 1); |
103 |
by (assume_tac 2); |
|
2469 | 104 |
by (subgoal_tac (*seems the easiest way of turning one to the other*) |
1606 | 105 |
"{i}*{succ(n1#+n1)} Un {i}*{n1#+n1} = {<i,n1#+n1>, <i,succ(n1#+n1)>}" 1); |
2875 | 106 |
by (Blast_tac 2); |
4091 | 107 |
by (asm_simp_tac (simpset() addsimps [domino.horiz]) 1); |
108 |
by (blast_tac (claset() addEs [mem_irrefl, mem_asym]) 1); |
|
1606 | 109 |
qed "dominoes_tile_row"; |
110 |
||
111 |
goal thy "!!m n. [| m: nat; n: nat |] ==> m * (n #+ n) : tiling(domino)"; |
|
112 |
by (nat_ind_tac "m" [] 1); |
|
4091 | 113 |
by (simp_tac (simpset() addsimps tiling.intrs) 1); |
114 |
by (asm_simp_tac (simpset() addsimps [Sigma_succ1]) 1); |
|
115 |
by (blast_tac (claset() addIs [tiling_UnI, dominoes_tile_row] |
|
1606 | 116 |
addEs [mem_irrefl]) 1); |
117 |
qed "dominoes_tile_matrix"; |
|
118 |
||
119 |
||
120 |
goal thy "!!m n. [| m: nat; n: nat; \ |
|
121 |
\ t = (succ(m)#+succ(m))*(succ(n)#+succ(n)); \ |
|
122 |
\ t' = t - {<0,0>} - {<succ(m#+m), succ(n#+n)>} |] ==> \ |
|
123 |
\ t' ~: tiling(domino)"; |
|
4152 | 124 |
by (rtac notI 1); |
125 |
by (dtac tiling_domino_0_1 1); |
|
1606 | 126 |
by (subgoal_tac "|evnodd(t',0)| < |evnodd(t',1)|" 1); |
4091 | 127 |
by (asm_full_simp_tac (simpset() addsimps [lt_not_refl]) 1); |
1606 | 128 |
by (subgoal_tac "t : tiling(domino)" 1); |
1624 | 129 |
(*Requires a small simpset that won't move the succ applications*) |
1606 | 130 |
by (asm_simp_tac (ZF_ss addsimps [nat_succI, add_type, |
2469 | 131 |
dominoes_tile_matrix]) 2); |
1606 | 132 |
by (subgoal_tac "(m#+m)#+(n#+n) = (m#+n)#+(m#+n)" 1); |
4091 | 133 |
by (asm_simp_tac (simpset() addsimps add_ac) 2); |
4723
9e2609b1bfb1
Adapted proofs because of new simplification tactics.
nipkow
parents:
4152
diff
changeset
|
134 |
by (asm_lr_simp_tac |
4091 | 135 |
(simpset() addsimps [evnodd_Diff, mod2_add_self, |
2469 | 136 |
mod2_succ_succ, tiling_domino_0_1 RS sym]) 1); |
4152 | 137 |
by (rtac lt_trans 1); |
1606 | 138 |
by (REPEAT |
139 |
(rtac Finite_imp_cardinal_Diff 1 |
|
140 |
THEN |
|
4091 | 141 |
asm_simp_tac (simpset() addsimps [tiling_domino_Finite, Finite_evnodd, |
2469 | 142 |
Finite_Diff]) 1 |
1606 | 143 |
THEN |
4091 | 144 |
asm_simp_tac (simpset() addsimps [evnodd_iff, nat_0_le RS ltD, |
2469 | 145 |
mod2_add_self]) 1)); |
1606 | 146 |
qed "mutil_not_tiling"; |