《推理与证明技术课件》由会员分享，可在线阅读，更多相关《推理与证明技术课件（103页珍藏版）》请在金锄头文库上搜索。
1、电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程离 散 数 学电子科技大学计算机科学与工程学院示 范 性 软 件 学 院18 18 九月九月 2024 2024电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2第第5 5章章 推理与证明技术推理与证明技术 数学归纳法的使用数学归纳法的使用 3CPCP规则相关证明规则相关证明4命题逻辑的推理理论命题逻辑的推理理论 1谓词逻辑的推理理论谓词逻辑的推理理论 2电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程35.1 5.1 本章学习要求本章学习要求1掌握各种不同掌握各
2、种不同类型的规则和类型的规则和公理，特别是公理，特别是命题逻辑和谓命题逻辑和谓词逻辑的推理词逻辑的推理规则和公理规则和公理 3理解谓词逻辑理解谓词逻辑的精髓，将其的精髓，将其思想贯穿于所思想贯穿于所有的证明之中有的证明之中 2熟练掌握不同熟练掌握不同证明方法的证证明方法的证明原理、不同明原理、不同的应用场景的应用场景 重点掌握重点掌握一般掌握一般掌握了解了解电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程45.2 5.2 命题逻辑的推理理论命题逻辑的推理理论 概念概念描述问题描述问题的句子；的句子；Add Your Text判断判断对概念的肯对概念的肯定与否定的定与
3、否定的判断；判断；推理推理从一个或多从一个或多个前提推出个前提推出结论的思维结论的思维过程。过程。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程5推理的有效性和结论的真实性推理的有效性和结论的真实性有效的推理不一定产生真实的结论有效的推理不一定产生真实的结论；而而产生真实结论的推理过程未必是有效的产生真实结论的推理过程未必是有效的。有效的推理有效的推理中可能包含为中可能包含为“假假”的前提的前提，而而无效的推理无效的推理却可能得到为却可能得到为“真真”的结论的结论 。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程6推理的有效性和结论的
4、真实性推理的有效性和结论的真实性所谓所谓推理有效推理有效， 指的是指的是它的结论是它的前提的合乎逻辑的结果它的结论是它的前提的合乎逻辑的结果。 即，如果它的即，如果它的前提都为真，那么所得的结论也前提都为真，那么所得的结论也必然为真必然为真，而并不是要求前提或结论一定为真或为，而并不是要求前提或结论一定为真或为假；假； 如果推理是有效的话，那么不可能它的前提都为如果推理是有效的话，那么不可能它的前提都为真时，而它的结论为假。真时，而它的结论为假。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程75.2.1 5.2.1 推理的基本概念和推理形式推理的基本概念和推理形式
5、 定义定义5.2.15.2.1 设设G G1 1, G, G2 2, ,G, ,Gn n, ,是公式，称是公式，称H H是是G G1 1, G, G2 2, ,G, ,Gn n的逻辑结果的逻辑结果(G(G1 1, G, G2 2, ,G, ,Gn n共同蕴涵共同蕴涵H)H)，当且仅当当且仅当H H 是是G G1 1GG2 2GGn n的逻辑结果的逻辑结果(logic conclusion)(logic conclusion)。 记记G G1 1, G, G2 2, ,G, ,Gn n ，此时称，此时称G G1 1, G, G2 2, ,G, ,Gn n 为为有有效的效的(efficacious
6、)(efficacious)，否则称为，否则称为无效的无效的（inefficaciousinefficacious）。）。 G G1 1, G, G2 2, ,G, ,Gn n称为一组前提称为一组前提(Premise)(Premise)，有时用集合，有时用集合来来表示，记表示，记 = G = G1 1, G, G2 2, ,G, ,Gn n 。H H称为称为结论结论(conclusion)(conclusion)。又称又称H H是前提集合的逻辑结果。记为是前提集合的逻辑结果。记为 H H。 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程8判定定理判定定理定理定理5
7、.2.15.2.1 公式公式H H是前提集合是前提集合=G=G1 1, G, G2 2, , G, , Gn n 的逻辑结果的逻辑结果当且仅当当且仅当G G1 1GG2 2GGn n为永真公为永真公式。式。 证明：证明：“”若若G G1 1, G, G2 2, ,G, ,Gn n ，但，但G G1 1GG2 2GGn nHH不是永真式。不是永真式。于是，必存在于是，必存在G G1 1, G, G2 2, ,G, ,Gn n，H H的一个解释的一个解释I I，使得，使得G G1 1GG2 2GGn n为真，而为真，而H H为假，因此对于该解释为假，因此对于该解释I I，有，有G G1 1, G,
8、 G2 2, ,G, ,Gn n都为真，而都为真，而H H为假，这就与推理形式为假，这就与推理形式G G1 1, , G G2 2, ,G, ,Gn n 是有效的相矛盾是有效的相矛盾. .故：故：G G1 1GG2 2GGn nHH是永真公式。是永真公式。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程9判定定理（续）判定定理（续） “”若若G G1 1GG2 2GGn nHH是永真式，但是永真式，但G G1 1, , G G2 2, ,G, ,Gn n 不是有效的推理形式，不是有效的推理形式， 故存在故存在G G1 1, G, G2 2, ,G, ,Gn n, H
9、, H的一个解释的一个解释I I，使，使得得G G1 1, G, G2 2, ,G, ,Gn n都为真，而都为真，而H H为假，故为假，故G G1 1GG2 2GGn n为真，而为真，而H H为假，即是说为假，即是说G G1 1GG2 2GGn n H H为假，这为假，这 就与就与G G1 1GG2 2GGn nHH是永真式相矛盾，是永真式相矛盾， 所以所以G G1 1, G, G2 2, ,G, ,Gn n 是有效的推理形式。是有效的推理形式。 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程10“”与与“”“”的不同的不同1.1.“”“”仅是一般的仅是一般的蕴涵
10、联结词蕴涵联结词，GHGH的结果仍是一个公的结果仍是一个公式，式， 而而“”却描述了两个公式却描述了两个公式G G，H H之间的一种逻辑蕴涵之间的一种逻辑蕴涵关系，关系，G G H H的的“结果结果”，是非命题公式；，是非命题公式；2.2. 用计算机来判断用计算机来判断G G H H是办不到的。是办不到的。 然而计算机却可然而计算机却可“计算计算”公式公式GHGH是否为永真是否为永真公式。公式。 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程115.2.2 5.2.2 判断有效结论的常用方法判断有效结论的常用方法 要求要求=G G1 1, G, G2 2, ,G,
11、 ,Gn n H H也就是也就是G G1 1GG2 2GGn n为永真公式为永真公式因而因而真值表技术、演绎法和真值表技术、演绎法和间接证明方法间接证明方法电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程121 1、真值表技术、真值表技术 设设P P1 1,P,P2 2,P,Pn n是出现在前提是出现在前提G G1 1,G,G2 2,G,Gn n和结和结论论H H中的一切命题变元，中的一切命题变元， 如果将如果将P P1 1,P,P2 2,P,Pn n中所有可能的解释及中所有可能的解释及G G1 1,G,G2 2,G,Gn n，H H的对应真值结果都列在一个表中，的
12、对应真值结果都列在一个表中，根据根据“”的定义，的定义，则有判断方法如下：则有判断方法如下：1.1.对对所所有有G G1 1,G,G2 2,G,Gn n都都具具有有真真值值T T的的行行( (表表示示前前提提为为真真的的行行) )，如如果果在在每每一一个个这这样样的的行行中中，H H也也具具有有真真值值T T，则则H H是是G G1 1,G,G2 2,G,Gn n的逻辑结果。的逻辑结果。2.2.对对所所有有H H具具有有真真值值为为F F的的行行( (表表示示结结论论为为假假的的行行),),如如果果在在每每一一个个这这样样的的行行中中，G G1 1,G,G2 2,G,Gn n中中至至少少有有一
13、一个个公公式式的的真真值为值为F(F(前提也为假前提也为假) )，则，则H H是是G G1 1,G,G2 2,G,Gn n的逻辑结果的逻辑结果. .电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程13例例5.2.1 5.2.1 判断下列判断下列H H是否是前提是否是前提G G1 1,G,G2 2的逻辑结果的逻辑结果(1)(1)H H：Q Q；G G1 1：P P；G G2 2：PQPQ；(2)(2)H H：P P； G G1 1：PQPQ；G G2 2：Q Q；(3)(3)H H：Q Q；G G1 1：P P；G G2 2：PQPQ。解解P P Q QG G1 1G
14、 G2 2H H0 0 0 00 01 10 00 0 1 10 01 11 11 1 0 01 10 00 01 1 1 11 11 11 1(1)P PQ QG G1 1G G2 2H H0 00 01 11 11 10 01 11 10 01 11 10 00 01 10 01 11 11 10 00 0(2)P PQ QG G1 1G G2 2H H0 00 01 11 10 00 01 11 11 11 11 10 00 00 00 01 11 10 01 11 1(3)电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程142 2 推理定律推理定律设设G G
15、，H H，I I，J J是任意的命题公式，则有：是任意的命题公式，则有：1)1)I I1 1：GH GH G G( (简化规则简化规则) )I I2 2：GH GH H H2)2)I I3 3：G G GHGH( (添加规则添加规则) )I I4 4：H H GHGH3)3)I I5 5：G G GHGHI I6 6：H H GHGH4)4)I I7 7：(GH) (GH) G GI I8 8：(GH) (GH) HH5)5)I I9 9：G,H G,H GHGH电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程152 2 推理定律推理定律( (续续) )6）I10：
16、G, G H H (选言选言/析取析取三段论三段论) I11：G, G H H7）I12：G, GH H(分离规则分离规则)8）I13：H, GH G (否定后件式否定后件式)9）I14：GH, HI GI (假言三段论假言三段论)10）I15：G H, GI, HI I (二难推论二难推论)电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程16例子例子1)1)、前提：、前提：1. 1. 如果明天天晴，我们准备外出旅游。如果明天天晴，我们准备外出旅游。 PQPQ2 2明天的确天晴。明天的确天晴。P P结论：我们外出旅游。结论：我们外出旅游。 Q Q可描述为：可描述为：
17、PQPQ，P P Q Q( (分离规则分离规则) )2)2)、前提：、前提：1.1.如果一个人是单身汉，则他不幸福。如果一个人是单身汉，则他不幸福。 PPQ Q2.2.如果一个人不幸福，则他死得早。如果一个人不幸福，则他死得早。QRQR结论：单身汉死得早。结论：单身汉死得早。 PRPR可描述为：可描述为：PPQ Q，QRQR PRPR( (假言三段论假言三段论) )电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程17例子例子( (续续1)1)3)3)、某、某人人在某日晚归家途中被杀害，据多方调查确在某日晚归家途中被杀害，据多方调查确证，凶手必为王某或陈某，但后又查证
18、，作案之晚证，凶手必为王某或陈某，但后又查证，作案之晚王某在工厂值夜班，没有外出，根据上述案情可得王某在工厂值夜班，没有外出，根据上述案情可得：前提：前提：1.1.凶手为王某或陈某凶手为王某或陈某。PQPQ 2.2.如果王某是凶手，则他在作案当晚必外如果王某是凶手，则他在作案当晚必外出出 PRPR3.3.王某案发之晚并未外出。王某案发之晚并未外出。 RR结论：陈某是凶手。结论：陈某是凶手。Q Q则则可描述为可描述为：PR,RPR,R PP( (否定后件式否定后件式) ) PQPQ，PP Q Q( (选言三段论选言三段论) )电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精
19、品课程18例子例子( (续续2)2)4)4)、前提：、前提：1.1.如果某同学为省二级以上运动员，则他如果某同学为省二级以上运动员，则他将被大学录取。将被大学录取。PRPR2.2.如果某同学高考总分在如果某同学高考总分在560560分以上，则分以上，则将被大学录取。将被大学录取。QRQR3.3.某同学高考总分在某同学高考总分在560560分以上或者是省分以上或者是省二级运动员。二级运动员。PQPQ结论：该同学被大学录取。结论：该同学被大学录取。R R则上述例子可描述为：则上述例子可描述为： PQPQ，PRPR，QRQR R R( (二难推论二难推论) )电子科技大学离散数学课程组电子科技大学离
20、散数学课程组国家精品课程国家精品课程193 3 演绎法演绎法 演绎法演绎法是从前提是从前提(假设假设)出发，依据公认的推理出发，依据公认的推理规则和推理定律，推导出一个结论来。规则和推理定律，推导出一个结论来。 YN触发规则触发规则新事实新事实事实事实=结论结论？事实库事实库规则匹配规则匹配公理库公理库将事实加入到事实库中将事实加入到事实库中结束结束引入事实引入事实电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程20引入推理规则引入推理规则在数理逻辑中，主要的推理规则有：在数理逻辑中，主要的推理规则有： P P规则（称为前提引用规则）：规则（称为前提引用规则）：在推
21、导的过程中，在推导的过程中，可可随时引入前提集合中的任意一个前提随时引入前提集合中的任意一个前提； 规则（逻辑结果引用规则）：规则（逻辑结果引用规则）：在推导的过程在推导的过程中，可以中，可以随时引入公式随时引入公式S S，该公式，该公式S S是由其前的一个是由其前的一个或多个公式推导出来的逻辑结果或多个公式推导出来的逻辑结果。 规则（附加前提规则）：规则（附加前提规则）：如果能从给定的如果能从给定的前提集合前提集合与公式与公式P P推导出推导出S S，则能从此，则能从此前提集合前提集合推导出推导出PSPS。 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程21演绎
22、的定义演绎的定义定义定义5.2.25.2.2 从前提集合从前提集合推出结论推出结论H H的一个的一个演绎演绎是指构造是指构造命题公式的一个有限序列：命题公式的一个有限序列： H H1 1，H H2 2，H Hn n 其中，其中，H Hi i或者是或者是中的某个前提，或者是前面中的某个前提，或者是前面的某些的某些H Hj j（jijx。 推导推导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，（，
23、（1） 使用使用USUS规则消去规则消去量量词，词，“y y”在公式中必在公式中必须是须是自由的自由的。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程50推理规则的正确使用（推理规则的正确使用（2 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
24、ES规则消规则消去去量词，量词，若还若还有其它有其它自由变自由变元元，则必须用则必须用关于自由变元关于自由变元的的函数符号函数符号来来取代常量符号取代常量符号. .电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程51推理规则的正确使用（推理规则的正确使用（3 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）注意：注意：使用使用UGUG规则规则来来添
25、加添加量词时，量词时， 所使用的变元符所使用的变元符号号不能与不能与辖域内的变元符号辖域内的变元符号相同相同. .电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程52推理规则的正确使用（推理规则的正确使用（4 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）注意：注意：使用使用EGEG规则规则来来添加添加量词时，量词时，所使用的变元符所使用的变元符号号不能与不能与辖域内的变元符号
26、辖域内的变元符号相同相同. .电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程535.3.2 5.3.2 谓词演算的综合推理方法谓词演算的综合推理方法（1）推导过程中可以引用命题演算中的）推导过程中可以引用命题演算中的规则规则P 和和规则规则T 。（2）如果）如果结论是以条件的形式结论是以条件的形式(或析取形式或析取形式)给出，给出，我们还可以我们还可以使用规则使用规则CP。（3）若需）若需消去量词消去量词，可以，可以引用规则引用规则US和规则和规则ES。（4）当所要求的结论可能被）当所要求的结论可能被定量定量时，此时可时，此时可引用引用规则规则UG和规则和规则EG
27、将其量词加入将其量词加入。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程54谓词演算的综合推理方法（续）谓词演算的综合推理方法（续）（5）证明时可采用如）证明时可采用如命题演算命题演算中的中的直接证明方法直接证明方法和间接证明方法和间接证明方法。（6）在推导过程中，）在推导过程中，对消去量词的公式或公式中对消去量词的公式或公式中不含量词的子公式不含量词的子公式，完全可以，完全可以引用命题演算中的基引用命题演算中的基本等价公式和基本蕴涵公式本等价公式和基本蕴涵公式。（7）在推导过程中，对）在推导过程中，对含有量词的公式含有量词的公式可以可以引用引用谓词中的基本等价公
28、式和基本蕴涵公式谓词中的基本等价公式和基本蕴涵公式。 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程55例例5.3.1 5.3.1 解解 设设H(x)H(x)：x x是人；是人；M(x)M(x)：x x是要死的；是要死的；s s：苏格：苏格拉底。则符号化为：拉底。则符号化为： ( ( x)(H(x)x)(H(x)M(x)M(x)，H(s) H(s) M(s)M(s)证明证明苏格拉底三段论苏格拉底三段论：“所有的人都是要死的；苏所有的人都是要死的；苏格拉底是人。所以苏格拉底是要死的。格拉底是人。所以苏格拉底是要死的。”证明：证明：(1)(1)( ( x)(H(x)x
29、)(H(x)M(x) M(x) P P (2)H(x) (2)H(x)M(x)M(x) US,(1) US,(1) (3)H(s) (3)H(s) P P (4) (4)M(s)M(s) T,(2),(3) T,(2),(3)，I I(4)(4)错了！错了！电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程56例例5.3.1 5.3.1 解解 设设H(x)H(x)：x x是人；是人；M(x)M(x)：x x是要死的；是要死的；s s：苏格：苏格拉底。则符号化为：拉底。则符号化为： ( ( x)(H(x)x)(H(x)M(x)M(x)，H(s) H(s) M(s) M(
30、s)证明证明苏格拉底三段论苏格拉底三段论：“所有的人都是要死的；苏所有的人都是要死的；苏格拉底是人。所以苏格拉底是要死的。格拉底是人。所以苏格拉底是要死的。”正确正确证明：证明：( (1)1)( ( x)(H(x)x)(H(x)M(x)M(x)P P (2) (2)H(H(s s) )M(M(s s) )US,(1)US,(1) (3) (3)H(s)H(s)P P (4) (4)M(s)M(s)T,(2),(3)T,(2),(3)，I I电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程57例例5.3.2 5.3.2 证明：证明：( ( x)(P(x)x)(P(x)
31、Q(x)Q(x)，( ( x)x)P(x)P(x)( ( x)x)Q(x)Q(x)有下面的推导（正确与否？）有下面的推导（正确与否？）： (1)(1) ( ( x)(P(x)x)(P(x)Q(x)Q(x) P P (2) (P(x) (2) (P(x)Q(x)Q(x) US,(1) US,(1) (3) (3) ( ( x)x)P(x)P(x) P P (4) (4) P(c)P(c) ES,(3) ES,(3) (5) (5) Q(c)Q(c) T,(2),(4),I T,(2),(4),I (6) (6) ( ( x)x)Q(x)Q(x) EG,(5) EG,(5)(4)(4)中的中的“c
32、”c”未必能保证未必能保证令令(2)(2)为真，为真，推导错误！推导错误！电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程58例例5.3.25.3.2（) )推导可修改为（正确与否？）推导可修改为（正确与否？）：(1)(1) ( ( x)(P(x)x)(P(x)Q(x) Q(x) P P(2) (P(c)(2) (P(c)Q(c)Q(c)US,(1)US,(1)(3) (3) ( ( x)x)P(x)P(x)P P(4) (4) P(c)P(c)ES,(3)ES,(3)(5) Q(c)(5) Q(c)T,(2),(4),IT,(2),(4),I(6) (6) ( (
33、 x)x)Q(x)Q(x)EG,(5)EG,(5)证明：证明：( ( x)(P(x)x)(P(x)Q(x)Q(x)，( ( x)x)P(x)P(x)( ( x)x)Q(x)Q(x)(2)(2)中的中的“c”c”未必能保证未必能保证令令(4)(4)为真，为真，推导错误！推导错误！电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程59例例5.3.25.3.2( () )正确推导正确推导如下：如下：(1)(1) ( ( x)x)P(x)P(x)P P(2) (2) P(c)P(c)ESES，(1)(1)(3) (3) ( ( x)(P(x)x)(P(x)Q(x)Q(x) P
34、 P(4) (P(c)(4) (P(c)Q(c)Q(c)US,(3)US,(3)(5) Q(c)(5) Q(c)T,(2),(4),IT,(2),(4),I(6) (6) ( ( x)x)Q(x)Q(x)EG,(5)EG,(5)证明：证明：( ( x)(P(x)x)(P(x)Q(x)Q(x)，( ( x)x)P(x)P(x)( ( x)x)Q(x)Q(x)电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程60例例5.3.35.3.3证明证明：1)(1)( x x) )(P(x)(P(x)Q(x)Q(x)P P 2)(P(c) 2)(P(c)Q(c)Q(c) ES,1)
35、 ES,1) 3)P(c) 3)P(c)T,2),IT,2),I 4)Q(c) 4)Q(c)T,2),IT,2),I 5) 5)( ( x x) )P(x)P(x)EG,3)EG,3) 6) 6)( ( x x) )Q(x)Q(x)EG,4)EG,4) 7) 7)( ( x x) )P(x)P(x)( x x) )Q(x)Q(x)T,5),6),I T,5),6),I 证明：证明：( ( x x) )(P(x)(P(x)Q(x)Q(x)( ( x)x)P(x)P(x)( ( x)x)Q(x)Q(x)电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程61例例5.3.35
36、.3.3( (续续1)1)1) (1) ( x x) )P(x)P(x)( x x) )Q(x)Q(x)P P2) 2) ( ( x x) )P(x)P(x)T,1),IT,1),I3) P(c)3) P(c)ES,2)ES,2)4) 4) ( ( x x) )Q(x)Q(x)T,1),IT,1),I5) Q(c)5) Q(c)ES,4)ES,4)6) (P(c)6) (P(c)Q(c)Q(c) T,3),4),I T,3),4),I7) 7) ( ( x x) )(P(x)(P(x)Q(x)Q(x)EG,6) EG,6) 请看上述推论的逆推导请看上述推论的逆推导（正确与否？）（正确与否？）
37、：证明：证明：( ( x x) )(P(x)(P(x)Q(x)Q(x)( ( x)x)P(x)P(x)( ( x)x)Q(x)Q(x)“c”c”未必能保证同时令未必能保证同时令(2)(2)和和(4)(4)为真，为真，推导错误！推导错误！电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程62例例5.3.35.3.3( (续续2)2)正确推导正确推导：1)(1)( x x) )P(x)P(x)( x x) )Q(x)Q(x)P P2)2)( ( x x) )P(x)P(x)T,1),IT,1),I3)P(c)3)P(c)ES,2)ES,2)4)4)( ( x x) )Q(
38、x)Q(x)T,1),IT,1),I5)Q(b)5)Q(b)ES,4)ES,4)6)(P(c)6)(P(c)Q(b)Q(b)T,3),4),IT,3),4),I7)7)( ( x x)()( y y) )(P(x)(P(x)Q(y)Q(y)EG,6) EG,6) ( ( x x) )(P(x)(P(x)Q(x)Q(x)( ( x)x)P(x)P(x)( ( x)x)Q(x)Q(x)的逆推导：的逆推导：电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程63例例5.3.4 5.3.4 证明证明( (采用反证法，采用反证法，CPCP规则的方法自己完成规则的方法自己完成) )
39、：1 1) ) ( ( ( x)P(x)x)P(x)( ( x)x)Q(x)Q(x)P(P(附加前提附加前提) )2 2) ) ( ( x)P(x)x)P(x) ( ( x)x)Q(x)Q(x)T,1),ET,1),E3) 3) ( ( x)P(x)x)P(x)T,2),IT,2),I4) 4) ( ( x)x)Q(x)Q(x)T,2),IT,2),I5) 5) ( ( x)x) P(x)P(x)T,3),ET,3),E6) 6) P(c)P(c) ES,5) ES,5)证明证明( ( x)(P(x)x)(P(x)Q(x) Q(x) ( ( x)P(x)x)P(x)( ( x)x)Q(x)Q(
40、x)电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程64例例5.3.4 5.3.4 证明（续）证明（续） 6) 6) P(c)P(c) ES,5) ES,5)7) (7) ( x)x) Q(x)Q(x) T,4),ET,4),E8) 8) Q(c)Q(c) US,7)US,7)9) 9) P(c)P(c) Q(c)Q(c) T,6),8),I T,6),8),I10)10) (P(c)(P(c)Q(c)Q(c) T,9),E T,9),E11)(11)( x)(P(x)x)(P(x)Q(x)Q(x) P P12)(P(c)12)(P(c)Q(c)Q(c) US,11
41、) US,11)13) 13) (P(c)(P(c)Q(c)Q(c)(P(c)(P(c)Q(c)Q(c) T,10),12)T,10),12)证明证明( ( x)(P(x)x)(P(x)Q(x) Q(x) ( ( x)P(x)x)P(x)( ( x)x)Q(x)Q(x)电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程655.3.3 5.3.3 谓词逻辑推理的难点谓词逻辑推理的难点（1 1）在推导过程中，如在推导过程中，如既要使用规则既要使用规则US又要使用规又要使用规则则ES消去公式中的量词，而且选用的个体是同一个消去公式中的量词，而且选用的个体是同一个符号，则必须
42、符号，则必须先使用规则先使用规则ES，再使用规则，再使用规则US。 然后再使用命题演算中的推理规则，最后使用然后再使用命题演算中的推理规则，最后使用规则规则UGUG或规则或规则EGEG引入量词，得到所要的结论。引入量词，得到所要的结论。（2 2）如一个变量是用如一个变量是用规则规则ES消去量词消去量词，对该变量再，对该变量再添加量词时，则添加量词时，则只能使用规则只能使用规则EG，而不能使用规则，而不能使用规则UGUG；如使用；如使用规则规则US消去量词消去量词，对该变量在添加量词，对该变量在添加量词时，则时，则可使用规则可使用规则EG和规则和规则UG。电子科技大学离散数学课程组电子科技大学离
43、散数学课程组国家精品课程国家精品课程66谓词逻辑推理的难点（续）谓词逻辑推理的难点（续）（3 3）如有如有两个含有存在量词的公式两个含有存在量词的公式，当用，当用规则规则ESES消消去量词去量词时，时，不能选用同样的一个常量符号不能选用同样的一个常量符号来取代两来取代两个公式中的变元，而应用不同的常量符号来取代它个公式中的变元，而应用不同的常量符号来取代它们。们。（4）在用规则在用规则US和规则和规则ES消去量词消去量词时，此量词必时，此量词必须位于须位于整个公式的最前端整个公式的最前端。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67谓词逻辑推理的难点（续）谓
44、词逻辑推理的难点（续）（5 5）在在添加量词添加量词( ( x)x)、( ( x)x)时，所选用的时，所选用的x x不不能在公式能在公式G(c)G(c)或或G(y)G(y)中中以任何约束出现以任何约束出现。（6 6）在使用在使用EGEG规则规则引入存在量词引入存在量词( ( x)x)，此此x x不得不得仅为仅为G(c)G(c)或或G(y)G(y)中的函数变元中的函数变元。在使用。在使用UGUG规则规则引入引入全称量词全称量词( ( x)x)时，时，此此x x不得为不得为G(y)G(y)中的函数变元中的函数变元( (因该函数变元不得作为自由变元因该函数变元不得作为自由变元) )。电子科技大学离散
45、数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程685.3.4 5.3.4 谓词逻辑推理的应用谓词逻辑推理的应用例例5.3.5 每个喜欢步行的人都不喜欢坐汽车；每个每个喜欢步行的人都不喜欢坐汽车；每个人或者喜欢坐汽车或者喜欢骑自行车；有的人不喜人或者喜欢坐汽车或者喜欢骑自行车；有的人不喜欢骑自行车。因而有的人不喜欢步行。欢骑自行车。因而有的人不喜欢步行。 证明证明 设设H(x)H(x)：x x是人；是人； P(x)P(x)：x x喜欢坐汽车；喜欢坐汽车； Q(x) Q(x)：x x喜欢骑自行车；喜欢骑自行车；R(x)R(x)：x x喜欢步行喜欢步行。则上述语句可符号化为：则上述语句
46、可符号化为： ( ( x)(H(x)R(x)x)(H(x)R(x) P(x) P(x)， ( ( x)(H(x)P(x)Q(x)x)(H(x)P(x)Q(x)， ( ( x)(H(x)x)(H(x) Q(x)Q(x)( ( x)(H(x)x)(H(x) R(x) R(x) 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程69例例5.3.5 5.3.5 证明（续）证明（续） 证：证：(1)(1)( x)(H(x) x)(H(x) Q(x) PQ(x) P (2)H(c) (2)H(c) Q(c) ESQ(c) ES，(1)(1) (3)H(c) T(3)H(c) T，
47、(2)(2) (4) (4) Q(c) TQ(c) T，(2)(2) (5)(5)( x)( H(x)P(x)Q(x) Px)( H(x)P(x)Q(x) P (6)H(c)P(c)Q(c) US(6)H(c)P(c)Q(c) US，(5)(5) (7)P(c)Q(c) T(7)P(c)Q(c) T，(3)(3)，(6)(6)，I I (8)P(c) T(8)P(c) T，(4)(4)，(7)(7)，I I上述语句可符号化为：上述语句可符号化为：( ( x)(H(x)R(x)x)(H(x)R(x) P(x),(P(x),( x)(H(x)P(x)Q(x), x)(H(x)P(x)Q(x), (
48、 ( x)(H(x)x)(H(x) Q(x) Q(x) ( ( x)(H(x)x)(H(x) R(x)R(x)电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程70例例5.3.5 5.3.5 证明（续）证明（续） (3)H(c) T(3)H(c) T，(2)(2) (8)P(c) T(8)P(c) T，(4)(4)，(7)(7)，I I(9)(9) ( ( x)(H(x)R(x)x)(H(x)R(x) P(x) PP(x) P(10) H(c)R(c)(10) H(c)R(c) P(c) USP(c) US，(9)(9)(11)(11) (H(c)R(c) T(H(c
49、)R(c) T，(8)(8)，(10)(10)，I I(12) (12) H(c)H(c) R(c) TR(c) T，(11)(11)，E E(13) (13) R(c) TR(c) T，(3)(3)，(12)(12)，I I(14) H(c)(14) H(c) R(c) TR(c) T，(3)(3)，(13)(13)，I I(15)(15) ( ( x)(H(x)x)(H(x) R(x) EGR(x) EG，(14) (14) 上述语句可符号化为：上述语句可符号化为：( ( x)(H(x)R(x)x)(H(x)R(x) P(x),(P(x),( x)(H(x)P(x)Q(x), x)(H(x
50、)P(x)Q(x), ( ( x)(H(x)x)(H(x) Q(x) Q(x) ( ( x)(H(x)x)(H(x) R(x)R(x)电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程71例例5.3.6 5.3.6 证明下述论断的正确性：证明下述论断的正确性：所有的哺乳动物都是脊椎动物；并非所有的哺乳动物所有的哺乳动物都是脊椎动物；并非所有的哺乳动物都是胎生动物；故有些脊椎动物不是胎生的。都是胎生动物；故有些脊椎动物不是胎生的。证明证明 设设谓词如下：谓词如下：P(x)P(x)：x x是哺乳动物；是哺乳动物；Q(x)Q(x)：x x是脊椎动物；是脊椎动物；R(x)R(
51、x)：x x是胎生动物。是胎生动物。则有则有： ( ( x)(P(x)x)(P(x)Q(x),Q(x), ( ( x)(P(x)x)(P(x)R(x)R(x)( ( x)x)(Q(x)(Q(x) R(x)R(x)电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程72请看下面推导：请看下面推导：1 1) ) ( ( x)(P(x)x)(P(x)R(x)R(x)P P2) 2) (P(x)(P(x)R(x)R(x)US,1)US,1)3) 3) ( ( P(x)P(x)R(x) T,2)R(x) T,2)，E E4) (P(x)4) (P(x) R(x)R(x)T,3),
52、ET,3),E5) P(x)5) P(x)T,4),IT,4),I6) 6) R(x)R(x)T,4),IT,4),I7) (7) ( x)(P(x)x)(P(x)Q(x) PQ(x) P8) P(x)8) P(x)Q(x)Q(x) US,7) US,7)9) Q(x)9) Q(x)T,(5),(8),IT,(5),(8),I10)Q(x)10)Q(x) R(x)R(x)T,6),9),IT,6),9),I11)11)( ( x)x)(Q(x)(Q(x) R(x)R(x)EG,10)EG,10)12)(12)( x)(Q(x)x)(Q(x) R(x)R(x)UG,10)UG,10) ( ( x
53、)(P(x)x)(P(x)Q(x),Q(x), ( ( x)(P(x)x)(P(x)R(x)R(x)( ( x)x)(Q(x)(Q(x) R(x)R(x)错误推导错误推导电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程73例例5.3.6 5.3.6 证明（续）证明（续）1 1) ) ( ( x)(P(x)x)(P(x)R(x)R(x)P P2) 2) ( ( x)x) ( ( P(x)P(x)R(x)R(x)T,1),ET,1),E3) 3) ( ( P(c)P(c)R(c)R(c) ES,2) ES,2)4) (P(c)4) (P(c) R(c)R(c)T,3),
54、ET,3),E5) P(c)5) P(c)T,4),IT,4),I6) 6) R(c)R(c)T,4),IT,4),I7) (7) ( x)(P(x)x)(P(x)Q(x)Q(x)P P8) P(c)8) P(c)Q(c)Q(c)US,7)US,7)9) Q(c)9) Q(c)T,5),8),IT,5),8),I10)Q(c)10)Q(c) R(c)R(c)T,6),9),IT,6),9),I11)11)( ( x)x)(Q(x)(Q(x) R(x)R(x)EG,10)EG,10) ( ( x)(P(x)x)(P(x)Q(x),Q(x), ( ( x)(P(x)x)(P(x)R(x)R(x)(
55、 ( x)x)(Q(x)(Q(x) R(x)R(x)正确推导正确推导电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程74例例5.3.7 5.3.7 证明下列论断的正确性：证明下列论断的正确性：有些有些信徒信徒相信所有的相信所有的神父神父；任何一个；任何一个信徒信徒都不相信骗都不相信骗子子；所以，所以，神父神父都不是骗子。都不是骗子。证明证明 设谓词如下：设谓词如下：S(x)S(x)：x x是信徒是信徒T(x)T(x)：x x是是神父神父P(x)P(x)：x x是骗子是骗子L(x,y)L(x,y)：x x相信相信y y则可符号化为：则可符号化为： ( ( x)x)(S
56、(x)(S(x)( y)(T(y)y)(T(y)L(x,y)L(x,y)， ( ( x)x)( ( y)(S(x)y)(S(x)P(y)P(y)L(x,y)L(x,y) ( ( x)(T(x)x)(T(x)P(x)P(x)电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程75例例5.3.7 5.3.7 证明（续）证明（续） 1) (1) ( x)x)(S(x)(S(x)( y)(T(y)y)(T(y)L(x,y) PL(x,y) P2) S(c)2) S(c)( y)(T(y)y)(T(y)L(c,y) ES,1)L(c,y) ES,1)3) S(c)3) S(c)
57、T,2),I T,2),I4) (4) ( y)(T(y)y)(T(y)L(c,y)L(c,y) T,2),I T,2),I5) T(x)5) T(x)L(c,x)L(c,x) US,4) US,4)6) (6) ( x)x)( ( y)(S(x)y)(S(x)P(y)P(y)L(x,y) PL(x,y) P7) (7) ( y)(S(c)y)(S(c)P(y)P(y)L(c,y) US,6)L(c,y) US,6)8 8) ) ( (S(c)S(c)P(x)P(x)L(c,x) US,7)L(c,x) US,7) ( ( x)x)(S(x)(S(x)( y)(T(y)y)(T(y)L(x,y
58、)L(x,y)， ( ( x)x)( ( y)(S(x)y)(S(x)P(y)P(y)L(x,y)L(x,y) ( ( x)(T(x)x)(T(x)P(x)P(x)电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程76例例5.3.7 5.3.7 证明（续）证明（续）3) S(c)3) S(c) T,2),I T,2),I8 8) ) ( (S(c)S(c)P(x)P(x)L(c,x) US,7)L(c,x) US,7)9) S(c)9) S(c)( (P(x)P(x)L(c,x) T,8),EL(c,x) T,8),E10) P(x)10) P(x)L(c,x)L(c
59、,x) T,3),8),E T,3),8),E11) L(c,x)11) L(c,x)P(x)P(x) T,10),E T,10),E12) T(12) T(x)x)P(x)P(x) T,5),11),E T,5),11),E13) (13) ( x)(x)(T(T(x)x)P(x) US,12)P(x) US,12) ( ( x)x)(S(x)(S(x)( y)(T(y)y)(T(y)L(x,y)L(x,y)， ( ( x)x)( ( y)(S(x)y)(S(x)P(y)P(y)L(x,y)L(x,y) ( ( x)(T(x)x)(T(x)P(x)P(x)电子科技大学离散数学课程组电子科技大
60、学离散数学课程组国家精品课程国家精品课程77例例5.3.85.3.8 现有一智力测验题目现有一智力测验题目(水容器问题水容器问题)：设有两个：设有两个分别能盛分别能盛7升与升与5升的水容器，开始时两个容器均空，升的水容器，开始时两个容器均空，允许对容器做三种操作：允许对容器做三种操作： （1）容器倒满水，）容器倒满水， （2）将容器中的水倒光，）将容器中的水倒光， （3）从一个容器倒水至另一容器，使一个容）从一个容器倒水至另一容器，使一个容器倒光而另一容器倒满。器倒光而另一容器倒满。 最后要求能使大容器最后要求能使大容器(能盛能盛7升的容器升的容器)中有中有4升水升水，并求其操作过程。，并求其
61、操作过程。 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程78例例5.3.85.3.8的解决方案的解决方案S(0,0)S(7,0)S(2,5) S(2,0) S(0,2)S(7,2)S(4,5)S(4,0)大容器注满大容器注满大容器注满大容器注满小容器倒空小容器倒空小容器注满小容器注满小容器倒空小容器倒空倒倒入入小小容容器器容容器器注注满满小容器注满小容器注满电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程79例例5.3.8 5.3.8 证明证明（1 1）S(0, 0) PS(0, 0) P（2 2）( ( x)(x)( y)(S(x,
62、 y)y)(S(x, y)S(7, y) PS(7, y) P（3 3）( ( y)(S(0, y)y)(S(0, y)S(7, y) US,(2)S(7, y) US,(2)（4 4）S(0, 0)S(0, 0)S(7, 0) US ,(3)S(7, 0) US ,(3)（5 5）S(7, 0) T,(1),(4).IS(7, 0) T,(1),(4).I（6 6）( ( x)(x)( y)(y)( z)(S(x,y)z)(S(x,y)S(z,5) PS(z,5) P（7 7）( ( y)(y)( z)(S(7,y)z)(S(7,y)S(z,5) USS(z,5) US，（，（6 6）（8
63、8）( ( z)(S(7,0)z)(S(7,0)S(z,5) USS(z,5) US，（，（7 7）（9 9）S(7, 0)S(7, 0)S(2,5) ESS(2,5) ES，（，（8 8）电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程80例例5.3.8 5.3.8 证明（续）证明（续）（1010）S(2, 5) T,(5),(9),IS(2, 5) T,(5),(9),I（1111）( ( x)(x)( y)(S(x,y)y)(S(x,y)S(x,0) PS(x,0) P（1212）( ( y)(S(2, y)y)(S(2, y)S(2,0) USS(2,0)
64、US，（，（1111）（1313）S(2, 5)S(2, 5)S(2,0) USS(2,0) US，（，（1212）（1414）S(2, 0) T,(10),(13),IS(2, 0) T,(10),(13),I（1515）( ( x)(x)( y)(y)( z)(S(x, y)z)(S(x, y)S(0, z) PS(0, z) P（1616）( ( y)(y)( z)(S(2, y)z)(S(2, y)S(0,z) USS(0,z) US，（1515）（1717）( ( z)(S(2, 0)z)(S(2, 0)S(0,z) USS(0,z) US，（1616）电子科技大学离散数学课程组电子
65、科技大学离散数学课程组国家精品课程国家精品课程81例例5.3.8 5.3.8 证明（续）证明（续）（1818）(S(2, 0)(S(2, 0)S(0, 2) ESS(0, 2) ES，（，（1717）（1919）S(0, 2) T,(14),(18),IS(0, 2) T,(14),(18),I（2020）( ( x)(x)( y)(S(x,y)y)(S(x,y)S(7,y) PS(7,y) P（2121）( ( y)(S(0,y)y)(S(0,y)S(7,y) USS(7,y) US，（，（2020）（2222）(S(0,2)(S(0,2)S(7,2) USS(7,2) US，（，（2121
66、）（2323）S(7,2) T,(19),(22),IS(7,2) T,(19),(22),I（2424）( ( x)(x)( y)(y)( z)(S(x,y)z)(S(x,y)S(z,5) PS(z,5) P（2525）( ( y)(y)( z)(S(7,y)z)(S(7,y)S(z,5) USS(z,5) US，（2424）（2626）( ( z)(S(7,2) z)(S(7,2) S(z,5) USS(z,5) US，（，（2525）电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程82例例5.3.8 5.3.8 证明（续）证明（续）（2727）S(7, 2)S
67、(7, 2)S(4, 5) ESS(4, 5) ES，（，（2626）（2828）S(4, 5) T,(23),(27),IS(4, 5) T,(23),(27),I（2929）( ( x)(x)( y)(S(x,y) y)(S(x,y) S(x,0) ) PS(x,0) ) P（3030）( ( y)(S(4,y)y)(S(4,y)S(4,0) USS(4,0) US，（，（2929）（3131）S(4, 5) S(4, 5) S(4, 0) USS(4, 0) US，（，（3030）（3232）S(4, 0) T,(30),(33),IS(4, 0) T,(30),(33),I电子科技大学
68、离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程835.4 5.4 数学归纳法数学归纳法 5.4.1 数学归纳法原理数学归纳法原理假设要证明的命题能写成形式假设要证明的命题能写成形式: nn0，有，有P(n) 其中其中n0是某个固定的整数，是某个固定的整数，即：希望证明对所有的整数即：希望证明对所有的整数nn0都有都有P(n)为真为真 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程84数学归纳法原理数学归纳法原理假设假设 1）验证）验证nn0，有，有P(n0)为真；为真； (归纳基础归纳基础)2）假设对于）假设对于nk(kn0)，有，有P(k)为真
69、；为真；(归纳假设归纳假设)3）证明）证明nk1，有，有P(k+1)为真。为真。 (归纳结论归纳结论)结论结论 对所有的整数对所有的整数nn0，都有，都有P(n)为真。为真。谓词表示：谓词表示： ( n0)(P(n0) ( n)(nk) P(k)P(k+1)1 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程85强形式数学归纳法原理强形式数学归纳法原理 假设假设 1 ） 验证验证nn0 、n0 +1，有，有P(n0)、 P(n0+1)为真；为真； (归纳基础归纳基础)2）假设对于）假设对于n k(kn0)，有，有P(n)为真；为真；(归纳假设归纳假设)3）证明）证明
70、nk1，有，有P(k+1)为真。为真。 (归纳结论归纳结论)结论结论 对所有的整数对所有的整数nn0，都有，都有P(n)为真。为真。谓词表示：谓词表示： ( n0)(P(n0) P(n0+1) ( n)(nk) P(n)P(k+1)1 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程86例例5.4.15.4.1用数学归纳法证明：用数学归纳法证明： 对所有对所有n1，有，有1+2+3+n= 证明证明 归纳基础验证归纳基础验证 1= 显然显然P(1)真值为真值为1； 归纳假设假定归纳假设假定 对于对于n=k(k1)，有，有P(k)为真，为真，即有即有 1+2+3+k=
71、； 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程87例例5.4.15.4.1归纳结论证明归纳结论证明 对于对于nk1，有，有P(k+1)为真为真 1+2+3+k+(k+1)= +(k+1) =由数学归纳法原理得到，由数学归纳法原理得到，P(n)对所有对所有n1为真。为真。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程88例例5.4.25.4.2对每个正整数对每个正整数n1，能惟一地写成，能惟一地写成，其中，其中pi是素数且满足是素数且满足p1p2Y) THEN a. IF (XY) THEN 1. X 1. XX-YX-Y b. E
72、LSE b. ELSE 1. Y 1. YY-XY-X 2. RETURN(X) 2. RETURN(X) END OF FUNCTION GCD END OF FUNCTION GCD 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程93例例5.4.3 5.4.3 证明证明 归纳基础验证归纳基础验证 因为在循环开始之前存在变量值因为在循环开始之前存在变量值X0X，Y0Y，因此，因此，P(0)是命题是命题GCD(X0, Y0)=GCD(X, Y)，显然命题为真；，显然命题为真；归纳假设假定归纳假设假定 设设P(k)是命题是命题GCD(Xk, Yk)=GCD(X, Y
73、)为真；为真；电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程94例例5.4.3 5.4.3 证明（续）证明（续） 归纳结论证明归纳结论证明 首先考虑首先考虑P(kP(k1)1)的左边，的左边，即即GCD(XGCD(Xk k1 1, Y, Yk k1 1) )。在通过。在通过k k1 1次循环后，次循环后，或者或者X Xk k1 1X Xk k和和Y Yk k1 1Y Yk kX Xk k；或者或者X Xk k1 1X Xk kYkYk和和Y Yk k1 1Y Yk k； 则由则由整数的基本性质整数的基本性质知，知，P(kP(k1)1)GCD(XGCD(Xk k1
74、1, Y, Yk k1 1) )GCD(XGCD(Xk k, Y, Yk k) )GCD(X, Y)GCD(X, Y)。 根据根据数学归纳法数学归纳法知：对所有知：对所有n n 0 0，有，有P(n)P(n)为真。为真。为此，该伪码程序输出的结果必是两个正整数的最为此，该伪码程序输出的结果必是两个正整数的最大公因子。大公因子。 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程95铺瓦问题铺瓦问题例例5.4.4 一个直角三正方形，是一个由三个正方形一个直角三正方形，是一个由三个正方形组成的对象，如图组成的对象，如图1所示。如果我们从所示。如果我们从nn(n为为2的的幂
75、幂)正方形的板中去掉一个正方形，则余下的图形正方形的板中去掉一个正方形，则余下的图形可用直角三正方形来铺成，如图可用直角三正方形来铺成，如图2。此处的铺成是。此处的铺成是用直角三正方形正好覆盖全图的图形，每个直角三用直角三正方形正好覆盖全图的图形，每个直角三正方形不能有重叠，也不许超出图形之外。我们缺正方形不能有重叠，也不许超出图形之外。我们缺少一个正方形的板称为一个缺方板，把此问题称为少一个正方形的板称为一个缺方板，把此问题称为铺瓦问题。铺瓦问题。 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程96铺瓦问题铺瓦问题电子科技大学离散数学课程组电子科技大学离散数学课
76、程组国家精品课程国家精品课程97铺瓦问题铺瓦问题 证明（续）证明（续）（归纳结论证明部分）归纳结论证明部分） 对于对于2k12k1的缺方板问的缺方板问题，我们可以将其分成四个题，我们可以将其分成四个2k2k的板，如图所示。的板，如图所示。旋转此板，使缺少的正方形在左上的四分之一中。旋转此板，使缺少的正方形在左上的四分之一中。由归纳假设，此左上的由归纳假设，此左上的2k2k缺方板可由直角三正方缺方板可由直角三正方形铺成，把一个直角三正方形形铺成，把一个直角三正方形T放在中间，则另外放在中间，则另外三个四分之一都是三个四分之一都是2k2k的缺方板。由归纳假设，它的缺方板。由归纳假设，它们的铺瓦问题
77、都是可以解决的。于是们的铺瓦问题都是可以解决的。于是2k12k1的缺的缺方板可由直角三正方形铺成。方板可由直角三正方形铺成。 由数学归纳法知，对任何的由数学归纳法知，对任何的n，nn正方形的铺正方形的铺瓦问题都是可以铺成的。瓦问题都是可以铺成的。 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程985.5 5.5 按定义证明方法按定义证明方法 在离散数学中，我们大量的定义描述都是用在离散数学中，我们大量的定义描述都是用蕴涵型蕴涵型“PQ”的方式来描述的。的方式来描述的。如集合中子集的包含关系的定义描述为：如集合中子集的包含关系的定义描述为： 集合集合A B ( a)
78、(a Aa B)电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程995.5.1 5.5.1 按定义证明方法原理按定义证明方法原理加上题目中的已知加上题目中的已知G G1 1, G, G2 2,G,Gn n证证明明问问题题H H中的中的Q Q规则触发规则触发引用公理引用公理引引入入证证明明问问题题H H中的中的 P P电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程1005.5.2 5.5.2 按定义证明方法应用按定义证明方法应用例例5.5.15.5.1 设设A A、B B是两个任意集合，证明是两个任意集合，证明 A A B B P(A)
79、P(A) P(B) P(B) 证明证明 （1 1）必要性必要性“”： 对任意的对任意的xP(A)xP(A)，则，则x x A A，由于，由于A A B B，所以所以x x B B，即有，即有xP(B)xP(B)。由。由CPCP规则知：规则知：P(A)P(B)P(A)P(B)。 即即 A A B B P(A) P(A) P(B) P(B) 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程101例例5.5.1 5.5.1 证明证明 （续）（续）（2 2）充分性充分性“”： 对任意的对任意的xAxA，则，则xP(A)xP(A)，由于，由于P(A) P(A) P(B)P(B
80、)，所以，所以xP(B)xP(B)，即有，即有xBxB。由。由CPCP规则知：规则知：A A B B。 即即 P(A) P(A) P(B) P(B) A A B B。 原式得证。原式得证。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程102例例5.5.2 5.5.2 如果如果A B，则，则A BB且且ABA 证明证明两个集合相等两个集合相等，即是证明，即是证明两个集合相互包两个集合相互包含含，请学生自证。，请学生自证。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程103作业作业1.（2）2.（1） （6）3.（3） （5）57. (8) (9)
