src/HOL/Lambda/Commutation.ML
changeset 1465 5d7a7e439cec
parent 1431 be7c6d77e19c
child 1641 46d2d4a249ca
equal deleted inserted replaced
1464:a608f83e3421 1465:5d7a7e439cec
    25 qed "square_reflcl";
    25 qed "square_reflcl";
    26 
    26 
    27 goalw Commutation.thy [square_def]
    27 goalw Commutation.thy [square_def]
    28   "!!R. square R S S T ==> square (R^*) S S (T^*)";
    28   "!!R. square R S S T ==> square (R^*) S S (T^*)";
    29 by(strip_tac 1);
    29 by(strip_tac 1);
    30 be rtrancl_induct 1;
    30 by (etac rtrancl_induct 1);
    31 by(fast_tac trancl_cs 1);
    31 by(fast_tac trancl_cs 1);
    32 by(fast_tac (HOL_cs addSEs [rtrancl_into_rtrancl]) 1);
    32 by(fast_tac (HOL_cs addSEs [rtrancl_into_rtrancl]) 1);
    33 qed "square_rtrancl";
    33 qed "square_rtrancl";
    34 
    34 
    35 goalw Commutation.thy [commute_def]
    35 goalw Commutation.thy [commute_def]
    36  "!!R. square R S (S^*) (R^=) ==> commute (R^*) (S^*)";
    36  "!!R. square R S (S^*) (R^=) ==> commute (R^*) (S^*)";
    37 bd square_reflcl 1;
    37 by (dtac square_reflcl 1);
    38 br subsetI 1;
    38 by (rtac subsetI 1);
    39 be r_into_rtrancl 1;
    39 by (etac r_into_rtrancl 1);
    40 bd square_sym 1;
    40 by (dtac square_sym 1);
    41 bd square_rtrancl 1;
    41 by (dtac square_rtrancl 1);
    42 by(Asm_full_simp_tac 1);
    42 by(Asm_full_simp_tac 1);
    43 bd square_sym 1;
    43 by (dtac square_sym 1);
    44 bd square_rtrancl 1;
    44 by (dtac square_rtrancl 1);
    45 by(Asm_full_simp_tac 1);
    45 by(Asm_full_simp_tac 1);
    46 qed "square_rtrancl_reflcl_commute";
    46 qed "square_rtrancl_reflcl_commute";
    47 
    47 
    48 (*** commute ***)
    48 (*** commute ***)
    49 
    49 
    66   "!!R. [| diamond R; diamond S; commute R S |] ==> diamond (R Un S)";
    66   "!!R. [| diamond R; diamond S; commute R S |] ==> diamond (R Un S)";
    67 by(REPEAT(ares_tac [commute_Un,commute_sym] 1));
    67 by(REPEAT(ares_tac [commute_Un,commute_sym] 1));
    68 qed "diamond_Un";
    68 qed "diamond_Un";
    69 
    69 
    70 goalw Commutation.thy [diamond_def] "!!R. diamond R ==> confluent (R)";
    70 goalw Commutation.thy [diamond_def] "!!R. diamond R ==> confluent (R)";
    71 be commute_rtrancl 1;
    71 by (etac commute_rtrancl 1);
    72 qed "diamond_confluent";
    72 qed "diamond_confluent";
    73 
    73 
    74 goalw Commutation.thy [diamond_def]
    74 goalw Commutation.thy [diamond_def]
    75   "!!R. square R R (R^=) (R^=) ==> confluent R";
    75   "!!R. square R R (R^=) (R^=) ==> confluent R";
    76 by(fast_tac (trancl_cs addIs [square_rtrancl_reflcl_commute,r_into_rtrancl]
    76 by(fast_tac (trancl_cs addIs [square_rtrancl_reflcl_commute,r_into_rtrancl]
    92 
    92 
    93 (*** Church_Rosser ***)
    93 (*** Church_Rosser ***)
    94 
    94 
    95 goalw Commutation.thy [square_def,commute_def,diamond_def,Church_Rosser_def]
    95 goalw Commutation.thy [square_def,commute_def,diamond_def,Church_Rosser_def]
    96   "Church_Rosser(R) = confluent(R)";
    96   "Church_Rosser(R) = confluent(R)";
    97 br iffI 1;
    97 by (rtac iffI 1);
    98  by(fast_tac (HOL_cs addIs
    98  by(fast_tac (HOL_cs addIs
    99       [Un_upper2 RS rtrancl_mono RS subsetD RS rtrancl_trans,
    99       [Un_upper2 RS rtrancl_mono RS subsetD RS rtrancl_trans,
   100        rtrancl_converseI, converseI, Un_upper1 RS rtrancl_mono RS subsetD])1);
   100        rtrancl_converseI, converseI, Un_upper1 RS rtrancl_mono RS subsetD])1);
   101 by(safe_tac HOL_cs);
   101 by(safe_tac HOL_cs);
   102 be rtrancl_induct 1;
   102 by (etac rtrancl_induct 1);
   103  by(fast_tac trancl_cs 1);
   103  by(fast_tac trancl_cs 1);
   104 by(slow_tac (rel_cs addIs [r_into_rtrancl]
   104 by(slow_tac (rel_cs addIs [r_into_rtrancl]
   105                     addEs [rtrancl_trans,r_into_rtrancl RS rtrancl_trans]) 1);
   105                     addEs [rtrancl_trans,r_into_rtrancl RS rtrancl_trans]) 1);
   106 qed "Church_Rosser_confluent";
   106 qed "Church_Rosser_confluent";