src/HOL/UNITY/Lift.ML
changeset 6570 a7d7985050a9
parent 6536 281d44905cab
child 6614 2d47dee036b5
equal deleted inserted replaced
6569:66c941ea1f01 6570:a7d7985050a9
    65 	  moving_up_def, moving_down_def];
    65 	  moving_up_def, moving_down_def];
    66 
    66 
    67 AddIffs [Min_le_Max];
    67 AddIffs [Min_le_Max];
    68 
    68 
    69 
    69 
    70 Goal "Lprg : Invariant open_stop";
    70 Goal "Lprg : Always open_stop";
    71 by (rtac InvariantI 1);
    71 by (rtac AlwaysI 1);
    72 by (Force_tac 1);
    72 by (Force_tac 1);
    73 by (constrains_tac 1);
    73 by (constrains_tac 1);
    74 qed "open_stop";
    74 qed "open_stop";
    75 
    75 
    76 Goal "Lprg : Invariant stop_floor";
    76 Goal "Lprg : Always stop_floor";
    77 by (rtac InvariantI 1);
    77 by (rtac AlwaysI 1);
    78 by (Force_tac 1);
    78 by (Force_tac 1);
    79 by (constrains_tac 1);
    79 by (constrains_tac 1);
    80 qed "stop_floor";
    80 qed "stop_floor";
    81 
    81 
    82 (*This one needs open_stop, which was proved above*)
    82 (*This one needs open_stop, which was proved above*)
    83 Goal "Lprg : Invariant open_move";
    83 Goal "Lprg : Always open_move";
    84 by (rtac InvariantI 1);
    84 by (rtac AlwaysI 1);
    85 by (rtac (open_stop RS Invariant_ConstrainsI RS StableI) 2);
    85 by (rtac (open_stop RS Always_ConstrainsI RS StableI) 2);
    86 by (Force_tac 1);
    86 by (Force_tac 1);
    87 by (constrains_tac 1);
    87 by (constrains_tac 1);
    88 qed "open_move";
    88 qed "open_move";
    89 
    89 
    90 Goal "Lprg : Invariant moving_up";
    90 Goal "Lprg : Always moving_up";
    91 by (rtac InvariantI 1);
    91 by (rtac AlwaysI 1);
    92 by (Force_tac 1);
    92 by (Force_tac 1);
    93 by (constrains_tac 1);
    93 by (constrains_tac 1);
    94 by (blast_tac (claset() addDs [zle_imp_zless_or_eq]) 1);
    94 by (blast_tac (claset() addDs [zle_imp_zless_or_eq]) 1);
    95 qed "moving_up";
    95 qed "moving_up";
    96 
    96 
    97 Goal "Lprg : Invariant moving_down";
    97 Goal "Lprg : Always moving_down";
    98 by (rtac InvariantI 1);
    98 by (rtac AlwaysI 1);
    99 by (Force_tac 1);
    99 by (Force_tac 1);
   100 by (constrains_tac 1);
   100 by (constrains_tac 1);
   101 by (blast_tac (claset() addDs [zle_imp_zless_or_eq]) 1);
   101 by (blast_tac (claset() addDs [zle_imp_zless_or_eq]) 1);
   102 qed "moving_down";
   102 qed "moving_down";
   103 
   103 
   104 Goal "Lprg : Invariant bounded";
   104 Goal "Lprg : Always bounded";
   105 by (rtac InvariantI 1);
   105 by (rtac AlwaysI 1);
   106 by (rtac (Invariant_Int_rule [moving_up, moving_down] RS Invariant_StableI) 2);
   106 by (rtac (Always_Int_rule [moving_up, moving_down] RS Always_StableI) 2);
   107 by (Force_tac 1);
   107 by (Force_tac 1);
   108 by (constrains_tac 1);
   108 by (constrains_tac 1);
   109 by (ALLGOALS Clarify_tac);
   109 by (ALLGOALS Clarify_tac);
   110 by (REPEAT_FIRST distinct_tac);
   110 by (REPEAT_FIRST distinct_tac);
   111 by Auto_tac;
   111 by Auto_tac;
   338 qed "lift_3_Req";
   338 qed "lift_3_Req";
   339 
   339 
   340 
   340 
   341 
   341 
   342 (*Now we observe that our integer metric is really a natural number*)
   342 (*Now we observe that our integer metric is really a natural number*)
   343 Goal "reachable Lprg <= {s. #0 <= metric n s}";
   343 Goal "Lprg : Always {s. #0 <= metric n s}";
   344 by (rtac (bounded RS Invariant_includes_reachable RS subset_trans) 1);
   344 by (rtac (bounded RS Always_weaken) 1);
   345 by (simp_tac (simpset() addsimps metric_simps @ zcompare_rls) 1);
   345 by (simp_tac (simpset() addsimps metric_simps @ zcompare_rls) 1);
   346 by (auto_tac (claset(),
   346 by (auto_tac (claset(),
   347 	      simpset() addsimps [zless_iff_Suc_zadd, zle_iff_zadd]));
   347 	      simpset() addsimps [zless_iff_Suc_zadd, zle_iff_zadd]));
   348 by (REPEAT_FIRST (etac ssubst));
   348 by (REPEAT_FIRST (etac ssubst));
   349 by (auto_tac (claset(), simpset() addsimps [zadd_int]));
   349 by (auto_tac (claset(), simpset() addsimps [zadd_int]));
   350 qed "reach_nonneg";
   350 qed "Always_nonneg";
   351 
   351 
   352 val R_thm11 = [reach_nonneg, E_thm11] MRS reachable_LeadsTo_weaken;
   352 val R_thm11 = [Always_nonneg, E_thm11] MRS Always_LeadsTo_weaken;
   353 
   353 
   354 Goal "Lprg : (moving Int Req n) LeadsTo (stopped Int atFloor n)";
   354 Goal "Lprg : (moving Int Req n) LeadsTo (stopped Int atFloor n)";
   355 by (rtac (reach_nonneg RS integ_0_le_induct) 1);
   355 by (rtac (Always_nonneg RS integ_0_le_induct) 1);
   356 by (case_tac "#0 < z" 1);
   356 by (case_tac "#0 < z" 1);
   357 (*If z <= #0 then actually z = #0*)
   357 (*If z <= #0 then actually z = #0*)
   358 by (fold_tac [zle_def]);
   358 by (fold_tac [zle_def]);
   359 by (force_tac (claset() addIs [R_thm11, zle_anti_sym], simpset()) 2);
   359 by (force_tac (claset() addIs [R_thm11, zle_anti_sym], simpset()) 2);
   360 by (rtac ([asm_rl, Un_upper1] MRS LeadsTo_weaken_R) 1);
   360 by (rtac ([asm_rl, Un_upper1] MRS LeadsTo_weaken_R) 1);
   372 by (rtac (E_thm01 RS LeadsTo_Trans_Un') 2);
   372 by (rtac (E_thm01 RS LeadsTo_Trans_Un') 2);
   373 by (rtac (lift_3 RS LeadsTo_Trans_Un') 2);
   373 by (rtac (lift_3 RS LeadsTo_Trans_Un') 2);
   374 by (rtac (lift_2 RS LeadsTo_Trans_Un') 2);
   374 by (rtac (lift_2 RS LeadsTo_Trans_Un') 2);
   375 by (rtac (E_thm03 RS LeadsTo_Trans_Un') 2);
   375 by (rtac (E_thm03 RS LeadsTo_Trans_Un') 2);
   376 by (rtac E_thm02 2);
   376 by (rtac E_thm02 2);
   377 by (rtac (open_move RS Invariant_LeadsToI) 1);
   377 by (rtac (open_move RS Always_LeadsToI) 1);
   378 by (rtac (open_stop RS Invariant_LeadsToI) 1);
   378 by (rtac (open_stop RS Always_LeadsToI) 1);
   379 by (rtac subset_imp_LeadsTo 1);
   379 by (rtac subset_imp_LeadsTo 1);
   380 by (Clarify_tac 1);
   380 by (Clarify_tac 1);
   381 (*The case split is not essential but makes Blast_tac much faster.
   381 (*The case split is not essential but makes Blast_tac much faster.
   382   Must also be careful to prevent simplification from looping*)
   382   Must also be careful to prevent simplification from looping*)
   383 by (case_tac "open x" 1);
   383 by (case_tac "open x" 1);