src/ZF/ex/Comb.ML
changeset 6144 7d38744313c8
parent 6141 a6922171b396
child 11316 b4e71bd751e4
equal deleted inserted replaced
6143:1eb364a68c54 6144:7d38744313c8
    38 
    38 
    39 val [_,_,comb_Ap] = comb.intrs;
    39 val [_,_,comb_Ap] = comb.intrs;
    40 val Ap_E = comb.mk_cases "p#q : comb";
    40 val Ap_E = comb.mk_cases "p#q : comb";
    41 
    41 
    42 AddSIs comb.intrs;
    42 AddSIs comb.intrs;
    43 AddSEs comb.free_SEs;
       
    44 
    43 
    45 
    44 
    46 (*** Results about Contraction ***)
    45 (*** Results about Contraction ***)
    47 
    46 
    48 (*For type checking: replaces a-1->b by a,b:comb *)
    47 (*For type checking: replaces a-1->b by a,b:comb *)
    85 
    84 
    86 AddIs  [contract.Ap1, contract.Ap2];
    85 AddIs  [contract.Ap1, contract.Ap2];
    87 AddSEs [K_contractE, S_contractE, Ap_contractE];
    86 AddSEs [K_contractE, S_contractE, Ap_contractE];
    88 
    87 
    89 Goalw [I_def] "I -1-> r ==> P";
    88 Goalw [I_def] "I -1-> r ==> P";
    90 by (Blast_tac 1);
    89 by Auto_tac;
    91 qed "I_contract_E";
    90 qed "I_contract_E";
    92 
    91 
    93 Goal "K#p -1-> r ==> (EX q. r = K#q & p -1-> q)";
    92 Goal "K#p -1-> r ==> (EX q. r = K#q & p -1-> q)";
    94 by (Blast_tac 1);
    93 by Auto_tac;
    95 qed "K1_contractD";
    94 qed "K1_contractD";
    96 
    95 
    97 Goal "[| p ---> q;  r: comb |] ==> p#r ---> q#r";
    96 Goal "[| p ---> q;  r: comb |] ==> p#r ---> q#r";
    98 by (forward_tac [rtrancl_type RS subsetD RS SigmaD1] 1);
    97 by (forward_tac [rtrancl_type RS subsetD RS SigmaD1] 1);
    99 by (dtac (field_contract_eq RS equalityD1 RS subsetD) 1);
    98 by (dtac (field_contract_eq RS equalityD1 RS subsetD) 1);
   154 AddSEs [Ap_E, K_parcontractE, S_parcontractE, Ap_parcontractE];
   153 AddSEs [Ap_E, K_parcontractE, S_parcontractE, Ap_parcontractE];
   155 
   154 
   156 (*** Basic properties of parallel contraction ***)
   155 (*** Basic properties of parallel contraction ***)
   157 
   156 
   158 Goal "K#p =1=> r ==> (EX p'. r = K#p' & p =1=> p')";
   157 Goal "K#p =1=> r ==> (EX p'. r = K#p' & p =1=> p')";
   159 by (Blast_tac 1);
   158 by Auto_tac;
   160 qed "K1_parcontractD";
   159 qed "K1_parcontractD";
       
   160 AddSDs [K1_parcontractD];
   161 
   161 
   162 Goal "S#p =1=> r ==> (EX p'. r = S#p' & p =1=> p')";
   162 Goal "S#p =1=> r ==> (EX p'. r = S#p' & p =1=> p')";
   163 by (Blast_tac 1);
   163 by Auto_tac;
   164 qed "S1_parcontractD";
   164 qed "S1_parcontractD";
       
   165 AddSDs [S1_parcontractD];
   165 
   166 
   166 Goal "S#p#q =1=> r ==> (EX p' q'. r = S#p'#q' & p =1=> p' & q =1=> q')";
   167 Goal "S#p#q =1=> r ==> (EX p' q'. r = S#p'#q' & p =1=> p' & q =1=> q')";
   167 by (blast_tac (claset() addSDs [S1_parcontractD]) 1);
   168 by Auto_tac;
   168 qed "S2_parcontractD";
   169 qed "S2_parcontractD";
       
   170 AddSDs [S2_parcontractD];
   169 
   171 
   170 (*Church-Rosser property for parallel contraction*)
   172 (*Church-Rosser property for parallel contraction*)
   171 Goalw [diamond_def] "diamond(parcontract)";
   173 Goalw [diamond_def] "diamond(parcontract)";
   172 by (rtac (impI RS allI RS allI) 1);
   174 by (rtac (impI RS allI RS allI) 1);
   173 by (etac parcontract.induct 1);
   175 by (etac parcontract.induct 1);
   174 by (ALLGOALS 
   176 by (ALLGOALS 
   175     (blast_tac (claset() addSDs [K1_parcontractD, S2_parcontractD]
   177     (blast_tac (claset() addSEs comb.free_SEs
   176                         addIs  [parcontract_combD2])));
   178 			 addIs [parcontract_combD2])));
   177 qed "diamond_parcontract";
   179 qed "diamond_parcontract";
   178 
   180 
   179 (*** Equivalence of p--->q and p===>q ***)
   181 (*** Equivalence of p--->q and p===>q ***)
   180 
   182 
   181 Goal "p-1->q ==> p=1=>q";
   183 Goal "p-1->q ==> p=1=>q";
   182 by (etac contract.induct 1);
   184 by (etac contract.induct 1);
   183 by (ALLGOALS Blast_tac);
   185 by Auto_tac;
   184 qed "contract_imp_parcontract";
   186 qed "contract_imp_parcontract";
   185 
   187 
   186 Goal "p--->q ==> p===>q";
   188 Goal "p--->q ==> p===>q";
   187 by (forward_tac [rtrancl_type RS subsetD RS SigmaD1] 1);
   189 by (forward_tac [rtrancl_type RS subsetD RS SigmaD1] 1);
   188 by (dtac (field_contract_eq RS equalityD1 RS subsetD) 1);
   190 by (dtac (field_contract_eq RS equalityD1 RS subsetD) 1);
   189 by (etac rtrancl_induct 1);
   191 by (etac rtrancl_induct 1);
   190 by (blast_tac (claset() addIs [r_into_trancl]) 1);
   192 by (blast_tac (claset() addIs [r_into_trancl]) 1);
   191 by (blast_tac (claset() addIs [contract_imp_parcontract, 
   193 by (blast_tac (claset() addIs [contract_imp_parcontract, 
   192 			      r_into_trancl, trans_trancl RS transD]) 1);
   194 			       r_into_trancl, trans_trancl RS transD]) 1);
   193 qed "reduce_imp_parreduce";
   195 qed "reduce_imp_parreduce";
   194 
   196 
   195 
   197 
   196 Goal "p=1=>q ==> p--->q";
   198 Goal "p=1=>q ==> p--->q";
   197 by (etac parcontract.induct 1);
   199 by (etac parcontract.induct 1);
   198 by (blast_tac (claset() addIs reduction_rls) 1);
   200 by (blast_tac (claset() addIs reduction_rls) 1);
   199 by (blast_tac (claset() addIs reduction_rls) 1);
   201 by (blast_tac (claset() addIs reduction_rls) 1);
   200 by (blast_tac (claset() addIs reduction_rls) 1);
   202 by (blast_tac (claset() addIs reduction_rls) 1);
   201 by (blast_tac 
   203 by (blast_tac 
   202     (claset() addIs [trans_rtrancl RS transD,
   204     (claset() addIs [trans_rtrancl RS transD,
   203 		    Ap_reduce1, Ap_reduce2, parcontract_combD1,
   205 		     Ap_reduce1, Ap_reduce2, parcontract_combD1,
   204 		    parcontract_combD2]) 1);
   206 		     parcontract_combD2]) 1);
   205 qed "parcontract_imp_reduce";
   207 qed "parcontract_imp_reduce";
   206 
   208 
   207 Goal "p===>q ==> p--->q";
   209 Goal "p===>q ==> p--->q";
   208 by (forward_tac [trancl_type RS subsetD RS SigmaD1] 1);
   210 by (forward_tac [trancl_type RS subsetD RS SigmaD1] 1);
   209 by (dtac (field_parcontract_eq RS equalityD1 RS subsetD) 1);
   211 by (dtac (field_parcontract_eq RS equalityD1 RS subsetD) 1);
   212 by (etac (trans_rtrancl RS transD) 1);
   214 by (etac (trans_rtrancl RS transD) 1);
   213 by (etac parcontract_imp_reduce 1);
   215 by (etac parcontract_imp_reduce 1);
   214 qed "parreduce_imp_reduce";
   216 qed "parreduce_imp_reduce";
   215 
   217 
   216 Goal "p===>q <-> p--->q";
   218 Goal "p===>q <-> p--->q";
   217 by (REPEAT (ares_tac [iffI, parreduce_imp_reduce, reduce_imp_parreduce] 1));
   219 by (blast_tac (claset() addIs [parreduce_imp_reduce, reduce_imp_parreduce]) 1);
   218 qed "parreduce_iff_reduce";
   220 qed "parreduce_iff_reduce";
   219 
   221 
   220 writeln"Reached end of file.";
   222 writeln"Reached end of file.";