doc-src/TutorialI/CTL/CTL.thy
changeset 15102 04b0e943fcc9
parent 13552 83d674e8cd2a
child 15106 e8cef6993701
equal deleted inserted replaced
15101:d027515e2aa6 15102:04b0e943fcc9
   115 named after David Park, is weaker but sufficient for this proof:
   115 named after David Park, is weaker but sufficient for this proof:
   116 \begin{center}
   116 \begin{center}
   117 @{thm lfp_lowerbound[of _ "S",no_vars]} \hfill (@{thm[source]lfp_lowerbound})
   117 @{thm lfp_lowerbound[of _ "S",no_vars]} \hfill (@{thm[source]lfp_lowerbound})
   118 \end{center}
   118 \end{center}
   119 The instance of the premise @{prop"f S \<subseteq> S"} is proved pointwise,
   119 The instance of the premise @{prop"f S \<subseteq> S"} is proved pointwise,
   120 a decision that clarification takes for us:
   120 a decision that \isa{auto} takes for us:
   121 *};
   121 *};
   122 apply(rule lfp_lowerbound);
   122 apply(rule lfp_lowerbound);
   123 apply(clarsimp simp add: af_def Paths_def);
   123 apply(auto simp add: af_def Paths_def);
   124 
   124 
   125 txt{*
   125 txt{*
   126 @{subgoals[display,indent=0,margin=70,goals_limit=1]}
   126 @{subgoals[display,indent=0,margin=70,goals_limit=1]}
   127 Now we eliminate the disjunction. The case @{prop"p(0::nat) \<in> A"} is trivial:
   127 In this remaining case, we set @{term t} to @{term"p(1::nat)"}.
   128 *};
   128 The rest is automatic.
   129 
       
   130 apply(erule disjE);
       
   131  apply(blast);
       
   132 
       
   133 txt{*\noindent
       
   134 In the other case we set @{term t} to @{term"p(1::nat)"} and simplify matters:
       
   135 *};
   129 *};
   136 
   130 
   137 apply(erule_tac x = "p 1" in allE);
   131 apply(erule_tac x = "p 1" in allE);
   138 apply(clarsimp);
   132 apply(auto);
   139 
       
   140 txt{*
       
   141 @{subgoals[display,indent=0,margin=70,goals_limit=1]}
       
   142 It merely remains to set @{term pa} to @{term"\<lambda>i. p(i+1::nat)"}, that is, 
       
   143 @{term p} without its first element.  The rest is automatic:
       
   144 *};
       
   145 
       
   146 apply(erule_tac x = "\<lambda>i. p(i+1)" in allE);
       
   147 apply force;
       
   148 done;
   133 done;
   149 
   134 
   150 
   135 
   151 text{*
   136 text{*
   152 The opposite inclusion is proved by contradiction: if some state
   137 The opposite inclusion is proved by contradiction: if some state
   387  eufix :: "state set \<Rightarrow> state set \<Rightarrow> state set \<Rightarrow> state set"
   372  eufix :: "state set \<Rightarrow> state set \<Rightarrow> state set \<Rightarrow> state set"
   388 "eufix A B T \<equiv> B \<union> A \<inter> (M\<inverse> `` T)"
   373 "eufix A B T \<equiv> B \<union> A \<inter> (M\<inverse> `` T)"
   389 
   374 
   390 lemma "lfp(eufix A B) \<subseteq> eusem A B"
   375 lemma "lfp(eufix A B) \<subseteq> eusem A B"
   391 apply(rule lfp_lowerbound)
   376 apply(rule lfp_lowerbound)
   392 apply(clarsimp simp add: eusem_def eufix_def);
   377 apply(auto simp add: eusem_def eufix_def);
   393 apply(erule disjE);
       
   394  apply(rule_tac x = "[]" in exI);
   378  apply(rule_tac x = "[]" in exI);
   395  apply simp
   379  apply simp
   396 apply(clarsimp);
       
   397 apply(rule_tac x = "y#xc" in exI);
   380 apply(rule_tac x = "y#xc" in exI);
   398 apply simp;
   381 apply simp;
   399 done
   382 done
   400 
   383 
   401 lemma mono_eufix: "mono(eufix A B)";
   384 lemma mono_eufix: "mono(eufix A B)";