数理逻辑-第三章-数学推理-数学归纳法

1、数理逻辑Mathematical Logic 第三章 数学推理Chapter 3 Mathematical Reasoning复习直接证明间接证明空证明平凡证明归谬证明分情形证明qppqp为假q为真p(rr)(p1p2pn)q(p1q)(p2q)(pnq)特殊情形复习证明n个命题等价p1p2 pn (p1p2)(p2p3)(pnp1)xP(x)构造性存在性证明非构造性存在性证明如何证明xP(x)为假？复习新泽西的每个人都生活在距离海洋50英里之内；新泽西的某个人从来没见过海洋。因此，生活在距离海洋50英里之内的某个人从来没见过海洋。N(x):x是新泽西人；L(x):x生活在距离海洋50英里以内

2、；S(x):x见过海洋。x(N(x)L(x);x(N(x)S(x)x(L(x)S(x)复习证明：若n是正整数，则n是偶数当且仅当7n+4是偶数p：n是偶数q：7n+4是偶数pq（直接证明）qp（间接证明）3.2 数学归纳法Mathematical Induction一、引言前n个正奇数之和的公式是什么？对n=1,2,3,4,5来说，前n个正奇数之和为：1=1，1+3=4，1+3+5=9，1+3+5+7=16，1+3+5+7+9=25猜测前n个正奇数之和是n2假如这个猜测是正确的，我们就需要一种方法来证明数学归纳法就是证明这种类型的断言的极为重要的证明技术如何使用数学归纳法为什么它是有效的证明技

3、术注意：数学归纳法只能证明通过其它方式获得的结果它不是发现公式或公理的工具一、引言二、良序性数学归纳法的有效性来源于如下关于整数集的基本公理：良序性每个非空的非负整数集都有最小元例：用良序性证明除法算法。若a是整数而且d是正整数，则存在唯一的整数q和r，满足0rd和a=dq+r例：用良序性证明除法算法。设S是形如a-dq的非负整数的集合，其中q是整数这个集合非空，因为-dq可以任意大（取q是绝对值很大的负整数）根据良序性，S有最小元r=a-dq0。整数r非负，而且rd假设rd，那么令r1=a-d(q0+1)=a-dq0-d=r-d0二、良序性例：用良序性证明除法算法。那么r1是S中比r更小的非

4、负整数推出了矛盾所以，r0，并且rd因此，存在满足0rd的整数r和q下一步还需要证明q和r是唯一的。二、良序性三、数学归纳法许多定理说：对所有正整数n来说P(n)为真1+2+3+n=n(n+1)/2n2nnP(n)数学归纳法证明对每个正整数n来说P(n)为真，包含如下两个步骤：基础步骤：P(1)为真归纳步骤：对每个正整数来说 P(n)P(n+1)为真对固定的正整数n来说，命题P(n)称为归纳假设当完成了如上两个步骤时，就证明了对所有正整数n来说P(n)为真三、数学归纳法把这种证明技术表示成推理规则就是p(1)n(P(n)P(n+1) nP(n)证明对所有正整数来说P(n)为真首先证明P(1)为

5、真然后证明对每个正整数n来说都有P(n)P(n+1)为真假设P(n)为真，证明在此假设下P(n+1)也必然为真三、数学归纳法注意：不假定对所有正整数来说P(n)为真，只是证明了：若假定P(n)为真，则P(n+1)也为真因此，数学归纳法不属于循环论证三、数学归纳法用数学归纳法证明定理时首先证明P(1)为真，然后知道P(2)为真，因为P(1)蕴含P(2)P(3)为真，因为P(2)蕴含P(3)以这样的方式继续下去，就可以看出对任意正整数k来说P(k)为真数学归纳法的形象解释三、数学归纳法为什么数学归纳法是有效的？假定知道P(1)为真，而且对所有正整数n来说P(n)P(n+1)为真为了证明对所有正整数

6、来说P(n)为真，假定至少存在一个使P(n)为假的正整数那么使P(n)为假的正整数集合S非空根据良序性，S有一个最小元，把它表示为k三、数学归纳法为什么数学归纳法是有效的？可以知道k不是1，因为P(1)为真因为k是正的，并且大于1，所以k-1是一个正整数因为k-1小于k，所以它不属于S所以P(k-1)必然为真因为P(k-1)P(k)为真，所以P(k)为真这与对k的选择相矛盾三、数学归纳法四、数学归纳法的例子例：用数学归纳法证明：前n个正奇数之和是n2解：设P(n)表示命题：前n个正奇数之和是n2必须首先完成基础步骤：P(1)为真然后必须完成归纳步骤：必须证明当假定P(n)为真时P(n+1)为真

7、基础步骤：P(1):前1个正奇数之和是12，这是真的，因为第一个正奇数是1例：用数学归纳法证明：前n个正奇数之和是n2归纳步骤：为了完成归纳步骤，必须证明对每个正整数n来说命题P(n)P(n+1)为真，为了证明这一点，假定对正整数n来说P(n)为真，即： 1+3+5+(2n-1)=n2必须证明假定P(n)为真，则P(n+1)为真四、数学归纳法的例子例：用数学归纳法证明：前n个正奇数之和是n2P(n+1)是命题 1+3+5+(2n-1)+(2n+1)=(n+1)2所以假定P(n)为真，得出 1+3+5+(2n-1)+(2n+1)=(1+3+5+(2n-1)+(2n+1)=n2+2n+1=(n+1

8、)2四、数学归纳法的例子例：用数学归纳法证明：前n个正奇数之和是n2这样就证明了从P(n)得出P(n+1)在第二个等式中我们使用了归纳假设P(n)因为P(1)为真，而且对所有正整数n来说P(n)P(n+1)为真，所以，由数学归纳法原理就证明了对所有正整数n来说P(n)为真四、数学归纳法的例子例：用数学归纳法证明：对所有正整数n来说不等式n2n解：设P(n)是命题“n2n”。基础步骤：P(1)为真，因为121=2归纳步骤：假定对正整数n来说P(n)为真，即假定n2n，需要证明P(n+1)为真，即需要证明n+12(n+1)。四、数学归纳法的例子例：用数学归纳法证明：对所有正整数n来说不等式n2n解

9、：对n2n两边加1，n+12n+1，又因为12n，所以 n+12n+12n+2n=2n+1因此，在P(n)为真的假定的基础上，已经证明了P(n+1)为真。归纳步骤完毕。四、数学归纳法的例子例：用数学归纳法证明：每当n是正整数时，n3-n就被3整除解：设P(n)是命题“n3-n被3整除”；基础步骤：P(1)为真归纳步骤：假定P(n)为真: n3-n被3整除，必须证明P(n+1)为真 (n+1)3-(n+1)=(n3+3n2+3n+1)-(n+1) =(n3-n)+3(n2+n)四、数学归纳法的例子如何证明对n=k,k+1,k+2,来说P(n)为真，其中k是不等于1的整数？只需改变基础步骤证明P(

10、k)为真例：用数学归纳法证明：对所有非负整数来说 1+2+22+2n=2n+1-1四、数学归纳法的例子解：设P(n)是命题：对非负整数n来说上述公式成立基础步骤：P(0)为真，因为20=1=21-1归纳步骤：假定P(n)为真，必须证明P(n+1)为真，即：1+2+22+2n+2n+1=2(n+1)+1-1=2n+2-1使用归纳假设P(n)，得出：1+2+22+2n+2n+1=2n+1-1+2n+1=2n+2-1归纳步骤完成，证毕。四、数学归纳法的例子在证明对n=k,k+1,k+2,来说P(n)为真时，k可以是负的、零或正的想象多米诺骨牌的比喻，现在首先撞到的是第k张骨牌（基础步骤），当每张骨牌

11、倒下时，它就撞到下一张骨牌（归纳步骤）。四、数学归纳法的例子例：几何级数求和几何级数是形如a,ar,ar2,arn,的序列，其中a和r是实数上例就是一种特殊情形，其中a=1和r=2用数学归纳法证明几何级数有穷多项之和的下列公式：当r1时四、数学归纳法的例子例：调和数不等式用数学归纳法证明：每当n是非负整数时就有H2n1+n/2例8-例11（P186）四、数学归纳法的例子例：设n是正整数。证明：可以用L形状的碎片来铺满去掉1个格子的任何2n2n棋盘，其中这些碎片一次覆盖3个格子。解：设P(n)是命题：可以用L形状的碎片来铺满去掉1个格子的任何2n2n棋盘四、数学归纳法的例子基础步骤：命题P(1)

12、为真，因为可以用1个L形状的碎片来铺满去掉1个格子的任何22棋盘，如下图：四、数学归纳法的例子归纳步骤：假定P(n)为真，必须证明在这个假定之下P(n+1)也必然为真为了证明这一点，我们考虑去掉1个格子的2n+12n+1棋盘，将这个棋盘分成4个2n2n棋盘，如下图四、数学归纳法的例子根据归纳假设，可以用L形状的碎片来覆盖第4个2n2n棋盘现在去掉另外三个2n2n棋盘的一角上的格子，如下图四、数学归纳法的例子根据归纳假设，可以用L形状的碎片来覆盖这3个2n2n棋盘另外可以用1个L形状的碎片来铺满这3个临时去掉的格子因此，可以用L形状碎片来铺满整个去掉1个格子的2n+12n+1棋盘归纳步骤完成，证

13、毕。四、数学归纳法的例子五、数学归纳法的第二原理假定对k=1,2,n来说P(k)为真，证明在这个假定的基础之上P(n+1)也必然为真（第二数学归纳法）证明对所有正整数n来说P(n)为真的两个步骤：基础步骤：证明P(1)为真归纳步骤：证明对每个正整数n来说，P(1)P(2)P(n)P(n+1)为真例：证明：若n是大于1的整数，则n可以写成素数之积解：设P(n)：n可以写成素数之积基础步骤：P(2)为真，因为P(2)可以写成一个素数之积，即它自身归纳步骤：假定对所有满足kn的正整数k来说P(k)为真，要完成归纳步骤就必须证明在这个假定下P(n+1)为真五、数学归纳法的第二原理例：证明：若n是大于1

14、的整数，则n可以写成素数之积解：分两种情况考虑：当n+1是素数时和当n+1是合数时。若n+1是素数，则P(n+1)为真；若n+1是合数，则可以将其表示成两个整数a和b之积，其中a、b满足2abn+1根据归纳假设，a和b可以写成素数之积五、数学归纳法的第二原理例：证明：若n是大于1的整数，则n可以写成素数之积解：因此，若n+1是合数，则它可以写成素数之积归纳步骤完成证毕。五、数学归纳法的第二原理例：证明：可以仅用4分和5分的邮票来组成等于或超过12分的每种邮票解：设P(n)是命题：可以用4分和5分的邮票来组成n分邮资第一数学归纳法基础步骤：P(12)为真，因为可以用3个4分邮票组成12分邮资五、

15、数学归纳法的第二原理例：证明：可以仅用4分和5分的邮票来组成等于或超过12分的每种邮票归纳步骤：假定P(n)为真，即：可以用4分和5分邮票组成n分邮资证明在该假定下，P(n+1)为真假设在组成n分邮资的时候用到了至少1个4分邮票，则可以用1个5分邮票代替它，就组成了n+1分邮资五、数学归纳法的第二原理例：证明：可以仅用4分和5分的邮票来组成等于或超过12分的每种邮票假设在组成n分邮资的时候没有用到4分邮票，由于n12，所以至少用了3个5分邮票，所有用4个4分邮票替代3个5分邮票，就组成了n+1分邮资归纳步骤完成，证毕。五、数学归纳法的第二原理例：证明：可以仅用4分和5分的邮票来组成等于或超过12分的每种邮票第二数学归纳法基础步骤：证明P(12)、P(13)、P(14)、P(15)都为真归纳步骤：假定对所有满足12kn的正整数P(k)为真(n15)，为了证明P(n+1)成立，可以用组成n-3分邮资的邮票加上1个4分邮票。归纳步骤完成，证毕。五、数学归纳法的第二原理注意：为了证明对n=k,k+1,来说P(n)为真，其中k是整数首先证明P(