离散数学第五版第一章(耿素云、屈婉玲、张立昂编著).ppt

《离散数学第五版第一章(耿素云、屈婉玲、张立昂编著).ppt》由会员分享，可在线阅读，更多相关《离散数学第五版第一章(耿素云、屈婉玲、张立昂编著).ppt（95页珍藏版）》请在三一办公上搜索。

1、离散数学,教材及参考书(1),教材耿素云，屈婉玲，张立昂：离散数学(第三版)，清华大学出版社,教材及参考书(2),参考书耿素云：离散数学(修订版)，高等教育出版社屈婉玲，耿素云，张立昂：离散数学题解（修订版），清华大学出版社李盘林，李丽双，李洋，王春立：离散数学，高等教育出版社,学习目的,初步掌握现代数学的观点和方法；初步掌握处理离散结构和方法，提高计算机系统设计和程序设计的逻辑数字的能力；初步掌握计算机在进行数的处理时的方法和计算；培养学习抽象思维和缜密思考的能力；,首都师范大学教育技术系,离散数学第一章 命题逻辑,第一章 命题逻辑,一、命题与联结词二、命题公式及其赋值三、等值式四、析取范式

2、与合取范式五、联结词的完备集六、推理的形式结构七、自然推理系统P,命题与联结词,一、命题,定义：能判断真假的陈述句，被称为命题。,说明：,命题的真值：作为命题所表达的判断只有两个结果：正确和错误，此结果称为命题的真值。命题是正确的，称此命题的真值为真；命题是错误的，称此命题的真值为假。真值为真的命题称为真命题；真值为假的命题称为假命题。任何命题的真值都是唯一的。,其它类型的句子，如疑问句、祈使句、感叹句均没有真假意义，因为均不是命题。在数理逻辑中，命题的真值的真和假，有时分别用1和0来表达，也有时分别用T和F来表达。,命题与联结词,如何判断命题：,首先判断其是否为陈述句,其次判断其是否有唯一真

3、值,例1：判断下列句子是否为命题，真值如何？,（1）10是整数。,（2）北京是我们祖国的首都。,真命题,真命题,（3）雪是黑的。,（4）x大于y。,（5）向右看齐！,（6）你吃饭了吗？,疑问句 非命题,祈使句 非命题,真值不唯一 非命题,假命题,命题与联结词,例1：判断下列句子是否为命题，真值如何？,（7）本命题是假的。,（8）我正在说谎。,悖论 非命题,悖论 非命题,（9）2014年元旦是晴天。,是命题 真假未定,命题与联结词,三、原子命题（简单命题）,定义：不能被分解为更简单的命题的命题，称为原子命题。,四、复合命题,定义：由若干个原子命题用命题联结词联结而成的命题，称为复合命题。,二、命

4、题符号化,本书中用小写字母p，q，r来表示命题。,例2:,p:10是整数。,q：北京是我们祖国的首都。,r:雪是黑的。,命题与联结词,例3：判断下列命题是否为复合命题。,（1）5能被2整除。,（2）2是素数当且仅当三角形有三条边。,原子命题,复合命题,（3）4是2的倍数或是3的倍数。,复合命题,（4）李明与王华是同学。,原子命题,（5）蓝色和黄色可以调配成绿色。,原子命题,（6）2不是合数。,复合命题,1.1 命题与联结词,五、命题联结词,否定 符号：,定义1.1：设p为命题，复合命题“非p”（或“p的否定”）称为p的否定式，记作 p，符号称为否定联结词。规定 p为真当且仅当p为假。,性质：p

5、p,命题与联结词,合取 符号：,定义1.2：设p，q为二命题，复合命题“p并且q”（或“p与q”）称为p与q的合取式，记作pq，符号称为合取联结词。并规定pq为真当且仅当p与q同时为真时为真。,不要见到“与”或“和”就使用联结词。,命题与联结词,例4：将下列命题符号化。,（1）吴颖既用功又聪明。,（2）吴颖不仅用功而且聪明。,（3）吴颖虽然聪明，但不用功。,（4）张辉与王丽都是三好学生。,（5）张辉与王丽是同学。,p:吴颖用功。,q:吴颖聪明。,r:张辉是三好学生。,s:王丽是三好学生。,t:张辉与王丽是同学。,p q,p q,p q,p q,s,命题与联结词,真值表：,析取 符号：,定义1.

6、3：设p，q为二命题，复合命题“p或q”称为p与q的析取式，记作p q，符号称为析取联结词。并规定pq为假当且仅当p与q同事为假。,注意：,自然语言中的“或”具有二义性，用它做联结的命题有时具有相容性，有时具有排斥性，对应的联结词分别称为相容或和排斥或,命题与联结词,例5：将下列命题符号化。,（1）张明正在睡觉或游泳。,（2）李强是位排球队员或是足球队员。,（3）他昨晚做了二十或三十道题。,（4）张静只能挑选202或203房间。,或表示约数，不能用析取,命题与联结词,蕴含 符号：,定义1.4：设p，q为二命题，复合命题“如果p，则q”称为p与q的蕴含式，记作p q，并称p是蕴含式的前件，q为蕴

7、含式的后件，符号 称为蕴含联结词。并规定p q为假当且仅当p为真q为假。,真值表：,P Q,p q的逻辑关系为q是p的必要条件 p是q的充分条件。,命题与联结词,注意：,蕴含 符号：,在自然语言和数学中，有很多方式来描述蕴含，例如：“只要p，就q”，”因为p，所以q”，”p仅当q”，”只有q才p”，”除非q才p”，”除非q，否则非p”，q是p的必要条件，因而所用的联结词应符号化为，各种描述方式都应该符号化为p q。,在自然语言中，“如果p，则q”中的前件p与后件q往往具有某种内在联系，而在数理逻辑中，p与q可以无任何内在联系。,在数学或其它自然科学中，“如果p，则q”往往表达的是前件p为真，后

8、件q也为真的推理。但在数理逻辑中，作为一种规定，当p为假时，无论q是真还是假，p q均为真，也就是说，只有p为真q为假这一种情况，使得复合命题p q为假。,命题与联结词,例6：将下列命题符号化。,（1）只要不下雨，我就骑自行车上班。,（2）只有不下雨，我才骑自行车上班。,（3）若2+2=4，则太阳从东方升起。,p:天下雨。q:我骑自行车上班。s:2+2=4。t:太阳从东方升起,r:太阳从西方升起。,（4）若2+2 4，则太阳从东方升起。,（5）若2+2=4，则太阳从西方升起。,（6）若2+2 4，则太阳从西方升起。,p q,q p,s t,s r,s r,s t,命题与联结词,等价 符号：,定

9、义1.5：设p，q为二命题，复合命题“p当且仅当q”称为p与q的等价式，记作p q，符号 称为等价联结词。并规定p q为真当且仅当p与q同时为真或同时为假。,p q 的逻辑关系为q与p的互为充分必要条件。,命题与联结词,例7：将下列命题符号化。,（1）2+2=4当且仅当3是奇数。,（2）2+2=4当且仅当3不是奇数。,p:2+2=4。q:3是奇数。,（3）2+2 4当且仅当3是奇数。,（4）2+2 4当且仅当3不是奇数。,p q,p q,p q,p q,命题与联结词,说明,由联结词集 中的一个联结词联结一个或两个原子命题组成的复合命题是简单的复合命题，可以称他们为基本的复合命题。,多次使用联结

10、词集中的联结词，可以组成更为复杂的复合命题。求复杂复合命题的真值时，还要规定联结词的先后顺序。将括号也算在内，这个顺序为，对同一优先级的联结词，先出现者先运算。,我们只关心复合命题中命题之间的真值关系，而不关心命题的内容。,例如:(PQ)R)(RP)Q)可写成:(PQR)RPQ 但有时为了看起来清楚醒目,也可以保留某些原可省去的括号。,例 8 将下列命题符号化设P表示“他有理论知识”,Q表示“他有实践经验”,则“他既有理论知识又有实践经验”可译为:。设P:明天下雨,Q:明天下雪,R:我去学校。则(i)“如果明天不是雨夹雪则我去学校”可写成;(ii)“如果明天不下雨并且不下雪则我去学校”可写成;

11、(iii)“如果明天下雨或下雪则我不去学校”可写成;(iv)“当且仅当明天不下雪并且不下雨时我才去学校;,命题与联结词,命题与联结词,例9：求式子的真值。,p:0 q:0 r:0p:1 q:0 r:1p:0 q:1 r:0,第一章 命题逻辑,一、命题与联结词二、命题公式及其赋值三、等值式四、析取范式与合取范式五、联结词的完备集六、推理的形式结构七、自然推理系统P,等值式,一、等值,定义2.1,注意,设A、B是两个命题公式，若A，B构成的等价式AB为重言式，则称A与B是等值的，记作AB。,不是联结符，它是用来说明A与B的等值，要与区分清楚。,如何判断两个命题公式是否等值？,方法一：通过真值表比较

12、在各相同赋值情况下，真值是否相同。,方法二：将A，B构成 AB等价式，判断其是否为重言式。,等值式,例1：判断下面两个公式是否等值：,(pq),pq,等值式,例2：判断下面公式是否等值：,(pq)(p q)q,等值式,(pq)(pr)(p(qr),(pq)(pr),(p(qr),(pq)(pr)(p(qr),等值式,二、16组重要的等值式,双重否定 A A,等幂律 A A AAAA,交换率AB B AAB B A,分配律(AB)C(AC)(BC)(AB)C(AC)(BC),结合律(AB)C A(BC)(AB)C A(BC),等值式,吸收律A(AB)AA(AB)A,德摩根律(AB)AB(AB)A

13、B,零律A11A00,同一律 A0AA1A,排中律AA1,等值式,矛盾律A 0,蕴涵等值式A A B,等价等值式AB(AB)(BA),假言易位AB B A,等价否定等值式 AB AB,归谬论(AB)(AB)A,等值式,注意：,以上的16组等值式都是用元语言符号书写的，称这样的等值式为等值式模式。可以将这些元语言符号用具体的命题公式代替，则这些具体命题公式被称为等值式模式的代入实例。,等值式,三、等值演算,定义,等值演算规则,由已知等值式推演出另外一些等值式的过程为等值演算。,置换规则 设(A)是含公式A的命题公式，(B)是用公式B置换了(A)中所有的A后得到的命题公式，若A B，则(A)(B)

14、,等值式,等值演算的用途,（1）证明等值式,例3：用等值演算法验证等值式：,(pq)r(pr)(qr),(pq)(pq)(pq),等值式,(pq)r(pr)(qr),方法一：（pq)r(pq)r(pq)r(pr)(qr)(pr)(qr),方法二：(pr)(qr)(pr)(qr)(pq)r(pq)r(pq)r,等值式,(pq)(pq)(pq),(pq)(pq)(qp)(pq)(qp)(pq)(qp)(pq)(qp)(pq)(qq)(pp)(qp)(pq)(qp)(pq)(pq),等值式,（2）判断命题公式的类型,例4：判断下列公式的类型：,(pq)p),(pq)(qp)(pq),(pq)(qp)

15、,等值式,(pq)p),(pq)p)(pq)p)(pq)p(pq)q0q0永假式(矛盾式),等值式,(pq)(qp)(pq),(pq)(qp)(pq)(pq)(pq)1永真式(重言式),等值式,(pq)(qp),(pq)(qp)(pq)(qp)(pq)(pq)(pq)(pq)(ppq)(qpq)pq可满足式,等值式,（3）等值演算方法还可以帮助人们解决现实生活中的一些判断问题,等值式,例5：用等值演算法解决下面问题。,A、B、C、D 4人做百米竞赛，观众甲、乙、丙预报比赛的名次为：甲：C第一，B第二；乙：C第二，D第三；丙：A第二，D第四。比赛结束后发现甲、乙、丙每人报告的情况都是各对一半，试

16、问实际名次如何（假设并无并列者）？,等值式,甲：C第一，B第二；乙：C第二，D第三；丙：A第二，D第四。,1)(r1q2)(r1q2)1,pi:A第iqi:B第i ri:C第i si:D第i,2)(r2s3)(r2s3)1,3)(p2s4)(p2s4)1,等值式,其中：r1 q2 r2 s3中C不可能既得第一名，又得第二名；r1 q2 r2 s3中B、C不能同时为第二名；,1)2)1(r1q2)(r1q2)(r2s3)(r2s3)(r1q2r2s3)(r1q2r2s3)(r1q2r2s3)(r1q2r2s3),4):1)2)(r1q2r2s3)(r1q2r2s3)1,等值式,第一章 命题逻辑,

17、一、命题与联结词二、命题公式及其赋值三、等值式四、析取范式与合取范式五、联结词的完备集六、推理的形式结构七、自然推理系统P,析取范式与合取范式,一、简单析取式、简单合取式,定义1.18,注意,命题变项及其否定统称作文字。仅由有限个文字构成的析取式称作简单析取式。仅由有限个文字构成的合取式称作简单合取式。,一个文字既是简单析取式，又是简单合取式。,定理,（1）一个简单析取式是重言式当且仅当它同时含某个命题变项及它的否定式。,（2）一个简单合取式是矛盾式当且仅当它同时含有某个命题变项及它的否定式。,例1：判断下面公式哪些是简单析取式，哪些是简单合取式：,析取范式与合取范式,(pq),ppr,pq,

18、ppr,pqr,pqr,p,二、析取范式、合取范式,定义1.19,（1）由有限个简单合取式构成的析取式被称为析取范式。,（2）由有限个简单析取式构成的合取式被称为合取范式。,（3）析取范式与合取范式统称为范式。,析取范式与合取范式,例2：判断下面公式哪些是析取式范式，哪些是合取范式：,析取范式与合取范式,(pq)(pq),(pq)(pr),prpq,pqr,p,二、析取范式、合取范式,定理,（1）一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式。,（2）一个合取范式是重言式当且仅当它的每个简单析取式都是重言式。,如何将一个命题公式转换成析取范式或合取范式,（1）首先，消去公式中的和联结

19、词。,（2）其次，范式中不允许出现p、(pq)、(pq)。,（3）最后，析取范式中不允许出现 A(BC),合取范式中不允许出现 A(BC),析取范式与合取范式,二、析取范式、合取范式,定理1.4（范式存在定理）,任一命题公式都存在着与之等值的析取范式与合取范式。,析取范式与合取范式,例3：求下面公式的析取范式与合取范式,析取范式与合取范式,(pq)r)p,(1)求合取范式(pq)r)p(pq)r)p(pq)r)p(pq)r)p(pq)(rp),三、极大项、极小项,定义1.20,在含有n个命题变项的简单合取式（简单析取式）中，若每个命题变项和它的否定式不同时出现，而二者之一必须出现且仅出现一次，

20、且第i个命题变项或它的否定式出现在从左算起的第i位上（若命题变项无角标，就按字典顺序排列），称这样的简单合取式（简单析取式）为极小项（极大项）。,析取范式与合取范式,析取范式与合取范式,例4：公式中出现P，Q，R三个命题变项，下列公式哪些是极小项，极大项？,PQ,PQP,不是极小项，P，P同时出现,不是极小项，其中没出现R,PQR,是极小项,PQ R,PQP,QP,是极大项,不是极大项，P，P同时出现,不是极大项，其中没出现R,三、极大项、极小项,极小项与极大项的记法,析取范式与合取范式,三、极大项、极小项,定理,设mi 与Mi 是命题变项p1，p2，p3，pn 形成的极小项和极大项，则 mi

21、 Mi，Mi mi。,析取范式与合取范式,四、主析取范式、主合取范式,定义1.21,设由n个命题变项构成的析取范式（合取范式）中所有的简单合取范式（简单析取范式）都是极小项（极大项），则称该析取范式（合取范式）为主析取范式（主合取范式）。,析取范式与合取范式,四、主析取范式、主合取范式,定理2.5,任何命题公式都存在着与之等值的主析取范式和主析取范式，并且是唯一的。,例5：求主析取范式和主合取范式,析取范式与合取范式,(pq)r)p,(1)求主合取范式(pq)r)p(pq)r)p(pq)r)p(pq)r)p(pq)(rp)(pq)(rr)(p(qq)r)(pqr)(pqr)(pqr),析取范式

22、与合取范式,(2)求主析取范式(pq)r)p(pq)r)p(pq)r)p(pq)r)p(pr)(qr)p(p(qq)r)(pp)qr)(p(qq)(rr)(pqr)(pqr)(pqr)(pqr)(pqr),析取范式与合取范式,四、主析取范式、主合取范式,主析取范式、主合取范式的用途,（1）求公式的成真与成假赋值,（2）判断公式类型A为重言式当且仅当A的主析取范式包含2n 个极小项。A为矛盾式当且仅当A的主析取范式不含任何极小项。A为可满足式当且仅当A的主析取范式至少含有一个极小项。,例6：用公式的主析取范式判断公式的类型,2.2析取范式与合取范式,(pq)q,p(pq),(pq)q(pq)q(

23、pq)q0,p(pq)p(pq)(pq)(pq)(pq)(pq)1,析取范式与合取范式,（3）判断两个公式是否等值。,例7：判断下列公式是否等值,p,(pq)(pq),pp(qq)(pq)(pq)所以两个公式等值,析取范式与合取范式,（4）应用主析取范式分析和解决实际问题。,例8：某科研所要从3名科研骨干A，B，C中挑选12名出国进修。由于工作需要，选派时要满足以下条件：若A去，则C同去；若B去，则C不能去；若C不去，则A或B可以去。问所里应如何选派他们？,2.2析取范式与合取范式,四、主析取范式、主合取范式,说明,（1）由公式的主析取范式求主合取范式,（2）重言式与矛盾式的主合取范式A为重言

24、式当且仅当A的主合取范式不包含任何极大项。A为矛盾式当且仅当A的主合取范式包含2n个极大项。A为可满足式当且仅当A的主合取范式包含的极大项少于2n个。,第一章 数理逻辑,一、命题与联结词二、命题公式及其赋值三、等值式四、析取范式与合取范式五、联结词的完备集六、推理的形式结构七、自然推理系统P,联结词的完备集,一、n元真值函数,定义,注意,称F:0，1n 0，1为n元真值函数。,n个命题变项可构成(2n个2相乘)个不同的n元真值函数。,二、联结词完备集,定义,设S是一个联结词集合，如果任何n（n=1）元真值函数都可以由仅含S中的联结词构成的公式表示，则称S是联结词完备集。,联结词的完备集,二、联

25、结词完备集,定理,S=、是联结词完备集。,推论,以下联结词集都是完备集：（1）S1、（2）S2、（3）S3、（4）S4、（5）S5、,联结词的完备集,二、联结词完备集,定义1.12 1.13,定理,设p、q为两个命题，复合命题“p与q的否定式”（“p或q的否定式”）称作p，q的与非式（或非式），记作pq(pq)。符号()称作与非联结词或非联结词）。pq为真当且仅当p与q不同时为真（pq为真当且仅当p与q同时为假）。,都是联结词完备集：,例：给定命题公式(PQ)R，该公式在联结词的完备集,中的形式为，在,中的形式为，在中的形式为，在中的形式为。,2.2析取范式与合取范式,第一章 命题逻辑,一、命

26、题与联结词二、命题公式及其赋值三、等值式四、析取范式与合取范式五、联结词的完备集六、推理的形式结构七、自然推理系统P,推理的形式结构,一、推理,推理定义,推理有效性定义（定义1.24）,推理是指从前提出发推出结论的思维过程，而前提是已知命题公式集合，结论是从前提出发应用推理规则推出的命题公式。,设A1，A2，Ak，B都是命题公式，若对于A1，A2，Ak，B 中出现的命题变项的任意一组赋值，或者A1 A2 Ak为假，或者当A1 A2 Ak为真时，B也为真，则称由前提A1，A2，Ak 推出B的推理是有效的或正确的，并称B是有效的结论。,3.1推理的形式结构,说明,（1）推理的正确性与前提的排列次序

27、无关，因而前提中的公式不一定是序列，而是一个有限公式集合，若这个集合极为，可将推B的推理记为B。若推理是正确的记为B，否则记为B。这里可以成B和 A1，A2，AkB为推理的形式结构。,3.1推理的形式结构,（2）设A1，A2，Ak，B中共出现n个命题变项，对于任一组赋值，前提和结论的取值情况有以下四种：A1A2Ak 为0，B为0；A1A2Ak 为0，B为1；A1A2Ak 为1，B为0；A1A2Ak 为1，B为1只要不出现3)中的情况，推理就是正确的，因此判断方法是判断是否会出现3)中的情况。,3.1推理的形式结构,（3）推理正确，并不能保证结论B一定为真，这与数学 中的推理不同。,例1：判断下

28、列推理是否正确：（1）p,pqq（2）p,qpq,方法一：真值表法，分别计算出前提合取式以及结论的真值情况，查看 是否出现情况3)，如果不出现，则有效推理。,方法二：简单推理法，首先判断结论为0时，各命题变项的取值情况，然 后，更据个变项取值求出前提合取式的真值，如果真值可以为1，则，推理不正确。,3.1推理的形式结构,定理,命题公式A1，A2，Ak推B的推理正确当且仅当(A1A2Ak)B为重言式。,如何证明该定理？,判断推理是否正确的三种方法,判断(A1A2Ak)B是否为重言式。,3.1推理的形式结构,例2:判断下列推理是否正确,（1）若a能被4整除，则a能被2整除。a能被4整除，所以a能被

29、2整除。,（2）若a能被4整除，则a能被2整除。a能被2整除，所以a能被4整除。,（3）若下午气温超过30摄氏度，则王小燕必去游泳。若她去游泳，她就不去看电影了。所以，若王 小燕没去看电影，下午气温必超过了30摄氏度。,3.1推理的形式结构,例2:判断下列推理是否正确,（4）如果他是理科学生，他必学好数学。如果他不是 文科学生，他必是理科学生。他没学好数学。所 以他是文科学生。,步骤：首先，将简单命题符号化，然后分别写出前提、结论。,然后，根据判断推理是否正确的方法，判断推理。真值表法、等值演算法或主析取范式法,3.1推理的形式结构,定义,九条重要的推理定律,人们在研究的过程中，发现的一些重要

30、的重言蕴含式，这些重要的重言蕴含式被称为推理定律。,二、推理定律,3.1推理的形式结构,3.1推理的形式结构,注意,（1）出现的A、B、C等依然是元语言符号，它们代表的 是任意的命题公式，因而九条推理定律全是以模式 的形式出现的。,（2）若一个推理的形式结构与某条推理定律对应的蕴含 式一致，则不用证明就可断定这个推理是正确的，只需说明用了某条推理定律即可。,（3）24个等值式中的每一个都派生出两条推理定律。,第一章 数理逻辑,一、命题与联结词二、命题公式及其赋值三、等值式四、析取范式与合取范式五、联结词的完备集六、推理的形式结构七、自然推理系统P,3.2自然推理系统P,定义3.2,一个形式系统

31、I由下面四个部分组成：,一、形式语言系统，形式演算系统,（1）非空的字母表，记作A(I)。,（2）A(I)中符号构造的合式公式集，记作E(I)。,（3）E(I)中一些特殊的公式组成的公理集，记作Ax(I)。,（4）推理规则集，记作R(I)。,可以将I记为4元组。其中是I的形式语言系统，而为I的形式演算系统。,3.2自然推理系统P,形式系统的分类,（1）自然推理系统,二、自然推理系统P,（2）公理推理系统,从任意给定的前提出发，应用系统中的推理规则进行推理演算，得到的最后命题公式是推理的结论（有时称为有效结论，它可是重言式，也可能不是）。,只能从若干条给定的公理出发，应用系统中的推理规则进行推理

32、演算，得到的结论是系统中的重言式，称为系统中的定理。,3.2自然推理系统P,定义,(1)字母表,二、自然推理系统P,命题变项符号：p,q,r,。,联结词符号：,。,括号与逗号：（）,，。,（2）合式公式,同定义1.6,3.2自然推理系统P,（3）推理规则,前提引入规则：在证明的任何步骤上都可以引入前提。,结论引入规则：在证明的任何步骤上所得到的结论都可以做为后继证明的前提。,置换规则：在证明的任何步骤上，命题公式中的子公式都可以用与之等值的公式置换，得到公式序列中又一个公式。,假言推理规则（或称分离规则）：ABA B,3.2自然推理系统P,附加规则：AAB,化简规则：A B A,拒取式规则：A

33、 B B A,假言三段论规则：AB BCAC,3.2自然推理系统P,析取三段论规则：A BB A,构造性二难推理规则：A B C D A C B D,构造性二难推理规则：A B C D B D A C,3.2自然推理系统P,合取引入规则：A B A B,3.2自然推理系统P,例3:在自然推理系统P中构造下面推理的证明：,（1）前提：pq,qr,ps,s 结论：r(p q),（2）前提：pr,qs,pq 结论：rs,（3）前提：p r,st,sr,pq,t 结论：q,3.2自然推理系统P,证明的两种方法,二、自然推理系统P,（1）附加前提证明法,前提：A1、A2、Ak。结论：AB转成 前提：A1、A2、Ak、A 结论：B,3.2自然推理系统P,例4:用附加前提证明法证明下列推理：,（1）前提：p(qr),sp,q 结论：sr,（2）如果小张和小王去看电影，则小李也去看电影，小赵不去看电影或小张去看电影。小王去看电 影。所以，当小赵去看电影时，小李也去。,3.2自然推理系统P,证明的两种方法,二、自然推理系统P,（2）归谬法,前提：A1、A2、Ak。结论：B转成 前提：A1、A2、Ak、B 结论：矛盾,3.2自然推理系统P,例5:用归谬证明法证明下列推理：,前提：p(rs)q),s,p 结论：q,