离散数学(09).ppt

《离散数学(09).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二章集合2.3归纳法和自然数2.3.3归纳证明归纳定义不仅提供了定义无限集合的一种方法,也为证明定理形成某些有效技术的基础。对于xP(x)形式的命题,如果其论述域S是归纳定义的集合,则归纳法往往是有效1的证明方法。归纳法证明通常由基础步骤和归纳步骤两部分组成,它们分别对应于S的定义的基础和归纳条款。(1)基础步骤。这一步证明S的定义中基础条款指定的每一元素x∈S,P(x)是真。2(2)归纳步骤。这一步证明如果事物x,y,z,…有性质P,那么用归纳条款指定的方法,组合它们所得的新元素也具有性质P。归纳

2、定义的极小性条款保证S的所有元素仅仅应用基础和归纳条款才能构成,因此证明了以上两步,就足以推出xP(x)。3现在举例说明这一方法。回顾定理1.2-1(P12):“设A和A*是对偶式。P1,P2,…,Pn是出现于A和A*”中的所有命题变元,于是:┐A(p1,p2,….pn)A*(┐p1,┐p2,….┐pn)(1)因为根据对偶式定义,公式A中仅含有联结词∧、∨、┐,因此公式A可归纳定义如下:4(1)Pi(1≤i≤n)是公式;T是公式;F是公式。(2)若A和B是公式,则┐A、(A∧B)、(A∨B)是公式。

3、(3)只有有限次运用条款(1)和(2)生成的才是公式。定理1.2-1是建立在归纳定义的公式集合上,因此可以用上述一般的归纳法证明。5(1)(基础步骤)A(P1,P2….)Pi；┐TF,(这时的A和A*仅是单个命题变元或者常元A=A*)┐A(P1,P2…)┐Pi；T┐FA*(┐P1,┐P2….)┐Pi(1≤i≤n)所以当A是由一个变元或常元时,公式(1)成立。(2)(归纳步骤)设A1(P1,P2,…,Pn)、A2(P1,P2,…,Pn)对公式(1)成立,即:6┐A1(P1,P2,…,Pn)A1

4、*(┐P1,┐P2,…,┐Pn)┐A2(P1,P2,…,Pn)A2*(┐P1,┐P2,…,┐Pn)现证明:①(A1∧A2)②(A1∨A2)③┐A1时,公式(1)也成立。情况1：(A1∧A2)记(A1∧A2)为A。A的对偶A*就是(A1*∨A2*)7┐A(p1,p2,…,pn)┐(A1(p1,p2,…,pn)∧A2(p1,p2,…,pn))┐A1(p1,p2,…,pn)∨┐A2(p1,p2,…,pn)A1*(┐p1,┐p2,…,┐pn)∨A2*(┐P1,P2,…,┐Pn)A*(┐p1,┐p2,…

5、,┐pn)这说明对于∧运算(1)式成立。情况2:(A1∨A2)方法与情况1类似,留给读者自证。8情况3:┐A1记┐A1为A┐A(p1,p2,…,pn)┐┐(A1(p1,p2,…,pn)┐A1*(┐p1,┐p2,…,┐pn)A*(┐p1,┐p2,…,┐pn)故对n个命题变元的一切运算情况公式(1)公式成立。以上的归纳是将对偶式中可能的命题运算9∧、∨、┐都进行了证明，这种归纳也叫完全归纳法（穷举法）。但通常的归纳证明是涉及自然数的,自然数具有以下归纳特征:(1)(基础)0∈N。(2)(归纳)如果n∈

6、N,那么n+1∈N。(3)(极小性)如果SN,且S有以下性质:10(i)0∈S;(ii)对每一n∈N,如果n∈S,那么(n+1)∈S。那么,S=N。这里,极小性条款是习惯上用于自然数定义中的形式,它叫做数学归纳法第一原理。我们适当地改变一下这个条款的形式,就可得到以自然数为论述域的xP(x)形式的断言的归纳证明过程。11通常我们使用过的数学归纳法是这样：证明：P(n)(n=1,2,3,…)成立（1）首先证明n=1时P(1)成立（2）假设n=k时P(k)成立（3）再证明n=k+1时P(k+1)成立(1

7、)式能说明对n的首项成立,(2)(3)式说明只要前项成立，后项就成立。结合已经证明过的首项，得到对任意的n，P(n)都成立。12令S={n

8、P(n)}是N的子集,于是极小性条款可改为“如果①P(0)为真,②n(P(n)→P(n+1))为真,(P(n)为真是作为假设前提)那么,对一切n,P(n)为真。”根据这一条款,立即得出归纳证明的过程如下:(1)(基础)先证明P(0)是真。可用任意证明技术。(2)(归纳)再证明n(P(n)→P(n+1))是真。为此,13一般先假设“P(n)对任意n∈N是真”这叫归

9、纳假设(或归纳前提),由此再推出P(n+1)也真,一旦证明了P(n)→P(n+1)对任意n是真,用全称推广规则得n(P(n)→P(n+1))。再根据数学归纳法第一原理得出xP(x)。14例8证明对所有n∈N,这里的定理是nP(n)的形式。P(n)是断言证：(1)(基础)证明P(1)因为即1=1,显然成立(2)(归纳)证明n(P(n)→P(n+1))。假设对一切n∈N,P(n)是真,即15我们希望证明P(n+1),也就是因为(根据归