src/HOL/ex/Simult.ML
changeset 1820 e381e1c51689
parent 1476 608483c2122a
child 1888 acb7363994cb
equal deleted inserted replaced
1819:245721624c8d 1820:e381e1c51689
    27 by (REPEAT (ares_tac [lfp_mono, subset_refl, usum_mono, uprod_mono] 1));
    27 by (REPEAT (ares_tac [lfp_mono, subset_refl, usum_mono, uprod_mono] 1));
    28 qed "TF_mono";
    28 qed "TF_mono";
    29 
    29 
    30 goalw Simult.thy [TF_def] "TF(sexp) <= sexp";
    30 goalw Simult.thy [TF_def] "TF(sexp) <= sexp";
    31 by (rtac lfp_lowerbound 1);
    31 by (rtac lfp_lowerbound 1);
    32 by (fast_tac (univ_cs addIs  sexp.intrs@[sexp_In0I, sexp_In1I]
    32 by (fast_tac (!claset addIs  sexp.intrs@[sexp_In0I, sexp_In1I]
    33                       addSEs [PartE]) 1);
    33                       addSEs [PartE]) 1);
    34 qed "TF_sexp";
    34 qed "TF_sexp";
    35 
    35 
    36 (* A <= sexp ==> TF(A) <= sexp *)
    36 (* A <= sexp ==> TF(A) <= sexp *)
    37 val TF_subset_sexp = standard
    37 val TF_subset_sexp = standard
    48 \    R(FNIL);                   \
    48 \    R(FNIL);                   \
    49 \    !!M N. [| M:  Part (TF A) In0;  N: Part (TF A) In1;  R(M);  R(N) \
    49 \    !!M N. [| M:  Part (TF A) In0;  N: Part (TF A) In1;  R(M);  R(N) \
    50 \            |] ==> R(FCONS M N)    \
    50 \            |] ==> R(FCONS M N)    \
    51 \    |] ==> R(i)";
    51 \    |] ==> R(i)";
    52 by (rtac ([TF_def, TF_fun_mono, major] MRS def_induct) 1);
    52 by (rtac ([TF_def, TF_fun_mono, major] MRS def_induct) 1);
    53 by (fast_tac (set_cs addIs (prems@[PartI])
    53 by (fast_tac (!claset addIs (prems@[PartI])
    54                        addEs [usumE, uprodE, PartE]) 1);
    54                        addEs [usumE, uprodE, PartE]) 1);
    55 qed "TF_induct";
    55 qed "TF_induct";
    56 
    56 
    57 (*This lemma replaces a use of subgoal_tac to prove tree_forest_induct*)
    57 (*This lemma replaces a use of subgoal_tac to prove tree_forest_induct*)
    58 val prems = goalw Simult.thy [Part_def]
    58 val prems = goalw Simult.thy [Part_def]
    59  "! M: TF(A). (M: Part (TF A) In0 --> P(M)) & (M: Part (TF A) In1 --> Q(M)) \
    59  "! M: TF(A). (M: Part (TF A) In0 --> P(M)) & (M: Part (TF A) In1 --> Q(M)) \
    60 \ ==> (! M: Part (TF A) In0. P(M)) & (! M: Part (TF A) In1. Q(M))";
    60 \ ==> (! M: Part (TF A) In0. P(M)) & (! M: Part (TF A) In1. Q(M))";
    61 by (cfast_tac prems 1);
    61 by (cfast_tac prems 1);
    62 qed "TF_induct_lemma";
    62 qed "TF_induct_lemma";
    63 
    63 
    64 val uplus_cs = set_cs addSIs [PartI]
    64 AddSIs [PartI];
    65                       addSDs [In0_inject, In1_inject]
    65 AddSDs [In0_inject, In1_inject];
    66                       addSEs [In0_neq_In1, In1_neq_In0, PartE];
    66 AddSEs [In0_neq_In1, In1_neq_In0, PartE];
    67 
    67 
    68 (*Could prove  ~ TCONS M N : Part (TF A) In1  etc. *)
    68 (*Could prove  ~ TCONS M N : Part (TF A) In1  etc. *)
    69 
    69 
    70 (*Induction on TF with separate predicates P, Q*)
    70 (*Induction on TF with separate predicates P, Q*)
    71 val prems = goalw Simult.thy TF_Rep_defs
    71 val prems = goalw Simult.thy TF_Rep_defs
    75 \               |] ==> Q(FCONS M N)     \
    75 \               |] ==> Q(FCONS M N)     \
    76 \    |] ==> (! M: Part (TF A) In0. P(M)) & (! N: Part (TF A) In1. Q(N))";
    76 \    |] ==> (! M: Part (TF A) In0. P(M)) & (! N: Part (TF A) In1. Q(N))";
    77 by (rtac (ballI RS TF_induct_lemma) 1);
    77 by (rtac (ballI RS TF_induct_lemma) 1);
    78 by (etac TF_induct 1);
    78 by (etac TF_induct 1);
    79 by (rewrite_goals_tac TF_Rep_defs);
    79 by (rewrite_goals_tac TF_Rep_defs);
    80 by (ALLGOALS (fast_tac (uplus_cs addIs prems)));
    80 by (ALLGOALS (fast_tac (!claset addIs prems)));
    81 (*29 secs??*)
    81 (*29 secs??*)
    82 qed "Tree_Forest_induct";
    82 qed "Tree_Forest_induct";
    83 
    83 
    84 (*Induction for the abstract types 'a tree, 'a forest*)
    84 (*Induction for the abstract types 'a tree, 'a forest*)
    85 val prems = goalw Simult.thy [Tcons_def,Fnil_def,Fcons_def]
    85 val prems = goalw Simult.thy [Tcons_def,Fnil_def,Fcons_def]
    89 \    |] ==> (! t. P(t)) & (! ts. Q(ts))";
    89 \    |] ==> (! t. P(t)) & (! ts. Q(ts))";
    90 by (res_inst_tac [("P1","%z.P(Abs_Tree(z))"),
    90 by (res_inst_tac [("P1","%z.P(Abs_Tree(z))"),
    91                   ("Q1","%z.Q(Abs_Forest(z))")] 
    91                   ("Q1","%z.Q(Abs_Forest(z))")] 
    92     (Tree_Forest_induct RS conjE) 1);
    92     (Tree_Forest_induct RS conjE) 1);
    93 (*Instantiates ?A1 to range(Leaf). *)
    93 (*Instantiates ?A1 to range(Leaf). *)
    94 by (fast_tac (set_cs addSEs [Rep_Tree_inverse RS subst, 
    94 by (fast_tac (!claset addSEs [Rep_Tree_inverse RS subst, 
    95                              Rep_Forest_inverse RS subst] 
    95                              Rep_Forest_inverse RS subst] 
    96                      addSIs [Rep_Tree,Rep_Forest]) 4);
    96                      addSIs [Rep_Tree,Rep_Forest]) 4);
    97 (*Cannot use simplifier: the rewrites work in the wrong direction!*)
    97 (*Cannot use simplifier: the rewrites work in the wrong direction!*)
    98 by (ALLGOALS (fast_tac (set_cs addSEs [Abs_Tree_inverse RS subst,
    98 by (ALLGOALS (fast_tac (!claset addSEs [Abs_Tree_inverse RS subst,
    99                           Abs_Forest_inverse RS subst] 
    99                           Abs_Forest_inverse RS subst] 
   100                      addSIs prems)));
   100                      addSIs prems)));
   101 qed "tree_forest_induct";
   101 qed "tree_forest_induct";
   102 
   102 
   103 
   103 
   129 (* c : A <*> Part (TF A) In1 
   129 (* c : A <*> Part (TF A) In1 
   130         <+> {Numb(0)} <+> Part (TF A) In0 <*> Part (TF A) In1 ==> c : TF(A) *)
   130         <+> {Numb(0)} <+> Part (TF A) In0 <*> Part (TF A) In1 ==> c : TF(A) *)
   131 val TF_I = TF_unfold RS equalityD2 RS subsetD;
   131 val TF_I = TF_unfold RS equalityD2 RS subsetD;
   132 
   132 
   133 (*For reasoning about the representation*)
   133 (*For reasoning about the representation*)
   134 val TF_Rep_cs = uplus_cs addIs [TF_I, uprodI, usum_In0I, usum_In1I]
   134 AddIs [TF_I, uprodI, usum_In0I, usum_In1I];
   135                          addSEs [Scons_inject];
   135 AddSEs [Scons_inject];
   136 
   136 
   137 val prems = goalw Simult.thy TF_Rep_defs
   137 val prems = goalw Simult.thy TF_Rep_defs
   138     "[| a: A;  M: Part (TF A) In1 |] ==> TCONS a M : Part (TF A) In0";
   138     "[| a: A;  M: Part (TF A) In1 |] ==> TCONS a M : Part (TF A) In0";
   139 by (fast_tac (TF_Rep_cs addIs prems) 1);
   139 by (fast_tac (!claset addIs prems) 1);
   140 qed "TCONS_I";
   140 qed "TCONS_I";
   141 
   141 
   142 (* FNIL is a TF(A) -- this also justifies the type definition*)
   142 (* FNIL is a TF(A) -- this also justifies the type definition*)
   143 goalw Simult.thy TF_Rep_defs "FNIL: Part (TF A) In1";
   143 goalw Simult.thy TF_Rep_defs "FNIL: Part (TF A) In1";
   144 by (fast_tac TF_Rep_cs 1);
   144 by (Fast_tac 1);
   145 qed "FNIL_I";
   145 qed "FNIL_I";
   146 
   146 
   147 val prems = goalw Simult.thy TF_Rep_defs
   147 val prems = goalw Simult.thy TF_Rep_defs
   148     "[| M: Part (TF A) In0;  N: Part (TF A) In1 |] ==> \
   148     "[| M: Part (TF A) In0;  N: Part (TF A) In1 |] ==> \
   149 \    FCONS M N : Part (TF A) In1";
   149 \    FCONS M N : Part (TF A) In1";
   150 by (fast_tac (TF_Rep_cs addIs prems) 1);
   150 by (fast_tac (!claset addIs prems) 1);
   151 qed "FCONS_I";
   151 qed "FCONS_I";
   152 
   152 
   153 (** Injectiveness of TCONS and FCONS **)
   153 (** Injectiveness of TCONS and FCONS **)
   154 
   154 
   155 goalw Simult.thy TF_Rep_defs "(TCONS K M=TCONS L N) = (K=L & M=N)";
   155 goalw Simult.thy TF_Rep_defs "(TCONS K M=TCONS L N) = (K=L & M=N)";
   156 by (fast_tac TF_Rep_cs 1);
   156 by (Fast_tac 1);
   157 qed "TCONS_TCONS_eq";
   157 qed "TCONS_TCONS_eq";
   158 bind_thm ("TCONS_inject", (TCONS_TCONS_eq RS iffD1 RS conjE));
   158 bind_thm ("TCONS_inject", (TCONS_TCONS_eq RS iffD1 RS conjE));
   159 
   159 
   160 goalw Simult.thy TF_Rep_defs "(FCONS K M=FCONS L N) = (K=L & M=N)";
   160 goalw Simult.thy TF_Rep_defs "(FCONS K M=FCONS L N) = (K=L & M=N)";
   161 by (fast_tac TF_Rep_cs 1);
   161 by (Fast_tac 1);
   162 qed "FCONS_FCONS_eq";
   162 qed "FCONS_FCONS_eq";
   163 bind_thm ("FCONS_inject", (FCONS_FCONS_eq RS iffD1 RS conjE));
   163 bind_thm ("FCONS_inject", (FCONS_FCONS_eq RS iffD1 RS conjE));
   164 
   164 
   165 (** Distinctness of TCONS, FNIL and FCONS **)
   165 (** Distinctness of TCONS, FNIL and FCONS **)
   166 
   166 
   167 goalw Simult.thy TF_Rep_defs "TCONS M N ~= FNIL";
   167 goalw Simult.thy TF_Rep_defs "TCONS M N ~= FNIL";
   168 by (fast_tac TF_Rep_cs 1);
   168 by (Fast_tac 1);
   169 qed "TCONS_not_FNIL";
   169 qed "TCONS_not_FNIL";
   170 bind_thm ("FNIL_not_TCONS", (TCONS_not_FNIL RS not_sym));
   170 bind_thm ("FNIL_not_TCONS", (TCONS_not_FNIL RS not_sym));
   171 
   171 
   172 bind_thm ("TCONS_neq_FNIL", (TCONS_not_FNIL RS notE));
   172 bind_thm ("TCONS_neq_FNIL", (TCONS_not_FNIL RS notE));
   173 val FNIL_neq_TCONS = sym RS TCONS_neq_FNIL;
   173 val FNIL_neq_TCONS = sym RS TCONS_neq_FNIL;
   174 
   174 
   175 goalw Simult.thy TF_Rep_defs "FCONS M N ~= FNIL";
   175 goalw Simult.thy TF_Rep_defs "FCONS M N ~= FNIL";
   176 by (fast_tac TF_Rep_cs 1);
   176 by (Fast_tac 1);
   177 qed "FCONS_not_FNIL";
   177 qed "FCONS_not_FNIL";
   178 bind_thm ("FNIL_not_FCONS", (FCONS_not_FNIL RS not_sym));
   178 bind_thm ("FNIL_not_FCONS", (FCONS_not_FNIL RS not_sym));
   179 
   179 
   180 bind_thm ("FCONS_neq_FNIL", (FCONS_not_FNIL RS notE));
   180 bind_thm ("FCONS_neq_FNIL", (FCONS_not_FNIL RS notE));
   181 val FNIL_neq_FCONS = sym RS FCONS_neq_FNIL;
   181 val FNIL_neq_FCONS = sym RS FCONS_neq_FNIL;
   182 
   182 
   183 goalw Simult.thy TF_Rep_defs "TCONS M N ~= FCONS K L";
   183 goalw Simult.thy TF_Rep_defs "TCONS M N ~= FCONS K L";
   184 by (fast_tac TF_Rep_cs 1);
   184 by (Fast_tac 1);
   185 qed "TCONS_not_FCONS";
   185 qed "TCONS_not_FCONS";
   186 bind_thm ("FCONS_not_TCONS", (TCONS_not_FCONS RS not_sym));
   186 bind_thm ("FCONS_not_TCONS", (TCONS_not_FCONS RS not_sym));
   187 
   187 
   188 bind_thm ("TCONS_neq_FCONS", (TCONS_not_FCONS RS notE));
   188 bind_thm ("TCONS_neq_FCONS", (TCONS_not_FCONS RS notE));
   189 val FCONS_neq_TCONS = sym RS TCONS_neq_FCONS;
   189 val FCONS_neq_TCONS = sym RS TCONS_neq_FCONS;
   192   Automatically generate symmetric forms?  Always expand TF_Rep_defs? *)
   192   Automatically generate symmetric forms?  Always expand TF_Rep_defs? *)
   193 
   193 
   194 (** Injectiveness of Tcons and Fcons **)
   194 (** Injectiveness of Tcons and Fcons **)
   195 
   195 
   196 (*For reasoning about abstract constructors*)
   196 (*For reasoning about abstract constructors*)
   197 val TF_cs = set_cs addSIs [Rep_Tree, Rep_Forest, TCONS_I, FNIL_I, FCONS_I]
   197 AddSIs [Rep_Tree, Rep_Forest, TCONS_I, FNIL_I, FCONS_I];
   198                    addSEs [TCONS_inject, FCONS_inject,
   198 AddSEs [TCONS_inject, FCONS_inject,
   199                            TCONS_neq_FNIL, FNIL_neq_TCONS,
   199                            TCONS_neq_FNIL, FNIL_neq_TCONS,
   200                            FCONS_neq_FNIL, FNIL_neq_FCONS,
   200                            FCONS_neq_FNIL, FNIL_neq_FCONS,
   201                            TCONS_neq_FCONS, FCONS_neq_TCONS]
   201                            TCONS_neq_FCONS, FCONS_neq_TCONS];
   202                    addSDs [inj_onto_Abs_Tree RS inj_ontoD,
   202 AddSDs [inj_onto_Abs_Tree RS inj_ontoD,
   203                            inj_onto_Abs_Forest RS inj_ontoD,
   203                            inj_onto_Abs_Forest RS inj_ontoD,
   204                            inj_Rep_Tree RS injD, inj_Rep_Forest RS injD,
   204                            inj_Rep_Tree RS injD, inj_Rep_Forest RS injD,
   205                            Leaf_inject];
   205                            Leaf_inject];
   206 
   206 
   207 goalw Simult.thy [Tcons_def] "(Tcons x xs=Tcons y ys) = (x=y & xs=ys)";
   207 goalw Simult.thy [Tcons_def] "(Tcons x xs=Tcons y ys) = (x=y & xs=ys)";
   208 by (fast_tac TF_cs 1);
   208 by (Fast_tac 1);
   209 qed "Tcons_Tcons_eq";
   209 qed "Tcons_Tcons_eq";
   210 bind_thm ("Tcons_inject", (Tcons_Tcons_eq RS iffD1 RS conjE));
   210 bind_thm ("Tcons_inject", (Tcons_Tcons_eq RS iffD1 RS conjE));
   211 
   211 
   212 goalw Simult.thy [Fcons_def,Fnil_def] "Fcons x xs ~= Fnil";
   212 goalw Simult.thy [Fcons_def,Fnil_def] "Fcons x xs ~= Fnil";
   213 by (fast_tac TF_cs 1);
   213 by (Fast_tac 1);
   214 qed "Fcons_not_Fnil";
   214 qed "Fcons_not_Fnil";
   215 
   215 
   216 bind_thm ("Fcons_neq_Fnil", Fcons_not_Fnil RS notE);
   216 bind_thm ("Fcons_neq_Fnil", Fcons_not_Fnil RS notE);
   217 val Fnil_neq_Fcons = sym RS Fcons_neq_Fnil;
   217 val Fnil_neq_Fcons = sym RS Fcons_neq_Fnil;
   218 
   218 
   219 
   219 
   220 (** Injectiveness of Fcons **)
   220 (** Injectiveness of Fcons **)
   221 
   221 
   222 goalw Simult.thy [Fcons_def] "(Fcons x xs=Fcons y ys) = (x=y & xs=ys)";
   222 goalw Simult.thy [Fcons_def] "(Fcons x xs=Fcons y ys) = (x=y & xs=ys)";
   223 by (fast_tac TF_cs 1);
   223 by (Fast_tac 1);
   224 qed "Fcons_Fcons_eq";
   224 qed "Fcons_Fcons_eq";
   225 bind_thm ("Fcons_inject", Fcons_Fcons_eq RS iffD1 RS conjE);
   225 bind_thm ("Fcons_inject", Fcons_Fcons_eq RS iffD1 RS conjE);
   226 
   226 
   227 
   227 
   228 (*** TF_rec -- by wf recursion on pred_sexp ***)
   228 (*** TF_rec -- by wf recursion on pred_sexp ***)