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); |