第一章 逻辑与证明(2).ppt

,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,Click to edit Master title style,NEC-DM,离散数学,2,证明,介绍一些证明的一般方法,用逻辑来分析正确和不正确的论证,1.5,推理规则,从一系列命题推出一个结论的过程称为,演绎推理,考虑下面一系列命题。,这个错误或者出现在模块,17,或者出现在模块,81,中。,这个错误是一个数值计算错误。,模块,81,没有数值计算错误。,假设这些句子为真，得出结论,错误出现在模块,17,2,3,1.5.2,命题逻辑的有效论证,从一系列前提得出结论的方法称为演绎推理。,前提：已知的命题系列,结论：由假设得出的结论,结论从前提导出,结论为真,任何论证过程都有形式：,如果,p,1,并且,p,2,并且,并且,p,n,则,q,。,论证有效在于形式不在于内容,4,定义,一个论证过程是一系列的命题，,p,1,p,2,p,n,/q,p,1,p,2,p,n,称为前提，命题,q,是结论,如,p,1,p,2,p,n,全为真，则,q,也必为真，,那么论证有效；否则论证过程是无效的,5,例,确定论证,p q,p/q,是否有效,p q,p q p q,T T,T T T,T F,F T F,F T,T F T,F F,T F F,注意：只要前提,p,q,和,p,为真，结论,q,就为真。所以论证过程是有效的。,6,例：,用符号表示论证过程,确定此论证过程是否有效,如果论证过程是有效的，那么要,p,q,和,q,同时为真，则,p,必为真。,假设,p,q,和,q,都为真，这在,p,为假,q,为真的时候是可能的；所以论证过程是无效的。,7,例,确定论证,p q,q/p,是否有效,p q,p q p q,T T,T T T,T F,F T F,F T,T F T,F F,T F F,注意：当前提,p,q,和,q,为真，结论,p,可能为假。所以论证过程是无效的。,8,1.5.3,命题的推理规则,假言推理,/,分离定律,合取,拒取,附加,化简,假设段论,析取段论,下列论证里使用了那个推理规则,若今天下雨，则我们今天将不野餐。若我们今天不野餐，则我们明天将野餐。因此，若今天下雨，则我们明天将野餐。,解：设,p,：“今天下雨”，,q:,“我们今天将不野餐”,r:,“我们明天将野餐”,p,q,q r,p r,假言三段论,9,1.5.4,用推理规则建立论证,证明：,前提：“今天下午没有出太阳 并且 今天比昨天冷,q,”,“只有今天 下午出太阳,p,，我们才去游泳,r,”,“若我们不去游泳，则我们将去乘独木舟游览,s,”,“若我们乘独木舟游览，则我们将在黄昏回家,t,”,结论：“我们将在黄昏回家”,解：,p,q,前提,p,r,p,r s,s t,10,r,s,t,1.5.5,消解,11,12,1.5.7,量词化句子推理规则,全称例化,全称一般化,存在例化,存在一般化,例,1.5.25,给出如下假设：,每个人都喜欢,Microsoft,或者,Apple,。,Lynn,不喜欢,Microsoft,，说明由假设可得出结论，,Lynn,喜欢,Apple,。,设,P(x),表示命题函数“,x,喜欢,Microsoft,”，,Q(x),表示命题函数“,x,喜欢,Apple,”。,第一个前提是,x,(,P(x),Q(x),),。,通过全称例化，得到,P(Lynn),Q(Lynn),。,第二个前提是,P(Lynn),。析取三段论推理规则得出,Q(Lynn),，代表命题“,Lynn,喜欢,Apple,”。这样，得出了,遵从假设,的结论。,13,14,本节复习,1.,什么是数学系统？,2.,什么是公理？,3.,什么是定义？,4.,什么是未定义项,5.,什么是定理？,6.,什么是证明？,7.,什么是引理？,8.,什么是直接证明？,9.,“,偶数,”,的形式化定义是什么？,10.,“,奇数,”,的形式化定义是什么？,11.,什么是反证法？,12.,什么是间接证明？,13.,什么是逆否证明？,14.,什么是分情况证明？,15.,什么是存在性证明？,16.,什么是演绎推理？,17.,什么是论证过程中的假设？,18.,什么是论证过程中的前提？,19.,什么是论证过程中的结论？,20.,什么是有效的论证？,21.,什么是无效的论证？,22.,说明假言推理规则。,练习,35,用符号表示下面的论证过程，并说明论证过程是否有效。设,p:,我努力学习。,q:,我的成绩是,A,。,r:,我发财了。,如果我努力学习，则我的成绩是,A,或者我发财了。,我的成绩不是,A,并且没有发财。,我不努力学习。,15,p (qr),q,r,_,p,p,q,r,qr,p (qr),q,r,p,T,T,T,T,T,F,T,F,T,F,T,T,T,F,F,F,T,F,F,F,T,F,F,F,16,p (qr),q,r,_,p,注意到：当,p (qr),，,q,，,r,三个命题都为,T,的时候，,p,也为,T,，因此本论证有效。,17,1.6,证明导论,数学系统,公理,定义,未定义项,定理、引理、推论、证明,论证一个定理为真的过程称为,证明,18,欧几里德几何,公理,例：给定两个不同的点，存在惟一的一条直线通过这两个点。,定义,例：如果,x,是正数或零，则实数,x,的绝对值,|,x,|,定义为,x,，其他情况定义成,-,x,。,19,欧几里德几何中的定理例,如果一个三角形的两条边相等，则这两条边相对的角相等。,如果四边形的对角线互相平分，则四边形为平行四边形,欧几里德几何中的推论例,如果一个三角形是等边的，则它是等角的。,20,1.6.5,直接证明法,构造一个条件语句,p,q,的直接证明,假设,p,为真,应用推理规则构造,推出,q,也一定为真,定义：整数,n,为偶数，如果存在一个整数,k,使得,n=2k;,整数,n,为奇数，如果存在一个整数,k,使得,n=2k+1,直接证明方法举例,例：如果,m,和,n,都是完全平方数，那么,mn,也是一个完全平方数。,（若有一个整数,b,使得,a=b,2,则整数,a,是一个完全平方数）,证明：根据完全平方数的定义，可知,存在,s,t,，使得,m=s,2,n=t,2,mn=s,2,t,2,=(st),2,所以,mn,是一个完全平方数,21,22,例,假设,d,、,d,1,、,d,2,和,x,是任意实数,if d=min(d1,d2)and x d,then x d1 and x d2,证明：,根据,min,的定义可以推出,d,d,1,并且,d,d,2,。依,x,d,并且,d,d,1,，可以根据前面的定理（例,1.5.5,的第二个定理）推出,x,d,1,。由于,x,d,并且,d,d,2,，可以根据前面的同一个定理推出,x,d,2,。因此，,x,d,1,并且,x,d,2,。,23,1.6.6,反证,法,反证法有时称为间接证明，它使用矛盾来证明命题。,通常用被否定了的结论作为前提，,推出矛盾，从而证明原命题为真,24,反证法的正确性,通过命题,p,q,和,(,p,q,)(,r,r,),的等价性来说明反证法的正确性。,例,给出定理“若,3n+2,是奇数，则,n,是奇数”的证明,若用直接法证明，设,3n+2,是奇数，则存在,k,使得,3n+2=2k+1,能否从中得出,n,是奇数的结论？,反正法：,第一,步：假设条件语句结论是假，即“,3n+2,是奇数，,n,不是奇数”，那么,n,是偶数。即：,n=2k+1,第二,步：根据上面的假设，则,3n+2=3(2k)+2=6k+2=2(3k+1),也就是得出,3n+2,是偶数，这与原命题的假设“,3n+2”,是奇数”矛盾,所以原来的条件语句为真，定理得证。,25,26,例,用反证法证明下面的陈述：,对于所有的实数,x,和,y,，,如,x+y2,，,则,x 1,或,y 1,证,:,设结论为假,x1,y1,则,x+y1,则,n,2,n”,论域是所有整数,解：命题,p(0),是条件语句“若,01,则,0,2,0,”。,因为前提,01,所假，所以,p(0),自动为真,注：在这里，条件语句的结论为假，与条件语句的真值无关，因为前提为假的条件保证 了条件语句为真,28,平凡证明,在条件语句,p q,中，如果知道结论,q,为真，那么就能得出条件语句为真。这种证明方法为平凡证明,例,设,p(n),表示“若,a,、,b,是满足,a,b,的正整数，则,a,n,b,n,”,其中论域是所有整数。证明命题,p(0),为真。,解：命题,p(0),是“若,a,、,b,是满足,a b,的正整数，则,a,0,b,0,”,因为,a,0,=b,0,=1,，即条件语句的结论为真，,所以条件语句,p(0),为真,29,利用等价关系证明,p,当且仅当,q,p,q,(p,q),(q,p),例,1.5.15,证明对于所有的整数,n,，,n,为奇数,当且仅当,n,1,为偶数。,30,利用等价关系证明,例,1.5.15,证明对于所有的整数,n,，,n,为奇数当且仅当,n,1,为偶数。,证明：,如果,n,为奇数，则,n,1,为偶数,。,若,n,为奇数，则,n,2k,1,，其中,k,为某个整数。于是,n,1,(2k,1),1,2k,，所以,n,1,为偶数。,下面证明“,如果,n,1,为偶数，则,n,为奇数,”。,如果,n,1,为偶数，则,n,1,2k,，其中,k,为某个整数。于是,n,2k,1,所以,n,为奇数。证毕。,31,反例证明法,反驳,x P(x),只需在论域内找到一个,x,，使,P(x),为假。,例,1.5.19,命题“,n(2,n,+1),是素数,”为假。,反例为,n,3,时，,2,3,9,，不是素数,32,1.7,证明方法和策略,穷举证明,分情况证明,存在性证明,唯一性证明,证明策略,33,1.7.2,穷举证明,有些定理可以通过有关的小数量例子测验来证明,穷举证明,例，当,n,是一个正整数，且,n 4,时，,(n+1),3,3,n,解：用穷举证明,对于,n=1,(n+1),3,=2,3,=8,而,3,1,=3,，即,(n+1),3,3,n,对于,n=2,，,(n+1),3,=3,3,=27,而,3,2,=9,，即,(n+1),3,3,n,对于,n=3,(n+1),3,=4,3,=64,而,3,3,=27,，即,(n+1),3,3,n,对于,n=4,(n+1),3,=5,3,=125,而,3,4,=81,，即,(n+1),3,3,n,对于论域中的每个,n,，都有,(n+1),3,3,n,34,分情况的证明法,例如，前提“,x,是一个实数”可以被分成两种情况：,(a)x,是一个非负实数,(b)x,是一个负实数。,例,1.5.14,证明对每个实数,x,，,x,|x|,。,证明：,当,x,0,时，根据绝对值的定义，,|x|,x,，于是,|x|,x,。当,x0,，,0 x,，所以,|x|x,。,两种情况下都有,|x|,x,，所以命题成立。,35,1.7.3,存在性证明,需在论域中找到一个,x,使,P(x),为真即可。,例,1.5.17,令,a,和,b,为实数且,ab,。证明存在实数,x,满足,axb,。,证明 只需找到一个实数,x,满足,axb,即可。实数,x,显然满足,ax0,的,x,都成立,下面来考虑,n+1,时的情况。,要证明的是对所有满足,1+x0,的,x,，,(1+x),n+1,1+(n+1)x,成立。,(1+x),n+1,=(1+x)(1+x),n,（根据归纳法）,(1+x)(1+nx),=1+(n+1)x+nx,2,1+(n+1)x,。,若,n,是自然数，且,1+x0,，则,(1+x),n,1+nx,47,例,2.4.7,覆盖问题,三联骨牌,n,是,2,的幂，,n*n,区域挖去一块，可以用三联骨牌覆盖剩余的区域,基本步,如果,k=1,，一个,22,缺块棋盘本身就是一个三联骨牌，所以可以用一个三联骨牌覆盖。,归纳步,假设可以覆盖一个,2,k,2,k,的缺块棋盘。要说明可以覆盖一个,2,k+1,2,k+1,的缺块棋盘。,考虑一个,2,k+1,2,k+1,的缺块棋盘。把棋盘分成,4,个,2,k,2,k,棋盘，旋转棋盘使缺失的方块处在左上区域。,48,49,50,51,本节复习,1.,叙述数学归纳法原理。,2.,解释数学归纳法证明是如何进行的。,