程序設計語言理論(參考版)
2024-07-31 07:13本頁面
【正文】 故 ?是良基的 歸 納 法 ? 命題 （良基歸納） 令 ?是集合 A上的良基關系， 令 P是 A上某個性質， 若每當所有的 P(b) (b ? a)為真，則 P(a)為真，即 ?a.(?b.(b ? a ? P(b)) ? P(a)) 那么，對所有的 a?A， P(a)為真 歸 納 法 ? 命題 （良基歸納） 若 ?a.(?b.(b ? a ? P(b)) ? P(a))，則 ?(a) ? 證明 – 若存在某個 x?A使得 ?P(x)成立，則下面集合非空 B ? { a?A | ? P(a) } – 由引理 ， B一定有極小元 a?B – 但是 ， 對所有的 b ? a， P(b)一定成立 （ 否則 a不是B的極小元 ） – 這就和假定 ?b.(b ? a ? P(b)) ? P(a)矛盾 歸 納 法 ? 良基歸納法的使用 如何理解：若每當所有的 P(b) (b ? a)為真，則 P(a)為真，即： (?b.(b ? a ? P(b)) ? P(a)) – 對某些 a，不存在 b，使得 b ? a，則 ?b.(b ? a ? P(b)) ? P(a) 等價于 P(a) （因為 ?b: ?. P(b)為真，其中 ?表示空集） – 對另一些 a，存在 b，使得 b ? a，則 ?b.(b ? a ? P(b)) ? P(a) 的證明是基于 ?b.(b ? a ? P(b)) 為真來推導 P(a)為 真 歸 納 法 表 常用歸納形式的良基關系 歸納形式 良基關系 自然數歸納 (1) m ? n， 如果 m +1 ? n 自然數歸納 (2) m ? n， 如果 m ? n 結構歸納 (1) e ? e?， 如果 e是 e?的直接子表達式 結構歸納 (2) e ? e?， 如果 e是 e?的子表達式 基于證明的歸納 ? ? ??， 如果 ?是證明 ??的最后一步推導規(guī)則的某個前提的證明 歸 納 法 ? 自然數歸納 （ 形式 1） 為證明對所有 n， P(n)為真 ， 只需證明 P(0)以及證明對任何 m， 如果 P(m)為真則 P(m+1)必定為真 ? 自然數歸納 （ 形式 2） 為證明對所有 n， P(n)為真 ， 只需證明對任何 m，如果所有的 P(i) (i ? m)為真則 P(m)必定為真 ? 詞典序（以 自然數序列為例 ） ?n1, n2, …, nk? ? ?m1, m2, …, ml? iff k l 或者 k ? l并且存在一個 i ? k， 使得對所有的 j i有 nj ? mj 并且 ni mi 習 題 ， ， 。如果 B無極小元，那么對每個 a?B，可以找到某個 a??B使得 a??a。程序設計語言理論 計算機科學與技術學院 陳意云， 3607043 課 程 簡 介 計算機科學的理論體系 模型理論 ? 關心的問題 – 給定模型 M，哪些問題可以由模型 M解決 – 如何比較模型的表達能力 ? 經典計算 – 確定的圖靈機，可計算性理論屬于模型理論 ? 新型計算 – 本質特點是交互 ( 并發(fā)、分布、網絡、網格、云 )
環(huán)評公示相關推薦
鄂ICP備17016276號-1