doc-src/TutorialI/Advanced/Partial.thy
changeset 12815 1f073030b97a
parent 12334 60bf75e157e4
child 15904 a6fb4ddc05c7
equal deleted inserted replaced
12814:2f5edb146f7e 12815:1f073030b97a
   136 Reasoning about such underdefined functions is like that for other
   136 Reasoning about such underdefined functions is like that for other
   137 recursive functions.  Here is a simple example of recursion induction:
   137 recursive functions.  Here is a simple example of recursion induction:
   138 *}
   138 *}
   139 
   139 
   140 lemma "wf(step1 f) \<longrightarrow> f(find(f,x)) = find(f,x)"
   140 lemma "wf(step1 f) \<longrightarrow> f(find(f,x)) = find(f,x)"
   141 apply(induct_tac f x rule:find.induct);
   141 apply(induct_tac f x rule: find.induct);
   142 apply simp
   142 apply simp
   143 done
   143 done
   144 
   144 
   145 subsubsection{*The {\tt\slshape while} Combinator*}
   145 subsubsection{*The {\tt\slshape while} Combinator*}
   146 
   146 
   191   \<exists>y. while (\<lambda>(x,x'). x' \<noteq> x) (\<lambda>(x,x'). (x',f x')) (x,f x) = (y,y) \<and>
   191   \<exists>y. while (\<lambda>(x,x'). x' \<noteq> x) (\<lambda>(x,x'). (x',f x')) (x,f x) = (y,y) \<and>
   192        f y = y"
   192        f y = y"
   193 apply(rule_tac P = "\<lambda>(x,x'). x' = f x" and
   193 apply(rule_tac P = "\<lambda>(x,x'). x' = f x" and
   194                r = "inv_image (step1 f) fst" in while_rule);
   194                r = "inv_image (step1 f) fst" in while_rule);
   195 apply auto
   195 apply auto
   196 apply(simp add:inv_image_def step1_def)
   196 apply(simp add: inv_image_def step1_def)
   197 done
   197 done
   198 
   198 
   199 text{*
   199 text{*
   200 The theorem itself is a simple consequence of this lemma:
   200 The theorem itself is a simple consequence of this lemma:
   201 *}
   201 *}
   202 
   202 
   203 theorem "wf(step1 f) \<Longrightarrow> f(find2 f x) = find2 f x"
   203 theorem "wf(step1 f) \<Longrightarrow> f(find2 f x) = find2 f x"
   204 apply(drule_tac x = x in lem)
   204 apply(drule_tac x = x in lem)
   205 apply(auto simp add:find2_def)
   205 apply(auto simp add: find2_def)
   206 done
   206 done
   207 
   207 
   208 text{* Let us conclude this section on partial functions by a
   208 text{* Let us conclude this section on partial functions by a
   209 discussion of the merits of the @{term while} combinator. We have
   209 discussion of the merits of the @{term while} combinator. We have
   210 already seen that the advantage of not having to
   210 already seen that the advantage of not having to