equal
deleted
inserted
replaced
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" .. |