doc-src/Functions/Thy/Functions.thy
changeset 39754 150f831ce4a3
parent 39752 06fc1a79b4bf
child 41846 b368a7aee46a
equal deleted inserted replaced
39753:ec6dfd9ce573 39754:150f831ce4a3
   761   @{subgoals[display,indent=0]}
   761   @{subgoals[display,indent=0]}
   762 
   762 
   763   \noindent The hypothesis in our lemma was used to satisfy the first premise in
   763   \noindent The hypothesis in our lemma was used to satisfy the first premise in
   764   the induction rule. However, we also get @{term
   764   the induction rule. However, we also get @{term
   765   "findzero_dom (f, n)"} as a local assumption in the induction step. This
   765   "findzero_dom (f, n)"} as a local assumption in the induction step. This
   766   allows to unfold @{term "findzero f n"} using the @{text psimps}
   766   allows unfolding @{term "findzero f n"} using the @{text psimps}
   767   rule, and the rest is trivial. Since the @{text psimps} rules carry the
   767   rule, and the rest is trivial.
   768   @{text "[simp]"} attribute by default, we just need a single step:
       
   769  *}
   768  *}
   770 apply simp
   769 apply (simp add: findzero.psimps)
   771 done
   770 done
   772 
   771 
   773 text {*
   772 text {*
   774   Proofs about partial functions are often not harder than for total
   773   Proofs about partial functions are often not harder than for total
   775   functions. Fig.~\ref{findzero_isar} shows a slightly more
   774   functions. Fig.~\ref{findzero_isar} shows a slightly more
   792                and IH: "\<lbrakk>f n \<noteq> 0; x \<in> {Suc n ..< findzero f (Suc n)}\<rbrakk> \<Longrightarrow> f x \<noteq> 0"
   791                and IH: "\<lbrakk>f n \<noteq> 0; x \<in> {Suc n ..< findzero f (Suc n)}\<rbrakk> \<Longrightarrow> f x \<noteq> 0"
   793                and x_range: "x \<in> {n ..< findzero f n}"
   792                and x_range: "x \<in> {n ..< findzero f n}"
   794   have "f n \<noteq> 0"
   793   have "f n \<noteq> 0"
   795   proof 
   794   proof 
   796     assume "f n = 0"
   795     assume "f n = 0"
   797     with dom have "findzero f n = n" by simp
   796     with dom have "findzero f n = n" by (simp add: findzero.psimps)
   798     with x_range show False by auto
   797     with x_range show False by auto
   799   qed
   798   qed
   800   
   799   
   801   from x_range have "x = n \<or> x \<in> {Suc n ..< findzero f n}" by auto
   800   from x_range have "x = n \<or> x \<in> {Suc n ..< findzero f n}" by auto
   802   thus "f x \<noteq> 0"
   801   thus "f x \<noteq> 0"
   803   proof
   802   proof
   804     assume "x = n"
   803     assume "x = n"
   805     with `f n \<noteq> 0` show ?thesis by simp
   804     with `f n \<noteq> 0` show ?thesis by simp
   806   next
   805   next
   807     assume "x \<in> {Suc n ..< findzero f n}"
   806     assume "x \<in> {Suc n ..< findzero f n}"
   808     with dom and `f n \<noteq> 0` have "x \<in> {Suc n ..< findzero f (Suc n)}" by simp
   807     with dom and `f n \<noteq> 0` have "x \<in> {Suc n ..< findzero f (Suc n)}" by (simp add: findzero.psimps)
   809     with IH and `f n \<noteq> 0`
   808     with IH and `f n \<noteq> 0`
   810     show ?thesis by simp
   809     show ?thesis by simp
   811   qed
   810   qed
   812 qed
   811 qed
   813 text_raw {*
   812 text_raw {*
  1067   the zero function. And in fact we have no problem proving this
  1066   the zero function. And in fact we have no problem proving this
  1068   property by induction.
  1067   property by induction.
  1069 *}
  1068 *}
  1070 (*<*)oops(*>*)
  1069 (*<*)oops(*>*)
  1071 lemma nz_is_zero: "nz_dom n \<Longrightarrow> nz n = 0"
  1070 lemma nz_is_zero: "nz_dom n \<Longrightarrow> nz n = 0"
  1072   by (induct rule:nz.pinduct) auto
  1071   by (induct rule:nz.pinduct) (auto simp: nz.psimps)
  1073 
  1072 
  1074 text {*
  1073 text {*
  1075   We formulate this as a partial correctness lemma with the condition
  1074   We formulate this as a partial correctness lemma with the condition
  1076   @{term "nz_dom n"}. This allows us to prove it with the @{text
  1075   @{term "nz_dom n"}. This allows us to prove it with the @{text
  1077   pinduct} rule before we have proved termination. With this lemma,
  1076   pinduct} rule before we have proved termination. With this lemma,
  1103 by pat_completeness auto
  1102 by pat_completeness auto
  1104 
  1103 
  1105 lemma f91_estimate: 
  1104 lemma f91_estimate: 
  1106   assumes trm: "f91_dom n" 
  1105   assumes trm: "f91_dom n" 
  1107   shows "n < f91 n + 11"
  1106   shows "n < f91 n + 11"
  1108 using trm by induct auto
  1107 using trm by induct (auto simp: f91.psimps)
  1109 
  1108 
  1110 termination
  1109 termination
  1111 proof
  1110 proof
  1112   let ?R = "measure (\<lambda>x. 101 - x)"
  1111   let ?R = "measure (\<lambda>x. 101 - x)"
  1113   show "wf ?R" ..
  1112   show "wf ?R" ..