src/HOL/TLA/TLA.ML
changeset 4477 b3e5857d8d99
parent 4423 a129b817b58a
child 4651 70dd492a1698
equal deleted inserted replaced
4476:fbdc87f8ac7e 4477:b3e5857d8d99
   133 bind_thm("dup_dmdD", (temp_unlift DmdDmd) RS iffD1);
   133 bind_thm("dup_dmdD", (temp_unlift DmdDmd) RS iffD1);
   134 
   134 
   135 
   135 
   136 (* ------------------------ STL4 ------------------------------------------- *)
   136 (* ------------------------ STL4 ------------------------------------------- *)
   137 qed_goal "STL4" TLA.thy "(F .-> G)  ==> ([]F .-> []G)"
   137 qed_goal "STL4" TLA.thy "(F .-> G)  ==> ([]F .-> []G)"
   138    (fn [prem] => [Auto_tac(),
   138    (fn [prem] => [Auto_tac,
   139 		  rtac ((temp_mp normalT) RS mp) 1,
   139 		  rtac ((temp_mp normalT) RS mp) 1,
   140 		  REPEAT (ares_tac [prem, necT RS tempD] 1)
   140 		  REPEAT (ares_tac [prem, necT RS tempD] 1)
   141 		 ]);
   141 		 ]);
   142 
   142 
   143 (* A more practical variant as an (unlifted) elimination rule *)
   143 (* A more practical variant as an (unlifted) elimination rule *)
   161    (fn prems => [ REPEAT (resolve_tac (prems @ [temp_mp DmdImpl]) 1) ]);
   161    (fn prems => [ REPEAT (resolve_tac (prems @ [temp_mp DmdImpl]) 1) ]);
   162 
   162 
   163 
   163 
   164 (* ------------------------ STL5 ------------------------------------------- *)
   164 (* ------------------------ STL5 ------------------------------------------- *)
   165 qed_goal "STL5" TLA.thy "([]F .& []G) .= ([](F .& G))"
   165 qed_goal "STL5" TLA.thy "([]F .& []G) .= ([](F .& G))"
   166    (fn _ => [Auto_tac(),
   166    (fn _ => [Auto_tac,
   167 	     subgoal_tac "sigma |= [](G .-> (F .& G))" 1,
   167 	     subgoal_tac "sigma |= [](G .-> (F .& G))" 1,
   168 	     etac ((temp_mp normalT) RS mp) 1, atac 1,
   168 	     etac ((temp_mp normalT) RS mp) 1, atac 1,
   169 	     ALLGOALS (fast_tac (temp_cs addSEs [STL4E]))
   169 	     ALLGOALS (fast_tac (temp_cs addSEs [STL4E]))
   170 	    ]);
   170 	    ]);
   171 (* rewrite rule to split conjunctions under boxes *)
   171 (* rewrite rule to split conjunctions under boxes *)
   236 	     atac 1
   236 	     atac 1
   237 	    ]);
   237 	    ]);
   238 
   238 
   239 qed_goalw "DmdImpl2" TLA.thy [dmd_def]
   239 qed_goalw "DmdImpl2" TLA.thy [dmd_def]
   240    "!!sigma. [| (sigma |= <>F); (sigma |= [](F .-> G)) |] ==> (sigma |= <>G)"
   240    "!!sigma. [| (sigma |= <>F); (sigma |= [](F .-> G)) |] ==> (sigma |= <>G)"
   241    (fn _ => [Auto_tac(),
   241    (fn _ => [Auto_tac,
   242 	     etac notE 1,
   242 	     etac notE 1,
   243 	     merge_box_tac 1,
   243 	     merge_box_tac 1,
   244 	     fast_tac (temp_cs addSEs [STL4E]) 1
   244 	     fast_tac (temp_cs addSEs [STL4E]) 1
   245 	    ]);
   245 	    ]);
   246 
   246 
   254 	  ]);
   254 	  ]);
   255 
   255 
   256 (* ------------------------ STL6 ------------------------------------------- *)
   256 (* ------------------------ STL6 ------------------------------------------- *)
   257 (* Used in the proof of STL6, but useful in itself. *)
   257 (* Used in the proof of STL6, but useful in itself. *)
   258 qed_goalw "BoxDmdT" TLA.thy [dmd_def] "[]F .& <>G .-> <>([]F .& G)"
   258 qed_goalw "BoxDmdT" TLA.thy [dmd_def] "[]F .& <>G .-> <>([]F .& G)"
   259   (fn _ => [ Auto_tac(),
   259   (fn _ => [ Auto_tac,
   260              etac dup_boxE 1,
   260              etac dup_boxE 1,
   261 	     merge_box_tac 1,
   261 	     merge_box_tac 1,
   262              etac swap 1,
   262              etac swap 1,
   263              fast_tac (temp_cs addSEs [STL4E]) 1 ]);
   263              fast_tac (temp_cs addSEs [STL4E]) 1 ]);
   264 bind_thm("BoxDmd", temp_conjmp BoxDmdT);
   264 bind_thm("BoxDmd", temp_conjmp BoxDmdT);
   265 
   265 
   266 (* weaker than BoxDmd, but more polymorphic (and often just right) *)
   266 (* weaker than BoxDmd, but more polymorphic (and often just right) *)
   267 qed_goalw "BoxDmdT2" TLA.thy [dmd_def] "<>F .& []G .-> <>(F .& G)"
   267 qed_goalw "BoxDmdT2" TLA.thy [dmd_def] "<>F .& []G .-> <>(F .& G)"
   268   (fn _ => [ Auto_tac(),
   268   (fn _ => [ Auto_tac,
   269 	     merge_box_tac 1,
   269 	     merge_box_tac 1,
   270              fast_tac (temp_cs addSEs [notE,STL4E]) 1
   270              fast_tac (temp_cs addSEs [notE,STL4E]) 1
   271 	   ]);
   271 	   ]);
   272 
   272 
   273 qed_goal "STL6" TLA.thy "<>[]F .& <>[]G .-> <>[](F .& G)"
   273 qed_goal "STL6" TLA.thy "<>[]F .& <>[]G .-> <>[](F .& G)"
   276 	    rtac ((temp_unlift DmdDmd) RS iffD1) 1,
   276 	    rtac ((temp_unlift DmdDmd) RS iffD1) 1,
   277 	    etac disjE 1,
   277 	    etac disjE 1,
   278 	    etac DmdImplE 1, rtac BoxDmdT 1,
   278 	    etac DmdImplE 1, rtac BoxDmdT 1,
   279 	    (* the second subgoal needs commutativity of .&, which complicates the proof *)
   279 	    (* the second subgoal needs commutativity of .&, which complicates the proof *)
   280 	    etac DmdImplE 1,
   280 	    etac DmdImplE 1,
   281 	    Auto_tac(),
   281 	    Auto_tac,
   282 	    etac (temp_conjimpE BoxDmdT) 1, atac 1, etac thin_rl 1,
   282 	    etac (temp_conjimpE BoxDmdT) 1, atac 1, etac thin_rl 1,
   283 	    fast_tac (temp_cs addSEs [DmdImplE]) 1
   283 	    fast_tac (temp_cs addSEs [DmdImplE]) 1
   284 	   ]);
   284 	   ]);
   285 
   285 
   286 
   286 
   345 
   345 
   346 (* ------------------------ Further rewrites ----------------------------------------- *)
   346 (* ------------------------ Further rewrites ----------------------------------------- *)
   347 section "Further rewrites";
   347 section "Further rewrites";
   348 
   348 
   349 qed_goalw "NotBox" TLA.thy [dmd_def] "(.~[]F) .= (<>.~F)"
   349 qed_goalw "NotBox" TLA.thy [dmd_def] "(.~[]F) .= (<>.~F)"
   350    (fn _ => [ Auto_tac() ]);
   350    (fn _ => [ Auto_tac ]);
   351 
   351 
   352 qed_goalw "NotDmd" TLA.thy [dmd_def] "(.~<>F) .= ([].~F)"
   352 qed_goalw "NotDmd" TLA.thy [dmd_def] "(.~<>F) .= ([].~F)"
   353    (fn _ => [ Auto_tac () ]);
   353    (fn _ => [ Auto_tac ]);
   354 
   354 
   355 (* These are not by default included in temp_css, because they could be harmful,
   355 (* These are not by default included in temp_css, because they could be harmful,
   356    e.g. []F .& .~[]F becomes []F .& <>.~F !! *)
   356    e.g. []F .& .~[]F becomes []F .& <>.~F !! *)
   357 val more_temp_simps =  (map temp_rewrite [STL3, DmdDmd, NotBox, NotDmd])
   357 val more_temp_simps =  (map temp_rewrite [STL3, DmdDmd, NotBox, NotDmd])
   358                        @ (map (fn th => (temp_unlift th) RS eq_reflection)
   358                        @ (map (fn th => (temp_unlift th) RS eq_reflection)
   361 qed_goal "BoxDmdBox" TLA.thy "([]<>[]F) .= (<>[]F)"
   361 qed_goal "BoxDmdBox" TLA.thy "([]<>[]F) .= (<>[]F)"
   362    (fn _ => [ auto_tac (temp_css addSDs2 [STL2D]),
   362    (fn _ => [ auto_tac (temp_css addSDs2 [STL2D]),
   363               rtac ccontr 1,
   363               rtac ccontr 1,
   364               subgoal_tac "sigma |= <>[][]F .& <>[].~[]F" 1,
   364               subgoal_tac "sigma |= <>[][]F .& <>[].~[]F" 1,
   365               etac thin_rl 1,
   365               etac thin_rl 1,
   366               Auto_tac(),
   366               Auto_tac,
   367 	      etac (temp_conjimpE STL6) 1, atac 1,
   367 	      etac (temp_conjimpE STL6) 1, atac 1,
   368 	      Asm_full_simp_tac 1,
   368 	      Asm_full_simp_tac 1,
   369 	      ALLGOALS (asm_full_simp_tac (simpset() addsimps more_temp_simps))
   369 	      ALLGOALS (asm_full_simp_tac (simpset() addsimps more_temp_simps))
   370 	    ]);
   370 	    ]);
   371 
   371 
   380 qed_goal "BoxOr" TLA.thy 
   380 qed_goal "BoxOr" TLA.thy 
   381    "!!sigma. [| (sigma |= []F .| []G) |] ==> (sigma |= [](F .| G))"
   381    "!!sigma. [| (sigma |= []F .| []G) |] ==> (sigma |= [](F .| G))"
   382    (fn _ => [ fast_tac (temp_cs addSEs [STL4E]) 1 ]);
   382    (fn _ => [ fast_tac (temp_cs addSEs [STL4E]) 1 ]);
   383 
   383 
   384 qed_goal "DBImplBD" TLA.thy "<>[](F::temporal) .-> []<>F"
   384 qed_goal "DBImplBD" TLA.thy "<>[](F::temporal) .-> []<>F"
   385   (fn _ => [Auto_tac(),
   385   (fn _ => [Auto_tac,
   386 	    rtac ccontr 1,
   386 	    rtac ccontr 1,
   387 	    auto_tac (temp_css addsimps2 more_temp_simps addEs2 [temp_conjimpE STL6])
   387 	    old_auto_tac (temp_css addsimps2 more_temp_simps 
       
   388 			           addEs2 [temp_conjimpE STL6])
   388 	   ]);
   389 	   ]);
   389 
   390 
   390 (* Although the script is the same, the derivation isn't polymorphic and doesn't
   391 (* Although the script is the same, the derivation isn't polymorphic and doesn't
   391    work for other types of formulas (uses STL2).
   392    work for other types of formulas (uses STL2).
   392 *)
   393 *)
   393 qed_goal "DBImplBDAct" TLA.thy "<>[](A::action) .-> []<>A"
   394 qed_goal "DBImplBDAct" TLA.thy "<>[](A::action) .-> []<>A"
   394   (fn _ => [Auto_tac(),
   395   (fn _ => [Auto_tac,
   395 	    rtac ccontr 1,
   396 	    rtac ccontr 1,
   396 	    auto_tac (temp_css addsimps2 more_temp_simps addEs2 [temp_conjimpE STL6])
   397 	    old_auto_tac (temp_css addsimps2 more_temp_simps addEs2 [temp_conjimpE STL6])
   397 	   ]);
   398 	   ]);
   398 
   399 
   399 qed_goal "BoxDmdDmdBox" TLA.thy
   400 qed_goal "BoxDmdDmdBox" TLA.thy
   400    "!!sigma. [| (sigma |= []<>F); (sigma |= <>[]G) |] ==> (sigma |= []<>(F .& G))"
   401    "!!sigma. [| (sigma |= []<>F); (sigma |= <>[]G) |] ==> (sigma |= []<>(F .& G))"
   401    (fn _ => [rtac ccontr 1,
   402    (fn _ => [rtac ccontr 1,
   418   (fn _ => [rewrite_goals_tac Init_simps,
   419   (fn _ => [rewrite_goals_tac Init_simps,
   419 	    fast_tac (temp_cs addSIs [temp_mp primeI, STL2bD]) 1]);
   420 	    fast_tac (temp_cs addSIs [temp_mp primeI, STL2bD]) 1]);
   420 
   421 
   421 (* Auxiliary lemma allows priming of boxed actions *)
   422 (* Auxiliary lemma allows priming of boxed actions *)
   422 qed_goal "BoxPrime" TLA.thy "[]P .-> [](P .& P`)"
   423 qed_goal "BoxPrime" TLA.thy "[]P .-> [](P .& P`)"
   423   (fn _ => [Auto_tac(),
   424   (fn _ => [Auto_tac,
   424 	    etac dup_boxE 1,
   425 	    etac dup_boxE 1,
   425 	    auto_tac (temp_css addsimps2 [boxact_def]
   426 	    auto_tac (temp_css addsimps2 [boxact_def]
   426 		               addSIs2 [STL2bD_pr] addSEs2 [STL4E])
   427 		               addSIs2 [STL2bD_pr] addSEs2 [STL4E])
   427 	   ]);
   428 	   ]);
   428 
   429 
   515 	     fast_tac (temp_cs addSEs [TLA2E]) 1,
   516 	     fast_tac (temp_cs addSEs [TLA2E]) 1,
   516 	     auto_tac (temp_css addsimps2 [stable_def] addSEs2 [INV1I,STL4E])
   517 	     auto_tac (temp_css addsimps2 [stable_def] addSEs2 [INV1I,STL4E])
   517 	    ]);
   518 	    ]);
   518 
   519 
   519 qed_goalw "DmdRec" TLA.thy [dmd_def] "(<>$P) .= (Init($P) .| (<>P$))"
   520 qed_goalw "DmdRec" TLA.thy [dmd_def] "(<>$P) .= (Init($P) .| (<>P$))"
   520    (fn _ => [Auto_tac(),
   521    (fn _ => [Auto_tac,
   521 	     etac notE 1,
   522 	     etac notE 1,
   522 	     SELECT_GOAL (auto_tac (temp_css addsimps2 (stable_def::Init_simps)
   523 	     SELECT_GOAL (auto_tac (temp_css addsimps2 (stable_def::Init_simps)
   523 				             addIs2 [INV1I] addEs2 [STL4E])) 1,
   524 				             addIs2 [INV1I] addEs2 [STL4E])) 1,
   524 	     SELECT_GOAL (auto_tac (temp_css addsimps2 Init_simps addSDs2 [STL2bD])) 1,
   525 	     SELECT_GOAL (auto_tac (temp_css addsimps2 Init_simps addSDs2 [STL2bD])) 1,
   525 	     fast_tac (temp_cs addSEs [notE,TLA2E]) 1
   526 	     fast_tac (temp_cs addSEs [notE,TLA2E]) 1
   531 	     SELECT_GOAL (auto_tac (temp_css addsimps2 [dmd_def])) 1
   532 	     SELECT_GOAL (auto_tac (temp_css addsimps2 [dmd_def])) 1
   532 	    ]);
   533 	    ]);
   533 
   534 
   534 (* The "=>" part of the following is a little intricate. *)
   535 (* The "=>" part of the following is a little intricate. *)
   535 qed_goal "InfinitePrime" TLA.thy "([]<>$P) .= ([]<>P$)"
   536 qed_goal "InfinitePrime" TLA.thy "([]<>$P) .= ([]<>P$)"
   536    (fn _ => [Auto_tac(),
   537    (fn _ => [Auto_tac,
   537 	     rtac classical 1,
   538 	     rtac classical 1,
   538 	     rtac (temp_mp DBImplBDAct) 1,
   539 	     rtac (temp_mp DBImplBDAct) 1,
   539 	     subgoal_tac "sigma |= <>[]$P" 1,
   540 	     subgoal_tac "sigma |= <>[]$P" 1,
   540 	     fast_tac (temp_cs addSEs [DmdImplE,TLA2E]) 1,
   541 	     fast_tac (temp_cs addSEs [DmdImplE,TLA2E]) 1,
   541 	     subgoal_tac "sigma |= <>[](<>$P .& [].~P$)" 1,
   542 	     subgoal_tac "sigma |= <>[](<>$P .& [].~P$)" 1,
   590    "!!sigma. [| (sigma |= Init P); (sigma |= P ~> Q) |] ==> (sigma |= <>Q)"
   591    "!!sigma. [| (sigma |= Init P); (sigma |= P ~> Q) |] ==> (sigma |= <>Q)"
   591    (fn _ => [ fast_tac (temp_cs addSDs [temp_mp STL2]) 1 ]);
   592    (fn _ => [ fast_tac (temp_cs addSDs [temp_mp STL2]) 1 ]);
   592 
   593 
   593 qed_goalw "streett_leadsto" TLA.thy [leadsto]
   594 qed_goalw "streett_leadsto" TLA.thy [leadsto]
   594    "([]<>P .-> []<>Q) .= (<>(P ~> Q))"
   595    "([]<>P .-> []<>Q) .= (<>(P ~> Q))"
   595    (fn _ => [Auto_tac(),
   596    (fn _ => [Auto_tac,
   596              asm_full_simp_tac (simpset() addsimps boxact_def::more_temp_simps) 1,
   597              asm_full_simp_tac (simpset() addsimps boxact_def::more_temp_simps) 1,
   597              SELECT_GOAL (auto_tac (temp_css addSEs2 [DmdImplE,STL4E] 
   598              SELECT_GOAL (auto_tac (temp_css addSEs2 [DmdImplE,STL4E] 
   598                                              addsimps2 Init_simps)) 1,
   599                                              addsimps2 Init_simps)) 1,
   599              SELECT_GOAL (auto_tac (temp_css addSIs2 [ImplDmdD] addSEs2 [STL4E])) 1,
   600              SELECT_GOAL (auto_tac (temp_css addSIs2 [ImplDmdD] addSEs2 [STL4E])) 1,
   600              subgoal_tac "sigma |= []<><>Q" 1,
   601              subgoal_tac "sigma |= []<><>Q" 1,
   723    "[| P .& N  .-> P` .| Q`;   \
   724    "[| P .& N  .-> P` .| Q`;   \
   724 \      P .& N .& <A>_v .-> Q`;   \
   725 \      P .& N .& <A>_v .-> Q`;   \
   725 \      P .& N .-> $(Enabled(<A>_v)) |]   \
   726 \      P .& N .-> $(Enabled(<A>_v)) |]   \
   726 \  ==> []N .& WF(A)_v .-> (P ~> Q)"
   727 \  ==> []N .& WF(A)_v .-> (P ~> Q)"
   727    (fn [prem1,prem2,prem3]
   728    (fn [prem1,prem2,prem3]
   728              => [auto_tac (temp_css addSDs2 [BoxWFI]),
   729 	 => [auto_tac (temp_css addSDs2 [BoxWFI]),
   729 		 etac STL4Edup 1, atac 1,
   730 	     etac STL4Edup 1, atac 1,
   730 		 Auto_tac(),
   731 	     Auto_tac,
   731 		 subgoal_tac "sigmaa |= [](P .-> P` .| Q`)" 1,
   732 	     subgoal_tac "sigmaa |= [](P .-> P` .| Q`)" 1,
   732 		 auto_tac (temp_css addSDs2 [unless]),
   733 	     auto_tac (temp_css addSDs2 [unless]),
   733 		 etac (temp_conjimpE INV1) 1, atac 1,
   734 	     etac (temp_conjimpE INV1) 1, atac 1,
   734 		 merge_box_tac 1,
   735 	     merge_box_tac 1,
   735 		 rtac STL2D 1,
   736 	     rtac STL2D 1,
   736 		 rtac EnsuresInfinite 1, atac 2,
   737 	     rtac EnsuresInfinite 1, atac 2,
   737 		 SELECT_GOAL (auto_tac (temp_css addsimps2 [WF_alt])) 1,
   738 	     SELECT_GOAL (old_auto_tac (temp_css addsimps2 [WF_alt])) 1,
   738 		 atac 2,
   739 	     atac 2,
   739 		 subgoal_tac "sigmaa |= [][]$(Enabled(<A>_v))" 1,
   740 	     subgoal_tac "sigmaa |= [][]$(Enabled(<A>_v))" 1,
   740 		 merge_box_tac 1,
   741 	     merge_box_tac 1,
   741 		 SELECT_GOAL (auto_tac (temp_css addsimps2 [dmd_def])) 1,
   742 	     SELECT_GOAL (auto_tac (temp_css addsimps2 [dmd_def])) 1,
   742 		 SELECT_GOAL ((rewtac (temp_rewrite STL3)) THEN
   743 	     SELECT_GOAL ((rewtac (temp_rewrite STL3)) THEN
   743 			      (auto_tac (temp_css addSEs2 [STL4E] addSIs2 [action_mp prem3]))) 1,
   744 			  (auto_tac (temp_css addSEs2 [STL4E] addSIs2 [action_mp prem3]))) 1,
   744 		 fast_tac (action_cs addSIs [action_mp prem2]) 1,
   745 	     fast_tac (action_cs addSIs [action_mp prem2]) 1,
   745 		 fast_tac (temp_cs addIs [temp_mp DmdPrime]) 1,
   746 	     fast_tac (temp_cs addIs [temp_mp DmdPrime]) 1,
   746 		 fast_tac (temp_cs addSEs [STL4E] addSIs [action_mp prem1]) 1
   747 	     fast_tac (temp_cs addSEs [STL4E] addSIs [action_mp prem1]) 1
   747 		]);
   748 	    ]);
   748 
   749 
   749 (* Sometimes easier to use; designed for action B rather than state predicate Q *)
   750 (* Sometimes easier to use; designed for action B rather than state predicate Q *)
   750 qed_goalw "WF_leadsto" TLA.thy [leadsto]
   751 qed_goalw "WF_leadsto" TLA.thy [leadsto]
   751    "[| N .& P .-> $Enabled (<A>_v);            \
   752    "[| N .& P .-> $Enabled (<A>_v);            \
   752 \      N .& <A>_v .-> B;                  \ 
   753 \      N .& <A>_v .-> B;                  \ 
   753 \      [](N .& [.~A]_v) .-> stable P  |]  \
   754 \      [](N .& [.~A]_v) .-> stable P  |]  \
   754 \   ==> []N .& WF(A)_v .-> (P ~> B)"
   755 \   ==> []N .& WF(A)_v .-> (P ~> B)"
   755    (fn [prem1,prem2,prem3]
   756    (fn [prem1,prem2,prem3]
   756        => [auto_tac (temp_css addSDs2 [BoxWFI]),
   757        => [auto_tac (temp_css addSDs2 [BoxWFI]),
   757            etac STL4Edup 1, atac 1,
   758            etac STL4Edup 1, atac 1,
   758            Auto_tac(),
   759            Auto_tac,
   759            subgoal_tac "sigmaa |= <><A>_v" 1,
   760            subgoal_tac "sigmaa |= <><A>_v" 1,
   760            SELECT_GOAL (auto_tac (temp_css addSEs2 [DmdImpl2,STL4E] addSIs2 [action_mp prem2])) 1,
   761            SELECT_GOAL (auto_tac (temp_css addSEs2 [DmdImpl2,STL4E] addSIs2 [action_mp prem2])) 1,
   761            rtac classical 1,
   762            rtac classical 1,
   762            rtac STL2D 1,
   763            rtac STL2D 1,
   763            auto_tac (temp_css addsimps2 WF_def::more_temp_simps addSEs2 [mp]),
   764            auto_tac (temp_css addsimps2 WF_def::more_temp_simps addSEs2 [mp]),
   777    (fn [prem1,prem2,prem3] =>
   778    (fn [prem1,prem2,prem3] =>
   778                 [auto_tac (temp_css addSDs2 [BoxSFI]),
   779                 [auto_tac (temp_css addSDs2 [BoxSFI]),
   779 		 eres_inst_tac [("F","F")] dup_boxE 1,
   780 		 eres_inst_tac [("F","F")] dup_boxE 1,
   780 		 merge_temp_box_tac 1,
   781 		 merge_temp_box_tac 1,
   781 		 etac STL4Edup 1, atac 1,
   782 		 etac STL4Edup 1, atac 1,
   782 		 Auto_tac(),
   783 		 Auto_tac,
   783 		 subgoal_tac "sigmaa |= [](P .-> P` .| Q`)" 1,
   784 		 subgoal_tac "sigmaa |= [](P .-> P` .| Q`)" 1,
   784 		 auto_tac (temp_css addSDs2 [unless]),
   785 		 auto_tac (temp_css addSDs2 [unless]),
   785 		 etac (temp_conjimpE INV1) 1, atac 1,
   786 		 etac (temp_conjimpE INV1) 1, atac 1,
   786 		 merge_act_box_tac 1,
   787 		 merge_act_box_tac 1,
   787 		 rtac STL2D 1,
   788 		 rtac STL2D 1,
   788 		 rtac EnsuresInfinite 1, atac 2,
   789 		 rtac EnsuresInfinite 1, atac 2,
   789 		 SELECT_GOAL (auto_tac (temp_css addsimps2 [SF_alt])) 1,
   790 		 SELECT_GOAL (old_auto_tac (temp_css addsimps2 [SF_alt])) 1,
   790 		 atac 2,
   791 		 atac 2,
   791 		 subgoal_tac "sigmaa |= []<>$(Enabled(<A>_v))" 1,
   792 		 subgoal_tac "sigmaa |= []<>$(Enabled(<A>_v))" 1,
   792 		 SELECT_GOAL (auto_tac (temp_css addsimps2 [dmd_def])) 1,
   793 		 SELECT_GOAL (auto_tac (temp_css addsimps2 [dmd_def])) 1,
   793 		 eres_inst_tac [("F","F")] dup_boxE 1,
   794 		 eres_inst_tac [("F","F")] dup_boxE 1,
   794 		 etac STL4Edup 1, atac 1,
   795 		 etac STL4Edup 1, atac 1,
   803 \      P .& P` .& <N .& A>_f .-> B;   \
   804 \      P .& P` .& <N .& A>_f .-> B;   \
   804 \      P .& $(Enabled(<M>_g)) .-> $(Enabled(<A>_f));   \
   805 \      P .& $(Enabled(<M>_g)) .-> $(Enabled(<A>_f));   \
   805 \      [](N .& [.~B]_f) .& WF(A)_f .& []F .& <>[]($(Enabled(<M>_g))) .-> <>[]P |]   \
   806 \      [](N .& [.~B]_f) .& WF(A)_f .& []F .& <>[]($(Enabled(<M>_g))) .-> <>[]P |]   \
   806 \  ==> []N .& WF(A)_f .& []F .-> WF(M)_g"
   807 \  ==> []N .& WF(A)_f .& []F .-> WF(M)_g"
   807    (fn [prem1,prem2,prem3,prem4]
   808    (fn [prem1,prem2,prem3,prem4]
   808        => [Auto_tac(),
   809        => [Auto_tac,
   809 	   case_tac "sigma |= <>[]$Enabled(<M>_g)" 1,
   810 	   case_tac "sigma |= <>[]$Enabled(<M>_g)" 1,
   810 	   SELECT_GOAL (auto_tac (temp_css addsimps2 [WF_def,dmd_def])) 2,
   811 	   SELECT_GOAL (auto_tac (temp_css addsimps2 [WF_def,dmd_def])) 2,
   811 	   case_tac "sigma |= <>[][.~B]_f" 1,
   812 	   case_tac "sigma |= <>[][.~B]_f" 1,
   812 	   subgoal_tac "sigma |= <>[]P" 1,
   813 	   subgoal_tac "sigma |= <>[]P" 1,
   813 	   asm_full_simp_tac (simpset() addsimps [WF_def]) 1,
   814 	   asm_full_simp_tac (simpset() addsimps [WF_def]) 1,
   817 	   subgoal_tac "sigma |= <>[]$Enabled(<A>_f)" 1,
   818 	   subgoal_tac "sigma |= <>[]$Enabled(<A>_f)" 1,
   818 	   dtac mp 1, atac 1,
   819 	   dtac mp 1, atac 1,
   819 	   subgoal_tac "sigma |= <>([]N .& []P .& []<><A>_f)" 1,
   820 	   subgoal_tac "sigma |= <>([]N .& []P .& []<><A>_f)" 1,
   820 	   rtac ((temp_unlift DmdBoxDmd) RS iffD1) 1,
   821 	   rtac ((temp_unlift DmdBoxDmd) RS iffD1) 1,
   821 	   eres_inst_tac [("F","[]N .& []P .& []<><A>_f")] DmdImplE 1,
   822 	   eres_inst_tac [("F","[]N .& []P .& []<><A>_f")] DmdImplE 1,
   822 	   SELECT_GOAL (Auto_tac()) 1,
   823 	   SELECT_GOAL Auto_tac 1,
   823 	   dres_inst_tac [("P","P")] (temp_mp BoxPrime) 1,
   824 	   dres_inst_tac [("P","P")] (temp_mp BoxPrime) 1,
   824 	   merge_act_box_tac 1,
   825 	   merge_act_box_tac 1,
   825 	   etac InfImpl 1, atac 1,
   826 	   etac InfImpl 1, atac 1,
   826 	   SELECT_GOAL (auto_tac (temp_css addsimps2 [angle_def] addSIs2 [action_mp prem2])) 1,
   827 	   SELECT_GOAL (auto_tac (temp_css addsimps2 [angle_def] addSIs2 [action_mp prem2])) 1,
   827 	   etac BoxDmd 1,
   828 	   etac BoxDmd 1,
   828 	   dres_inst_tac [("F","<><A>_f"),("G","[]P")] BoxDmd 1, atac 1,
   829 	   dres_inst_tac [("F","<><A>_f"),("G","[]P")] BoxDmd 1, atac 1,
   829 	   eres_inst_tac [("F","[]<><A>_f .& []P")] DmdImplE 1,
   830 	   eres_inst_tac [("F","[]<><A>_f .& []P")] DmdImplE 1,
   830 	   SELECT_GOAL (Auto_tac ()) 1,
   831 	   SELECT_GOAL Auto_tac 1,
   831 	   rtac (temp_mp (prem3 RS STL4 RS DmdImpl)) 1,
   832 	   rtac (temp_mp (prem3 RS STL4 RS DmdImpl)) 1,
   832 	   fast_tac (temp_cs addIs [STL4E,DmdImplE]) 1,
   833 	   fast_tac (temp_cs addIs [STL4E,DmdImplE]) 1,
   833 	   etac (temp_conjimpE STL6) 1, atac 1,
   834 	   etac (temp_conjimpE STL6) 1, atac 1,
   834 	   eres_inst_tac [("V","sigma |= <>[][.~ B]_f")] thin_rl 1,
   835 	   eres_inst_tac [("V","sigma |= <>[][.~ B]_f")] thin_rl 1,
   835 	   dtac BoxWFI 1,
   836 	   dtac BoxWFI 1,
   855 \      P .& P` .& <N .& A>_f .-> B;   \
   856 \      P .& P` .& <N .& A>_f .-> B;   \
   856 \      P .& $(Enabled(<M>_g)) .-> $(Enabled(<A>_f));   \
   857 \      P .& $(Enabled(<M>_g)) .-> $(Enabled(<A>_f));   \
   857 \      [](N .& [.~B]_f) .& SF(A)_f .& []F .& []<>($(Enabled(<M>_g))) .-> <>[]P |]   \
   858 \      [](N .& [.~B]_f) .& SF(A)_f .& []F .& []<>($(Enabled(<M>_g))) .-> <>[]P |]   \
   858 \  ==> []N .& SF(A)_f .& []F .-> SF(M)_g"
   859 \  ==> []N .& SF(A)_f .& []F .-> SF(M)_g"
   859    (fn [prem1,prem2,prem3,prem4]
   860    (fn [prem1,prem2,prem3,prem4]
   860        => [Auto_tac(),
   861        => [Auto_tac,
   861 	   case_tac "sigma |= []<>$Enabled(<M>_g)" 1,
   862 	   case_tac "sigma |= []<>$Enabled(<M>_g)" 1,
   862 	   SELECT_GOAL (auto_tac (temp_css addsimps2 [SF_def,dmd_def])) 2,
   863 	   SELECT_GOAL (auto_tac (temp_css addsimps2 [SF_def,dmd_def])) 2,
   863 	   case_tac "sigma |= <>[][.~B]_f" 1,
   864 	   case_tac "sigma |= <>[][.~B]_f" 1,
   864 	   subgoal_tac "sigma |= <>[]P" 1,
   865 	   subgoal_tac "sigma |= <>[]P" 1,
   865 	   asm_full_simp_tac (simpset() addsimps [SF_def]) 1,
   866 	   asm_full_simp_tac (simpset() addsimps [SF_def]) 1,
   869 	   subgoal_tac "sigma |= []<>$Enabled(<A>_f)" 1,
   870 	   subgoal_tac "sigma |= []<>$Enabled(<A>_f)" 1,
   870 	   dtac mp 1, atac 1,
   871 	   dtac mp 1, atac 1,
   871 	   subgoal_tac "sigma |= <>([]N .& []P .& []<><A>_f)" 1,
   872 	   subgoal_tac "sigma |= <>([]N .& []P .& []<><A>_f)" 1,
   872 	   rtac ((temp_unlift DmdBoxDmd) RS iffD1) 1,
   873 	   rtac ((temp_unlift DmdBoxDmd) RS iffD1) 1,
   873 	   eres_inst_tac [("F","[]N .& []P .& []<><A>_f")] DmdImplE 1,
   874 	   eres_inst_tac [("F","[]N .& []P .& []<><A>_f")] DmdImplE 1,
   874 	   SELECT_GOAL (Auto_tac()) 1,
   875 	   SELECT_GOAL Auto_tac 1,
   875 	   dres_inst_tac [("P","P")] (temp_mp BoxPrime) 1,
   876 	   dres_inst_tac [("P","P")] (temp_mp BoxPrime) 1,
   876 	   merge_act_box_tac 1,
   877 	   merge_act_box_tac 1,
   877 	   etac InfImpl 1, atac 1,
   878 	   etac InfImpl 1, atac 1,
   878 	   SELECT_GOAL (auto_tac (temp_css addsimps2 [angle_def] addSIs2 [action_mp prem2])) 1,
   879 	   SELECT_GOAL (auto_tac (temp_css addsimps2 [angle_def] addSIs2 [action_mp prem2])) 1,
   879 	   etac BoxDmd 1,
   880 	   etac BoxDmd 1,
   880 	   dres_inst_tac [("F","<><A>_f"),("G","[]P")] BoxDmd 1, atac 1,
   881 	   dres_inst_tac [("F","<><A>_f"),("G","[]P")] BoxDmd 1, atac 1,
   881 	   eres_inst_tac [("F","[]<><A>_f .& []P")] DmdImplE 1,
   882 	   eres_inst_tac [("F","[]<><A>_f .& []P")] DmdImplE 1,
   882 	   SELECT_GOAL (Auto_tac ()) 1,
   883 	   SELECT_GOAL Auto_tac 1,
   883 	   rtac (temp_mp (prem3 RS DmdImpl RS STL4)) 1,
   884 	   rtac (temp_mp (prem3 RS DmdImpl RS STL4)) 1,
   884 	   fast_tac (temp_cs addEs [STL4E,DmdImplE]) 1,
   885 	   fast_tac (temp_cs addEs [STL4E,DmdImplE]) 1,
   885 	   dtac BoxSFI 1,
   886 	   dtac BoxSFI 1,
   886 	   eres_inst_tac [("F","N")] dup_boxE 1,
   887 	   eres_inst_tac [("F","N")] dup_boxE 1,
   887 	   eres_inst_tac [("F","F")] dup_boxE 1,
   888 	   eres_inst_tac [("F","F")] dup_boxE 1,
   913          [cut_facts_tac [prem1] 1,
   914          [cut_facts_tac [prem1] 1,
   914           etac wf_induct 1,
   915           etac wf_induct 1,
   915           subgoal_tac "sigma |= []((REX y. #((y,x):r) .& F y) .-> <>G)" 1,
   916           subgoal_tac "sigma |= []((REX y. #((y,x):r) .& F y) .-> <>G)" 1,
   916 	  cut_facts_tac prems 1,
   917 	  cut_facts_tac prems 1,
   917 	  etac STL4Edup 1, atac 1,
   918 	  etac STL4Edup 1, atac 1,
   918 	  Auto_tac(), etac swap 1, atac 1,
   919 	  Auto_tac, etac swap 1, atac 1,
   919 	  rtac dup_dmdD 1,
   920 	  rtac dup_dmdD 1,
   920 	  etac DmdImpl2 1, atac 1,
   921 	  etac DmdImpl2 1, atac 1,
   921 	  subgoal_tac "sigma |= [](RALL y. #((y,x):r) .& F y .-> <>G)" 1,
   922 	  subgoal_tac "sigma |= [](RALL y. #((y,x):r) .& F y .-> <>G)" 1,
   922 	  fast_tac (temp_cs addSEs [STL4E]) 1,
   923 	  fast_tac (temp_cs addSEs [STL4E]) 1,
   923 	  auto_tac (temp_css addsimps2 [all_box]),
   924 	  auto_tac (temp_css addsimps2 [all_box]),
   941 	       ]);
   942 	       ]);
   942 
   943 
   943 (* If r is well-founded, state function v cannot decrease forever *)
   944 (* If r is well-founded, state function v cannot decrease forever *)
   944 qed_goal "wf_not_box_decrease" TLA.thy
   945 qed_goal "wf_not_box_decrease" TLA.thy
   945   "!!r. wf r ==> [][ {[v$, $v]} .: #r ]_v .-> <>[][#False]_v"
   946   "!!r. wf r ==> [][ {[v$, $v]} .: #r ]_v .-> <>[][#False]_v"
   946   (fn _ => [Auto_tac(),
   947   (fn _ => [Auto_tac,
   947             subgoal_tac "ALL x. (sigma |= [](Init($v .= #x) .-> <>[][#False]_v))" 1,
   948             subgoal_tac "ALL x. (sigma |= [](Init($v .= #x) .-> <>[][#False]_v))" 1,
   948             etac allE 1,
   949             etac allE 1,
   949             dtac STL2D 1,
   950             dtac STL2D 1,
   950             auto_tac (temp_css addsimps2 [Init_def]),
   951             auto_tac (temp_css addsimps2 [Init_def]),
   951             etac wf_dmd 1,
   952             etac wf_dmd 1,
   966             etac swap 1,
   967             etac swap 1,
   967             subgoal_tac "sigma |= []($v .= #xa)" 1,
   968             subgoal_tac "sigma |= []($v .= #xa)" 1,
   968             dres_inst_tac [("P", "$v .= #xa")] (temp_mp BoxPrime) 1,
   969             dres_inst_tac [("P", "$v .= #xa")] (temp_mp BoxPrime) 1,
   969             SELECT_GOAL (auto_tac (temp_css addEs2 [STL4E] addsimps2 [square_def])) 1,
   970             SELECT_GOAL (auto_tac (temp_css addEs2 [STL4E] addsimps2 [square_def])) 1,
   970             SELECT_GOAL (auto_tac (temp_css addSIs2 [INV1I] addsimps2 [Init_def])) 1,
   971             SELECT_GOAL (auto_tac (temp_css addSIs2 [INV1I] addsimps2 [Init_def])) 1,
   971             auto_tac (temp_css addsimps2 [square_def] addSIs2 [unless] addSEs2 [STL4E])
   972             old_auto_tac (temp_css addsimps2 [square_def] addSIs2 [unless] addSEs2 [STL4E])
   972            ]);
   973            ]);
   973 
   974 
   974 (* "wf ?r  ==>  <>[][{[?v$, $?v]} .: #?r]_?v .-> <>[][#False]_?v" *)
   975 (* "wf ?r  ==>  <>[][{[?v$, $?v]} .: #?r]_?v .-> <>[][#False]_?v" *)
   975 bind_thm("wf_not_dmd_box_decrease",
   976 bind_thm("wf_not_dmd_box_decrease",
   976          standard(rewrite_rule more_temp_simps (wf_not_box_decrease RS DmdImpl)));
   977          standard(rewrite_rule more_temp_simps (wf_not_box_decrease RS DmdImpl)));
   978 (* If there are infinitely many steps where v decreases w.r.t. r, then there
   979 (* If there are infinitely many steps where v decreases w.r.t. r, then there
   979    have to be infinitely many non-stuttering steps where v doesn't decrease.
   980    have to be infinitely many non-stuttering steps where v doesn't decrease.
   980 *)
   981 *)
   981 qed_goal "wf_box_dmd_decrease" TLA.thy
   982 qed_goal "wf_box_dmd_decrease" TLA.thy
   982   "wf r ==> []<>({[v$, $v]} .: #r) .-> []<><.~({[v$, $v]} .: #r)>_v"
   983   "wf r ==> []<>({[v$, $v]} .: #r) .-> []<><.~({[v$, $v]} .: #r)>_v"
   983   (fn [prem] => [Auto_tac(),
   984   (fn [prem] => [Auto_tac,
   984                  rtac ccontr 1,
   985                  rtac ccontr 1,
   985                  asm_full_simp_tac 
   986                  asm_full_simp_tac 
   986                    (simpset() addsimps ([action_rewrite not_angle] @ more_temp_simps)) 1,
   987                    (simpset() addsimps ([action_rewrite not_angle] @ more_temp_simps)) 1,
   987                  dtac (prem RS (temp_mp wf_not_dmd_box_decrease)) 1,
   988                  dtac (prem RS (temp_mp wf_not_dmd_box_decrease)) 1,
   988                  dtac BoxDmdDmdBox 1, atac 1,
   989                  dtac BoxDmdDmdBox 1, atac 1,
   989                  subgoal_tac "sigma |= []<>((#False)::action)" 1,
   990                  subgoal_tac "sigma |= []<>((#False)::action)" 1,
   990                  SELECT_GOAL (Auto_tac()) 1,
   991                  SELECT_GOAL Auto_tac 1,
   991                  etac STL4E 1,
   992                  etac STL4E 1,
   992                  rtac DmdImpl 1,
   993                  rtac DmdImpl 1,
   993                  auto_tac (action_css addsimps2 [square_def] addSEs2 [prem RS wf_irrefl])
   994                  auto_tac (action_css addsimps2 [square_def] addSEs2 [prem RS wf_irrefl])
   994                 ]);
   995                 ]);
   995 
   996 
   996 (* In particular, for natural numbers, if n decreases infinitely often
   997 (* In particular, for natural numbers, if n decreases infinitely often
   997    then it has to increase infinitely often.
   998    then it has to increase infinitely often.
   998 *)
   999 *)
   999 qed_goal "nat_box_dmd_decrease" TLA.thy
  1000 qed_goal "nat_box_dmd_decrease" TLA.thy
  1000   "!!n::nat stfun. []<>(n$ .< $n) .-> []<>($n .< n$)"
  1001   "!!n::nat stfun. []<>(n$ .< $n) .-> []<>($n .< n$)"
  1001   (fn _ => [Auto_tac(),
  1002   (fn _ => [Auto_tac,
  1002             subgoal_tac "sigma |= []<><.~( {[n$,$n]} .: #less_than)>_n" 1,
  1003             subgoal_tac "sigma |= []<><.~( {[n$,$n]} .: #less_than)>_n" 1,
  1003             etac thin_rl 1, etac STL4E 1, rtac DmdImpl 1,
  1004             etac thin_rl 1, etac STL4E 1, rtac DmdImpl 1,
  1004             SELECT_GOAL (auto_tac (claset(), simpset() addsimps [angle_def])) 1,
  1005             SELECT_GOAL (auto_tac (claset(), simpset() addsimps [angle_def])) 1,
  1005             rtac nat_less_cases 1,
  1006             rtac nat_less_cases 1,
  1006             Auto_tac(),
  1007             Auto_tac,
  1007             rtac (temp_mp wf_box_dmd_decrease) 1,
  1008             rtac (temp_mp wf_box_dmd_decrease) 1,
  1008             auto_tac (claset() addSEs [STL4E] addSIs [DmdImpl], simpset())
  1009             auto_tac (claset() addSEs [STL4E] addSIs [DmdImpl], simpset())
  1009            ]);
  1010            ]);
  1010 
  1011 
  1011 (* ------------------------------------------------------------------------- *)
  1012 (* ------------------------------------------------------------------------- *)