src/HOL/TLA/TLA.ML
changeset 9517 f58863b1406a
parent 9168 77658111e122
child 10231 178a272bceeb
equal deleted inserted replaced
9516:72b5d28aae58 9517:f58863b1406a
     6 Lemmas and tactics for temporal reasoning.
     6 Lemmas and tactics for temporal reasoning.
     7 *)
     7 *)
     8 
     8 
     9 (* Specialize intensional introduction/elimination rules for temporal formulas *)
     9 (* Specialize intensional introduction/elimination rules for temporal formulas *)
    10 
    10 
    11 qed_goal "tempI" TLA.thy "(!!sigma. sigma |= (F::temporal)) ==> |- F"
    11 val [prem] = goal thy "(!!sigma. sigma |= (F::temporal)) ==> |- F";
    12   (fn [prem] => [ REPEAT (resolve_tac [prem,intI] 1) ]);
    12 by (REPEAT (resolve_tac [prem,intI] 1));
    13 
    13 qed "tempI";
    14 qed_goal "tempD" TLA.thy "|- (F::temporal) ==> sigma |= F"
    14 
    15   (fn [prem] => [ rtac (prem RS intD) 1 ]);
    15 val [prem] = goal thy "|- (F::temporal) ==> sigma |= F";
       
    16 by (rtac (prem RS intD) 1);
       
    17 qed "tempD";
    16 
    18 
    17 
    19 
    18 (* ======== Functions to "unlift" temporal theorems ====== *)
    20 (* ======== Functions to "unlift" temporal theorems ====== *)
    19 
    21 
    20 (* The following functions are specialized versions of the corresponding
    22 (* The following functions are specialized versions of the corresponding
    73 (***           "Simple temporal logic": only [] and <>                     ***)
    75 (***           "Simple temporal logic": only [] and <>                     ***)
    74 (* ------------------------------------------------------------------------- *)
    76 (* ------------------------------------------------------------------------- *)
    75 section "Simple temporal logic";
    77 section "Simple temporal logic";
    76 
    78 
    77 (* []~F == []~Init F *)
    79 (* []~F == []~Init F *)
    78 bind_thm("boxNotInit", rewrite_rule Init_simps (read_instantiate [("F", "LIFT ~F")] boxInit));
    80 bind_thm("boxNotInit", 
    79 
    81          rewrite_rule Init_simps (read_instantiate [("F", "LIFT ~F")] boxInit));
    80 qed_goalw "dmdInit" TLA.thy [dmd_def] "TEMP <>F == TEMP <> Init F"
    82 
    81   (fn _ => [rewtac (read_instantiate [("F", "LIFT ~F")] boxInit),
    83 Goalw [dmd_def] "TEMP <>F == TEMP <> Init F";
    82             simp_tac (simpset() addsimps Init_simps) 1]);
    84 by (rewtac (read_instantiate [("F", "LIFT ~F")] boxInit));
    83 
    85 by (simp_tac (simpset() addsimps Init_simps) 1);
    84 bind_thm("dmdNotInit", rewrite_rule Init_simps (read_instantiate [("F", "LIFT ~F")] dmdInit));
    86 qed "dmdInit";
       
    87 
       
    88 bind_thm("dmdNotInit", 
       
    89          rewrite_rule Init_simps (read_instantiate [("F", "LIFT ~F")] dmdInit));
    85 
    90 
    86 (* boxInit and dmdInit cannot be used as rewrites, because they loop.
    91 (* boxInit and dmdInit cannot be used as rewrites, because they loop.
    87    Non-looping instances for state predicates and actions are occasionally useful.
    92    Non-looping instances for state predicates and actions are occasionally useful.
    88 *)
    93 *)
    89 bind_thm("boxInit_stp", read_instantiate [("'a","state")] boxInit);
    94 bind_thm("boxInit_stp", read_instantiate [("'a","state")] boxInit);
   101 
   106 
   102 (* ------------------------ STL2 ------------------------------------------- *)
   107 (* ------------------------ STL2 ------------------------------------------- *)
   103 bind_thm("STL2", reflT);
   108 bind_thm("STL2", reflT);
   104 
   109 
   105 (* The "polymorphic" (generic) variant *)
   110 (* The "polymorphic" (generic) variant *)
   106 qed_goal "STL2_gen" TLA.thy "|- []F --> Init F"
   111 Goal "|- []F --> Init F";
   107   (fn _ => [rewtac (read_instantiate [("F", "F")] boxInit),
   112 by (rewtac (read_instantiate [("F", "F")] boxInit));
   108             rtac STL2 1]);
   113 by (rtac STL2 1);
       
   114 qed "STL2_gen";
   109 
   115 
   110 (* see also STL2_pr below: "|- []P --> Init P & Init (P`)" *)
   116 (* see also STL2_pr below: "|- []P --> Init P & Init (P`)" *)
   111 
   117 
   112 
   118 
   113 (* Dual versions for <> *)
   119 (* Dual versions for <> *)
   114 qed_goalw "InitDmd" TLA.thy [dmd_def] "|- F --> <> F"
   120 Goalw [dmd_def] "|- F --> <> F";
   115    (fn _ => [ auto_tac (temp_css addSDs2 [STL2]) ]);
   121 by (auto_tac (temp_css addSDs2 [STL2]));
   116 
   122 qed "InitDmd";
   117 qed_goal "InitDmd_gen" TLA.thy "|- Init F --> <>F"
   123 
   118    (fn _ => [Clarsimp_tac 1,
   124 Goal "|- Init F --> <>F";
   119              dtac (temp_use InitDmd) 1,
   125 by (Clarsimp_tac 1);
   120              asm_full_simp_tac (simpset() addsimps [dmdInitD]) 1]);
   126 by (dtac (temp_use InitDmd) 1);
       
   127 by (asm_full_simp_tac (simpset() addsimps [dmdInitD]) 1);
       
   128 qed "InitDmd_gen";
   121 
   129 
   122 
   130 
   123 (* ------------------------ STL3 ------------------------------------------- *)
   131 (* ------------------------ STL3 ------------------------------------------- *)
   124 qed_goal "STL3" TLA.thy "|- ([][]F) = ([]F)"
   132 Goal "|- ([][]F) = ([]F)";
   125    (K [force_tac (temp_css addEs2 [transT,STL2]) 1]);
   133 by (force_tac (temp_css addEs2 [transT,STL2]) 1);
       
   134 qed "STL3";
   126 
   135 
   127 (* corresponding elimination rule introduces double boxes: 
   136 (* corresponding elimination rule introduces double boxes: 
   128    [| (sigma |= []F); (sigma |= [][]F) ==> PROP W |] ==> PROP W
   137    [| (sigma |= []F); (sigma |= [][]F) ==> PROP W |] ==> PROP W
   129 *)
   138 *)
   130 bind_thm("dup_boxE", make_elim((temp_unlift STL3) RS iffD2));
   139 bind_thm("dup_boxE", make_elim((temp_unlift STL3) RS iffD2));
   131 bind_thm("dup_boxD", (temp_unlift STL3) RS iffD1);
   140 bind_thm("dup_boxD", (temp_unlift STL3) RS iffD1);
   132 
   141 
   133 (* dual versions for <> *)
   142 (* dual versions for <> *)
   134 qed_goalw "DmdDmd" TLA.thy [dmd_def] "|- (<><>F) = (<>F)"
   143 Goal "|- (<><>F) = (<>F)";
   135    (fn _ => [ auto_tac (temp_css addsimps2 [STL3]) ]);
   144 by (auto_tac (temp_css addsimps2 [dmd_def,STL3]));
       
   145 qed "DmdDmd";
   136 bind_thm("dup_dmdE", make_elim((temp_unlift DmdDmd) RS iffD2));
   146 bind_thm("dup_dmdE", make_elim((temp_unlift DmdDmd) RS iffD2));
   137 bind_thm("dup_dmdD", (temp_unlift DmdDmd) RS iffD1);
   147 bind_thm("dup_dmdD", (temp_unlift DmdDmd) RS iffD1);
   138 
   148 
   139 
   149 
   140 (* ------------------------ STL4 ------------------------------------------- *)
   150 (* ------------------------ STL4 ------------------------------------------- *)
   141 qed_goal "STL4" TLA.thy "|- F --> G  ==> |- []F --> []G"
   151 val [prem] = goal thy "|- F --> G  ==> |- []F --> []G";
   142    (fn [prem] => [Clarsimp_tac 1,
   152 by (Clarsimp_tac 1);
   143 		  rtac (temp_use normalT) 1,
   153 by (rtac (temp_use normalT) 1);
   144                   rtac (temp_use (prem RS necT)) 1,
   154 by (rtac (temp_use (prem RS necT)) 1);
   145 		  atac 1
   155 by (atac 1);
   146 		 ]);
   156 qed "STL4";
   147 
   157 
   148 (* Unlifted version as an elimination rule *)
   158 (* Unlifted version as an elimination rule *)
   149 qed_goal "STL4E" TLA.thy 
   159 val prems = goal thy "[| sigma |= []F; |- F --> G |] ==> sigma |= []G";
   150          "[| sigma |= []F; |- F --> G |] ==> sigma |= []G"
   160 by (REPEAT (resolve_tac (prems @ [temp_use STL4]) 1));
   151    (fn prems => [ REPEAT (resolve_tac (prems @ [temp_use STL4]) 1) ]);
   161 qed "STL4E";
   152 
   162 
   153 qed_goal "STL4_gen" TLA.thy "|- Init F --> Init G ==> |- []F --> []G"
   163 val [prem] = goal thy "|- Init F --> Init G ==> |- []F --> []G";
   154    (fn [prem] => [rtac (rewrite_rule [boxInitD] (prem RS STL4)) 1]);
   164 by (rtac (rewrite_rule [boxInitD] (prem RS STL4)) 1);
   155 
   165 qed "STL4_gen";
   156 qed_goal "STL4E_gen" TLA.thy
   166 
   157          "[| sigma |= []F; |- Init F --> Init G |] ==> sigma |= []G"
   167 val prems = goal thy
   158    (fn prems => [ REPEAT (resolve_tac (prems @ [temp_use STL4_gen]) 1) ]);
   168    "[| sigma |= []F; |- Init F --> Init G |] ==> sigma |= []G";
       
   169 by (REPEAT (resolve_tac (prems @ [temp_use STL4_gen]) 1));
       
   170 qed "STL4E_gen";
   159 
   171 
   160 (* see also STL4Edup below, which allows an auxiliary boxed formula:
   172 (* see also STL4Edup below, which allows an auxiliary boxed formula:
   161        []A /\ F => G
   173        []A /\ F => G
   162      -----------------
   174      -----------------
   163      []A /\ []F => []G
   175      []A /\ []F => []G
   164 *)
   176 *)
   165 
   177 
   166 (* The dual versions for <> *)
   178 (* The dual versions for <> *)
   167 qed_goalw "DmdImpl" TLA.thy [dmd_def]
   179 val [prem] = goalw thy [dmd_def]
   168    "|- F --> G ==> |- <>F --> <>G"
   180    "|- F --> G ==> |- <>F --> <>G";
   169    (fn [prem] => [fast_tac (temp_cs addSIs [prem] addSEs [STL4E]) 1]);
   181 by (fast_tac (temp_cs addSIs [prem] addSEs [STL4E]) 1);
   170 
   182 qed "DmdImpl";
   171 qed_goal "DmdImplE" TLA.thy
   183 
   172    "[| sigma |= <>F; |- F --> G |] ==> sigma |= <>G"
   184 val prems = goal thy "[| sigma |= <>F; |- F --> G |] ==> sigma |= <>G";
   173    (fn prems => [ REPEAT (resolve_tac (prems @ [temp_use DmdImpl]) 1) ]);
   185 by (REPEAT (resolve_tac (prems @ [temp_use DmdImpl]) 1));
       
   186 qed "DmdImplE";
   174 
   187 
   175 
   188 
   176 (* ------------------------ STL5 ------------------------------------------- *)
   189 (* ------------------------ STL5 ------------------------------------------- *)
   177 qed_goal "STL5" TLA.thy "|- ([]F & []G) = ([](F & G))"
   190 Goal "|- ([]F & []G) = ([](F & G))";
   178    (fn _ => [Auto_tac,
   191 by Auto_tac;
   179 	     subgoal_tac "sigma |= [](G --> (F & G))" 1,
   192 by (subgoal_tac "sigma |= [](G --> (F & G))" 1);
   180 	     etac (temp_use normalT) 1, atac 1,
   193 by (etac (temp_use normalT) 1);
   181 	     ALLGOALS (fast_tac (temp_cs addSEs [STL4E]))
   194 by (ALLGOALS (fast_tac (temp_cs addSEs [STL4E])));
   182 	    ]);
   195 qed "STL5";
       
   196 
   183 (* rewrite rule to split conjunctions under boxes *)
   197 (* rewrite rule to split conjunctions under boxes *)
   184 bind_thm("split_box_conj", (temp_unlift STL5) RS sym);
   198 bind_thm("split_box_conj", (temp_unlift STL5) RS sym);
   185 
   199 
   186 (* the corresponding elimination rule allows to combine boxes in the hypotheses
   200 (* the corresponding elimination rule allows to combine boxes in the hypotheses
   187    (NB: F and G must have the same type, i.e., both actions or temporals.)
   201    (NB: F and G must have the same type, i.e., both actions or temporals.)
   188    Use "addSE2" etc. if you want to add this to a claset, otherwise it will loop!
   202    Use "addSE2" etc. if you want to add this to a claset, otherwise it will loop!
   189 *)
   203 *)
   190 qed_goal "box_conjE" TLA.thy
   204 val prems = goal thy
   191    "[| sigma |= []F; sigma |= []G; sigma |= [](F&G) ==> PROP R |] ==> PROP R"
   205    "[| sigma |= []F; sigma |= []G; sigma |= [](F&G) ==> PROP R |] ==> PROP R";
   192    (fn prems => [ REPEAT (resolve_tac
   206 by (REPEAT (resolve_tac (prems @ [(temp_unlift STL5) RS iffD1, conjI]) 1));
   193 			   (prems @ [(temp_unlift STL5) RS iffD1, conjI]) 1) ]);
   207 qed "box_conjE";
   194 
   208 
   195 (* Instances of box_conjE for state predicates, actions, and temporals
   209 (* Instances of box_conjE for state predicates, actions, and temporals
   196    in case the general rule is "too polymorphic".
   210    in case the general rule is "too polymorphic".
   197 *)
   211 *)
   198 bind_thm("box_conjE_temp", read_instantiate [("'a","behavior")] box_conjE);
   212 bind_thm("box_conjE_temp", read_instantiate [("'a","behavior")] box_conjE);
   227       (sigma |= [](! x. F x)) = (! x. (sigma |= []F x))
   241       (sigma |= [](! x. F x)) = (! x. (sigma |= []F x))
   228 *)
   242 *)
   229 bind_thm("all_box", standard((temp_unlift allT) RS sym));
   243 bind_thm("all_box", standard((temp_unlift allT) RS sym));
   230 
   244 
   231 
   245 
   232 qed_goal "DmdOr" TLA.thy "|- (<>(F | G)) = (<>F | <>G)"
   246 Goal "|- (<>(F | G)) = (<>F | <>G)";
   233    (fn _ => [auto_tac (temp_css addsimps2 [dmd_def,split_box_conj]),
   247 by (auto_tac (temp_css addsimps2 [dmd_def,split_box_conj]));
   234              TRYALL (EVERY' [etac swap, 
   248 by (ALLGOALS (EVERY' [etac swap, 
   235                              merge_box_tac, 
   249                       merge_box_tac, 
   236                              fast_tac (temp_cs addSEs [STL4E])])
   250                       fast_tac (temp_cs addSEs [STL4E])]));
   237             ]);
   251 qed "DmdOr";
   238 
   252 
   239 qed_goal "exT" TLA.thy "|- (? x. <>(F x)) = (<>(? x. F x))"
   253 Goal "|- (EX x. <>(F x)) = (<>(EX x. F x))";
   240    (fn _ => [ auto_tac (temp_css addsimps2 [dmd_def,Not_Rex,all_box]) ]);
   254 by (auto_tac (temp_css addsimps2 [dmd_def,Not_Rex,all_box]));
       
   255 qed "exT";
   241 
   256 
   242 bind_thm("ex_dmd", standard((temp_unlift exT) RS sym));
   257 bind_thm("ex_dmd", standard((temp_unlift exT) RS sym));
   243 	     
   258 	     
   244 
   259 
   245 qed_goal "STL4Edup" TLA.thy
   260 Goal "!!sigma. [| sigma |= []A; sigma |= []F; |- F & []A --> G |] ==> sigma |= []G";
   246    "!!sigma. [| sigma |= []A; sigma |= []F; |- F & []A --> G |] ==> sigma |= []G"
   261 by (etac dup_boxE 1);
   247    (fn _ => [etac dup_boxE 1,
   262 by (merge_box_tac 1);
   248 	     merge_box_tac 1,
   263 by (etac STL4E 1);
   249 	     etac STL4E 1,
   264 by (atac 1);
   250 	     atac 1
   265 qed "STL4Edup";
   251 	    ]);
   266 
   252 
   267 Goalw [dmd_def]
   253 qed_goalw "DmdImpl2" TLA.thy [dmd_def]
   268    "!!sigma. [| sigma |= <>F; sigma |= [](F --> G) |] ==> sigma |= <>G";
   254    "!!sigma. [| sigma |= <>F; sigma |= [](F --> G) |] ==> sigma |= <>G"
   269 by Auto_tac;
   255    (fn _ => [Auto_tac,
   270 by (etac notE 1);
   256 	     etac notE 1,
   271 by (merge_box_tac 1);
   257 	     merge_box_tac 1,
   272 by (fast_tac (temp_cs addSEs [STL4E]) 1);
   258 	     fast_tac (temp_cs addSEs [STL4E]) 1
   273 qed "DmdImpl2";
   259 	    ]);
   274 
   260 
   275 val [prem1,prem2,prem3] = goal thy
   261 qed_goal "InfImpl" TLA.thy
   276   "[| sigma |= []<>F; sigma |= []G; |- F & G --> H |] ==> sigma |= []<>H";
   262    "[| sigma |= []<>F; sigma |= []G; |- F & G --> H |] ==> sigma |= []<>H"
   277 by (cut_facts_tac [prem1,prem2] 1);
   263    (fn [prem1,prem2,prem3] 
   278 by (eres_inst_tac [("F","G")] dup_boxE 1);
   264        => [cut_facts_tac [prem1,prem2] 1,
   279 by (merge_box_tac 1);
   265 	   eres_inst_tac [("F","G")] dup_boxE 1,
   280 by (fast_tac (temp_cs addSEs [STL4E,DmdImpl2] addSIs [prem3]) 1);
   266 	   merge_box_tac 1,
   281 qed "InfImpl";
   267 	   fast_tac (temp_cs addSEs [STL4E,DmdImpl2] addSIs [prem3]) 1
       
   268 	  ]);
       
   269 
   282 
   270 (* ------------------------ STL6 ------------------------------------------- *)
   283 (* ------------------------ STL6 ------------------------------------------- *)
   271 (* Used in the proof of STL6, but useful in itself. *)
   284 (* Used in the proof of STL6, but useful in itself. *)
   272 qed_goalw "BoxDmd" TLA.thy [dmd_def] "|- []F & <>G --> <>([]F & G)"
   285 Goalw [dmd_def] "|- []F & <>G --> <>([]F & G)";
   273   (fn _ => [ Clarsimp_tac 1,
   286 by (Clarsimp_tac 1);
   274              etac dup_boxE 1,
   287 by (etac dup_boxE 1);
   275 	     merge_box_tac 1,
   288 by (merge_box_tac 1);
   276              etac swap 1,
   289 by (etac swap 1);
   277              fast_tac (temp_cs addSEs [STL4E]) 1 ]);
   290 by (fast_tac (temp_cs addSEs [STL4E]) 1);
       
   291 qed "BoxDmd";
   278 
   292 
   279 (* weaker than BoxDmd, but more polymorphic (and often just right) *)
   293 (* weaker than BoxDmd, but more polymorphic (and often just right) *)
   280 qed_goalw "BoxDmd_simple" TLA.thy [dmd_def] "|- []F & <>G --> <>(F & G)"
   294 Goalw [dmd_def] "|- []F & <>G --> <>(F & G)";
   281   (fn _ => [ Clarsimp_tac 1,
   295 by (Clarsimp_tac 1);
   282 	     merge_box_tac 1,
   296 by (merge_box_tac 1);
   283              fast_tac (temp_cs addSEs [notE,STL4E]) 1
   297 by (fast_tac (temp_cs addSEs [notE,STL4E]) 1);
   284 	   ]);
   298 qed "BoxDmd_simple";
   285 
   299 
   286 qed_goalw "BoxDmd2_simple" TLA.thy [dmd_def] "|- []F & <>G --> <>(G & F)"
   300 Goalw [dmd_def] "|- []F & <>G --> <>(G & F)";
   287   (fn _ => [ Clarsimp_tac 1,
   301 by (Clarsimp_tac 1);
   288 	     merge_box_tac 1,
   302 by (merge_box_tac 1);
   289              fast_tac (temp_cs addSEs [notE,STL4E]) 1
   303 by (fast_tac (temp_cs addSEs [notE,STL4E]) 1);
   290 	   ]);
   304 qed "BoxDmd2_simple";
   291 
   305 
   292 qed_goal "DmdImpldup" TLA.thy 
   306 val [p1,p2,p3] = goal thy
   293    "[| sigma |= []A; sigma |= <>F; |- []A & F --> G |] ==> sigma |= <>G"
   307    "[| sigma |= []A; sigma |= <>F; |- []A & F --> G |] ==> sigma |= <>G";
   294    (fn [p1,p2,p3] => [rtac ((p2 RS (p1 RS (temp_use BoxDmd))) RS DmdImplE) 1,
   308 by (rtac ((p2 RS (p1 RS (temp_use BoxDmd))) RS DmdImplE) 1);
   295                       rtac p3 1]);
   309 by (rtac p3 1);
   296 
   310 qed "DmdImpldup";
   297 qed_goal "STL6" TLA.thy "|- <>[]F & <>[]G --> <>[](F & G)"
   311 
   298   (fn _ => [auto_tac (temp_css addsimps2 [symmetric (temp_rewrite STL5)]),
   312 Goal "|- <>[]F & <>[]G --> <>[](F & G)";
   299 	    dtac (temp_use linT) 1, atac 1, etac thin_rl 1,
   313 by (auto_tac (temp_css addsimps2 [symmetric (temp_rewrite STL5)]));
   300 	    rtac ((temp_unlift DmdDmd) RS iffD1) 1,
   314 by (dtac (temp_use linT) 1);
   301 	    etac disjE 1,
   315 by (atac 1); 
   302 	    etac DmdImplE 1, rtac BoxDmd 1,
   316 by (etac thin_rl 1);
   303 	    (* the second subgoal needs commutativity of &, which complicates the proof *)
   317 by (rtac ((temp_unlift DmdDmd) RS iffD1) 1);
   304 	    etac DmdImplE 1,
   318 by (etac disjE 1);
   305 	    Auto_tac,
   319 by (etac DmdImplE 1);
   306 	    dtac (temp_use BoxDmd) 1, atac 1, etac thin_rl 1,
   320 by (rtac BoxDmd 1);
   307 	    fast_tac (temp_cs addSEs [DmdImplE]) 1
   321 by (etac DmdImplE 1);
   308 	   ]);
   322 by Auto_tac;
       
   323 by (dtac (temp_use BoxDmd) 1); 
       
   324 by (atac 1); 
       
   325 by (etac thin_rl 1);
       
   326 by (fast_tac (temp_cs addSEs [DmdImplE]) 1);
       
   327 qed "STL6";
   309 
   328 
   310 
   329 
   311 (* ------------------------ True / False ----------------------------------------- *)
   330 (* ------------------------ True / False ----------------------------------------- *)
   312 section "Simplification of constants";
   331 section "Simplification of constants";
   313 
   332 
   314 qed_goal "BoxConst" TLA.thy "|- ([]#P) = #P"
   333 Goal "|- ([]#P) = #P";
   315   (fn _ => [rtac tempI 1,
   334 by (rtac tempI 1);
   316             case_tac "P" 1,
   335 by (case_tac "P" 1);
   317             auto_tac (temp_css addSIs2 [necT] addDs2 [STL2_gen] 
   336 by (auto_tac (temp_css addSIs2 [necT] addDs2 [STL2_gen] 
   318                                addsimps2 Init_simps)
   337                        addsimps2 Init_simps));
   319            ]);
   338 qed "BoxConst";
   320 
   339 
   321 qed_goalw "DmdConst" TLA.thy [dmd_def] "|- (<>#P) = #P"
   340 Goalw [dmd_def] "|- (<>#P) = #P";
   322   (fn _ => [case_tac "P" 1,
   341 by (case_tac "P" 1);
   323             ALLGOALS (asm_full_simp_tac (simpset() addsimps [BoxConst]))
   342 by (ALLGOALS (asm_full_simp_tac (simpset() addsimps [BoxConst])));
   324            ]);
   343 qed "DmdConst";
   325 
   344 
   326 val temp_simps = map temp_rewrite [BoxConst, DmdConst];
   345 val temp_simps = map temp_rewrite [BoxConst, DmdConst];
   327 
   346 
   328 (* Make these rewrites active by default *)
   347 (* Make these rewrites active by default *)
   329 Addsimps temp_simps;
   348 Addsimps temp_simps;
   332 
   351 
   333 
   352 
   334 (* ------------------------ Further rewrites ----------------------------------------- *)
   353 (* ------------------------ Further rewrites ----------------------------------------- *)
   335 section "Further rewrites";
   354 section "Further rewrites";
   336 
   355 
   337 qed_goalw "NotBox" TLA.thy [dmd_def] "|- (~[]F) = (<>~F)"
   356 Goalw [dmd_def] "|- (~[]F) = (<>~F)";
   338    (fn _ => [ Simp_tac 1 ]);
   357 by (Simp_tac 1);
   339 
   358 qed "NotBox";
   340 qed_goalw "NotDmd" TLA.thy [dmd_def] "|- (~<>F) = ([]~F)"
   359 
   341    (fn _ => [ Simp_tac 1 ]);
   360 Goalw [dmd_def] "|- (~<>F) = ([]~F)";
       
   361 by (Simp_tac 1);
       
   362 qed "NotDmd";
   342 
   363 
   343 (* These are not by default included in temp_css, because they could be harmful,
   364 (* These are not by default included in temp_css, because they could be harmful,
   344    e.g. []F & ~[]F becomes []F & <>~F !! *)
   365    e.g. []F & ~[]F becomes []F & <>~F !! *)
   345 val more_temp_simps =  (map temp_rewrite [STL3, DmdDmd, NotBox, NotDmd])
   366 val more_temp_simps =  (map temp_rewrite [STL3, DmdDmd, NotBox, NotDmd])
   346                        @ (map (fn th => (temp_unlift th) RS eq_reflection)
   367                        @ (map (fn th => (temp_unlift th) RS eq_reflection)
   347 		         [NotBox, NotDmd]);
   368 		         [NotBox, NotDmd]);
   348 
   369 
   349 qed_goal "BoxDmdBox" TLA.thy "|- ([]<>[]F) = (<>[]F)"
   370 Goal "|- ([]<>[]F) = (<>[]F)";
   350    (fn _ => [ auto_tac (temp_css addSDs2 [STL2]),
   371 by (auto_tac (temp_css addSDs2 [STL2]));
   351               rtac ccontr 1,
   372 by (rtac ccontr 1);
   352               subgoal_tac "sigma |= <>[][]F & <>[]~[]F" 1,
   373 by (subgoal_tac "sigma |= <>[][]F & <>[]~[]F" 1);
   353               etac thin_rl 1,
   374 by (etac thin_rl 1);
   354               Auto_tac,
   375 by Auto_tac;
   355 	      dtac (temp_use STL6) 1, atac 1,
   376 by (dtac (temp_use STL6) 1); 
   356 	      Asm_full_simp_tac 1,
   377 by (atac 1);
   357 	      ALLGOALS (asm_full_simp_tac (simpset() addsimps more_temp_simps))
   378 by (Asm_full_simp_tac 1);
   358 	    ]);
   379 by (ALLGOALS (asm_full_simp_tac (simpset() addsimps more_temp_simps)));
   359 
   380 qed "BoxDmdBox";
   360 qed_goalw "DmdBoxDmd" TLA.thy [dmd_def] "|- (<>[]<>F) = ([]<>F)"
   381 
   361   (fn _ => [ auto_tac (temp_css addsimps2 [rewrite_rule [dmd_def] BoxDmdBox]) ]);
   382 Goalw [dmd_def] "|- (<>[]<>F) = ([]<>F)";
       
   383 by (auto_tac (temp_css addsimps2 [rewrite_rule [dmd_def] BoxDmdBox]));
       
   384 qed "DmdBoxDmd";
   362 
   385 
   363 val more_temp_simps = more_temp_simps @ (map temp_rewrite [BoxDmdBox, DmdBoxDmd]);
   386 val more_temp_simps = more_temp_simps @ (map temp_rewrite [BoxDmdBox, DmdBoxDmd]);
   364 
   387 
   365 
   388 
   366 (* ------------------------ Miscellaneous ----------------------------------- *)
   389 (* ------------------------ Miscellaneous ----------------------------------- *)
   367 
   390 
   368 qed_goal "BoxOr" TLA.thy 
   391 Goal "!!sigma. [| sigma |= []F | []G |] ==> sigma |= [](F | G)";
   369    "!!sigma. [| sigma |= []F | []G |] ==> sigma |= [](F | G)"
   392 by (fast_tac (temp_cs addSEs [STL4E]) 1);
   370    (fn _ => [ fast_tac (temp_cs addSEs [STL4E]) 1 ]);
   393 qed "BoxOr";
   371 
   394 
   372 (* "persistently implies infinitely often" *)
   395 (* "persistently implies infinitely often" *)
   373 qed_goal "DBImplBD" TLA.thy "|- <>[]F --> []<>F"
   396 Goal "|- <>[]F --> []<>F";
   374   (fn _ => [Clarsimp_tac 1,
   397 by (Clarsimp_tac 1);
   375 	    rtac ccontr 1,
   398 by (rtac ccontr 1);
   376             asm_full_simp_tac (simpset() addsimps more_temp_simps) 1,
   399 by (asm_full_simp_tac (simpset() addsimps more_temp_simps) 1);
   377             dtac (temp_use STL6) 1, atac 1,
   400 by (dtac (temp_use STL6) 1); 
   378             Asm_full_simp_tac 1
   401 by (atac 1);
   379 	   ]);
   402 by (Asm_full_simp_tac 1);
   380 
   403 qed "DBImplBD";
   381 qed_goal "BoxDmdDmdBox" TLA.thy
   404 
   382    "|- []<>F & <>[]G --> []<>(F & G)"
   405 Goal "|- []<>F & <>[]G --> []<>(F & G)";
   383    (fn _ => [Clarsimp_tac 1,
   406 by (Clarsimp_tac 1);
   384              rtac ccontr 1,
   407 by (rtac ccontr 1);
   385 	     rewrite_goals_tac more_temp_simps,
   408 by (rewrite_goals_tac more_temp_simps);
   386 	     dtac (temp_use STL6) 1, atac 1,
   409 by (dtac (temp_use STL6) 1);
   387 	     subgoal_tac "sigma |= <>[]~F" 1,
   410 by (atac 1);
   388 	     force_tac (temp_css addsimps2 [dmd_def]) 1,
   411 by (subgoal_tac "sigma |= <>[]~F" 1);
   389 	     fast_tac (temp_cs addEs [DmdImplE,STL4E]) 1
   412  by (force_tac (temp_css addsimps2 [dmd_def]) 1);
   390 	    ]);
   413 by (fast_tac (temp_cs addEs [DmdImplE,STL4E]) 1);
       
   414 qed "BoxDmdDmdBox";
   391 
   415 
   392 
   416 
   393 (* ------------------------------------------------------------------------- *)
   417 (* ------------------------------------------------------------------------- *)
   394 (***          TLA-specific theorems: primed formulas                       ***)
   418 (***          TLA-specific theorems: primed formulas                       ***)
   395 (* ------------------------------------------------------------------------- *)
   419 (* ------------------------------------------------------------------------- *)
   396 section "priming";
   420 section "priming";
   397 
   421 
   398 (* ------------------------ TLA2 ------------------------------------------- *)
   422 (* ------------------------ TLA2 ------------------------------------------- *)
   399 qed_goal "STL2_pr" TLA.thy
   423 Goal "|- []P --> Init P & Init P`";
   400   "|- []P --> Init P & Init P`"
   424 by (fast_tac (temp_cs addSIs [primeI, STL2_gen]) 1);
   401   (fn _ => [fast_tac (temp_cs addSIs [primeI, STL2_gen]) 1]);
   425 qed "STL2_pr";
   402 
   426 
   403 (* Auxiliary lemma allows priming of boxed actions *)
   427 (* Auxiliary lemma allows priming of boxed actions *)
   404 qed_goal "BoxPrime" TLA.thy "|- []P --> []($P & P$)"
   428 Goal "|- []P --> []($P & P$)";
   405   (fn _ => [Clarsimp_tac 1,
   429 by (Clarsimp_tac 1);
   406 	    etac dup_boxE 1,
   430 by (etac dup_boxE 1);
   407             rewtac boxInit_act,
   431 by (rewtac boxInit_act);
   408             etac STL4E 1,
   432 by (etac STL4E 1);
   409 	    auto_tac (temp_css addsimps2 Init_simps addSDs2 [STL2_pr])
   433 by (auto_tac (temp_css addsimps2 Init_simps addSDs2 [STL2_pr]));
   410 	   ]);
   434 qed "BoxPrime";
   411 
   435 
   412 qed_goal "TLA2" TLA.thy "|- $P & P$ --> A  ==>  |- []P --> []A"
   436 val prems = goal thy "|- $P & P$ --> A  ==>  |- []P --> []A";
   413   (fn prems => [Clarsimp_tac 1,
   437 by (Clarsimp_tac 1);
   414                 dtac (temp_use BoxPrime) 1,
   438 by (dtac (temp_use BoxPrime) 1);
   415                 auto_tac (temp_css addsimps2 [Init_stp_act_rev] addSIs2 prems addSEs2 [STL4E])
   439 by (auto_tac (temp_css addsimps2 [Init_stp_act_rev] 
   416                ]);
   440                        addSIs2 prems addSEs2 [STL4E]));
   417 
   441 qed "TLA2";
   418 qed_goal "TLA2E" TLA.thy 
   442 
   419    "[| sigma |= []P; |- $P & P$ --> A |] ==> sigma |= []A"
   443 val prems = goal thy 
   420    (fn prems => [REPEAT (resolve_tac (prems @ (prems RL [temp_use TLA2])) 1)]);
   444   "[| sigma |= []P; |- $P & P$ --> A |] ==> sigma |= []A";
   421 
   445 by (REPEAT (resolve_tac (prems @ (prems RL [temp_use TLA2])) 1));
   422 qed_goalw "DmdPrime" TLA.thy [dmd_def] "|- (<>P`) --> (<>P)"
   446 qed "TLA2E";
   423    (fn _ => [ fast_tac (temp_cs addSEs [TLA2E]) 1 ]);
   447 
       
   448 Goalw [dmd_def] "|- (<>P`) --> (<>P)";
       
   449 by (fast_tac (temp_cs addSEs [TLA2E]) 1);
       
   450 qed "DmdPrime";
   424 
   451 
   425 bind_thm("PrimeDmd", (temp_use InitDmd_gen) RS (temp_use DmdPrime));
   452 bind_thm("PrimeDmd", (temp_use InitDmd_gen) RS (temp_use DmdPrime));
   426 
   453 
   427 (* ------------------------ INV1, stable --------------------------------------- *)
   454 (* ------------------------ INV1, stable --------------------------------------- *)
   428 section "stable, invariant";
   455 section "stable, invariant";
   429 
   456 
   430 qed_goal "ind_rule" TLA.thy
   457 val prems = goal thy
   431    "[| sigma |= []H; sigma |= Init P; |- H --> (Init P & ~[]F --> Init(P`) & F) |] \
   458    "[| sigma |= []H; sigma |= Init P; |- H --> (Init P & ~[]F --> Init(P`) & F) |] \
   432 \   ==> sigma |= []F"
   459 \   ==> sigma |= []F";
   433    (fn prems => [rtac (temp_use indT) 1,
   460 by (rtac (temp_use indT) 1);
   434 		 REPEAT (resolve_tac (prems @ (prems RL [STL4E])) 1)]);
   461 by (REPEAT (resolve_tac (prems @ (prems RL [STL4E])) 1));
   435 
   462 qed "ind_rule";
   436 qed_goalw "box_stp_act" TLA.thy [boxInit_act] "|- ([]$P) = ([]P)"
   463 
   437   (K [simp_tac (simpset() addsimps Init_simps) 1]);
   464 Goalw [boxInit_act] "|- ([]$P) = ([]P)";
       
   465 by (simp_tac (simpset() addsimps Init_simps) 1);
       
   466 qed "box_stp_act";
   438 bind_thm("box_stp_actI", zero_var_indexes ((temp_use box_stp_act) RS iffD2));
   467 bind_thm("box_stp_actI", zero_var_indexes ((temp_use box_stp_act) RS iffD2));
   439 bind_thm("box_stp_actD", zero_var_indexes ((temp_use box_stp_act) RS iffD1));
   468 bind_thm("box_stp_actD", zero_var_indexes ((temp_use box_stp_act) RS iffD1));
   440 
   469 
   441 val more_temp_simps = (temp_rewrite box_stp_act)::more_temp_simps;
   470 val more_temp_simps = (temp_rewrite box_stp_act)::more_temp_simps;
   442 
   471 
   443 qed_goalw "INV1" TLA.thy [stable_def,boxInit_stp,boxInit_act] 
   472 Goalw [stable_def,boxInit_stp,boxInit_act] 
   444   "|- (Init P) --> (stable P) --> []P"
   473   "|- (Init P) --> (stable P) --> []P";
   445   (K [Clarsimp_tac 1,
   474 by (Clarsimp_tac 1);
   446       etac ind_rule 1,
   475 by (etac ind_rule 1);
   447       auto_tac (temp_css addsimps2 Init_simps addEs2 [ind_rule])
   476 by (auto_tac (temp_css addsimps2 Init_simps addEs2 [ind_rule]));
   448      ]);
   477 qed "INV1";
   449 
   478 
   450 qed_goalw "StableT" TLA.thy [stable_def]
   479 Goalw [stable_def]
   451    "|- $P & A --> P` ==> |- []A --> stable P"
   480    "!!P. |- $P & A --> P` ==> |- []A --> stable P";
   452    (fn [prem] => [fast_tac (temp_cs addSEs [STL4E] addIs [prem]) 1]);
   481 by (fast_tac (temp_cs addSEs [STL4E]) 1);
   453 
   482 qed "StableT";
   454 qed_goal "Stable" TLA.thy
   483 
   455    "[| sigma |= []A; |- $P & A --> P` |] ==> sigma |= stable P"
   484 val prems = goal thy
   456    (fn prems => [ REPEAT (resolve_tac (prems @ [temp_use StableT]) 1) ]);
   485    "[| sigma |= []A; |- $P & A --> P` |] ==> sigma |= stable P";
       
   486 by (REPEAT (resolve_tac (prems @ [temp_use StableT]) 1));
       
   487 qed "Stable";
   457 
   488 
   458 (* Generalization of INV1 *)
   489 (* Generalization of INV1 *)
   459 qed_goalw "StableBox" TLA.thy [stable_def]
   490 Goalw [stable_def] "|- (stable P) --> [](Init P --> []P)";
   460    "|- (stable P) --> [](Init P --> []P)"
   491 by (Clarsimp_tac 1);
   461    (K [Clarsimp_tac 1,
   492 by (etac dup_boxE 1);
   462        etac dup_boxE 1,
   493 by (force_tac (temp_css addsimps2 [stable_def] addEs2 [STL4E, INV1]) 1);
   463        force_tac (temp_css addsimps2 [stable_def] addEs2 [STL4E, INV1]) 1]);
   494 qed "StableBox";
   464 
   495 
   465 qed_goal "DmdStable" TLA.thy 
   496 Goal "|- (stable P) & <>P --> <>[]P";
   466    "|- (stable P) & <>P --> <>[]P"
   497 by (Clarsimp_tac 1);
   467    (fn _ => [Clarsimp_tac 1,
   498 by (rtac DmdImpl2 1);
   468              rtac DmdImpl2 1,
   499 by (etac (temp_use StableBox) 2);
   469 	     etac (temp_use StableBox) 2,
   500 by (asm_simp_tac (simpset() addsimps [dmdInitD]) 1);
   470 	     asm_simp_tac (simpset() addsimps [dmdInitD]) 1
   501 qed "DmdStable";
   471 	    ]);
       
   472 
   502 
   473 (* ---------------- (Semi-)automatic invariant tactics ---------------------- *)
   503 (* ---------------- (Semi-)automatic invariant tactics ---------------------- *)
   474 
   504 
   475 (* inv_tac reduces goals of the form ... ==> sigma |= []P *)
   505 (* inv_tac reduces goals of the form ... ==> sigma |= []P *)
   476 fun inv_tac css = SELECT_GOAL
   506 fun inv_tac css = SELECT_GOAL
   489 fun auto_inv_tac ss = SELECT_GOAL
   519 fun auto_inv_tac ss = SELECT_GOAL
   490     ((inv_tac (claset(),ss) 1) THEN
   520     ((inv_tac (claset(),ss) 1) THEN
   491      (TRYALL (action_simp_tac (ss addsimps [Init_stp,Init_act]) [] [squareE])));
   521      (TRYALL (action_simp_tac (ss addsimps [Init_stp,Init_act]) [] [squareE])));
   492 
   522 
   493 
   523 
   494 qed_goalw "unless" TLA.thy [dmd_def]
   524 Goalw [dmd_def] "|- []($P --> P` | Q`) --> (stable P) | <>Q";
   495    "|- []($P --> P` | Q`) --> (stable P) | <>Q"
   525 by (clarsimp_tac (temp_css addSDs2 [BoxPrime]) 1);
   496    (fn _ => [clarsimp_tac (temp_css addSDs2 [BoxPrime]) 1,
   526 by (merge_box_tac 1);
   497 	     merge_box_tac 1,
   527 by (etac swap 1);
   498              etac swap 1,
   528 by (fast_tac (temp_cs addSEs [Stable]) 1);
   499 	     fast_tac (temp_cs addSEs [Stable]) 1
   529 qed "unless";
   500 	    ]);
       
   501 
   530 
   502 
   531 
   503 (* --------------------- Recursive expansions --------------------------------------- *)
   532 (* --------------------- Recursive expansions --------------------------------------- *)
   504 section "recursive expansions";
   533 section "recursive expansions";
   505 
   534 
   506 (* Recursive expansions of [] and <> for state predicates *)
   535 (* Recursive expansions of [] and <> for state predicates *)
   507 qed_goal "BoxRec" TLA.thy "|- ([]P) = (Init P & []P`)"
   536 Goal "|- ([]P) = (Init P & []P`)";
   508    (fn _ => [auto_tac (temp_css addSIs2 [STL2_gen]),
   537 by (auto_tac (temp_css addSIs2 [STL2_gen]));
   509 	     fast_tac (temp_cs addSEs [TLA2E]) 1,
   538 by (fast_tac (temp_cs addSEs [TLA2E]) 1);
   510 	     auto_tac (temp_css addsimps2 [stable_def] addSEs2 [INV1,STL4E])
   539 by (auto_tac (temp_css addsimps2 [stable_def] addSEs2 [INV1,STL4E]));
   511 	    ]);
   540 qed "BoxRec";
   512 
   541 
   513 qed_goalw "DmdRec" TLA.thy [dmd_def, temp_rewrite BoxRec] "|- (<>P) = (Init P | <>P`)" 
   542 Goalw [dmd_def, temp_rewrite BoxRec] "|- (<>P) = (Init P | <>P`)";
   514   (K [ auto_tac (temp_css addsimps2 Init_simps) ]);
   543 by (auto_tac (temp_css addsimps2 Init_simps));
   515 
   544 qed "DmdRec";
   516 qed_goal "DmdRec2" TLA.thy
   545 
   517  "!!sigma. [| sigma |= <>P; sigma |= []~P` |] ==> sigma |= Init P"
   546 Goal "!!sigma. [| sigma |= <>P; sigma |= []~P` |] ==> sigma |= Init P";
   518    (K [ force_tac (temp_css addsimps2 [DmdRec,dmd_def]) 1]);
   547 by (force_tac (temp_css addsimps2 [DmdRec,dmd_def]) 1);
   519 
   548 qed "DmdRec2";
   520 (* The "-->" part of the following is a little intricate. *)
   549 
   521 qed_goal "InfinitePrime" TLA.thy "|- ([]<>P) = ([]<>P`)"
   550 Goal "|- ([]<>P) = ([]<>P`)";
   522    (fn _ => [Auto_tac,
   551 by Auto_tac;
   523 	     rtac classical 1,
   552 by (rtac classical 1);
   524 	     rtac (temp_use DBImplBD) 1,
   553 by (rtac (temp_use DBImplBD) 1);
   525 	     subgoal_tac "sigma |= <>[]P" 1,
   554 by (subgoal_tac "sigma |= <>[]P" 1);
   526 	     fast_tac (temp_cs addSEs [DmdImplE,TLA2E]) 1,
   555  by (fast_tac (temp_cs addSEs [DmdImplE,TLA2E]) 1);
   527 	     subgoal_tac "sigma |= <>[](<>P & []~P`)" 1,
   556  by (subgoal_tac "sigma |= <>[](<>P & []~P`)" 1);
   528 	     force_tac (temp_css addsimps2 [boxInit_stp]
   557   by (force_tac (temp_css addsimps2 [boxInit_stp]
   529 			             addSEs2 [DmdImplE,STL4E,DmdRec2]) 1,
   558                           addSEs2 [DmdImplE,STL4E,DmdRec2]) 1);
   530 	     force_tac (temp_css addSIs2 [STL6] addsimps2 more_temp_simps) 1,
   559  by (force_tac (temp_css addSIs2 [STL6] addsimps2 more_temp_simps) 1);
   531 	     fast_tac (temp_cs addIs [DmdPrime] addSEs [STL4E]) 1
   560 by (fast_tac (temp_cs addIs [DmdPrime] addSEs [STL4E]) 1);
   532 	    ]);
   561 qed "InfinitePrime";
   533 
   562 
   534 qed_goal "InfiniteEnsures" TLA.thy
   563 val prems = goalw thy [temp_rewrite InfinitePrime]
   535    "[| sigma |= []N; sigma |= []<>A; |- A & N --> P` |] ==> sigma |= []<>P"
   564   "[| sigma |= []N; sigma |= []<>A; |- A & N --> P` |] ==> sigma |= []<>P";
   536    (fn prems => [rewtac (temp_rewrite InfinitePrime),
   565 by (rtac InfImpl 1);
   537                  rtac InfImpl 1,
   566 by (REPEAT (resolve_tac prems 1));
   538                  REPEAT (resolve_tac prems 1)
   567 qed "InfiniteEnsures";
   539                 ]);
       
   540 
   568 
   541 (* ------------------------ fairness ------------------------------------------- *)
   569 (* ------------------------ fairness ------------------------------------------- *)
   542 section "fairness";
   570 section "fairness";
   543 
   571 
   544 (* alternative definitions of fairness *)
   572 (* alternative definitions of fairness *)
   545 qed_goalw "WF_alt" TLA.thy [WF_def,dmd_def] 
   573 Goalw [WF_def,dmd_def] 
   546    "|- WF(A)_v = ([]<>~Enabled(<A>_v) | []<><A>_v)"
   574   "|- WF(A)_v = ([]<>~Enabled(<A>_v) | []<><A>_v)";
   547    (fn _ => [ fast_tac temp_cs 1 ]);
   575 by (fast_tac temp_cs 1);
   548 
   576 qed "WF_alt";
   549 qed_goalw "SF_alt" TLA.thy [SF_def,dmd_def]
   577 
   550    "|- SF(A)_v = (<>[]~Enabled(<A>_v) | []<><A>_v)"
   578 Goalw [SF_def,dmd_def]
   551    (fn _ => [ fast_tac temp_cs 1 ]);
   579   "|- SF(A)_v = (<>[]~Enabled(<A>_v) | []<><A>_v)";
       
   580 by (fast_tac temp_cs 1);
       
   581 qed "SF_alt";
   552 
   582 
   553 (* theorems to "box" fairness conditions *)
   583 (* theorems to "box" fairness conditions *)
   554 qed_goal "BoxWFI" TLA.thy "|- WF(A)_v --> []WF(A)_v"
   584 Goal "|- WF(A)_v --> []WF(A)_v";
   555    (fn _ => [ auto_tac (temp_css addsimps2 (WF_alt::more_temp_simps) 
   585 by (auto_tac (temp_css addsimps2 (WF_alt::more_temp_simps) 
   556                                  addSIs2 [BoxOr]) ]);
   586                        addSIs2 [BoxOr]));
   557 
   587 qed "BoxWFI";
   558 qed_goal "WF_Box" TLA.thy "|- ([]WF(A)_v) = WF(A)_v"
   588 
   559   (fn prems => [ fast_tac (temp_cs addSIs [BoxWFI] addSDs [STL2]) 1 ]);
   589 Goal "|- ([]WF(A)_v) = WF(A)_v";
   560 
   590 by (fast_tac (temp_cs addSIs [BoxWFI] addSDs [STL2]) 1);
   561 qed_goal "BoxSFI" TLA.thy "|- SF(A)_v --> []SF(A)_v"
   591 qed "WF_Box";
   562    (fn _ => [ auto_tac (temp_css addsimps2 (SF_alt::more_temp_simps) 
   592 
   563                                  addSIs2 [BoxOr]) ]);
   593 Goal "|- SF(A)_v --> []SF(A)_v";
   564 
   594 by (auto_tac (temp_css addsimps2 (SF_alt::more_temp_simps) 
   565 qed_goal "SF_Box" TLA.thy "|- ([]SF(A)_v) = SF(A)_v"
   595                        addSIs2 [BoxOr]));
   566   (fn prems => [ fast_tac (temp_cs addSIs [BoxSFI] addSDs [STL2]) 1 ]);
   596 qed "BoxSFI";
       
   597 
       
   598 Goal "|- ([]SF(A)_v) = SF(A)_v";
       
   599 by (fast_tac (temp_cs addSIs [BoxSFI] addSDs [STL2]) 1);
       
   600 qed "SF_Box";
   567 
   601 
   568 val more_temp_simps = more_temp_simps @ (map temp_rewrite [WF_Box, SF_Box]);
   602 val more_temp_simps = more_temp_simps @ (map temp_rewrite [WF_Box, SF_Box]);
   569 
   603 
   570 qed_goalw "SFImplWF" TLA.thy [SF_def,WF_def] "|- SF(A)_v --> WF(A)_v"
   604 Goalw [SF_def,WF_def] "|- SF(A)_v --> WF(A)_v";
   571   (fn _ => [ fast_tac (temp_cs addSDs [DBImplBD]) 1 ]);
   605 by (fast_tac (temp_cs addSDs [DBImplBD]) 1);
       
   606 qed "SFImplWF";
   572 
   607 
   573 (* A tactic that "boxes" all fairness conditions. Apply more_temp_simps to "unbox". *)
   608 (* A tactic that "boxes" all fairness conditions. Apply more_temp_simps to "unbox". *)
   574 val box_fair_tac = SELECT_GOAL (REPEAT (dresolve_tac [BoxWFI,BoxSFI] 1));
   609 val box_fair_tac = SELECT_GOAL (REPEAT (dresolve_tac [BoxWFI,BoxSFI] 1));
   575 
   610 
   576 
   611 
   577 (* ------------------------------ leads-to ------------------------------ *)
   612 (* ------------------------------ leads-to ------------------------------ *)
   578 
   613 
   579 section "~>";
   614 section "~>";
   580 
   615 
   581 qed_goalw "leadsto_init" TLA.thy [leadsto_def]
   616 Goalw  [leadsto_def] "|- (Init F) & (F ~> G) --> <>G";
   582    "|- (Init F) & (F ~> G) --> <>G"
   617 by (auto_tac (temp_css addSDs2 [STL2]));
   583    (fn _ => [ auto_tac (temp_css addSDs2 [STL2]) ]);
   618 qed "leadsto_init";
   584 
   619 
   585 (* |- F & (F ~> G) --> <>G *)
   620 (* |- F & (F ~> G) --> <>G *)
   586 bind_thm("leadsto_init_temp", 
   621 bind_thm("leadsto_init_temp", 
   587          rewrite_rule Init_simps (read_instantiate [("'a","behavior")] leadsto_init));
   622          rewrite_rule Init_simps (read_instantiate [("'a","behavior")] leadsto_init));
   588 
   623 
   589 qed_goalw "streett_leadsto" TLA.thy [leadsto_def]
   624 Goalw [leadsto_def] "|- ([]<>Init F --> []<>G) = (<>(F ~> G))";
   590    "|- ([]<>Init F --> []<>G) = (<>(F ~> G))" (K [
   625 by Auto_tac;
   591              Auto_tac,
   626 by (asm_full_simp_tac (simpset() addsimps more_temp_simps) 1);
   592              asm_full_simp_tac (simpset() addsimps more_temp_simps) 1,
   627 by (fast_tac (temp_cs addSEs [DmdImplE,STL4E]) 1);
   593              fast_tac (temp_cs addSEs [DmdImplE,STL4E]) 1,
   628 by (fast_tac (temp_cs addSIs [InitDmd] addSEs [STL4E]) 1);
   594              fast_tac (temp_cs addSIs [InitDmd] addSEs [STL4E]) 1,
   629 by (subgoal_tac "sigma |= []<><>G" 1);
   595              subgoal_tac "sigma |= []<><>G" 1,
   630 by (asm_full_simp_tac (simpset() addsimps more_temp_simps) 1);
   596              asm_full_simp_tac (simpset() addsimps more_temp_simps) 1,
   631 by (dtac (temp_use BoxDmdDmdBox) 1); 
   597              dtac (temp_use BoxDmdDmdBox) 1, atac 1,
   632 by (atac 1);
   598              fast_tac (temp_cs addSEs [DmdImplE,STL4E]) 1
   633 by (fast_tac (temp_cs addSEs [DmdImplE,STL4E]) 1);
   599             ]);
   634 qed "streett_leadsto";
   600 
   635 
   601 qed_goal "leadsto_infinite" TLA.thy
   636 Goal "|- []<>F & (F ~> G) --> []<>G";
   602    "|- []<>F & (F ~> G) --> []<>G"
   637 by (Clarsimp_tac 1);
   603    (fn _ => [Clarsimp_tac 1,
   638 by (etac ((temp_use InitDmd) RS 
   604              etac ((temp_use InitDmd) RS 
   639           ((temp_unlift streett_leadsto) RS iffD2 RS mp)) 1);
   605                    ((temp_unlift streett_leadsto) RS iffD2 RS mp)) 1,
   640 by (asm_simp_tac (simpset() addsimps [dmdInitD]) 1);
   606              asm_simp_tac (simpset() addsimps [dmdInitD]) 1
   641 qed "leadsto_infinite";
   607             ]);
       
   608 
   642 
   609 (* In particular, strong fairness is a Streett condition. The following
   643 (* In particular, strong fairness is a Streett condition. The following
   610    rules are sometimes easier to use than WF2 or SF2 below.
   644    rules are sometimes easier to use than WF2 or SF2 below.
   611 *)
   645 *)
   612 qed_goalw "leadsto_SF" TLA.thy [SF_def]
   646 Goalw [SF_def] "|- (Enabled(<A>_v) ~> <A>_v) --> SF(A)_v";
   613   "|- (Enabled(<A>_v) ~> <A>_v) --> SF(A)_v"
   647 by (clarsimp_tac (temp_css addSEs2 [leadsto_infinite]) 1);
   614   (K [clarsimp_tac (temp_css addSEs2 [leadsto_infinite]) 1]);
   648 qed "leadsto_SF";
   615 
   649 
   616 qed_goal "leadsto_WF" TLA.thy 
   650 Goal "|- (Enabled(<A>_v) ~> <A>_v) --> WF(A)_v";
   617   "|- (Enabled(<A>_v) ~> <A>_v) --> WF(A)_v"
   651 by (clarsimp_tac (temp_css addSIs2 [SFImplWF, leadsto_SF]) 1);
   618   (K [ clarsimp_tac (temp_css addSIs2 [SFImplWF, leadsto_SF]) 1 ]);
   652 qed "leadsto_WF";
   619 
   653 
   620 (* introduce an invariant into the proof of a leadsto assertion.
   654 (* introduce an invariant into the proof of a leadsto assertion.
   621    []I --> ((P ~> Q)  =  (P /\ I ~> Q))
   655    []I --> ((P ~> Q)  =  (P /\ I ~> Q))
   622 *)
   656 *)
   623 qed_goalw "INV_leadsto" TLA.thy [leadsto_def]
   657 Goalw [leadsto_def] "|- []I & (P & I ~> Q) --> (P ~> Q)";
   624    "|- []I & (P & I ~> Q) --> (P ~> Q)"
   658 by (Clarsimp_tac 1);
   625    (fn _ => [Clarsimp_tac 1,
   659 by (etac STL4Edup 1); 
   626              etac STL4Edup 1, atac 1,
   660 by (atac 1);
   627 	     auto_tac (temp_css addsimps2 Init_simps addSDs2 [STL2_gen])
   661 by (auto_tac (temp_css addsimps2 Init_simps addSDs2 [STL2_gen]));
   628 	    ]);
   662 qed "INV_leadsto";
   629 
   663 
   630 qed_goalw "leadsto_classical" TLA.thy [leadsto_def,dmd_def]
   664 Goalw [leadsto_def,dmd_def]
   631    "|- (Init F & []~G ~> G) --> (F ~> G)"
   665   "|- (Init F & []~G ~> G) --> (F ~> G)";
   632    (fn _ => [force_tac (temp_css addsimps2 Init_simps addSEs2 [STL4E]) 1]);
   666 by (force_tac (temp_css addsimps2 Init_simps addSEs2 [STL4E]) 1);
   633 
   667 qed "leadsto_classical";
   634 qed_goalw "leadsto_false" TLA.thy [leadsto_def]
   668 
   635   "|- (F ~> #False) = ([]~F)"
   669 Goalw [leadsto_def] "|- (F ~> #False) = ([]~F)";
   636   (fn _ => [ simp_tac (simpset() addsimps [boxNotInitD]) 1 ]);
   670 by (simp_tac (simpset() addsimps [boxNotInitD]) 1);
   637 
   671 qed "leadsto_false";
   638 qed_goalw "leadsto_exists" TLA.thy [leadsto_def]
   672 
   639   "|- ((? x. F x) ~> G) = (!x. (F x ~> G))"
   673 Goalw [leadsto_def] "|- ((EX x. F x) ~> G) = (ALL x. (F x ~> G))";
   640   (K [auto_tac (temp_css addsimps2 allT::Init_simps addSEs2 [STL4E])]);
   674 by (auto_tac (temp_css addsimps2 allT::Init_simps addSEs2 [STL4E]));
   641 
   675 qed "leadsto_exists";
   642 
   676 
   643 (* basic leadsto properties, cf. Unity *)
   677 (* basic leadsto properties, cf. Unity *)
   644 
   678 
   645 qed_goalw "ImplLeadsto_gen" TLA.thy [leadsto_def]
   679 Goalw [leadsto_def] "|- [](Init F --> Init G) --> (F ~> G)";
   646    "|- [](Init F --> Init G) --> (F ~> G)"
   680 by (auto_tac (temp_css addSIs2 [InitDmd_gen] addSEs2 [STL4E_gen]
   647    (fn _ => [auto_tac (temp_css addSIs2 [InitDmd_gen] 
   681                        addsimps2 Init_simps));
   648                                 addSEs2 [STL4E_gen] addsimps2 Init_simps)
   682 qed "ImplLeadsto_gen";
   649 	    ]);
       
   650 
   683 
   651 bind_thm("ImplLeadsto",
   684 bind_thm("ImplLeadsto",
   652          rewrite_rule Init_simps 
   685          rewrite_rule Init_simps 
   653              (read_instantiate [("'a","behavior"), ("'b","behavior")] ImplLeadsto_gen));
   686              (read_instantiate [("'a","behavior"), ("'b","behavior")] ImplLeadsto_gen));
   654 
   687 
   655 qed_goal "ImplLeadsto_simple" TLA.thy
   688 Goal "!!F G. |- F --> G ==> |- F ~> G";
   656   "|- F --> G ==> |- F ~> G"
   689 by (auto_tac (temp_css addsimps2 [Init_def] 
   657   (fn [prem] => [auto_tac (temp_css addsimps2 [Init_def] 
   690                        addSIs2 [ImplLeadsto_gen,necT]));
   658                                     addSIs2 [ImplLeadsto_gen,necT,prem])]);
   691 qed "ImplLeadsto_simple";
   659 
   692 
   660 qed_goalw "EnsuresLeadsto" TLA.thy [leadsto_def]
   693 val [prem] = goalw thy [leadsto_def]
   661    "|- A & $P --> Q` ==> |- []A --> (P ~> Q)" (fn [prem] => [
   694   "|- A & $P --> Q` ==> |- []A --> (P ~> Q)";
   662 		  clarsimp_tac (temp_css addSEs2 [INV_leadsto]) 1, 
   695 by (clarsimp_tac (temp_css addSEs2 [INV_leadsto]) 1); 
   663                   etac STL4E_gen 1,
   696 by (etac STL4E_gen 1);
   664                   auto_tac (temp_css addsimps2 Init_defs
   697 by (auto_tac (temp_css addsimps2 Init_defs addSIs2 [PrimeDmd,prem]));
   665                                      addSIs2 [PrimeDmd, prem])
   698 qed "EnsuresLeadsto";
   666                  ]);
   699 
   667 
   700 Goalw  [leadsto_def] "|- []($P --> Q`) --> (P ~> Q)";
   668 qed_goalw "EnsuresLeadsto2" TLA.thy [leadsto_def]
   701 by (Clarsimp_tac 1);
   669    "|- []($P --> Q`) --> (P ~> Q)"
   702 by (etac STL4E_gen 1);
   670    (fn _ => [Clarsimp_tac 1,
   703 by (auto_tac (temp_css addsimps2 Init_simps addSIs2 [PrimeDmd]));
   671              etac STL4E_gen 1,
   704 qed "EnsuresLeadsto2";
   672              auto_tac (temp_css addsimps2 Init_simps addSIs2 [PrimeDmd])
   705 
   673             ]);
   706 val [p1,p2] = goalw thy [leadsto_def]
   674 
       
   675 qed_goalw "ensures" TLA.thy [leadsto_def]
       
   676   "[| |- $P & N --> P` | Q`; \
   707   "[| |- $P & N --> P` | Q`; \
   677 \     |- ($P & N) & A --> Q` \
   708 \     |- ($P & N) & A --> Q` \
   678 \  |] ==> |- []N & []([]P --> <>A) --> (P ~> Q)"
   709 \  |] ==> |- []N & []([]P --> <>A) --> (P ~> Q)";
   679   (fn [p1,p2] => [Clarsimp_tac 1,
   710 by (Clarsimp_tac 1);
   680                   etac STL4Edup 1, atac 1,
   711 by (etac STL4Edup 1); 
   681                   Clarsimp_tac 1,
   712 by (atac 1);
   682                   subgoal_tac "sigmaa |= []($P --> P` | Q`)" 1,
   713 by (Clarsimp_tac 1);
   683                    dtac (temp_use unless) 1,
   714 by (subgoal_tac "sigmaa |= []($P --> P` | Q`)" 1);
   684                    clarsimp_tac (temp_css addSDs2 [INV1]) 1,
   715  by (dtac (temp_use unless) 1);
   685                    rtac ((temp_use (p2 RS DmdImpl)) RS (temp_use DmdPrime)) 1,
   716  by (clarsimp_tac (temp_css addSDs2 [INV1]) 1);
   686                    force_tac (temp_css addSIs2 [BoxDmd_simple]
   717  by (rtac ((temp_use (p2 RS DmdImpl)) RS (temp_use DmdPrime)) 1);
   687                                        addsimps2 [split_box_conj,box_stp_act]) 1,
   718  by (force_tac (temp_css addSIs2 [BoxDmd_simple]
   688                   force_tac (temp_css addEs2 [STL4E] addDs2 [p1]) 1
   719                          addsimps2 [split_box_conj,box_stp_act]) 1);
   689                  ]);
   720 by (force_tac (temp_css addEs2 [STL4E] addDs2 [p1]) 1);
   690 
   721 qed "ensures";
   691 qed_goal "ensures_simple" TLA.thy
   722 
       
   723 val prems = goal thy
   692   "[| |- $P & N --> P` | Q`; \
   724   "[| |- $P & N --> P` | Q`; \
   693 \     |- ($P & N) & A --> Q` \
   725 \     |- ($P & N) & A --> Q` \
   694 \  |] ==> |- []N & []<>A --> (P ~> Q)"
   726 \  |] ==> |- []N & []<>A --> (P ~> Q)";
   695   (fn prems => [Clarsimp_tac 1,
   727 by (Clarsimp_tac 1);
   696                 rtac (temp_use ensures) 1,
   728 by (rtac (temp_use ensures) 1);
   697                 TRYALL (ares_tac prems),
   729 by (TRYALL (ares_tac prems));
   698                 force_tac (temp_css addSEs2 [STL4E]) 1
   730 by (force_tac (temp_css addSEs2 [STL4E]) 1);
   699                ]);
   731 qed "ensures_simple";
   700 
   732 
   701 qed_goal "EnsuresInfinite" TLA.thy
   733 val prems = goal thy
   702    "[| sigma |= []<>P; sigma |= []A; |- A & $P --> Q` |] ==> sigma |= []<>Q"
   734   "[| sigma |= []<>P; sigma |= []A; |- A & $P --> Q` |] ==> sigma |= []<>Q";
   703    (fn prems => [REPEAT (resolve_tac (prems @ [temp_use leadsto_infinite,
   735 by (REPEAT (resolve_tac (prems @ 
   704 					       temp_use EnsuresLeadsto]) 1)]);
   736                          (map temp_use [leadsto_infinite, EnsuresLeadsto])) 1));
       
   737 qed "EnsuresInfinite";
   705 
   738 
   706 
   739 
   707 (*** Gronning's lattice rules (taken from TLP) ***)
   740 (*** Gronning's lattice rules (taken from TLP) ***)
   708 section "Lattice rules";
   741 section "Lattice rules";
   709 
   742 
   710 qed_goalw "LatticeReflexivity" TLA.thy [leadsto_def] "|- F ~> F"
   743 Goalw [leadsto_def] "|- F ~> F";
   711    (fn _ => [REPEAT (resolve_tac [necT,InitDmd_gen] 1)]);
   744 by (REPEAT (resolve_tac [necT,InitDmd_gen] 1));
   712 
   745 qed "LatticeReflexivity";
   713 qed_goalw "LatticeTransitivity" TLA.thy [leadsto_def]
   746 
   714    "|- (G ~> H) & (F ~> G) --> (F ~> H)"
   747 Goalw [leadsto_def] "|- (G ~> H) & (F ~> G) --> (F ~> H)";
   715    (fn _ => [Clarsimp_tac 1,
   748 by (Clarsimp_tac 1);
   716              etac dup_boxE 1,  (* [][](Init G --> H) *)
   749 by (etac dup_boxE 1);  (* [][](Init G --> H) *)
   717 	     merge_box_tac 1,
   750 by (merge_box_tac 1);
   718 	     clarsimp_tac (temp_css addSEs2 [STL4E]) 1,
   751 by (clarsimp_tac (temp_css addSEs2 [STL4E]) 1);
   719              rtac dup_dmdD 1,
   752 by (rtac dup_dmdD 1);
   720              subgoal_tac "sigmaa |= <>Init G" 1,
   753 by (subgoal_tac "sigmaa |= <>Init G" 1);
   721              etac DmdImpl2 1, atac 1,
   754  by (etac DmdImpl2 1); 
   722              asm_simp_tac (simpset() addsimps [dmdInitD]) 1
   755  by (atac 1);
   723 	    ]);
   756 by (asm_simp_tac (simpset() addsimps [dmdInitD]) 1);
   724 
   757 qed "LatticeTransitivity";
   725 qed_goalw "LatticeDisjunctionElim1" TLA.thy [leadsto_def]
   758 
   726    "|- (F | G ~> H) --> (F ~> H)"
   759 Goalw [leadsto_def] "|- (F | G ~> H) --> (F ~> H)";
   727    (fn _ => [ auto_tac (temp_css addsimps2 Init_simps addSEs2 [STL4E]) ]);
   760 by (auto_tac (temp_css addsimps2 Init_simps addSEs2 [STL4E]));
   728 
   761 qed "LatticeDisjunctionElim1";
   729 qed_goalw "LatticeDisjunctionElim2" TLA.thy [leadsto_def]
   762 
   730    "|- (F | G ~> H) --> (G ~> H)"
   763 Goalw [leadsto_def] "|- (F | G ~> H) --> (G ~> H)";
   731    (fn _ => [ auto_tac (temp_css addsimps2 Init_simps addSEs2 [STL4E]) ]);
   764 by (auto_tac (temp_css addsimps2 Init_simps addSEs2 [STL4E]));
   732 
   765 qed "LatticeDisjunctionElim2";
   733 qed_goalw "LatticeDisjunctionIntro" TLA.thy [leadsto_def]
   766 
   734    "|- (F ~> H) & (G ~> H) --> (F | G ~> H)"
   767 Goalw [leadsto_def] "|- (F ~> H) & (G ~> H) --> (F | G ~> H)";
   735    (fn _ => [Clarsimp_tac 1,
   768 by (Clarsimp_tac 1);
   736              merge_box_tac 1,
   769 by (merge_box_tac 1);
   737 	     auto_tac (temp_css addsimps2 Init_simps addSEs2 [STL4E])
   770 by (auto_tac (temp_css addsimps2 Init_simps addSEs2 [STL4E]));
   738 	    ]);
   771 qed "LatticeDisjunctionIntro";
   739 
   772 
   740 qed_goal "LatticeDisjunction" TLA.thy
   773 Goal "|- (F | G ~> H) = ((F ~> H) & (G ~> H))";
   741    "|- (F | G ~> H) = ((F ~> H) & (G ~> H))"
   774 by (auto_tac (temp_css addIs2 [LatticeDisjunctionIntro,
   742    (fn _ => [auto_tac (temp_css addIs2 [LatticeDisjunctionIntro,
   775                                LatticeDisjunctionElim1, LatticeDisjunctionElim2]));
   743                                 LatticeDisjunctionElim1, LatticeDisjunctionElim2])]);
   776 qed "LatticeDisjunction";
   744 
   777 
   745 qed_goal "LatticeDiamond" TLA.thy
   778 Goal "|- (A ~> B | C) & (B ~> D) & (C ~> D) --> (A ~> D)";
   746    "|- (A ~> B | C) & (B ~> D) & (C ~> D) --> (A ~> D)"
   779 by (Clarsimp_tac 1);
   747    (fn _ => [Clarsimp_tac 1,
   780 by (subgoal_tac "sigma |= (B | C) ~> D" 1);
   748              subgoal_tac "sigma |= (B | C) ~> D" 1,
   781 by (eres_inst_tac [("G", "LIFT (B | C)")] (temp_use LatticeTransitivity) 1);
   749 	     eres_inst_tac [("G", "LIFT (B | C)")] (temp_use LatticeTransitivity) 1,
   782 by (ALLGOALS (fast_tac (temp_cs addSIs [LatticeDisjunctionIntro])));
   750 	     ALLGOALS (fast_tac (temp_cs addSIs [LatticeDisjunctionIntro]))
   783 qed "LatticeDiamond";
   751 	    ]);
   784 
   752 
   785 Goal "|- (A ~> D | B) & (B ~> D) --> (A ~> D)";
   753 qed_goal "LatticeTriangle" TLA.thy
   786 by (Clarsimp_tac 1);
   754    "|- (A ~> D | B) & (B ~> D) --> (A ~> D)"
   787 by (subgoal_tac "sigma |= (D | B) ~> D" 1);
   755    (fn _ => [Clarsimp_tac 1,
   788 by (eres_inst_tac [("G", "LIFT (D | B)")] (temp_use LatticeTransitivity) 1); 
   756              subgoal_tac "sigma |= (D | B) ~> D" 1,
   789 by (atac 1);
   757 	     eres_inst_tac [("G", "LIFT (D | B)")] (temp_use LatticeTransitivity) 1, atac 1,
   790 by (auto_tac (temp_css addIs2 [LatticeDisjunctionIntro,LatticeReflexivity]));
   758 	     auto_tac (temp_css addSIs2 [LatticeDisjunctionIntro] 
   791 qed "LatticeTriangle";
   759                                 addIs2 [LatticeReflexivity])
   792 
   760 	    ]);
   793 Goal "|- (A ~> B | D) & (B ~> D) --> (A ~> D)";
   761 
   794 by (Clarsimp_tac 1);
   762 qed_goal "LatticeTriangle2" TLA.thy
   795 by (subgoal_tac "sigma |= B | D ~> D" 1);
   763    "|- (A ~> B | D) & (B ~> D) --> (A ~> D)"
   796 by (eres_inst_tac [("G", "LIFT (B | D)")] (temp_use LatticeTransitivity) 1); 
   764    (fn _ => [Clarsimp_tac 1,
   797 by (atac 1);
   765              subgoal_tac "sigma |= B | D ~> D" 1,
   798 by (auto_tac (temp_css addIs2 [LatticeDisjunctionIntro,LatticeReflexivity]));
   766 	     eres_inst_tac [("G", "LIFT (B | D)")] (temp_use LatticeTransitivity) 1, atac 1,
   799 qed "LatticeTriangle2";
   767 	     auto_tac (temp_css addSIs2 [LatticeDisjunctionIntro] 
       
   768                                 addIs2 [LatticeReflexivity])
       
   769 	    ]);
       
   770 
   800 
   771 (*** Lamport's fairness rules ***)
   801 (*** Lamport's fairness rules ***)
   772 section "Fairness rules";
   802 section "Fairness rules";
   773 
   803 
   774 qed_goal "WF1" TLA.thy
   804 val prems = goal thy
   775    "[| |- $P & N  --> P` | Q`;   \
   805   "[| |- $P & N  --> P` | Q`;   \
   776 \      |- ($P & N) & <A>_v --> Q`;   \
   806 \     |- ($P & N) & <A>_v --> Q`;   \
   777 \      |- $P & N --> $(Enabled(<A>_v)) |]   \
   807 \     |- $P & N --> $(Enabled(<A>_v)) |]   \
   778 \  ==> |- []N & WF(A)_v --> (P ~> Q)"  (fn prems => [
   808 \ ==> |- []N & WF(A)_v --> (P ~> Q)";
   779              clarsimp_tac (temp_css addSDs2 [BoxWFI]) 1,
   809 by (clarsimp_tac (temp_css addSDs2 [BoxWFI]) 1);
   780              rtac (temp_use ensures) 1,
   810 by (rtac (temp_use ensures) 1);
   781              TRYALL (ares_tac prems),
   811 by (TRYALL (ares_tac prems));
   782              etac STL4Edup 1, atac 1,
   812 by (etac STL4Edup 1); 
   783              clarsimp_tac (temp_css addsimps2 [WF_def]) 1,
   813 by (atac 1);
   784              rtac (temp_use STL2) 1,
   814 by (clarsimp_tac (temp_css addsimps2 [WF_def]) 1);
   785              clarsimp_tac (temp_css addSEs2 [mp] addSIs2 [InitDmd]) 1,
   815 by (rtac (temp_use STL2) 1);
   786              resolve_tac ((map temp_use (prems RL [STL4])) RL [box_stp_actD]) 1,
   816 by (clarsimp_tac (temp_css addSEs2 [mp] addSIs2 [InitDmd]) 1);
   787              asm_simp_tac (simpset() addsimps [split_box_conj,box_stp_actI]) 1
   817 by (resolve_tac ((map temp_use (prems RL [STL4])) RL [box_stp_actD]) 1);
   788             ]);
   818 by (asm_simp_tac (simpset() addsimps [split_box_conj,box_stp_actI]) 1);
       
   819 qed "WF1";
   789 
   820 
   790 (* Sometimes easier to use; designed for action B rather than state predicate Q *)
   821 (* Sometimes easier to use; designed for action B rather than state predicate Q *)
   791 qed_goalw "WF_leadsto" TLA.thy [leadsto_def]
   822 val [prem1,prem2,prem3] = goalw thy [leadsto_def]
   792    "[| |- N & $P --> $Enabled (<A>_v);            \
   823   "[| |- N & $P --> $Enabled (<A>_v);            \
   793 \      |- N & <A>_v --> B;                  \ 
   824 \     |- N & <A>_v --> B;                  \ 
   794 \      |- [](N & [~A]_v) --> stable P  |]  \
   825 \     |- [](N & [~A]_v) --> stable P  |]  \
   795 \   ==> |- []N & WF(A)_v --> (P ~> B)"
   826 \  ==> |- []N & WF(A)_v --> (P ~> B)";
   796    (fn [prem1,prem2,prem3]
   827 by (clarsimp_tac (temp_css addSDs2 [BoxWFI]) 1);
   797        => [clarsimp_tac (temp_css addSDs2 [BoxWFI]) 1,
   828 by (etac STL4Edup 1); 
   798            etac STL4Edup 1, atac 1,
   829 by (atac 1);
   799            Clarsimp_tac 1,
   830 by (Clarsimp_tac 1);
   800            rtac (temp_use (prem2 RS DmdImpl)) 1,
   831 by (rtac (temp_use (prem2 RS DmdImpl)) 1);
   801            rtac (temp_use BoxDmd_simple) 1, atac 1,
   832 by (rtac (temp_use BoxDmd_simple) 1); 
   802            rtac classical 1,
   833 by (atac 1);
   803            rtac (temp_use STL2) 1,
   834 by (rtac classical 1);
   804            clarsimp_tac (temp_css addsimps2 [WF_def] addSEs2 [mp] addSIs2 [InitDmd]) 1,
   835 by (rtac (temp_use STL2) 1);
   805            rtac ((temp_use (prem1 RS STL4)) RS box_stp_actD) 1,
   836 by (clarsimp_tac (temp_css addsimps2 [WF_def] addSEs2 [mp] addSIs2 [InitDmd]) 1);
   806            asm_simp_tac (simpset() addsimps [split_box_conj,box_stp_act]) 1,
   837 by (rtac ((temp_use (prem1 RS STL4)) RS box_stp_actD) 1);
   807            etac (temp_use INV1) 1,
   838 by (asm_simp_tac (simpset() addsimps [split_box_conj,box_stp_act]) 1);
   808            rtac (temp_use prem3) 1,
   839 by (etac (temp_use INV1) 1);
   809            asm_full_simp_tac (simpset() addsimps [split_box_conj,temp_use NotDmd,not_angle]) 1
   840 by (rtac (temp_use prem3) 1);
   810           ]);
   841 by (asm_full_simp_tac (simpset() addsimps [split_box_conj,temp_use NotDmd,not_angle]) 1);
   811 
   842 qed "WF_leadsto";
   812 qed_goal "SF1" TLA.thy
   843 
   813    "[| |- $P & N  --> P` | Q`;   \
   844 val prems = goal thy
   814 \      |- ($P & N) & <A>_v --> Q`;   \
   845   "[| |- $P & N  --> P` | Q`;   \
   815 \      |- []P & []N & []F --> <>Enabled(<A>_v) |]   \
   846 \     |- ($P & N) & <A>_v --> Q`;   \
   816 \  ==> |- []N & SF(A)_v & []F --> (P ~> Q)"
   847 \     |- []P & []N & []F --> <>Enabled(<A>_v) |]   \
   817    (fn prems => [
   848 \ ==> |- []N & SF(A)_v & []F --> (P ~> Q)";
   818              clarsimp_tac (temp_css addSDs2 [BoxSFI]) 1,
   849 by (clarsimp_tac (temp_css addSDs2 [BoxSFI]) 1);
   819              rtac (temp_use ensures) 1,
   850 by (rtac (temp_use ensures) 1);
   820              TRYALL (ares_tac prems),
   851 by (TRYALL (ares_tac prems));
   821              eres_inst_tac [("F","F")] dup_boxE 1,
   852 by (eres_inst_tac [("F","F")] dup_boxE 1);
   822              merge_temp_box_tac 1,
   853 by (merge_temp_box_tac 1);
   823              etac STL4Edup 1, atac 1,
   854 by (etac STL4Edup 1); 
   824              clarsimp_tac (temp_css addsimps2 [SF_def]) 1,
   855 by (atac 1);
   825              rtac (temp_use STL2) 1, etac mp 1,
   856 by (clarsimp_tac (temp_css addsimps2 [SF_def]) 1);
   826              resolve_tac (map temp_use (prems RL [STL4])) 1,
   857 by (rtac (temp_use STL2) 1); 
   827              asm_simp_tac (simpset() addsimps [split_box_conj, STL3]) 1
   858 by (etac mp 1);
   828             ]);
   859 by (resolve_tac (map temp_use (prems RL [STL4])) 1);
   829 
   860 by (asm_simp_tac (simpset() addsimps [split_box_conj, STL3]) 1);
   830 qed_goal "WF2" TLA.thy
   861 qed "SF1";
   831    "[| |- N & <B>_f --> <M>_g;   \
   862 
   832 \      |- $P & P` & <N & A>_f --> B;   \
   863 val [prem1,prem2,prem3,prem4] = goal thy
   833 \      |- P & Enabled(<M>_g) --> Enabled(<A>_f);   \
   864   "[| |- N & <B>_f --> <M>_g;   \
   834 \      |- [](N & [~B]_f) & WF(A)_f & []F & <>[]Enabled(<M>_g) --> <>[]P |]   \
   865 \     |- $P & P` & <N & A>_f --> B;   \
   835 \  ==> |- []N & WF(A)_f & []F --> WF(M)_g"
   866 \     |- P & Enabled(<M>_g) --> Enabled(<A>_f);   \
   836 (fn [prem1,prem2,prem3,prem4] => [
   867 \     |- [](N & [~B]_f) & WF(A)_f & []F & <>[]Enabled(<M>_g) --> <>[]P |]   \
   837 	   clarsimp_tac (temp_css addSDs2 [BoxWFI, (temp_use BoxDmdBox) RS iffD2] 
   868 \ ==> |- []N & WF(A)_f & []F --> WF(M)_g";
   838                             addsimps2 [read_instantiate [("A","M")] WF_def]) 1,
   869 by (clarsimp_tac (temp_css addSDs2 [BoxWFI, (temp_use BoxDmdBox) RS iffD2] 
   839            eres_inst_tac [("F","F")] dup_boxE 1,
   870                            addsimps2 [read_instantiate [("A","M")] WF_def]) 1);
   840            merge_temp_box_tac 1,
   871 by (eres_inst_tac [("F","F")] dup_boxE 1);
   841            etac STL4Edup 1, atac 1,
   872 by (merge_temp_box_tac 1);
   842            clarsimp_tac (temp_css addSIs2 [(temp_use BoxDmd_simple) RS (temp_use (prem1 RS DmdImpl))]) 1,
   873 by (etac STL4Edup 1); 
   843            rtac classical 1,
   874 by (atac 1);
   844            subgoal_tac "sigmaa |= <>(($P & P` & N) & <A>_f)" 1,
   875 by (clarsimp_tac (temp_css addSIs2
   845            force_tac (temp_css addsimps2 [angle_def] addSIs2 [prem2] addSEs2 [DmdImplE]) 1,
   876          [(temp_use BoxDmd_simple) RS (temp_use (prem1 RS DmdImpl))]) 1);
   846            rtac (temp_use (rewrite_rule [temp_rewrite DmdDmd] (BoxDmd_simple RS DmdImpl))) 1,
   877 by (rtac classical 1);
   847            asm_full_simp_tac (simpset() addsimps [temp_use NotDmd, not_angle]) 1,
   878 by (subgoal_tac "sigmaa |= <>(($P & P` & N) & <A>_f)" 1);
   848            merge_act_box_tac 1,
   879  by (force_tac (temp_css addsimps2 [angle_def] addSIs2 [prem2] addSEs2 [DmdImplE]) 1);
   849            forward_tac [temp_use prem4] 1, TRYALL atac,
   880 by (rtac (temp_use (rewrite_rule [temp_rewrite DmdDmd] (BoxDmd_simple RS DmdImpl))) 1);
   850            dtac (temp_use STL6) 1, atac 1, 
   881 by (asm_full_simp_tac (simpset() addsimps [temp_use NotDmd, not_angle]) 1);
   851            eres_inst_tac [("V","sigmaa |= <>[]P")] thin_rl 1,
   882 by (merge_act_box_tac 1);
   852            eres_inst_tac [("V","sigmaa |= []F")] thin_rl 1,
   883 by (forward_tac [temp_use prem4] 1); 
   853            dtac (temp_use BoxWFI) 1,
   884 by (TRYALL atac);
   854            eres_inst_tac [("F", "ACT N & [~B]_f")] dup_boxE 1,
   885 by (dtac (temp_use STL6) 1); 
   855            merge_temp_box_tac 1,
   886 by (atac 1);
   856            etac DmdImpldup 1, atac 1,
   887 by (eres_inst_tac [("V","sigmaa |= <>[]P")] thin_rl 1);
   857            auto_tac (temp_css addsimps2 [split_box_conj,STL3,WF_Box,box_stp_act]),
   888 by (eres_inst_tac [("V","sigmaa |= []F")] thin_rl 1);
   858            force_tac (temp_css addSEs2 [read_instantiate [("P","P")] TLA2E]) 1,
   889 by (dtac (temp_use BoxWFI) 1);
   859            rtac (temp_use STL2) 1,
   890 by (eres_inst_tac [("F", "ACT N & [~B]_f")] dup_boxE 1);
   860            force_tac (temp_css addsimps2 [WF_def,split_box_conj] addSEs2 [mp] 
   891 by (merge_temp_box_tac 1);
   861                                addSIs2 [InitDmd, prem3 RS STL4]) 1
   892 by (etac DmdImpldup 1); 
   862 	  ]);
   893 by (atac 1);
   863 
   894 by (auto_tac (temp_css addsimps2 [split_box_conj,STL3,WF_Box,box_stp_act]));
   864 qed_goal "SF2" TLA.thy
   895  by (force_tac (temp_css addSEs2 [read_instantiate [("P","P")] TLA2E]) 1);
   865    "[| |- N & <B>_f --> <M>_g;   \
   896 by (rtac (temp_use STL2) 1);
   866 \      |- $P & P` & <N & A>_f --> B;   \
   897 by (force_tac (temp_css addsimps2 [WF_def,split_box_conj] addSEs2 [mp] 
   867 \      |- P & Enabled(<M>_g) --> Enabled(<A>_f);   \
   898                         addSIs2 [InitDmd, prem3 RS STL4]) 1);
   868 \      |- [](N & [~B]_f) & SF(A)_f & []F & []<>Enabled(<M>_g) --> <>[]P |]   \
   899 qed "WF2";
   869 \  ==> |- []N & SF(A)_f & []F --> SF(M)_g"
   900 
   870 (fn [prem1,prem2,prem3,prem4] => [
   901 val [prem1,prem2,prem3,prem4] = goal thy
   871 	   clarsimp_tac (temp_css addSDs2 [BoxSFI] 
   902   "[| |- N & <B>_f --> <M>_g;   \
   872                             addsimps2 [read_instantiate [("A","M")] SF_def]) 1,
   903 \     |- $P & P` & <N & A>_f --> B;   \
   873            eres_inst_tac [("F","F")] dup_boxE 1,
   904 \     |- P & Enabled(<M>_g) --> Enabled(<A>_f);   \
   874            eres_inst_tac [("F","TEMP <>Enabled(<M>_g)")] dup_boxE 1,
   905 \     |- [](N & [~B]_f) & SF(A)_f & []F & []<>Enabled(<M>_g) --> <>[]P |]   \
   875            merge_temp_box_tac 1,
   906 \ ==> |- []N & SF(A)_f & []F --> SF(M)_g";
   876            etac STL4Edup 1, atac 1,
   907 by (clarsimp_tac (temp_css addSDs2 [BoxSFI] 
   877            clarsimp_tac (temp_css addSIs2 [(temp_use BoxDmd_simple) RS (temp_use (prem1 RS DmdImpl))]) 1,
   908                            addsimps2 [read_instantiate [("A","M")] SF_def]) 1);
   878            rtac classical 1,
   909 by (eres_inst_tac [("F","F")] dup_boxE 1);
   879            subgoal_tac "sigmaa |= <>(($P & P` & N) & <A>_f)" 1,
   910 by (eres_inst_tac [("F","TEMP <>Enabled(<M>_g)")] dup_boxE 1);
   880            force_tac (temp_css addsimps2 [angle_def] addSIs2 [prem2] addSEs2 [DmdImplE]) 1,
   911 by (merge_temp_box_tac 1);
   881            rtac (temp_use (rewrite_rule [temp_rewrite DmdDmd] (BoxDmd_simple RS DmdImpl))) 1,
   912 by (etac STL4Edup 1); 
   882            asm_full_simp_tac (simpset() addsimps [temp_use NotDmd, not_angle]) 1,
   913 by (atac 1);
   883            merge_act_box_tac 1,
   914 by (clarsimp_tac (temp_css addSIs2
   884            forward_tac [temp_use prem4] 1, TRYALL atac,
   915         [(temp_use BoxDmd_simple) RS (temp_use (prem1 RS DmdImpl))]) 1);
   885            eres_inst_tac [("V","sigmaa |= []F")] thin_rl 1,
   916 by (rtac classical 1);
   886            dtac (temp_use BoxSFI) 1,
   917 by (subgoal_tac "sigmaa |= <>(($P & P` & N) & <A>_f)" 1);
   887            eres_inst_tac [("F","TEMP <>Enabled(<M>_g)")] dup_boxE 1,
   918  by (force_tac (temp_css addsimps2 [angle_def] addSIs2 [prem2] addSEs2 [DmdImplE]) 1);
   888            eres_inst_tac [("F", "ACT N & [~B]_f")] dup_boxE 1,
   919 by (rtac (temp_use (rewrite_rule [temp_rewrite DmdDmd] (BoxDmd_simple RS DmdImpl))) 1);
   889            merge_temp_box_tac 1,
   920 by (asm_full_simp_tac (simpset() addsimps [temp_use NotDmd, not_angle]) 1);
   890            etac DmdImpldup 1, atac 1,
   921 by (merge_act_box_tac 1);
   891            auto_tac (temp_css addsimps2 [split_box_conj,STL3,SF_Box,box_stp_act]),
   922 by (forward_tac [temp_use prem4] 1); 
   892            force_tac (temp_css addSEs2 [read_instantiate [("P","P")] TLA2E]) 1,
   923 by (TRYALL atac);
   893            rtac (temp_use STL2) 1,
   924 by (eres_inst_tac [("V","sigmaa |= []F")] thin_rl 1);
   894            force_tac (temp_css addsimps2 [SF_def,split_box_conj] addSEs2 [mp,InfImpl] 
   925 by (dtac (temp_use BoxSFI) 1);
   895                                addSIs2 [prem3]) 1
   926 by (eres_inst_tac [("F","TEMP <>Enabled(<M>_g)")] dup_boxE 1);
   896 	  ]);
   927 by (eres_inst_tac [("F", "ACT N & [~B]_f")] dup_boxE 1);
       
   928 by (merge_temp_box_tac 1);
       
   929 by (etac DmdImpldup 1); 
       
   930 by (atac 1);
       
   931 by (auto_tac (temp_css addsimps2 [split_box_conj,STL3,SF_Box,box_stp_act]));
       
   932  by (force_tac (temp_css addSEs2 [read_instantiate [("P","P")] TLA2E]) 1);
       
   933 by (rtac (temp_use STL2) 1);
       
   934 by (force_tac (temp_css addsimps2 [SF_def,split_box_conj] addSEs2 [mp,InfImpl] 
       
   935                         addSIs2 [prem3]) 1);
       
   936 qed "SF2";
   897 
   937 
   898 (* ------------------------------------------------------------------------- *)
   938 (* ------------------------------------------------------------------------- *)
   899 (***           Liveness proofs by well-founded orderings                   ***)
   939 (***           Liveness proofs by well-founded orderings                   ***)
   900 (* ------------------------------------------------------------------------- *)
   940 (* ------------------------------------------------------------------------- *)
   901 section "Well-founded orderings";
   941 section "Well-founded orderings";
   902 
   942 
   903 qed_goal "wf_leadsto" TLA.thy
   943 val p1::prems = goal thy
   904   "[| wf r;  \
   944   "[| wf r;  \
   905 \     !!x. sigma |= F x ~> (G | (? y. #((y,x):r) & F y))   \
   945 \     !!x. sigma |= F x ~> (G | (EX y. #((y,x):r) & F y))   \
   906 \  |] ==> sigma |= F x ~> G"
   946 \  |] ==> sigma |= F x ~> G";
   907   (fn p1::prems =>
   947 by (rtac (p1 RS wf_induct) 1);
   908      [rtac (p1 RS wf_induct) 1,
   948 by (rtac (temp_use LatticeTriangle) 1);
   909       rtac (temp_use LatticeTriangle) 1,
   949 by (resolve_tac prems 1);
   910       resolve_tac prems 1,
   950 by (auto_tac (temp_css addsimps2 [leadsto_exists]));
   911       auto_tac (temp_css addsimps2 [leadsto_exists]),
   951 by (case_tac "(y,x):r" 1);
   912       case_tac "(y,x):r" 1,
   952  by (Force_tac 1);
   913        Force_tac 1,
   953 by (force_tac (temp_css addsimps2 leadsto_def::Init_simps addSIs2 [necT]) 1);
   914       force_tac (temp_css addsimps2 leadsto_def::Init_simps addSIs2 [necT]) 1]);
   954 qed "wf_leadsto";
   915 
   955 
   916 (* If r is well-founded, state function v cannot decrease forever *)
   956 (* If r is well-founded, state function v cannot decrease forever *)
   917 qed_goal "wf_not_box_decrease" TLA.thy
   957 Goal "!!r. wf r ==> |- [][ (v`, $v) : #r ]_v --> <>[][#False]_v";
   918   "!!r. wf r ==> |- [][ (v`, $v) : #r ]_v --> <>[][#False]_v"
   958 by (Clarsimp_tac 1);
   919   (fn _ => [Clarsimp_tac 1,
   959 by (rtac ccontr 1);
   920             rtac ccontr 1,
   960 by (subgoal_tac "sigma |= (EX x. v=#x) ~> #False" 1);
   921             subgoal_tac "sigma |= (? x. v=#x) ~> #False" 1,
   961  by (dtac ((temp_use leadsto_false) RS iffD1 RS (temp_use STL2_gen)) 1);
   922              dtac ((temp_use leadsto_false) RS iffD1 RS (temp_use STL2_gen)) 1,
   962  by (force_tac (temp_css addsimps2 Init_defs) 1);
   923              force_tac (temp_css addsimps2 Init_defs) 1,
   963 by (clarsimp_tac (temp_css addsimps2 [leadsto_exists,not_square]@more_temp_simps) 1);
   924             clarsimp_tac (temp_css addsimps2 [leadsto_exists,not_square]@more_temp_simps) 1,
   964 by (etac wf_leadsto 1);
   925             etac wf_leadsto 1,
   965 by (rtac (temp_use ensures_simple) 1); 
   926             rtac (temp_use ensures_simple) 1, TRYALL atac,
   966 by (TRYALL atac);
   927             auto_tac (temp_css addsimps2 [square_def,angle_def])
   967 by (auto_tac (temp_css addsimps2 [square_def,angle_def]));
   928            ]);
   968 qed "wf_not_box_decrease";
   929 
   969 
   930 (* "wf r  ==>  |- <>[][ (v`, $v) : #r ]_v --> <>[][#False]_v" *)
   970 (* "wf r  ==>  |- <>[][ (v`, $v) : #r ]_v --> <>[][#False]_v" *)
   931 bind_thm("wf_not_dmd_box_decrease",
   971 bind_thm("wf_not_dmd_box_decrease",
   932          standard(rewrite_rule more_temp_simps (wf_not_box_decrease RS DmdImpl)));
   972          standard(rewrite_rule more_temp_simps (wf_not_box_decrease RS DmdImpl)));
   933 
   973 
   934 (* If there are infinitely many steps where v decreases, then there
   974 (* If there are infinitely many steps where v decreases, then there
   935    have to be infinitely many non-stuttering steps where v doesn't decrease.
   975    have to be infinitely many non-stuttering steps where v doesn't decrease.
   936 *)
   976 *)
   937 qed_goal "wf_box_dmd_decrease" TLA.thy
   977 val [prem] = goal thy
   938   "wf r ==> |- []<>((v`, $v) : #r) --> []<><(v`, $v) ~: #r>_v"
   978   "wf r ==> |- []<>((v`, $v) : #r) --> []<><(v`, $v) ~: #r>_v";
   939   (fn [prem] => [
   979 by (Clarsimp_tac 1);
   940             Clarsimp_tac 1,
   980 by (rtac ccontr 1);
   941             rtac ccontr 1,
   981 by (asm_full_simp_tac (simpset() addsimps not_angle::more_temp_simps) 1);
   942             asm_full_simp_tac (simpset() addsimps not_angle::more_temp_simps) 1,
   982 by (dtac (prem RS (temp_use wf_not_dmd_box_decrease)) 1);
   943             dtac (prem RS (temp_use wf_not_dmd_box_decrease)) 1,
   983 by (dtac (temp_use BoxDmdDmdBox) 1); 
   944             dtac (temp_use BoxDmdDmdBox) 1, atac 1,
   984 by (atac 1);
   945             subgoal_tac "sigma |= []<>((#False)::action)" 1,
   985 by (subgoal_tac "sigma |= []<>((#False)::action)" 1);
   946             Force_tac 1,
   986  by (Force_tac 1);
   947             etac STL4E 1,
   987 by (etac STL4E 1);
   948             rtac DmdImpl 1,
   988 by (rtac DmdImpl 1);
   949             force_tac (temp_css addIs2 [prem RS wf_irrefl]) 1
   989 by (force_tac (temp_css addIs2 [prem RS wf_irrefl]) 1);
   950            ]);
   990 qed "wf_box_dmd_decrease";
   951 
   991 
   952 (* In particular, for natural numbers, if n decreases infinitely often
   992 (* In particular, for natural numbers, if n decreases infinitely often
   953    then it has to increase infinitely often.
   993    then it has to increase infinitely often.
   954 *)
   994 *)
   955 qed_goal "nat_box_dmd_decrease" TLA.thy
   995 Goal "!!n::nat stfun. |- []<>(n` < $n) --> []<>($n < n`)";
   956   "!!n::nat stfun. |- []<>(n` < $n) --> []<>($n < n`)"
   996 by (Clarsimp_tac 1);
   957   (K [Clarsimp_tac 1,
   997 by (subgoal_tac "sigma |= []<><~( (n`,$n) : #less_than )>_n" 1);
   958       subgoal_tac "sigma |= []<><~( (n`,$n) : #less_than )>_n" 1,
   998  by (etac thin_rl 1); 
   959       etac thin_rl 1, etac STL4E 1, rtac DmdImpl 1,
   999  by (etac STL4E 1); 
   960       clarsimp_tac (temp_css addsimps2 [angle_def]) 1,
  1000  by (rtac DmdImpl 1);
   961       rtac nat_less_cases 1,
  1001  by (clarsimp_tac (temp_css addsimps2 [angle_def]) 1);
   962       Auto_tac,
  1002  by (rtac nat_less_cases 1);
   963       rtac (temp_use wf_box_dmd_decrease) 1,
  1003  by Auto_tac;
   964       auto_tac (temp_css addSEs2 [STL4E,DmdImplE])
  1004 by (rtac (temp_use wf_box_dmd_decrease) 1);
   965      ]);
  1005 by (auto_tac (temp_css addSEs2 [STL4E,DmdImplE]));
       
  1006 qed "nat_box_dmd_decrease";
   966 
  1007 
   967 
  1008 
   968 (* ------------------------------------------------------------------------- *)
  1009 (* ------------------------------------------------------------------------- *)
   969 (***           Flexible quantification over state variables                ***)
  1010 (***           Flexible quantification over state variables                ***)
   970 (* ------------------------------------------------------------------------- *)
  1011 (* ------------------------------------------------------------------------- *)
   971 section "Flexible quantification";
  1012 section "Flexible quantification";
   972 
  1013 
   973 qed_goal "aallI" TLA.thy 
  1014 val [prem1,prem2] = goal thy
   974   "[| basevars vs; (!!x. basevars (x,vs) ==> sigma |= F x) |] ==> sigma |= (AALL x. F x)"
  1015   "[| basevars vs; (!!x. basevars (x,vs) ==> sigma |= F x) |]\
   975   (fn [prem1,prem2] => [auto_tac (temp_css addsimps2 [aall_def] addSEs2 [eexE] 
  1016 \  ==> sigma |= (AALL x. F x)";
   976                                    addSIs2 [prem1] addSDs2 [prem2])]);
  1017 by (auto_tac (temp_css addsimps2 [aall_def] addSEs2 [eexE] 
   977 
  1018                        addSIs2 [prem1] addSDs2 [prem2]));
   978 qed_goalw "aallE" TLA.thy [aall_def] "|- (AALL x. F x) --> F x"
  1019 qed "aallI";
   979    (K [Clarsimp_tac 1, etac swap 1,
  1020 
   980        force_tac (temp_css addSIs2 [eexI]) 1]);
  1021 Goalw [aall_def] "|- (AALL x. F x) --> F x";
       
  1022 by (Clarsimp_tac 1);
       
  1023 by (etac swap 1);
       
  1024 by (force_tac (temp_css addSIs2 [eexI]) 1);
       
  1025 qed "aallE";
   981 
  1026 
   982 (* monotonicity of quantification *)
  1027 (* monotonicity of quantification *)
   983 qed_goal "eex_mono" TLA.thy
  1028 val [min,maj] = goal thy
   984   "[| sigma |= EEX x. F x; !!x. sigma |= F x --> G x |] ==> sigma |= EEX x. G x"
  1029   "[| sigma |= EEX x. F x; !!x. sigma |= F x --> G x |] ==> sigma |= EEX x. G x";
   985   (fn [min,maj] => [rtac (unit_base RS (min RS eexE)) 1,
  1030 by (rtac (unit_base RS (min RS eexE)) 1);
   986                     rtac (temp_use eexI) 1,
  1031 by (rtac (temp_use eexI) 1);
   987                     etac ((rewrite_rule intensional_rews maj) RS mp) 1
  1032 by (etac ((rewrite_rule intensional_rews maj) RS mp) 1);
   988                    ]);
  1033 qed "eex_mono";
   989 
  1034 
   990 qed_goal "aall_mono" TLA.thy
  1035 val [min,maj] = goal thy
   991   "[| sigma |= AALL x. F(x); !!x. sigma |= F(x) --> G(x) |] ==> sigma |= AALL x. G(x)"
  1036   "[| sigma |= AALL x. F(x); !!x. sigma |= F(x) --> G(x) |] ==> sigma |= AALL x. G(x)";
   992   (fn [min,maj] => [rtac (unit_base RS aallI) 1,
  1037 by (rtac (unit_base RS aallI) 1);
   993                     rtac ((rewrite_rule intensional_rews maj) RS mp) 1,
  1038 by (rtac ((rewrite_rule intensional_rews maj) RS mp) 1);
   994                     rtac (min RS (temp_use aallE)) 1
  1039 by (rtac (min RS (temp_use aallE)) 1);
   995                    ]);
  1040 qed "aall_mono";
   996 
  1041 
   997 (* Derived history introduction rule *)
  1042 (* Derived history introduction rule *)
   998 qed_goal "historyI" TLA.thy
  1043 val [p1,p2,p3,p4,p5] = goal thy
   999   "[| sigma |= Init I; sigma |= []N; basevars vs; \
  1044   "[| sigma |= Init I; sigma |= []N; basevars vs; \
  1000 \     (!!h. basevars(h,vs) ==> |- I & h = ha --> HI h); \
  1045 \     (!!h. basevars(h,vs) ==> |- I & h = ha --> HI h); \
  1001 \     (!!h s t. [| basevars(h,vs); N (s,t); h t = hb (h s) (s,t) |] ==> HN h (s,t)) \
  1046 \     (!!h s t. [| basevars(h,vs); N (s,t); h t = hb (h s) (s,t) |] ==> HN h (s,t)) \
  1002 \  |] ==> sigma |= EEX h. Init (HI h) & [](HN h)" 
  1047 \  |] ==> sigma |= EEX h. Init (HI h) & [](HN h)";
  1003   (fn [p1,p2,p3,p4,p5] 
  1048 by (rtac ((temp_use history) RS eexE) 1);
  1004    => [rtac ((temp_use history) RS eexE) 1,
  1049  by (rtac p3 1);
  1005        rtac p3 1,
  1050 by (rtac (temp_use eexI) 1);
  1006        rtac (temp_use eexI) 1,
  1051 by (Clarsimp_tac 1); 
  1007        Clarsimp_tac 1, rtac conjI 1,
  1052 by (rtac conjI 1);
  1008        cut_facts_tac [p2] 2,
  1053 by (cut_facts_tac [p2] 2);
  1009        merge_box_tac 2,
  1054 by (merge_box_tac 2);
  1010        force_tac (temp_css addSEs2 [STL4E,p5]) 2,
  1055 by (force_tac (temp_css addSEs2 [STL4E,p5]) 2);
  1011        cut_facts_tac [p1] 1,
  1056 by (cut_facts_tac [p1] 1);
  1012        force_tac (temp_css addsimps2 Init_defs addSEs2 [p4]) 1
  1057 by (force_tac (temp_css addsimps2 Init_defs addSEs2 [p4]) 1);
  1013       ]);
  1058 qed "historyI";
  1014 
  1059 
  1015 (* ----------------------------------------------------------------------
  1060 (* ----------------------------------------------------------------------
  1016    example of a history variable: existence of a clock
  1061    example of a history variable: existence of a clock
  1017 
  1062 
  1018 Goal "|- EEX h. Init(h = #True) & [](h` = (~$h))";
  1063 Goal "|- EEX h. Init(h = #True) & [](h` = (~$h))";
  1020 by (rtac historyI 1);
  1065 by (rtac historyI 1);
  1021 by (REPEAT (force_tac (temp_css addsimps2 Init_defs addIs2 [unit_base, necT]) 1));
  1066 by (REPEAT (force_tac (temp_css addsimps2 Init_defs addIs2 [unit_base, necT]) 1));
  1022 (** solved **)
  1067 (** solved **)
  1023 
  1068 
  1024 ---------------------------------------------------------------------- *)
  1069 ---------------------------------------------------------------------- *)
  1025