离散数学课程组国家级课程课件.ppt

离 散 数 学,电子科技大学,计算机科学与工程学院示范性软件学院,2022年11月24日星期四,离 散 数 学电子科技大学计算机科学与工程学院24 九月 2,第5章 推理与证明技术,第5章 推理与证明技术 数学归纳法的使用 3CP规则相关证,5.1 本章学习要求,5.1 本章学习要求1掌握各种不同类型的规则和公理，特别是命,5.2 命题逻辑的推理理论,5.2 命题逻辑的推理理论 概念描述问题的句子；Add Y,推理的有效性和结论的真实性,有效的推理不一定产生真实的结论；而产生真实结论的推理过程未必是有效的。有效的推理中可能包含为“假”的前提，而无效的推理却可能得到为“真”的结论 。,推理的有效性和结论的真实性有效的推理不一定产生真实的结论；,推理的有效性和结论的真实性,所谓推理有效， 指的是它的结论是它前提的合乎逻辑的结果。 即，如果它的前提都为真，那么所得的结论也必然为真，而并不是要求前提或结论一定为真或为假； 如果推理是有效的话，那么不可能它的前提都为真时，而它的结论为假。,推理的有效性和结论的真实性所谓推理有效，,5.2.1 推理的基本概念和推理形式,定义5.2.1 设G1, G2, ,Gn,是公式，称H是G1, G2, ,Gn的逻辑结果(G1, G2, ,Gn共同蕴涵H)，当且仅当H 是G1G2Gn的逻辑结果(logic conclusion)。记为G1, G2, ,Gn ，此时称G1, G2, ,Gn 为有效的(efficacious)，否则称为无效的（inefficacious）。G1, G2, ,Gn称为一组前提(Premise)，有时用集合来表示，记 = G1, G2, ,Gn。H称为结论(conclusion)。又称H是前提集合的逻辑结果。记为 H。,5.2.1 推理的基本概念和推理形式 定义5.2.1 设G,判定定理,定理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是永真公式。,判定定理定理5.2.1 公式H是前提集合=G1, G2,判定定理（续）,“”若G1G2GnH是永真式，但G1, G2, ,Gn 不是有效的推理形式，故存在G1, G2, ,Gn, H的一个解释I，使得G1, G2, ,Gn都为真，而H为假，故G1G2Gn为真，而H为假，即是说G1G2GnH为假，这就与G1G2GnH是永真式相矛盾，所以G1, G2, ,Gn 是有效的推理形式。,判定定理（续） “”若G1G2GnH是永真,“”与“”的不同,1.“”仅是一般的蕴涵联结词，GH的结果仍是一个公式，而“”却描述了两个公式G，H之间的一种逻辑蕴涵关系，G H的“结果”，是非命题公式；,2. 用计算机来判断G H是办不到的。然而计算机却可“计算”公式GH是否为永真公式。,“”与“”的不同1.“”仅是一般的蕴涵联结词，GH的,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的逻辑结果.,1、真值表技术 设P1,P2,Pn是出现在前提G1,例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。,解,例5.2.1 判断下列H是否是前提G1,G2的逻辑结果解PQ,5.2.2 判断有效结论的常用方法,5.2.2 判断有效结论的常用方法 要求=G1, G2,离散数学课程组国家级课程课件,设G，H，S是任何的公式，则：,基本等价公式,1：G(HS)(GH)S(结合律)2: G(HS)(GH)S3：GHHG (交换律)4：GHHG5：GGG (幂等律)6：GGG7：G(GH) G (吸收律)8：G(GH) G,设G，H，S是任何的公式，则：基本等价公式1：G(HS,9：G(HS)(GH)(GS)(分配律） 10：G(HS)(GH)(GS)11：GG(同一律) 12：GG 13：G(零律) 14：G15：GG (排中律)16：GG (矛盾律),基本等价公式（续）,9：G(HS)(GH)(GS)(分配律）基本,基本等价公式（续）,17：(G)G(双重否定律)18：(GH)GH(De MoRGan定律) 19：(GH)GH20: (GH)(GH)(HG)(等价式)21：(GH)(GH)(蕴涵式)E22： GG(假言易位)E23： GG(等价否定等式)E24： (G)(G)G(归谬论),基本等价公式（续）17：(G)G(双重否定律),5.2.2 判断有效结论的常用方法,5.2.2 判断有效结论的常用方法 要求=G1, G2,真值表技术,真值表技术G1G2G3GnH0101001011101001,2 推理定律,设G，H，I，J是任意的命题公式，则有：,I1：GHG(简化规则)I2：GHHI3：GGH(添加规则)I4：HGHI5：GGHI6：HGHI7：(GH)GI8：(GH)HI9：G,HGH,2 推理定律设G，H，I，J是任意的命题公式，则有：I1：,2 推理定律(续),6）I10：G,GHH (选言三段论) I11：G,G HH7）I12：G,GHH(分离规则)8）I13：H,GHG(否定后件式)9）I14：GH,HIGI(假言三段论)10）I15：GH,GI,HII (二难推论),2 推理定律(续)6）I10：G,GHH,例子,1)、前提：1. 如果明天天晴，我们准备外出旅游。PQ2明天的确天晴。P结论：我们外出旅游。Q可描述为：PQ，PQ(分离规则)2)、前提：1.如果一个人是单身汉，则他不幸福。PQ2.如果一个人不幸福，则他死得早。QR结论：单身汉死得早。 PR可描述为：PQ，QRPR(假言三段论),例子1)、前提：,例子(续1),3)、某女子在某日晚归家途中被杀害，据多方调查确证，凶手必为王某或陈某，但后又查证，作案之晚王某在工厂值夜班，没有外出，根据上述案情可得前提：1.凶手为王某或陈某。PQ 2.如果王某是凶手，则他在作案当晚必外出PR 3.王某案发之晚并未外出。 R结论：陈某是凶手。Q则可描述为：PR,RP(否定后件式) PQ，PQ(选言三段论),例子(续1)3)、某女子在某日晚归家途中被杀害，据多方调查确,例子(续2),4)、前提：1.如果某同学为省二级以上运动员，则他将被大学录取。PR2.如果某同学高考总分在560分以上，则将被大学录取。QR3.某同学高考总分在560分以上或者是省二级运动员。PQ 结论：该同学被大学录取。R 则上述例子可描述为： PQ，PR，QRR(二难推论),例子(续2)4)、前提：,3 演绎法,演绎法是从前提(假设)出发，依据公认的推理规则和推理定律，推导出一个结论来。,3 演绎法 演绎法是从前提(假设)出发，依据公,引入推理规则,在数理逻辑中，主要的推理规则有： P规则（称为前提引用规则）：在推导的过程中，可随时引入前提集合中的任意一个前提； 规则（逻辑结果引用规则）：在推导的过程中，可以随时引入公式S，该公式S是由其前的一个或多个公式推导出来的逻辑结果。 规则（附加前提规则）：如果能从给定的前提集合与公式P推导出S，则能从此前提集合推导出PS。,引入推理规则在数理逻辑中，主要的推理规则有：,演绎的定义,定义5.2.2 从前提集合推出结论H的一个演绎是构造命题公式的一个有限序列： H1，H2，Hn 其中，Hi或者是中的某个前提，或者是前面的某些Hj（ji）的有效结论，并且Hn就是H，则称公式H为该演绎的有效结论，或者称从前提能够演绎出结论H来。,演绎的定义定义5.2.2,例5.2.2 设前提=PQ,PR,QS,G=SR。证明G。,例5.2.2,证明G的方法 ？,（1）建立公式PQ, PR, QS, SR的真值表，利用真值表技术，判断前提与结论之间是否有逻辑关系；（2）利用公式的等价转换，判断公式(PQ)(PR)(QS)(SR)是否是永真公式；（3）任取解释I，若I满足(PQ)(PR)(QS)，证明I满足(SR)；（4）利用演绎法中的直接证明方法，证明如何从前提演绎出结论；（5）由于结论为(SR)，而SRSR，为此可以采取引入附加前提S，采用CP规则，利用演绎法证明如何从前提演绎出结论。,证明G的方法 ？（1）建立公式PQ, PR, Q,例5.2.2,证明1 PQP PQT,(1),E QSP PST,I SPT,E PRP (PR)(RP) ,E PR ,I SR T,I SRT,(9),E,设前提=PQ,PR,QS,G=SR。证明G。,例5.2.2 证明1 PQP设前提=P,证明2 SP(附加前提) QSP QT,I PQP PT,I PR P (PR)(RP) ,E PR,I R T,I SR CP, SR T, ,E,设前提=PQ,PR,QS,G=SR。证明G。,证明2 SP(附加前提)设前提=PQ,P,例5.2.3,证 RP(附加前提)RPPPT,IP(QS)PQST,IQPST,IRSCP,设=P(QS),RP,Q,G=RS。证明：G。,例5.2.3证 RP(附加前提)设=P(Q,4 间接证明法（反证法）,前面使用过的一些证明方法都是正向推理。但在数学领域中，经常会遇到一些问题，当采用正向推理时很难从前提为真推出结论为真。,PQ等价于QP，因此，为了间接地证明PQ，可以假设Q为假(Q)，然后证明P为假(P)。,4 间接证明法（反证法） 前面使用过的一些证明方法,例5.2.4,设n是一个整数，证明：如果n2是奇数，那么n是奇数。,证明 设n是偶数，则n2k，这里k是一个整数。于是有： n2(2k)2=4k2=2(2k2)所以n2是偶数。 因而证明了若n是偶数，则n2是偶数，它是已知命题的逆否式。因此，证明了所给的命题。,例5.2.4 设n是一个整数，证明：如果n2是奇数，那么,定义5.2.3, 假设G1,G2,Gn是一组命题公式，P1,P2,Pn是出现在中的一切命题变元，I是它的任意解释，若有解释I使G1G2Gn取值为“真”，则称公式G1,G2,Gn是一致的，或者说是相容的。 如对任意的解释I，都有G1G2Gn取值为“假”,则称公式G1,G2,Gn是不一致的。或者说G1G2Gn是一个矛盾式。,G1G2Gn是矛盾式当且仅当G1G2Gn,其中，R可为任意公式，RR为一矛盾式。,定义5.2.3 假设G1,G2,Gn是一组命题公式，,间接证明方法,将结论的否定加入到前提集合中构成一组新的前提，然后证明这组新的前提集合是不相容的，即蕴涵一个矛盾式。G1,G2,Gn,H RR,定理5.2.2 设命题公式集合G1,G2,Gn是一致的，于是从前提集合出发可以逻辑地推出公式H的充要条件是从前提集合G1,G2,Gn ，H出发，可以逻辑地推出一个矛盾（永假）式来。,间接证明方法将结论的否定加入到前提集合中构成一组新的前提，然,例5.2.5,证明不存在有理数p/q其平方为2，即，证明 是无理数。,证明 对某两个整数p和q，假设(p/q)2=2成立，并且p和q没有公因子。如果原来选择的p/q不是最小项，则可以用它等价的最小项形式来取代它。 于是p2=2q2，所以p2是偶数，这就推出p是偶数，因为一个奇数的平方是奇数。,例5.2.5证明不存在有理数p/q其平方为2，即，证明,例5.2.5 证明（续）,因此存在某个整数n使得p2n成立。因此2q2p2(2n)2=4n2， 即有q2=2n2，所以q2是偶数，从而q是偶数，于是得到p和q都是偶数，故它们有一个公因子2，这与假设相矛盾。 因此假设一定为假。,例5.2.5 证明（续） 因此存在某个整数n使得p2n成,例5.2.6,用反证法证明二难推论 PQ，PR，QRR,证明 PR P R (附加前提) P T,I QR P Q T,I PQ P ,I PP ,I,例5.2.6用反证法证明二难推论 PQ，PR，QR,三种证明方法之间的关系,G1,G2,Gn, G1,G2,Gn () G1,G2,Gn() G1,G2,Gn,反证法CP规则证明法直接证明法,三种证明方法之间的关系 G1,G2,Gn,5.2.3 命题逻辑推理的难点,1、弄清楚蕴涵式PQ的逻辑关系及其真值，这里Q是P的必要条件。无论蕴涵关系如何表述，都要仔细地区分出蕴涵式的前件和后件。2、推理过程中推理规则、基本等值式和逻辑蕴涵式的引用要适当，逻辑思维要清晰。,5.2.3 命题逻辑推理的难点 1、弄清楚蕴涵式PQ的逻,5.2.3 命题逻辑推理的难点,3、弄清楚几种推理方法的区别与联系，对于命题逻辑推理而言，任何一个问题的推理，都可以采取三种推理方法中的任何一种来证明，针对不同的问题选用不同的推理方法。一般而言，对于结论是蕴涵式或析取式的，大多可以采取带CP规则的直接证明方法。,5.2.3 命题逻辑推理的难点 3、弄清楚几种推理方法的区,5.2.4 命题逻辑推理的应用,例5.2.7 符号化下面的语句，并用演绎法证明结论是否有效。 或者明天下午是天晴，或者是下雨；如果明天下午是天晴，则我将去看电影；如果我去看电影，我就不看书。如果我看书，则天在下雨。,设P：明天下午天晴； Q：明天下午下雨； R：明天下午去看电影；S：明天下午看书。 则上述命题可符号化为： P Q，PR，RS SQ。,5.2.4 命题逻辑推理的应用 例5.2.7 符号化下面,例5.2.7 证明,（1）S P (附加前提) （2）RS P （3）R ，（1），（2），I （4）PR P （5）P ，（3），（4），I （6）P Q （7）Q ，（4），（7），I,例5.2.7 证明 （1）S,例5.2.8,一个公安人员审查一件盗窃案，已知的事实如下： A或B盗窃了x； 若A盗窃了x，则作案时间不能发生在午夜前； 若B证词正确，则在午夜时屋里灯光未灭； 若B证词不正确，则作案时间发生在午夜前； 午夜时屋里灯光灭了。B盗窃了x。,例5.2.8一个公安人员审查一件盗窃案，已知的事实如下：,例5.2.8 证明,设 P：A盗窃了x；Q：B盗窃了x； R：作案时间发生在午夜前； S：B证词正确； T：在午夜时屋里灯光未灭。 则上述命题可符号化为：PQ，PR，ST，SR，T Q,例5.2.8 证明 设 P：A盗窃了x；Q：B盗窃了x；,例5.2.8 证明（续）,证明1 采用直接证明方法（反证法请学生完成） （1）T （2）ST （3）S ，（1），（2），I （4）SR （5）R ，（3），（4），I （6）PR P （7）P ，（5），（6），I （8）PQ （9）Q ，（7），（8），I,例5.2.8 证明（续）证明1 采用直接证明方法（反证法请,回顾,1、推理规则：P： 前提T： 中间结论CP： PQ E24：I15：,回顾1、推理规则：,2、三种证明方法,G1,G2,Gn G1,G2,Gn,直接证明法反证法CP规则证明法,G1,G2,Gn (),2、三种证明方法 G1,G2,Gn直接证明法G1,证明 令 P：马会飞；Q：羊吃草； R：母鸡是飞鸟； S：烤熟的鸭子会跑。符号化上述语句为：=PQR,RS,S,G=Q。证明G。,如果马会飞或羊吃草，则母鸡就会是飞鸟；如果母鸡是飞鸟，那么烤熟的鸭子还会跑；烤熟的鸭子不会跑。所以羊不吃草。,例5.2.8,证明 令 P：马会飞；Q：羊吃草；如果马会飞或羊吃草，则母,例5.2.8 证明 （续）,S PRS PR T,IPQR P(PQ) T,IPQ T,EQ T,I,例5.2.8 证明 （续）S,5.3 谓词逻辑的推理理论,5.3.1 谓词演算的演绎与推理,定义5.3.1 设G1, G2, ,Gn,是公式，称H是G1, G2, ,Gn的逻辑结果(G1, G2, ,Gn共同蕴涵H)，当且仅当H 是G1G2Gn的逻辑结果(logic conclusion)。记为G1, G2, ,Gn ，此时称G1, G2, ,Gn 为有效的(efficacious)，否则称为无效的（inefficacious）。G1, G2, ,Gn称为一组前提(Premise)，有时用集合来表示，记 = G1, G2, ,Gn。H称为结论(conclusion)。又称H是前提集合的逻辑结果。记为 H。,5.3 谓词逻辑的推理理论 5.3.1 谓词演算的演绎与,定理5.3.1,定理5.3.1 公式H是前提集合=G1, G2, ,Gn的逻辑结果当且仅当G1G2Gn为有效公式。,定理5.3.1 定理5.3.1 公式H是前提集合=G1,谓词演算中的有效公式,（1）E25：(x)G(x) = (y)G(y)； E26：(x)G(x) = (y)G(y)； -(改名规则) （2）E27： (x)G(x) = (x)G(x)； E28：(x)G(x) = (x)G(x)； - (量词转换律/量词否定等值式),谓词演算中的有效公式 （1）E25：(x)G(x) = (,谓词演算中的有效公式（续）,（3）E29：(x)(G(x)S) = (x)G(x)S； E30：(x)(G(x)S) = (x)G(x)S； E31：(x)(G(x)S) = (x)G(x)S； E32：(x)(G(x)S) = (x)G(x)S； - (量词辖域的扩张与收律),谓词演算中的有效公式（续）,谓词演算中的有效公式,（4）E33：(x)(G(x)H(x) =(x)G(x)(x)H(x)； E34：(x)(G(x)H(x) =(x)G(x)(x)H(x)； (量词分配律)（5）E35：(x)G(x)(x)H(x) =(x)(y)(G(x)H(y)； E36：(x)G(x)(x)H(x) =(x)(y)(G(x)H(y)；,注意： (x)(G(x)H(x) =(x)G(x)(x)H(x)；,谓词演算中的有效公式（4）E33：(x)(G(x)H(x,一 推理规律,（1）I16：(x)G(x) (x)G(x)；（2）I17：(x)G(x)(x)H(x)(x)(G(x)H(x) I18：(x)(G(x)H(x)(x)G(x)(x)H(x)（3）I19：(x)(G(x)H(x)(x)G(x)(x)H(x) I20：(x)(G(x)H(x)(x)G(x)(x)H(x),一 推理规律（1）I16：(x)G(x) (x)G(,推理规律（续）,（4）I21：(x)(y)G(x,y) (y)(x)G(x,y)； I22：(x)(y)G(x,y) (y)(x)G(x,y)； I23：(y)(x)G(x,y) (x)(y)G(x,y)； I24：(y)(x)G(x,y) (x)(y)G(x,y)； I25：(x)(y)G(x,y) (y)(x)G(x,y)；,推理规律（续）（4）I21：(x)(y)G(x,y) ,二 推理规则,1、US（全称特指规则，Universal Specify）： (x)G(x) G(y)，其中G(x)对y是自由的 推广： (x)G(x) G(c)，其中c为任意个体常量,2、ES（存在特指规则， Existential Specify ）： (x)G(x) G(c)，其中c为特定个体常量,二 推理规则1、US（全称特指规则，Universal S,推理规则（续）,3、UG（全称推广规则， Universal Generalize ）： G(y) (x)G(x)，其中G(y)对x是自由的,4、EG（存在推广规则， Existential Generalize ）： G(c) (x)G(x)，其中c为特定个体常量 推广： G(y) (x)G(x)，其中G(y)对x是自由的,推理规则（续）3、UG（全称推广规则， Universal,4.4.2 Skolem标准型,定义4.4.2 设公式G是一个前束范式，如消去G中所有的存在量词和全称量词，所得到的公式称为Skolem标准型。,定理4.4.2 任意一个公式G都有相应的Skolem标准形存在，但此Skolem标准形不一定与原公式等值。,4.4.2 Skolem标准型 定义4.4.2 设公式G,例4.4.2,求公式(x)(y)(z)(u)(v)(w)P(x, y, z, u, v, w)的Skolem标准型。,消去(y),消去(x),(y)(z)(u)(v)(w)P(a, y, z, u, v, w),(z)(u)(v)(w)P(a, y, z, u, v, w),消去(z),(u)(v)(w)P(a, y, z, u, v, w),(x)(y)(z)(u)(v)(w)P(x,y,z,u,v,w),消去(w),(v)(w)P(a, y, z, f(y,z), v, w),消去(u),(w)P(a, y, z, f(y,z), v, w),P(a, y, z, f(y,z), v, g(y,z,v),消去(v),解,例4.4.2求公式(x)(y)(z)(u)(v)(,推理规则的正确使用(1),例5.3.1 设实数集中，语句“不存在最大的实数”可符号化为： (x)(y)G(x, y)。 其中：G(x, y)：yx。,推导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规则来消去量词时，所选用取代x的变元y在公式中必须是自由的。,推理规则的正确使用(1)例5.3.1 设实数集中，语句“不,推理规则的正确使用（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规则来消去量词时， 若还有其它自由变元时，则必须用关于自由变元的函数符号来取代常量符号.,推理规则的正确使用（2）推导2：分析：推导2是错误的。正确的,推理规则的正确使用（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规则来添加量词时， 所使用的变元符号不能与辖域内的变元符号相同.,推理规则的正确使用（3）推导3：分析：推导3是错误的。正确的,推理规则的正确使用（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规则来添加量词时， 所使用的变元符号不能与辖域内的变元符号相同.,推理规则的正确使用（4）推导4：分析：推导4是错误的。正确的,5.3.2 谓词演算的综合推理方法,（1）推导过程中可以引用命题演算中的规则P 和规则T 。（2）如果结论是以条件的形式(或析取形式)给出，我们还可以使用规则CP。（3）若需消去量词，可以引用规则US和规则ES。（4）当所要求的结论可能被定量时，此时可引用规则UG和规则EG将其量词加入。,5.3.2 谓词演算的综合推理方法（1）推导过程中可以引用,谓词演算的综合推理方法（续）,（5）证明时可采用如命题演算中的直接证明方法和间接证明方法。（6）在推导过程中，对消去量词的公式或公式中不含量词的子公式，完全可以引用命题演算中的基本等价公式和基本蕴涵公式。（7）在推导过程中，对含有量词的公式可以引用谓词中的基本等价公式和基本蕴涵公式。,谓词演算的综合推理方法（续）（5）证明时可采用如命题演算中的,例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,证明：(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,(4)错了！正确的为,例5.3.1 解 设H(x)：x是人；M(x)：x是要死的；,例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),错!,例5.3.2 证明：有下面的推导：错!,例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),还错!,c=5,c=3,例5.3.2（)推导可修改为：还错!c=5c=3,例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),例5.3.2()正确地推导如下：,例5.3.3 ,证明：1)(x)(P(x)Q(x)P 2)(P(c)Q(c) ES,1) 3)P(c)T,2),I 4)Q(c)T,2),I 5)(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),例5.3.3 证明：1)(x)(P(x)Q(x),例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),请看上述推论的逆推导：,错!,P(x):x喜欢踢足球；Q(x)：x喜欢跳舞,例5.3.3(续1)1)(x)P(x)(x)Q(x),例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),例5.3.3(续2)正确地推导：,例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),例5.3.4 证明(采用反证法，CP规则的方法由学生完成)：,例5.3.4 证明（续）,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),例5.3.4 证明（续） 7) (x)Q(x),5.3.3 谓词逻辑推理的难点,（1）在推导过程中，如既要使用规则US又要使用规则ES消去公式中的量词，而且选用的个体是同一个符号，则必须先先使用规则ES，再使用规则US。然后再使用命题演算中的推理规则，最后使用规则UG或规则EG引入量词，得到所要的结论。（2）如一个变量是用规则ES消去量词，对该变量在添加量词时，则只能使用规则EG，而不能使用规则UG；如使用规则US消去量词，对该变量在添加量词时，则可使用规则EG和规则UG。,5.3.3 谓词逻辑推理的难点（1）在推导过程中，如既要使,谓词逻辑推理的难点（续）,（3）如有两个含有存在量词的公式，当用规则ES消去量词时，不能选用同样的一个常量符号来取代两个公式中的变元，而应用不同的常量符号来取代它们。（4）在用规则US和规则ES消去量词时，此量词必须位于整个公式的最前端。,谓词逻辑推理的难点（续）（3）如有两个含有存在量词的公式，当,谓词逻辑推理的难点（续）,（5）在添加量词(x)、(x)时，所选用的x不能在公式G(c)或G(y)中以任何约束出现。（6）在使用EG规则引入存在量词(x)，此x不得仅为G(c)或G(y)中的函数变元。在使用UG规则引入全称量词(x)时，此x不得为G(y)中的函数变元(因该函数变元不得作为自由变元)。,谓词逻辑推理的难点（续）（5）在添加量词(x)、(x)时,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),5.3.4 谓词逻辑推理的应用例5.3.5 每个喜欢步行,例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,例5.3.5 证明（续） (1)(x)(H(x)Q(,例5.3.5 证明（续）,(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),例5.3.5 证明（续） (9) (x)(H(x)R(x,例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),例5.3.6 证明下述论断的正确性：,请看下面推导：,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)没有位于整个公式的最前端！,请看下面推导：1) (x)(P(x)R(x)P错!,例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),例5.3.6 证明（续）1) (x)(P(x)R(x),例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),例5.3.7 证明下列论断的正确性：,例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),例5.3.7 证明（续） 1) (x)(S(x)(y),例5.3.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),例5.3.7 证明（续）9) S(c)(P(x)L(,5.4 数学归纳法,5.4.1 数学归纳法原理,假设要证明的命题能写成形式:nn0，有P(n) 其中n0是某个固定的整数，即：希望证明对所有的整数nn0都有P(n)为真,5.4 数学归纳法 5.4.1 数学归纳法原理假设要证明,数学归纳法原理,假设 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 其中(kn0),数学归纳法原理假设 谓词表示：,例5.4.1,用数学归纳法证明： 对所有n1，有1+2+3+n=,证明 归纳基础验证 1= 显然P(1)真值为1； 归纳假设假定 对于n=k(k1)，有P(k)为真，即有 1+2+3+k= ；,例5.4.1用数学归纳法证明：证明 归纳基础验证,例5.4.1,归纳结论证明 对于nk1，有P(k+1)为真 1+2+3+k+(k+1)= +(k+1) =由数学归纳法原理得到，P(n)对所有n1为真。,例5.4.1归纳结论证明 对于nk1，有P(k+1),5.5 按定义证明方法,在离散数学中，我们大量的定义描述都是用蕴涵型“PQ”的方式来描述的。,如集合中子集的包含关系的定义描述为： 集合A B (a)(aAaB),5.5 按定义证明方法 在离散数学中，我们,5.5.1 按定义证明方法原理,5.5.1 按定义证明方法原理加上题目中的已知证明问题H中,5.5.2 按定义证明方法应用,例5.5.1 设A、B是两个任意集合，证明 A B P(A) P(B),证明 （1）必要性“”： 对任意的xP(A)，则x A，由于A B，所以x B，即有xP(B)。由CP规则