src/ZF/ex/Mutil.ML
changeset 11316 b4e71bd751e4
parent 9548 15bee2731e43
equal deleted inserted replaced
11315:fbca0f74bcef 11316:b4e71bd751e4
    13 
    13 
    14 Goalw [evnodd_def] "<i,j>: evnodd(A,b) <-> <i,j>: A & (i#+j) mod 2 = b";
    14 Goalw [evnodd_def] "<i,j>: evnodd(A,b) <-> <i,j>: A & (i#+j) mod 2 = b";
    15 by (Blast_tac 1);
    15 by (Blast_tac 1);
    16 qed "evnodd_iff";
    16 qed "evnodd_iff";
    17 
    17 
    18 Goalw [evnodd_def] "evnodd(A, b) <= A";
    18 Goalw [evnodd_def] "evnodd(A, b) \\<subseteq> A";
    19 by (Blast_tac 1);
    19 by (Blast_tac 1);
    20 qed "evnodd_subset";
    20 qed "evnodd_subset";
    21 
    21 
    22 (* Finite(X) ==> Finite(evnodd(X,b)) *)
    22 (* Finite(X) ==> Finite(evnodd(X,b)) *)
    23 bind_thm("Finite_evnodd", evnodd_subset RS subset_imp_lepoll RS lepoll_Finite);
    23 bind_thm("Finite_evnodd", evnodd_subset RS subset_imp_lepoll RS lepoll_Finite);
    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,