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

1离散数学2教材及参考书(1)教材耿素云，屈婉玲，张立昂：离散数学(第三版)，清华大学出版社3教材及参考书(2)参考书耿素云：离散数学(修订版)，高等教育出版社屈婉玲，耿素云，张立昂：离散数学题解（修订版），清华大学出版社李盘林，李丽双，李洋，王春立：离散数学，高等教育出版社4学习目的初步掌握现代数学的观点和方法；初步掌握处理离散结构和方法，提高计算机系统设计和程序设计的逻辑数字的能力；初步掌握计算机在进行数的处理时的方法和计算；培养学习抽象思维和缜密思考的能力；5首都师范大学教育技术系离散数学第一章命题逻辑6第一章命题逻辑一、命题与联结词二、命题公式及其赋值三、等值式四、析取范式与合取范式五、联结词的完备集六、推理的形式结构七、自然推理系统P7命题与联结词一、命题定义：能判断真假的陈述句，被称为命题。说明：1)命题的真值：作为命题所表达的判断只有两个结果：正确和错误，此结果称为命题的真值。命题是正确的，称此命题的真值为真；命题是错误的，称此命题的真值为假。真值为真的命题称为真命题；真值为假的命题称为假命题。任何命题的真值都是唯一的。2)其它类型的句子，如疑问句、祈使句、感叹句均没有真假意义，因为均不是命题。在数理逻辑中，命题的真值的真和假，有时分别用1和0来表达，也有时分别用T和F来表达。8命题与联结词如何判断命题：1)首先判断其是否为陈述句2)其次判断其是否有唯一真值例1：判断下列句子是否为命题，真值如何？（1）10是整数。（2）北京是我们祖国的首都。真命题真命题（3）雪是黑的。（4）x大于y。（5）向右看齐！（6）你吃饭了吗？疑问句非命题祈使句非命题真值不唯一非命题假命题9命题与联结词例1：判断下列句子是否为命题，真值如何？（7）本命题是假的。（8）我正在说谎。悖论非命题悖论非命题（9）2014年元旦是晴天。是命题真假未定10命题与联结词三、原子命题（简单命题）定义：不能被分解为更简单的命题的命题，称为原子命题。四、复合命题定义：由若干个原子命题用命题联结词联结而成的命题，称为复合命题。二、命题符号化本书中用小写字母p，q，r来表示命题。例2:p:10是整数。q：北京是我们祖国的首都。r:雪是黑的。11命题与联结词例3：判断下列命题是否为复合命题。（1）5能被2整除。（2）2是素数当且仅当三角形有三条边。原子命题复合命题（3）4是2的倍数或是3的倍数。复合命题（4）李明与王华是同学。原子命题（5）蓝色和黄色可以调配成绿色。原子命题（6）2不是合数。复合命题121.1命题与联结词五、命题联结词1.否定符号：pp0110真值表：定义1.1：设p为命题，复合命题“非p”（或“p的否定”）称为p的否定式，记作p，符号称为否定联结词。规定p为真当且仅当p为假。说明：1)是一元联结词2)念作“等值”，表示该符号两边的两个命题在任何情况下真值相同。性质：pp13命题与联结词2.合取符号：定义1.2：设p，q为二命题，复合命题“p并且q”（或“p与q”）称为p与q的合取式，记作pq，符号称为合取联结词。并规定pq为真当且仅当p与q同时为真时为真。真值表：PQPQ000010100111注意：1)自然语言中的“既……，又……”，“不但……，而且……”，“虽然……，但是……”，“一面……，一面……”等联结次可符号化为。2)不要见到“与”或“和”就使用联结词。14命题与联结词例4：将下列命题符号化。（1）吴颖既用功又聪明。（2）吴颖不仅用功而且聪明。（3）吴颖虽然聪明，但不用功。（4）张辉与王丽都是三好学生。（5）张辉与王丽是同学。p:吴颖用功。q:吴颖聪明。r:张辉是三好学生。s:王丽是三好学生。t:张辉与王丽是同学。pqpqpqpqs15命题与联结词真值表：3.析取符号：定义1.3：设p，q为二命题，复合命题“p或q”称为p与q的析取式，记作pq，符号称为析取联结词。并规定pq为假当且仅当p与q同事为假。PQPQ000011101111注意：1)自然语言中的“或”具有二义性，用它做联结的命题有时具有相容性，有时具有排斥性，对应的联结词分别称为相容或和排斥或16命题与联结词例5：将下列命题符号化。（1）张明正在睡觉或游泳。（2）李强是位排球队员或是足球队员。（3）他昨晚做了二十或三十道题。（4）张静只能挑选202或203房间。或表示约数，不能用析取p:张明正在睡觉。q:张明正在游泳pq排斥或p:李强是位排球队员。q:李强是位足球队员pq相容或p:张静挑选202房间。q:张静挑选203房间（pq）（pq）pq不正确17命题与联结词4.蕴含符号：定义1.4：设p，q为二命题，复合命题“如果p，则q”称为p与q的蕴含式，记作pq，并称p是蕴含式的前件，q为蕴含式的后件，符号称为蕴含联结词。并规定pq为假当且仅当p为真q为假。真值表：PQPQ001011100111pq的逻辑关系为q是p的必要条件p是q的充分条件。18命题与联结词注意：4.蕴含符号：1)在自然语言和数学中，有很多方式来描述蕴含，例如：“只要p，就q”，”因为p，所以q”，”p仅当q”，”只有q才p”，”除非q才p”，”除非q，否则非p”，q是p的必要条件，因而所用的联结词应符号化为，各种描述方式都应该符号化为pq。2)在自然语言中，“如果p，则q”中的前件p与后件q往往具有某种内在联系，而在数理逻辑中，p与q可以无任何内在联系。3)在数学或其它自然科学中，“如果p，则q”往往表达的是前件p为真，后件q也为真的推理。但在数理逻辑中，作为一种规定，当p为假时，无论q是真还是假，pq均为真，也就是说，只有p为真q为假这一种情况，使得复合命题pq为假。19命题与联结词例6：将下列命题符号化。（1）只要不下雨，我就骑自行车上班。（2）只有不下雨，我才骑自行车上班。（3）若2+2=4，则太阳从东方升起。p:天下雨。q:我骑自行车上班。s:2+2=4。t:太阳从东方升起r:太阳从西方升起。（4）若2+24，则太阳从东方升起。（5）若2+2=4，则太阳从西方升起。（6）若2+24，则太阳从西方升起。pqqpstsrsrst20命题与联结词5.等价符号：定义1.5：设p，q为二命题，复合命题“p当且仅当q”称为p与q的等价式，记作pq，符号称为等价联结词。并规定pq为真当且仅当p与q同时为真或同时为假。真值表：PQPQ001010100111pq的逻辑关系为q与p的互为充分必要条件。21命题与联结词例7：将下列命题符号化。（1）2+2=4当且仅当3是奇数。（2）2+2=4当且仅当3不是奇数。p:2+2=4。q:3是奇数。（3）2+24当且仅当3是奇数。（4）2+24当且仅当3不是奇数。pqpqpqpq22命题与联结词6.说明1)由联结词集｛｝中的一个联结词联结一个或两个原子命题组成的复合命题是简单的复合命题，可以称他们为基本的复合命题。，，，，2)多次使用联结词集中的联结词，可以组成更为复杂的复合命题。求复杂复合命题的真值时，还要规定联结词的先后顺序。将括号也算在内，这个顺序为，对同一优先级的联结词，先出现者先运算。，，，，（），3)我们只关心复合命题中命题之间的真值关系，而不关心命题的内容。例如:(((P∧Q)∨R)→((R∨P)∨Q))可写成:(P∧Q∨R)→R∨P∨Q但有时为了看起来清楚醒目,也可以保留某些原可省去的括号。23例8将下列命题符号化①设P表示“他有理论知识”,Q表示“他有实践经验”,则“他既有理论知识又有实践经验”可译为:。②设P:明天下雨,Q:明天下雪,R:我去学校。则(i)“如果明天不是雨夹雪则我去学校”可写成;(ii)“如果明天不下雨并且不下雪则我去学校”可写成;(iii)“如果明天下雨或下雪则我不去学校”可写成;(iv)“当且仅当明天不下雪并且不下雨时我才去学校;命题与联结词24命题与联结词例9：求式子的真值。)()(rprq①p:0q:0r:0②p:1q:0r:1③p:0q:1r:025第一章命题逻辑一、命题与联结词二、命题公式及其赋值三、等值式四、析取范式与合取范式五、联结词的完备集六、推理的形式结构七、自然推理系统P26等值式一、等值1.定义2.12.注意设A、B是两个命题公式，若A，B构成的等价式AB为重言式，则称A与B是等值的，记作AB。不是联结符，它是用来说明A与B的等值，要与区分清楚。3.如何判断两个命题公式是否等值？方法一：通过真值表比较在各相同赋值情况下，真值是否相同。方法二：将A，B构成AB等价式，判断其是否为重言式。27等值式例1：判断下面两个公式是否等值：(pq)PQ00001010011101010111pq(pq)(pq)(pq)pq28等值式例2：判断下面公式是否等值：(pq)(pq)qpq00001010011100001101(pq)(pq)(pq)(pq)29等值式pqr000111001111010111011111100001101001110001111111((pq)(pr))(p(qr))((pq)(pr))(p(qr))((pq)(pr))(p(qr))30等值式二、16组重要的等值式1.双重否定AA2.等幂律AAAAAA3.交换率ABBAABBA5.分配律(AB)C(AC)(BC)(AB)C(AC)(BC)4.结合律(AB)CA(BC)(AB)CA(BC)31等值式7.吸收律A(AB)AA(AB)A6.德摩根律(AB)AB(AB)AB8.零律A11A009.同一律A0AA1A10.排中律AA132等值式11.矛盾律A012.蕴涵等值式AAB13.等价等值式AB(AB)(BA)14.假言易位ABBA15.等价否定等值式ABAB16.归谬论(AB)(AB)A33等值式注意：以上的16组等值式都是用元语言符号书写的，称这样的等值式为等值式模式。可以将这些元语言符号用具体的命题公式代替，则这些具体命题公式被称为等值式模式的代入实例。34等值式三、等值演算1.定义2.等值演算规则由已知等值式推演出另外一些等值式的过程为等值演算。置换规则设(A)是含公式A的命题公式，(B)是用公式B置换了(A)中所有的A后得到的命题公式，若AB，则(A)(B)35等值式3.等值演算的用途（1）证明等值式例3：用等值演算法验证等值式：(pq)r(pr)(qr)(pq)((pq)(pq))36等值式(pq)r(pr)(qr)方法一：（pq)r(pq)r(pq)r(pr)(qr)(pr)(qr)方法二：(pr)(qr)(pr)(qr)(pq)r(pq)r(pq)r37等值式(pq)((pq)(pq))(pq)((pq)(qp))((pq)(qp))(pq)(qp)(pq)(qp)(pq)(qq)(pp)(qp)(pq)(qp)(pq)(pq)38等值式（2）判断命题公式的类型例4：判断下列公式的类型：((pq)p)((pq)(qp))(pq)(pq)(qp)39等值式((pq)p)((pq)p)((pq)p)(pq)p(pq)q0q0永假式(矛盾式)40等值式((pq)(qp))(pq)((pq)(qp