《推理与证明技术》PPT课件.ppt
《《推理与证明技术》PPT课件.ppt》由会员分享,可在线阅读,更多相关《《推理与证明技术》PPT课件.ppt(103页珍藏版)》请在装配图网上搜索。
离散数学,电子科技大学,计算机科学与工程学院示范性软件学院,2020年4月29日星期三,2020/4/29,第5章推理与证明技术,2020/4/29,5.1本章学习要求,2020/4/29,5.2命题逻辑的推理理论,2020/4/29,推理的有效性和结论的真实性,有效的推理不一定产生真实的结论;而产生真实结论的推理过程未必是有效的。有效的推理中可能包含为“假”的前提,而无效的推理却可能得到为“真”的结论。,2020/4/29,推理的有效性和结论的真实性,所谓推理有效,指的是它的结论是它的前提的合乎逻辑的结果。即,如果它的前提都为真,那么所得的结论也必然为真,而并不是要求前提或结论一定为真或为假;如果推理是有效的话,那么不可能它的前提都为真时,而它的结论为假。,2020/4/29,5.2.1推理的基本概念和推理形式,定义5.2.1设G1,G2,Gn,是公式,称H是G1,G2,Gn的逻辑结果(G1,G2,Gn共同蕴涵H),当且仅当H是G1G2Gn的逻辑结果(logicconclusion)。记G1,G2,Gn,此时称G1,G2,Gn为有效的(efficacious),否则称为无效的(inefficacious)。G1,G2,Gn称为一组前提(Premise),有时用集合来表示,记=G1,G2,Gn。H称为结论(conclusion)。又称H是前提集合的逻辑结果。记为H。,2020/4/29,判定定理,定理5.2.1公式H是前提集合=G1,G2,Gn的逻辑结果当且仅当G1G2Gn为永真公式。,证明:“”若G1,G2,Gn,但G1G2GnH不是永真式。于是,必存在G1,G2,Gn,H的一个解释I,使得G1G2Gn为真,而H为假,因此对于该解释I,有G1,G2,Gn都为真,而H为假,这就与推理形式G1,G2,Gn是有效的相矛盾.故:G1G2GnH是永真公式。,2020/4/29,判定定理(续),“”若G1G2GnH是永真式,但G1,G2,Gn不是有效的推理形式,故存在G1,G2,Gn,H的一个解释I,使得G1,G2,Gn都为真,而H为假,故G1G2Gn为真,而H为假,即是说G1G2GnH为假,这就与G1G2GnH是永真式相矛盾,所以G1,G2,Gn是有效的推理形式。,2020/4/29,“”与“”的不同,1.“”仅是一般的蕴涵联结词,GH的结果仍是一个公式,而“”却描述了两个公式G,H之间的一种逻辑蕴涵关系,GH的“结果”,是非命题公式;,2.用计算机来判断GH是办不到的。然而计算机却可“计算”公式GH是否为永真公式。,2020/4/29,5.2.2判断有效结论的常用方法,2020/4/29,1、真值表技术,设P1,P2,Pn是出现在前提G1,G2,Gn和结论H中的一切命题变元,如果将P1,P2,Pn中所有可能的解释及G1,G2,Gn,H的对应真值结果都列在一个表中,根据“”的定义,则有判断方法如下:,对所有G1,G2,Gn都具有真值T的行(表示前提为真的行),如果在每一个这样的行中,H也具有真值T,则H是G1,G2,Gn的逻辑结果。对所有H具有真值为F的行(表示结论为假的行),如果在每一个这样的行中,G1,G2,Gn中至少有一个公式的真值为F(前提也为假),则H是G1,G2,Gn的逻辑结果.,2020/4/29,例5.2.1,判断下列H是否是前提G1,G2的逻辑结果(1)H:Q;G1:P;G2:PQ;(2)H:P;G1:PQ;G2:Q;(3)H:Q;G1:P;G2:PQ。,解,2020/4/29,2推理定律,设G,H,I,J是任意的命题公式,则有:,I1:GHG(简化规则)I2:GHHI3:GGH(添加规则)I4:HGHI5:GGHI6:HGHI7:(GH)GI8:(GH)HI9:G,HGH,2020/4/29,2推理定律(续),6)I10:G,GHH(选言/析取三段论)I11:G,GHH7)I12:G,GHH(分离规则)8)I13:H,GHG(否定后件式)9)I14:GH,HIGI(假言三段论)10)I15:GH,GI,HII(二难推论),2020/4/29,例子,1)、前提:1.如果明天天晴,我们准备外出旅游。PQ2明天的确天晴。P结论:我们外出旅游。Q可描述为:PQ,PQ(分离规则)2)、前提:1.如果一个人是单身汉,则他不幸福。PQ2.如果一个人不幸福,则他死得早。QR结论:单身汉死得早。PR可描述为:PQ,QRPR(假言三段论),2020/4/29,例子(续1),3)、某人在某日晚归家途中被杀害,据多方调查确证,凶手必为王某或陈某,但后又查证,作案之晚王某在工厂值夜班,没有外出,根据上述案情可得:前提:1.凶手为王某或陈某。PQ2.如果王某是凶手,则他在作案当晚必外出PR3.王某案发之晚并未外出。R结论:陈某是凶手。Q则可描述为:PR,RP(否定后件式)PQ,PQ(选言三段论),2020/4/29,例子(续2),4)、前提:1.如果某同学为省二级以上运动员,则他将被大学录取。PR2.如果某同学高考总分在560分以上,则将被大学录取。QR3.某同学高考总分在560分以上或者是省二级运动员。PQ结论:该同学被大学录取。R则上述例子可描述为:PQ,PR,QRR(二难推论),2020/4/29,3演绎法,演绎法是从前提(假设)出发,依据公认的推理规则和推理定律,推导出一个结论来。,引入事实,2020/4/29,引入推理规则,在数理逻辑中,主要的推理规则有:P规则(称为前提引用规则):在推导的过程中,可随时引入前提集合中的任意一个前提;规则(逻辑结果引用规则):在推导的过程中,可以随时引入公式S,该公式S是由其前的一个或多个公式推导出来的逻辑结果。规则(附加前提规则):如果能从给定的前提集合与公式P推导出S,则能从此前提集合推导出PS。,2020/4/29,演绎的定义,定义5.2.2从前提集合推出结论H的一个演绎是指构造命题公式的一个有限序列:H1,H2,Hn其中,Hi或者是中的某个前提,或者是前面的某些Hj(jx。,推导1:(1)(x)(y)G(x,y)P(2)(y)G(y,y)US,(1),分析:推导1是错误的。正确的推导如下:(1)(x)(y)G(x,y)P(2)(y)G(z,y)US,(1),使用US规则消去量词,“y”在公式中必须是自由的。,2020/4/29,推理规则的正确使用(2),推导2:(1)(x)(y)G(x,y)P(2)(y)G(z,y)US,(1)(3)G(z,c)ES,(2),分析:推导2是错误的。正确的推导如下:(1)(x)(y)G(x,y)P(2)(y)G(z,y)US,(1)(3)G(z,f(z)ES,(2),使用ES规则消去量词,若还有其它自由变元,则必须用关于自由变元的函数符号来取代常量符号.,2020/4/29,推理规则的正确使用(3),推导3:(1)(y)G(z,y)P(2)(y)(y)G(y,y)UG,(1),分析:推导3是错误的。正确的推导如下:(1)(y)G(z,y)P(2)(z)(y)G(z,y)UG,(1),注意:使用UG规则来添加量词时,所使用的变元符号不能与辖域内的变元符号相同.,2020/4/29,推理规则的正确使用(4),推导4:(1)G(x,c)P(2)(x)G(x,x)EG,(2),分析:推导4是错误的。正确的推导如下:(1)G(x,c)P(2)(y)G(x,y)EG,(2),注意:使用EG规则来添加量词时,所使用的变元符号不能与辖域内的变元符号相同.,2020/4/29,5.3.2谓词演算的综合推理方法,(1)推导过程中可以引用命题演算中的规则P和规则T。(2)如果结论是以条件的形式(或析取形式)给出,我们还可以使用规则CP。(3)若需消去量词,可以引用规则US和规则ES。(4)当所要求的结论可能被定量时,此时可引用规则UG和规则EG将其量词加入。,2020/4/29,谓词演算的综合推理方法(续),(5)证明时可采用如命题演算中的直接证明方法和间接证明方法。(6)在推导过程中,对消去量词的公式或公式中不含量词的子公式,完全可以引用命题演算中的基本等价公式和基本蕴涵公式。(7)在推导过程中,对含有量词的公式可以引用谓词中的基本等价公式和基本蕴涵公式。,2020/4/29,例5.3.1,解设H(x):x是人;M(x):x是要死的;s:苏格拉底。则符号化为:(x)(H(x)M(x),H(s)M(s),证明苏格拉底三段论:“所有的人都是要死的;苏格拉底是人。所以苏格拉底是要死的。”,证明:(1)(x)(H(x)M(x)P(2)H(x)M(x)US,(1)(3)H(s)P(4)M(s)T,(2),(3),I,(4)错了!,2020/4/29,例5.3.1,解设H(x):x是人;M(x):x是要死的;s:苏格拉底。则符号化为:(x)(H(x)M(x),H(s)M(s),证明苏格拉底三段论:“所有的人都是要死的;苏格拉底是人。所以苏格拉底是要死的。”,正确证明:(1)(x)(H(x)M(x)P(2)H(s)M(s)US,(1)(3)H(s)P(4)M(s)T,(2),(3),I,2020/4/29,例5.3.2,证明:(x)(P(x)Q(x),(x)P(x)(x)Q(x),有下面的推导(正确与否?):(1)(x)(P(x)Q(x)P(2)(P(x)Q(x)US,(1)(3)(x)P(x)P(4)P(c)ES,(3)(5)Q(c)T,(2),(4),I(6)(x)Q(x)EG,(5),(4)中的“c”未必能保证令(2)为真,推导错误!,2020/4/29,例5.3.2(),推导可修改为(正确与否?):(1)(x)(P(x)Q(x)P(2)(P(c)Q(c)US,(1)(3)(x)P(x)P(4)P(c)ES,(3)(5)Q(c)T,(2),(4),I(6)(x)Q(x)EG,(5),证明:(x)(P(x)Q(x),(x)P(x)(x)Q(x),(2)中的“c”未必能保证令(4)为真,推导错误!,2020/4/29,例5.3.2(),正确推导如下:(1)(x)P(x)P(2)P(c)ES,(1)(3)(x)(P(x)Q(x)P(4)(P(c)Q(c)US,(3)(5)Q(c)T,(2),(4),I(6)(x)Q(x)EG,(5),证明:(x)(P(x)Q(x),(x)P(x)(x)Q(x),2020/4/29,例5.3.3,证明:1)(x)(P(x)Q(x)P2)(P(c)Q(c)ES,1)3)P(c)T,2),I4)Q(c)T,2),I5)(x)P(x)EG,3)6)(x)Q(x)EG,4)7)(x)P(x)(x)Q(x)T,5),6),I,证明:(x)(P(x)Q(x)(x)P(x)(x)Q(x),2020/4/29,例5.3.3(续1),1)(x)P(x)(x)Q(x)P2)(x)P(x)T,1),I3)P(c)ES,2)4)(x)Q(x)T,1),I5)Q(c)ES,4)6)(P(c)Q(c)T,3),4),I7)(x)(P(x)Q(x)EG,6),请看上述推论的逆推导(正确与否?):,证明:(x)(P(x)Q(x)(x)P(x)(x)Q(x),“c”未必能保证同时令(2)和(4)为真,推导错误!,2020/4/29,例5.3.3(续2),正确推导:1)(x)P(x)(x)Q(x)P2)(x)P(x)T,1),I3)P(c)ES,2)4)(x)Q(x)T,1),I5)Q(b)ES,4)6)(P(c)Q(b)T,3),4),I7)(x)(y)(P(x)Q(y)EG,6),(x)(P(x)Q(x)(x)P(x)(x)Q(x)的逆推导:,2020/4/29,例5.3.4,证明(采用反证法,CP规则的方法自己完成):1)(x)P(x)(x)Q(x)P(附加前提)2)(x)P(x)(x)Q(x)T,1),E3)(x)P(x)T,2),I4)(x)Q(x)T,2),I5)(x)P(x)T,3),E6)P(c)ES,5),证明(x)(P(x)Q(x)(x)P(x)(x)Q(x),2020/4/29,例5.3.4证明(续),6)P(c)ES,5)7)(x)Q(x)T,4),E8)Q(c)US,7)9)P(c)Q(c)T,6),8),I10)(P(c)Q(c)T,9),E11)(x)(P(x)Q(x)P12)(P(c)Q(c)US,11)13)(P(c)Q(c)(P(c)Q(c)T,10),12),证明(x)(P(x)Q(x)(x)P(x)(x)Q(x),2020/4/29,5.3.3谓词逻辑推理的难点,(1)在推导过程中,如既要使用规则US又要使用规则ES消去公式中的量词,而且选用的个体是同一个符号,则必须先使用规则ES,再使用规则US。然后再使用命题演算中的推理规则,最后使用规则UG或规则EG引入量词,得到所要的结论。(2)如一个变量是用规则ES消去量词,对该变量再添加量词时,则只能使用规则EG,而不能使用规则UG;如使用规则US消去量词,对该变量在添加量词时,则可使用规则EG和规则UG。,2020/4/29,谓词逻辑推理的难点(续),(3)如有两个含有存在量词的公式,当用规则ES消去量词时,不能选用同样的一个常量符号来取代两个公式中的变元,而应用不同的常量符号来取代它们。(4)在用规则US和规则ES消去量词时,此量词必须位于整个公式的最前端。,2020/4/29,谓词逻辑推理的难点(续),(5)在添加量词(x)、(x)时,所选用的x不能在公式G(c)或G(y)中以任何约束出现。(6)在使用EG规则引入存在量词(x),此x不得仅为G(c)或G(y)中的函数变元。在使用UG规则引入全称量词(x)时,此x不得为G(y)中的函数变元(因该函数变元不得作为自由变元)。,2020/4/29,5.3.4谓词逻辑推理的应用,例5.3.5每个喜欢步行的人都不喜欢坐汽车;每个人或者喜欢坐汽车或者喜欢骑自行车;有的人不喜欢骑自行车。因而有的人不喜欢步行。,证明设H(x):x是人;P(x):x喜欢坐汽车;Q(x):x喜欢骑自行车;R(x):x喜欢步行。则上述语句可符号化为:(x)(H(x)R(x)P(x),(x)(H(x)P(x)Q(x),(x)(H(x)Q(x)(x)(H(x)R(x),2020/4/29,例5.3.5证明(续),证:(1)(x)(H(x)Q(x)P(2)H(c)Q(c)ES,(1)(3)H(c)T,(2)(4)Q(c)T,(2)(5)(x)(H(x)P(x)Q(x)P(6)H(c)P(c)Q(c)US,(5)(7)P(c)Q(c)T,(3),(6),I(8)P(c)T,(4),(7),I,上述语句可符号化为:(x)(H(x)R(x)P(x),(x)(H(x)P(x)Q(x),(x)(H(x)Q(x)(x)(H(x)R(x),2020/4/29,例5.3.5证明(续),(3)H(c)T,(2)(8)P(c)T,(4),(7),I(9)(x)(H(x)R(x)P(x)P(10)H(c)R(c)P(c)US,(9)(11)(H(c)R(c)T,(8),(10),I(12)H(c)R(c)T,(11),E(13)R(c)T,(3),(12),I(14)H(c)R(c)T,(3),(13),I(15)(x)(H(x)R(x)EG,(14),上述语句可符号化为:(x)(H(x)R(x)P(x),(x)(H(x)P(x)Q(x),(x)(H(x)Q(x)(x)(H(x)R(x),2020/4/29,例5.3.6,证明下述论断的正确性:所有的哺乳动物都是脊椎动物;并非所有的哺乳动物都是胎生动物;故有些脊椎动物不是胎生的。证明设谓词如下:P(x):x是哺乳动物;Q(x):x是脊椎动物;R(x):x是胎生动物。则有:(x)(P(x)Q(x),(x)(P(x)R(x)(x)(Q(x)R(x),2020/4/29,请看下面推导:,1)(x)(P(x)R(x)P2)(P(x)R(x)US,1)3)(P(x)R(x)T,2),E4)(P(x)R(x)T,3),E5)P(x)T,4),I6)R(x)T,4),I7)(x)(P(x)Q(x)P8)P(x)Q(x)US,7)9)Q(x)T,(5),(8),I10)Q(x)R(x)T,6),9),I11)(x)(Q(x)R(x)EG,10)12)(x)(Q(x)R(x)UG,10),(x)(P(x)Q(x),(x)(P(x)R(x)(x)(Q(x)R(x),错误推导,2020/4/29,例5.3.6证明(续),1)(x)(P(x)R(x)P2)(x)(P(x)R(x)T,1),E3)(P(c)R(c)ES,2)4)(P(c)R(c)T,3),E5)P(c)T,4),I6)R(c)T,4),I7)(x)(P(x)Q(x)P8)P(c)Q(c)US,7)9)Q(c)T,5),8),I10)Q(c)R(c)T,6),9),I11)(x)(Q(x)R(x)EG,10),(x)(P(x)Q(x),(x)(P(x)R(x)(x)(Q(x)R(x),正确推导,2020/4/29,例5.3.7,证明下列论断的正确性:有些信徒相信所有的神父;任何一个信徒都不相信骗子;所以,神父都不是骗子。证明设谓词如下:S(x):x是信徒T(x):x是神父P(x):x是骗子L(x,y):x相信y则可符号化为:(x)(S(x)(y)(T(y)L(x,y),(x)(y)(S(x)P(y)L(x,y)(x)(T(x)P(x),2020/4/29,例5.3.7证明(续),1)(x)(S(x)(y)(T(y)L(x,y)P2)S(c)(y)(T(y)L(c,y)ES,1)3)S(c)T,2),I4)(y)(T(y)L(c,y)T,2),I5)T(x)L(c,x)US,4)6)(x)(y)(S(x)P(y)L(x,y)P7)(y)(S(c)P(y)L(c,y)US,6)8)(S(c)P(x)L(c,x)US,7),(x)(S(x)(y)(T(y)L(x,y),(x)(y)(S(x)P(y)L(x,y)(x)(T(x)P(x),2020/4/29,例5.3.7证明(续),3)S(c)T,2),I8)(S(c)P(x)L(c,x)US,7)9)S(c)(P(x)L(c,x)T,8),E10)P(x)L(c,x)T,3),8),E11)L(c,x)P(x)T,10),E12)T(x)P(x)T,5),11),E13)(x)(T(x)P(x)US,12),(x)(S(x)(y)(T(y)L(x,y),(x)(y)(S(x)P(y)L(x,y)(x)(T(x)P(x),2020/4/29,例5.3.8,现有一智力测验题目(水容器问题):设有两个分别能盛7升与5升的水容器,开始时两个容器均空,允许对容器做三种操作:(1)容器倒满水,(2)将容器中的水倒光,(3)从一个容器倒水至另一容器,使一个容器倒光而另一容器倒满。最后要求能使大容器(能盛7升的容器)中有4升水,并求其操作过程。,2020/4/29,例5.3.8的解决方案,2020/4/29,例5.3.8证明,(1)S(0,0)P(2)(x)(y)(S(x,y)S(7,y)P(3)(y)(S(0,y)S(7,y)US,(2)(4)S(0,0)S(7,0)US,(3)(5)S(7,0)T,(1),(4).I(6)(x)(y)(z)(S(x,y)S(z,5)P(7)(y)(z)(S(7,y)S(z,5)US,(6)(8)(z)(S(7,0)S(z,5)US,(7)(9)S(7,0)S(2,5)ES,(8),2020/4/29,例5.3.8证明(续),(10)S(2,5)T,(5),(9),I(11)(x)(y)(S(x,y)S(x,0)P(12)(y)(S(2,y)S(2,0)US,(11)(13)S(2,5)S(2,0)US,(12)(14)S(2,0)T,(10),(13),I(15)(x)(y)(z)(S(x,y)S(0,z)P(16)(y)(z)(S(2,y)S(0,z)US,(15)(17)(z)(S(2,0)S(0,z)US,(16),2020/4/29,例5.3.8证明(续),(18)(S(2,0)S(0,2)ES,(17)(19)S(0,2)T,(14),(18),I(20)(x)(y)(S(x,y)S(7,y)P(21)(y)(S(0,y)S(7,y)US,(20)(22)(S(0,2)S(7,2)US,(21)(23)S(7,2)T,(19),(22),I(24)(x)(y)(z)(S(x,y)S(z,5)P(25)(y)(z)(S(7,y)S(z,5)US,(24)(26)(z)(S(7,2)S(z,5)US,(25),2020/4/29,例5.3.8证明(续),(27)S(7,2)S(4,5)ES,(26)(28)S(4,5)T,(23),(27),I(29)(x)(y)(S(x,y)S(x,0)P(30)(y)(S(4,y)S(4,0)US,(29)(31)S(4,5)S(4,0)US,(30)(32)S(4,0)T,(30),(33),I,2020/4/29,5.4数学归纳法,5.4.1数学归纳法原理,假设要证明的命题能写成形式:nn0,有P(n)其中n0是某个固定的整数,即:希望证明对所有的整数nn0都有P(n)为真,2020/4/29,数学归纳法原理,假设1)验证nn0,有P(n0)为真;(归纳基础)2)假设对于nk(kn0),有P(k)为真;(归纳假设)3)证明nk1,有P(k+1)为真。(归纳结论)结论对所有的整数nn0,都有P(n)为真。,谓词表示:(n0)(P(n0)(n)(nk)P(k)P(k+1)1,2020/4/29,强形式数学归纳法原理,假设1)验证nn0、n0+1,有P(n0)、P(n0+1)为真;(归纳基础)2)假设对于nk(kn0),有P(n)为真;(归纳假设)3)证明nk1,有P(k+1)为真。(归纳结论)结论对所有的整数nn0,都有P(n)为真。,谓词表示:(n0)(P(n0)P(n0+1)(n)(nk)P(n)P(k+1)1,2020/4/29,例5.4.1,用数学归纳法证明:对所有n1,有1+2+3+n=,证明归纳基础验证1=显然P(1)真值为1;归纳假设假定对于n=k(k1),有P(k)为真,即有1+2+3+k=;,2020/4/29,例5.4.1,归纳结论证明对于nk1,有P(k+1)为真1+2+3+k+(k+1)=+(k+1)=由数学归纳法原理得到,P(n)对所有n1为真。,2020/4/29,例5.4.2,对每个正整数n1,能惟一地写成,其中pi是素数且满足p1p2Y)THEN1.XX-Yb.ELSE1.YY-X2.RETURN(X)ENDOFFUNCTIONGCD,2020/4/29,例5.4.3证明,归纳基础验证因为在循环开始之前存在变量值X0X,Y0Y,因此,P(0)是命题GCD(X0,Y0)=GCD(X,Y),显然命题为真;归纳假设假定设P(k)是命题GCD(Xk,Yk)=GCD(X,Y)为真;,2020/4/29,例5.4.3证明(续),归纳结论证明首先考虑P(k1)的左边,即GCD(Xk1,Yk1)。在通过k1次循环后,或者Xk1Xk和Yk1YkXk;或者Xk1XkYk和Yk1Yk;则由整数的基本性质知,P(k1)GCD(Xk1,Yk1)GCD(Xk,Yk)GCD(X,Y)。根据数学归纳法知:对所有n0,有P(n)为真。为此,该伪码程序输出的结果必是两个正整数的最大公因子。,2020/4/29,铺瓦问题,例5.4.4一个直角三正方形,是一个由三个正方形组成的对象,如图1所示。如果我们从nn(n为2的幂)正方形的板中去掉一个正方形,则余下的图形可用直角三正方形来铺成,如图2。此处的铺成是用直角三正方形正好覆盖全图的图形,每个直角三正方形不能有重叠,也不许超出图形之外。我们缺少一个正方形的板称为一个缺方板,把此问题称为铺瓦问题。,2020/4/29,铺瓦问题,2020/4/29,铺瓦问题证明(续),(归纳结论证明部分)对于2k12k1的缺方板问题,我们可以将其分成四个2k2k的板,如图所示。旋转此板,使缺少的正方形在左上的四分之一中。由归纳假设,此左上的2k2k缺方板可由直角三正方形铺成,把一个直角三正方形T放在中间,则另外三个四分之一都是2k2k的缺方板。由归纳假设,它们的铺瓦问题都是可以解决的。于是2k12k1的缺方板可由直角三正方形铺成。由数学归纳法知,对任何的n,nn正方形的铺瓦问题都是可以铺成的。,2020/4/29,5.5按定义证明方法,在离散数学中,我们大量的定义描述都是用蕴涵型“PQ”的方式来描述的。,如集合中子集的包含关系的定义描述为:集合AB(a)(aAaB),2020/4/29,5.5.1按定义证明方法原理,2020/4/29,5.5.2按定义证明方法应用,例5.5.1设A、B是两个任意集合,证明ABP(A)P(B),证明(1)必要性“”:对任意的xP(A),则xA,由于AB,所以xB,即有xP(B)。由CP规则知:P(A)P(B)。即ABP(A)P(B),2020/4/29,例5.5.1证明(续),(2)充分性“”:对任意的xA,则xP(A),由于P(A)P(B),所以xP(B),即有xB。由CP规则知:AB。即P(A)P(B)AB。原式得证。,2020/4/29,例5.5.2,如果AB,则ABB且ABA,证明两个集合相等,即是证明两个集合相互包含,请学生自证。,2020/4/29,作业,1.(2)2.(1)(6)3.(3)(5)57.(8)(9),- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 推理与证明技术 推理 证明 技术 PPT 课件
装配图网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
关于本文