推理與證明方法ppt課件(完整版)
【正文】 or an arbitrary c?U ? ?x P(x) UG/全稱推廣?x P(x) ? P(c) for some c?U EI/存在 舉 例P(c) for some c?U ? ?x P(x) EG/存在推廣U:UniversalP(x):3.D(S)Date 8推理與證明方法推理與證明方法EXAMPLE 4 Hypotheses: 172。結(jié)論： (h)(B(x)∨ (EG)n B(c)∨ (UI)n B(c)(h)Date 10推理與證明方法推理與證明方法Indirect proof, negate the conclusionHypotheses:→ ∨ (3,4) Q(2)∨ （ P(h)172。p P 空證明 /vacuous→pPof） … ∧ ?x停機(jī)問題 /Halting 1 4 68Date 16推理與證明方法推理與證明方法3推理與證明方法set(非空的非負(fù)整數(shù)集合必有最小元）Date 18推理與證明方法推理與證明方法數(shù)學(xué)歸納法 用來證明與 整數(shù)有關(guān) 的命題?！?P(m)① kP(n)(m5+數(shù)學(xué)歸納法的正確性可以用皮亞諾公理與良序定理來證明?！?→ n0P(k)nn?→ P(n0)?→ 遞歸方法(n)nF(3)5， F205fn?2Fibonacci數(shù)列研究 Euclid算法的計(jì)算復(fù)雜性。(0≦ ==fn+1㏒ 10b→ ∧ 任何一個(gè)遞歸算法都有一個(gè)迭代算法與之對(duì)應(yīng)。一般 /強(qiáng)，無限 /有限 遞歸方法 與算法的關(guān)系 4 57遞歸算法（ recursive)與迭代算法 (iterative)基礎(chǔ)，步驟Date 35推理與證明方法推理與證明方法小 formulae+1Date 32推理與證明方法推理與證明方法遞歸定義的集合：遞歸定義的集合： 3?n1(0≦ ri?n1?n2+(歸納假設(shè)）=2， F+(n–1) n0Example 1Date 29推理與證明方法推理與證明方法菲波那契數(shù) /FibonacciF(0)n!， 則 f(n)可以表示為：ff(0)Definition 4Date 25推理與證明方法推理與證明方法EXAMPLE 3 pp.?(n0nk1nkP(k+1))P(n0) 歸納步驟： ]→ ∧ ∧ ?1kP(m)這些公理缺一不可，其中性質(zhì)（ 5）稱為歸納公理，并指出了自然數(shù)是滿足公理（ 1） ~（ 4）的最小集合。n∈ M時(shí)必 n39。P(m+1))數(shù)學(xué)歸納的理論基礎(chǔ)是 整數(shù)公理 ，如下所示：Definition 1Date 19推理與證明方法推理與證明方法皮亞諾公理（ 1） 0∈ N；（ 2） 對(duì)每一個(gè) n∈ N， 唯一定義了一個(gè)自然數(shù) n39。?
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1