推理與證明方法

推理與證明方法7/13/20231第1頁，課件共38頁，創(chuàng)作于2023年2月定理/Theorem:一個真值為T的命題語句。證明/Proof：用論證方式形成的一個命題語句序列說明一個定理為T。證明的構(gòu)造/形式：由兩個部分組成

1、公理、假定或前提/axiom、postulate、hypotheses2、推理規(guī)則/ruleofinference其它：引理/lemma、推論/corollary、猜想/conjecture一些基本概念7/13/20232第2頁，課件共38頁，創(chuàng)作于2023年2月Definition1蘊(yùn)涵演算/logicalimplyingoperation

對于任意的公式P和Q，如果P

→Q為T，則稱P蘊(yùn)涵Q，記為P

Q或P/Q蘊(yùn)涵演算的推廣表示：

P1、

P2、…

、Pn

Q

前提組/hypotheses結(jié)論/conclusion證明的基本工具：等值演算，真值表，范式，引用已知簡單結(jié)論下表是一些常用的簡單結(jié)論7/13/20233第3頁，課件共38頁，創(chuàng)作于2023年2月Table1RuleofInference

NamePP∨QAddition/析取附加式P∧QPSimplification/合取化簡式P、QP∧QConjunction/并發(fā)式P、P→QQModusponens/分離式?Q、P→Q?PModustollens/拒取式?p、P∨QQDisjunctivesyllogism/析取三段式P→Q、Q→RP→RHypotheticalsyllogism/假言三段式7/13/20234第4頁，課件共38頁，創(chuàng)作于2023年2月EXAMPLE6Hypotheses:(1)Itisnotsunnythisafternoonanditiscolderthanyesterday.(2)Wewillgoswimmingonlyifitissunny.(3)Ifwedon’tgoswimming,thenwewilltakeacanoetrip.(4)Ifwetakeacanoetrip,thenwewillbehomebysunset.Conclusion:Wewillbehomebysunset.P:Itissunnythisafternoon.Q:Itiscolderthanyesterday.R:Wewillgoswimming.S:Wewilltakeacanoetrip.T:Wewillbehomebysunset.7/13/20235第5頁，課件共38頁，創(chuàng)作于2023年2月Thehypothesesbecome?P∧Q,R→P,?R→S,andS→T,TheconclusionisT?P∧Q(h)7.S→T(h)

?P(s)8.TR→P(h)?R(m)?R→S(h)S(m)7/13/20236第6頁，課件共38頁，創(chuàng)作于2023年2月Table2.RuleofInferenceNamexP(x)P(c)ifcUUI/全稱舉例P(c)foranarbitrarycUxP(x)UG/全稱推廣xP(x)P(c)forsomecUEI/存在舉例P(c)forsomecUxP(x)EG/存在推廣U:UniversalI:InstantiationE:ExistentialG:Generalization7/13/20237第7頁，課件共38頁，創(chuàng)作于2023年2月EXAMPLE3蘇格拉底論證：人固有一死，蘇格拉底是人，因此蘇格拉底固有一死。P(x):x是人，D(x):x是要死的，S:蘇格拉底。x(P(x)→D(x)),P(S)D(S)1.x(P(x)→D(x))(h)3.P(S)2.P(s)→D(s)(UG)4.D(S)7/13/20238第8頁，課件共38頁，創(chuàng)作于2023年2月EXAMPLE4Hypotheses:任何人如果他喜歡步行，則他就不喜歡乘汽車；每個人喜歡乘汽車或者喜歡騎自行車；有的人不喜歡騎自行車，Conclusion:因此有的人不喜歡步行。W(x):喜歡步行，B(x):x喜歡乘汽車，K(x)：x喜歡騎自行車；前提：x(W(x)→?B(x))，x(B(x)∨K(x)),x(?K(x)),結(jié)論：x(?W(x))7/13/20239第9頁，課件共38頁，創(chuàng)作于2023年2月x(?K(x))(h)7.W(c)→?B(c)(UI)?K(c)(EI)8.?W(c)x(B(x)∨K(x))(h)9.x(?W(x))(EG)B(c)∨K(c)(UI)B(c)x(W(x)→?B(x))(h)7/13/202310第10頁，課件共38頁，創(chuàng)作于2023年2月Indirectproof,negatetheconclusionHypotheses:P∨Q,P→R,Q→SConclusion:S∨RProof:P∨Q,P→R,Q→SS∨R?(S∨R)（否定結(jié)論）5.?Q(3,4)9.?P∧?Q(5,8)?S∧?R（DM）

6.?R(2)10.?(P∨Q)(9)?S（化簡）

7.P→R(h)11.P∨Q(h)Q→S(h)8.?P(6,7)12.F(11,12)7/13/202311第11頁，課件共38頁，創(chuàng)作于2023年2月定理證明方法：1、直接證明/directproof:p→Q

2、間接證明/indirectproof:p→Q

?Q→?P3、空證明/vacuousproof:p→Q其中P為F4、平凡證明/trivialproof：p→Q其中Q為T7/13/202312第12頁，課件共38頁，創(chuàng)作于2023年2月5、反證明/proofofcontradiction：

P?PS∧?S6、分例證明/proofofcases：

P1∨P2…

∨Pn→Q

（P1→Q）∧（P2→Q）…∧（Pn→Q）定理證明方法：7/13/202313第13頁，課件共38頁，創(chuàng)作于2023年2月7、存在證明/existenceproof：

xP(x)constructive,nonconstructive8、歸納證明/inductionproof：

xP(x)定理證明方法：（含有量詞）7/13/202314第14頁，課件共38頁，創(chuàng)作于2023年2月進(jìn)一步的思考

1、從等值演算到蘊(yùn)涵演算

2、從命題公式的推理到謂詞公式的推理

3、停機(jī)問題/HaltingProblem

7/13/202315第15頁，課件共38頁，創(chuàng)作于2023年2月練習(xí)

pp.1834、16、43、687/13/202316第16頁，課件共38頁，創(chuàng)作于2023年2月3數(shù)學(xué)推理

MathematicalReasoning3.1推理與證明方法

3.2數(shù)學(xué)歸納方法

MathematicalInduction3.3遞推方法7/13/202317第17頁，課件共38頁，創(chuàng)作于2023年2月Thewell-orderingpropertyThewell-orderingproperty(良序定理）Everynonemptysetofnonnegativeintegershasaleastelement(非空的非負(fù)整數(shù)集合必有最小元）7/13/202318第18頁，課件共38頁，創(chuàng)作于2023年2月數(shù)學(xué)歸納法用來證明與整數(shù)有關(guān)的命題。數(shù)學(xué)歸納法的公式表示：[P(1)∧m(m

1∧P(m)→P(m+1))]→nP(n)1、歸納基礎(chǔ)：P(1)2、歸納步驟：

m(m

1∧P(m)→P(m+1))數(shù)學(xué)歸納的理論基礎(chǔ)是整數(shù)公理，如下所示：Definition17/13/202319第19頁，課件共38頁，創(chuàng)作于2023年2月皮亞諾公理（1）0∈N；（2）對每一個n∈N，唯一定義了一個自然數(shù)n'，n'稱為n的后鄰；（3）不同的自然數(shù)，其后鄰也不同；（4）沒有一個自然數(shù)的后鄰是0；（5）如果有一個子集MN滿足：①

0∈M；②

n∈M時(shí)必n'∈M,則M=N自然數(shù)全體N通過皮亞諾公理的五條公理組成。這些公理缺一不可，其中性質(zhì)（5）稱為歸納公理，并指出了自然數(shù)是滿足公理（1）~（4）的最小集合。

7/13/202320第20頁，課件共38頁，創(chuàng)作于2023年2月數(shù)學(xué)歸納法的一般公式表示：[P(k)∧m(m

k∧P(m)→P(m+1))]→nP(n)1、歸納基礎(chǔ)：P(k)2、歸納步驟：

m(m

k∧P(m)→P(m+1))Definition27/13/202321第21頁，課件共38頁，創(chuàng)作于2023年2月EXAMPLE1pp.191example51+2+22+…+2n=2n+1-1

數(shù)學(xué)歸納法的正確性可以用皮亞諾公理與良序定理來證明。7/13/202322第22頁，課件共38頁，創(chuàng)作于2023年2月第二數(shù)學(xué)歸納法：[P(n0)∧k(k>n0∧P(n0)∧P(n0+1)∧…∧P(k)→P(k+1))]→nP(n)1、歸納基礎(chǔ)：P(n0)2、歸納步驟：k(k>n0∧P(n0)∧P(n0+1)∧…∧P(k)→P(k+1))Definition37/13/202323第23頁，課件共38頁，創(chuàng)作于2023年2月EXAMPLE2證明：任意一個大于1的自然數(shù)或?yàn)橘|(zhì)數(shù)，或能表示為若干個質(zhì)數(shù)的乘積。7/13/202324第24頁，課件共38頁，創(chuàng)作于2023年2月有限數(shù)學(xué)歸納法：對于n0

nnk

的P(n)有限數(shù)學(xué)歸納法的前推公式表示：[P(n0)∧n(n0

nnk-1

∧

P(n))→P(n+1))]→

n(n0

nnk→P(n))1、歸納基礎(chǔ)：P(n0)2、歸納步驟：

n(n0

nnk-1

∧

P(n))→P(n+1))]Definition47/13/202325第25頁，課件共38頁，創(chuàng)作于2023年2月EXAMPLE3pp.195Example11，12，147/13/202326第26頁，課件共38頁，創(chuàng)作于2023年2月3.3遞歸方法

RecursiveDefinition7/13/202327第27頁，課件共38頁，創(chuàng)作于2023年2月DEFINITION1定義1 如果一個對象部分地由自己所組成，或者按它自己定義，則稱為是遞歸的（Recursion）。遞歸定義的函數(shù)f：f的定義域：非負(fù)整數(shù)集

1、遞歸基礎(chǔ)：

f(0)2、遞歸步驟：f(n)=g(f(k)),k<n,n≥0,7/13/202328第28頁，課件共38頁，創(chuàng)作于2023年2月自然數(shù)階乘n!就是采用遞歸方法計(jì)算出來的。令f(n)=n!，則f(n)可以表示為：

f(0)=1 f(n)=n·f(n–1) n>0Example17/13/202329第29頁，課件共38頁，創(chuàng)作于2023年2月菲波那契數(shù)/Fibonacci

F(0)=0，F(xiàn)(1)=1 F(n)=F(n–1)+F(n–2) n>1由上述公式，我們得到：

F(2)=1，F(xiàn)(3)=2，F(xiàn)(4)=3，

F(5)=5，F(xiàn)(6)=8，……利用菲波那契數(shù)可以推算出兔子繁衍規(guī)律。

Example27/13/202330第30頁，課件共38頁，創(chuàng)作于2023年2月Example6（PP.205

），

f3=2>,f4=3>2,(歸納基礎(chǔ)）

fn-1>n-3,fn>n-2(n>3)(歸納假設(shè)）

fn+1=fn-1+fn>n-2+n-3=n-3(1+)=n-3·2=n-1(歸納證明）7/13/202331第31頁，課件共38頁，創(chuàng)作于2023年2月利用Fibonacci數(shù)列研究Euclid算法的計(jì)算復(fù)雜性。

a=r0,b=r1ri=ri+1·qi+1+ri+2(0≦ri+2<ri+1,0≦I<n-2)rn-1=rn·qnrn≧1=f2,rn-1≧2rn≧2f2=f3,假設(shè)ri+1≧fn+1-i，ri+2≧fn-i

ri≧ri+1+ri+2≧fn+1-i+fn-i=fn+2-i(0≦i<n-2)因此b=r1≧fn+1>n-1,㏒10b>(n-1)㏒10>(n-1)/5he