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

离散数学第五版第一章离散数学第五版第一章(耿素云、屈婉玲、张立耿素云、屈婉玲、张立昂编著昂编著)2教材及参考教材及参考书(1)教材教材n耿素云，屈婉玲，张立昂：离散数学耿素云，屈婉玲，张立昂：离散数学(第三版第三版)，清，清华大学出版社华大学出版社3教材及参考教材及参考书(2)参考书参考书n耿素云：离散数学(修订版)，高等教育出版社n屈婉玲，耿素云，张立昂：离散数学题解（修订版），清华大学出版社n李盘林，李丽双，李洋，王春立：离散数学，高等教育出版社4学学习目的目的v初步掌握现代数学的观点和方法；初步掌握现代数学的观点和方法；v初步掌握处理离散结构和方法，提高计算机系初步掌握处理离散结构和方法，提高计算机系统设计和程序设计的逻辑数字的能力；统设计和程序设计的逻辑数字的能力；v初步掌握计算机在进行数的处理时的方法和计初步掌握计算机在进行数的处理时的方法和计算；算；v培养学习抽象思维和缜密思考的能力；培养学习抽象思维和缜密思考的能力；5首都首都师范大学教育技范大学教育技术系系离散数学离散数学第一章第一章 命题逻辑命题逻辑6第一章第一章 命命题逻辑一、命题与联结词二、命题公式及其赋值三、等值式四、析取范式与合取范式五、联结词的完备集六、推理的形式结构七、自然推理系统P7命命题与与联结词一、命题 定义：能判断真假的陈述句，被称为命题。说明：1)命题的真值：作为命题所表达的判断只有两个结果：正确和错误，此结果称为命题的真值。命题是正确的，称此命题的真值为真；命题是错误的，称此命题的真值为假。真值为真的命题称为真命题；真值为假的命题称为假命题。任何命题的真值都是唯一的。2)其它类型的句子，如疑问句、祈使句、感叹句均没有真假意义，因为均不是命题。在数理逻辑中，命题的真值的真和假，有时分别用在数理逻辑中，命题的真值的真和假，有时分别用1 1和和0 0来来表达，也有时分别用表达，也有时分别用T T和和F F来表达。来表达。8命命题与与联结词如何判断命题：1)首先判断其是否为陈述句2)其次判断其是否有唯一真值例1：判断下列句子是否为命题，真值如何？（1）1010是整数。是整数。（2）北京是我们祖国的首都。北京是我们祖国的首都。真命题真命题真命题真命题（3）雪是黑的。雪是黑的。（4）x x大于大于y y。（5）向右看齐！向右看齐！（6）你吃饭了吗？你吃饭了吗？疑问句疑问句 非命题非命题祈使句祈使句 非命题非命题真值不唯一真值不唯一 非命题非命题假命题假命题9命命题与与联结词例1：判断下列句子是否为命题，真值如何？（7）本命题是假的本命题是假的 。（8）我正在说谎。我正在说谎。悖论悖论 非命题非命题悖论悖论 非命题非命题（9）20142014年元旦是晴天。年元旦是晴天。是命题是命题 真假未定真假未定10命命题与与联结词三、原子命题（简单命题）定义：不能被分解为更简单的命题的命题，称为原子命题。四、复合命题 定义：由若干个原子命题用命题联结词联结而成的命题，称为复合命题。二、命题符号化 本书中用小写字母p，q，r来表示命题。例2:p:1010是整数。是整数。q：北京是我们祖国的首都。北京是我们祖国的首都。r:雪是黑的。雪是黑的。11命命题与与联结词例3：判断下列命题是否为复合命题。（1）5 5能被能被2 2整除。整除。（2）2 2是素数当且仅当三角形有三条边。是素数当且仅当三角形有三条边。原子命题原子命题复合命题复合命题（3）4 4是是2 2的倍数或是的倍数或是3 3的倍数。的倍数。复合命题复合命题（4）李明与王华是同学。李明与王华是同学。原子命题原子命题（5）蓝色和黄色可以调配成绿色。蓝色和黄色可以调配成绿色。原子命题原子命题（6）2 2不是合数。不是合数。复合命题复合命题121.1 命命题与与联结词五、命题联结词 1.1.否定否定 符号：pp0110真值表：定义1.1：设p为命题，复合命题“非p”（或“p的否定”）称为p的否定式，记作p，符号称为否定联结词。规定p为真当且仅当p为假。说明：1)是一元联结词 2)念作“等值”，表示该符号两边的两个命题在任何情况下真值相同。性质：pp13命命题与与联结词2.2.合取合取 符号：定义1.2：设p，q为二命题，复合命题“p并且q”（或“p与q”）称为p与q的合取式，记作pq，符号称为合取联结词。并规定pq为真当且仅当p与q同时为真时为真。真值表：PQPQ000010100111注意：1)自然语言中的“既，又”，“不但，而且”，“虽然，但是”，“一面，一面”等联结次可符号化为。2)不要见到“与”或“和”就使用联结词。14命命题与与联结词例4：将下列命题符号化。（1）吴颖既用功又聪明。吴颖既用功又聪明。（2）吴颖不仅用功而且聪明。吴颖不仅用功而且聪明。（3）吴颖虽然聪明，但不用功。吴颖虽然聪明，但不用功。（4）张辉与王丽都是三好学生。张辉与王丽都是三好学生。（5）张辉与王丽是同学。张辉与王丽是同学。p:吴颖用功。q:吴颖聪明。r:张辉是三好学生。s:王丽是三好学生。t:张辉与王丽是同学。p p q qp p q qp p qp p q qs s15命命题与与联结词真值表：3.3.析取析取 符号：定义1.3：设p，q为二命题，复合命题“p或q”称为p与q的析取式，记作p q，符号称为析取联结词。并规定pq为假当且仅当p与q同事为假。PQPQ000011101111注意：1)自然语言中的“或”具有二义性，用它做联结的命题有时具有相容性，有时具有排斥性，对应的联结词分别称为相容或和排斥或16命命题与与联结词例5：将下列命题符号化。（1）张明正在睡觉或游泳。张明正在睡觉或游泳。（2）李强是位排球队员或是足球队员。李强是位排球队员或是足球队员。（3）他昨晚做了二十或三十道题。他昨晚做了二十或三十道题。（4）张静只能挑选张静只能挑选202202或或203203房间。房间。或表示约数，不能用析取或表示约数，不能用析取p:张明正在睡觉。q:张明正在游泳 pq 排斥或排斥或p:李强是位排球队员。q:李强是位足球队员 pq 相容或相容或p:张静挑选202房间。q:张静挑选203房间（p q）（pq）pq不正确不正确17命命题与与联结词4.4.蕴含蕴含 符号：定义1.4：设p，q为二命题，复合命题“如果p，则q”称为p与q的蕴含式，记作p q，并称p是蕴含式的前件，q为蕴含式的后件，符号 称为蕴含联结词。并规定p q为假当且仅当p为真q为假。真值表：PQPQ001011100111p q的逻辑关系为q是p的必要条件 p是q的充分条件。18命命题与与联结词注意：4.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=42+2=4，则太阳从东方升起。，则太阳从东方升起。p:天下雨。q:我骑自行车上班。s:2+2=4。t:太阳从东方升起r:太阳从西方升起。（4）若若2+2 42+2 4，则太阳从东方升起。，则太阳从东方升起。（5）若若2+2=42+2=4，则太阳从西方升起。，则太阳从西方升起。（6）若若2+2 42+2 4，则太阳从西方升起。，则太阳从西方升起。p qq p s t s rs rs t20命命题与与联结词5.5.等价等价 符号：定义1.5：设p，q为二命题，复合命题“p当且仅当q”称为p与q的等价式，记作p q，符号 称为等价联结词。并规定p q为真当且仅当p与q同时为真或同时为假。真值表：PQPQ001010100111p q 的逻辑关系为q与p的互为充分必要条件。21命命题与与联结词例7：将下列命题符号化。（1）2+2=42+2=4当且仅当当且仅当3 3是奇数。是奇数。（2）2+2=42+2=4当且仅当当且仅当3 3不是奇数。不是奇数。p:2+2=42+2=4。q:3 3是奇数是奇数。（3）2+2 42+2 4当且仅当当且仅当3 3是奇数。是奇数。（4）2+2 42+2 4当且仅当当且仅当3 3不是奇数。不是奇数。p qp q p q p q22命命题与与联结词6.6.说明说明 1)由联结词集 中的一个联结词联结一个或两个原子命题组成的复合命题是简单的复合命题，可以称他们为基本的复合命题。2)多次使用联结词集中的联结词，可以组成更为复杂的复合命题。求复杂复合命题的真值时，还要规定联结词的先后顺序。将括号也算在内，这个顺序为 ，对同一优先级的联结词，先出现者先运算。3)我们只关心复合命题中命题之间的真值关系，而不关心命题的内容。例如:(PQ)R)(RP)Q)可写成:(PQR)RPQ 但有时为了看起来清楚醒目,也可以保留某些原可省去的括号。23例例8将下列命题符号化将下列命题符号化设P表示“他有理论知识”,Q表示“他有实践经验”,则“他既有理论知识又有实践经验”可译为:。设P:明天下雨,Q:明天下雪,R:我去学校。则 (i)“如果明天不是雨夹雪则我去学校”可写成 ;(ii)“如果明天不下雨并且不下雪则我去学校”可写成 ;(iii)“如 果 明 天 下 雨 或 下 雪 则 我 不 去 学 校”可 写 成 ;(iv)“当 且 仅 当 明 天 不 下 雪 并 且 不 下 雨 时 我 才 去 学 校 ;命命题与与联结词24命命题与与联结词例9：求式子的真值。p:0 q:0 r:0p:1 q:0 r:1p:0 q:1 r:025第一章第一章 命命题逻辑一、命题与联结词二、命题公式及其赋值三、等值式四、析取范式与合取范式五、联结词的完备集六、推理的形式结构七、自然推理系统P26等等值式式一、等值等值 1.定义2.12.注意设A、B是两个命题公式，若A，B构成的等价式AB为重言式，则称A与B是等值的，记作AB。不是联结符，它是用来说明A与B的等值，要与区分清楚。3.如何判断两个命题公式是否等值？方法一：通过真值表比较在各相同赋值情况下，真值是否相同。方法二：将A，B构成 AB等价式，判断其是否为重言式。27等等值式式例1：判断下面两个公式是否等值：(p q)PQ00001010011101010111 pq(p q)(p q)(pq)pq28等等值式式例2：判断下面公式是否等值：(p q)(pq)q p q00001010011100001101(p q)(pq)(p q)(pq)29等等值式式p q r000111001111010111011111100001101001110001111111(pq)(pr)(p(q r)(pq)(pr)(p(q r)(pq)(pr)(p(q r)30等等值式式二、1616组重要的等值式组重要的等值式 1.双重否定 A A2.等幂律 A A A AAA 3.交换率AB B AAB B A5.分配律(AB)C (AC)(BC)(AB)C (AC)(BC)4.结合律(AB)C A(BC)(AB)C A(BC)31等等值式式7.吸收律A(AB)AA(AB)A6.德摩根律(AB)AB(AB)AB8.零律A11A009.同一律 A0AA1A10.排中律 AA132等等值式式11.矛盾律A 012.蕴涵等值式A A B13.等价等值式AB(AB)(BA)14.假言易位AB B A15.等价否定等值式 AB AB 16.归谬论(AB)(AB)A33等等值式式注意：以上的16组等值式都是用元语言符号书写的，称这样的等值式为等值式模式。可以将这些元语言符号用具体的命题公式代替，则这些具体命题公式被称为等值式模式的代入实例。34等等值式式三、等值演算等值演算1.定义2.等值演算规则由已知等值式推演出另外一些等值式的过程为等值演算。置换规则 设(A)是含公式A的命题公式，(B)是用公式B置换了(A)中所有的A后得到的命题公式，若A B，则(A)(B)35等等值式式3.等值演算的用途（1）证明等值式 例3：用等值演算法验证等值式：(pq)r(pr)(qr)(pq)(pq)(pq)36等等值式式(pq)r(pr)(qr)方法一：（pq)r(pq)r(pq)r(pr)(qr)(pr)(qr)方法二：(pr)(qr)(pr)(qr)(pq)r(pq)r(pq)r 37等等值式式(pq)(pq)(pq)(pq)(pq)(qp)(pq)(qp)(pq)(qp)(pq)(qp)(pq)(qq)(pp)(qp)(pq)(qp)(pq)(pq)38等等值式式（2）判断命题公式的类型 例4：判断下列公式的类型：(pq)p)(pq)(qp)(pq)(pq)(qp)39等等值式式(pq)p)(pq)p)(pq)p)(pq)p(pq)q0q0永假式(矛盾式)40等等值式式(pq)(qp)(pq)(pq)(qp)(pq)(pq)(pq)1永真式(重言式)41等等值式式(pq)(qp)(pq)(qp)(pq)(qp)(pq)(pq)(pq)(pq)(ppq)(qpq)pq可满足式42等等值式式（3）等值演算方法还可以帮助人们解决现实生活中的一些判断问题 43等等值式式例5：用等值演算法解决下面问题。A、B、C、D 4人做百米竞赛，观众甲、乙、丙预报比赛的名次为：甲：C第一，B第二；乙：C第二，D第三；丙：A第二，D第四。比赛结束后发现甲、乙、丙每人报告的情况都是各对一半，试问实际名次如何（假设并无并列者）？44等等值式式甲：C第一，B第二；乙：C第二，D第三；丙：A第二，D第四。1)(r1q2)(r1q2)1 pi:A第iqi:B第i ri:C第i si:D第i2)(r2s3)(r2s3)1 3)(p2s4)(p2s4)1 45等等值式式其中：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)146等等值式式第三名第一名、第四名、第二名、所以：DCBA1)()()()()()()()()()4)31322142322142322142322142322142322132214242srqrspsrqrspsrqrspsrqrspsrqrspsrqrsrqrspsp47第一章第一章 命命题逻辑一、命题与联结词二、命题公式及其赋值三、等值式四、析取范式与合取范式五、联结词的完备集六、推理的形式结构七、自然推理系统P48析取范式与合取范式析取范式与合取范式一、简单析取式、简单合取式简单析取式、简单合取式 1.定义1.182.注意命题变项及其否定统称作文字。仅由有限个文字构成的析取式称作简单析取式。仅由有限个文字构成的合取式称作简单合取式。一个文字既是简单析取式，又是简单合取式。3.定理（1）一个简单析取式是重言式当且仅当它同时含某个命题变项及它的否定式。（2）一个简单合取式是矛盾式当且仅当它同时含有某个命题变项及它的否定式。49例1：判断下面公式哪些是简单析取式，哪些是简单合取式：析取范式与合取范式析取范式与合取范式(pq)pprpqpprpqrpqrp50二、析取范式、合取范式析取范式、合取范式 1.定义1.19（1）由有限个简单合取式构成的析取式被称为析取范式。（2）由有限个简单析取式构成的合取式被称为合取范式。（3）析取范式与合取范式统称为范式。析取范式与合取范式析取范式与合取范式51例2：判断下面公式哪些是析取式范式，哪些是合取范式：注意：（1）简单析取式既是析取范式，也是合取范式；（2）简单合取式既是合取范式，也是析取范式；析取范式与合取范式析取范式与合取范式(pq)(pq)(pq)(pr)prpqpqrp52二、析取范式、合取范式析取范式、合取范式 2.定理（1）一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式。（2）一个合取范式是重言式当且仅当它的每个简单析取式都是重言式。3.如何将一个命题公式转换成析取范式或合取范式（1）首先，消去公式中的和联结词。（2）其次，范式中不允许出现p、(pq)、(pq)。（3）最后，析取范式中不允许出现 A(BC),合取范式中不允许出现 A(BC)析取范式与合取范式析取范式与合取范式53二、析取范式、合取范式析取范式、合取范式 4.定理1.4（范式存在定理）任一命题公式都存在着与之等值的析取范式与合取范式。析取范式与合取范式析取范式与合取范式54例3：求下面公式的析取范式与合取范式 析取范式与合取范式析取范式与合取范式注意：命题公式的析取范式与合取范式不唯一；prqrpprqpprqpprqpprqp)()()()()()()(求析取范式2(pq)r)p(1)求合取范式 (pq)r)p(pq)r)p(pq)r)p(pq)r)p(pq)(rp)55三、极大项、极小项极大项、极小项 1.定义1.20在含有n个命题变项的简单合取式（简单析取式）中，若每个命题变项和它的否定式不同时出现，而二者之一必须出现且仅出现一次，且第i个命题变项或它的否定式出现在从左算起的第i位上（若命题变项无角标，就按字典顺序排列），称这样的简单合取式（简单析取式）为极小项（极大项）。析取范式与合取范式析取范式与合取范式56析取范式与合取范式析取范式与合取范式例4：公式中出现P，Q，R三个命题变项，下列公式哪些是极小项，极大项？PQPQP不是极小项，P，P同时出现 不是极小项，其中没出现RPQR是极小项PQ RPQPQP是极大项不是极大项，P，P同时出现 不是极大项，其中没出现R注意：n个命题变项共可产生2n 个不同的极小项，也可产生2n 个不同的极大项。57三、极大项、极小项极大项、极小项 2.极小项与极大项的记法析取范式与合取范式析取范式与合取范式极小项极小项极大项极大项公式公式成真赋值成真赋值名称名称公式公式成假赋值成假赋值名称名称 PQR000m0P Q R000M0 PQ R001m1P QR001M1 P QR010m2PQ R010M2 P Q R011m3PQR011M3PQR100m4 P Q R100M4PQ R101m5 P QR101M5P QR110m6 PQ R110M6P Q R111m7 PQR111M758三、极大项、极小项极大项、极小项 3.定理设mi 与Mi 是命题变项p1，p2，p3，pn 形成的极小项和极大项，则 mi Mi，Mi mi。析取范式与合取范式析取范式与合取范式四、主析取范式、主合取范式主析取范式、主合取范式 1.定义1.21设由n个命题变项构成的析取范式（合取范式）中所有的简单合取范式（简单析取范式）都是极小项（极大项），则称该析取范式（合取范式）为主析取范式（主合取范式）。59析取范式与合取范式析取范式与合取范式四、主析取范式、主合取范式主析取范式、主合取范式 2.定理2.5任何命题公式都存在着与之等值的主析取范式和主析取范式，并且是唯一的。60例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)61析取范式与合取范式析取范式与合取范式(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)62析取范式与合取范式析取范式与合取范式四、主析取范式、主合取范式主析取范式、主合取范式 3.主析取范式、主合取范式的用途（1）求公式的成真与成假赋值（2）判断公式类型A为重言式当且仅当A的主析取范式包含2n 个极小项。A为矛盾式当且仅当A的主析取范式不含任何极小项。A为可满足式当且仅当A的主析取范式至少含有一个极小项。63例6：用公式的主析取范式判断公式的类型2.2析取范式与合取范式析取范式与合取范式(pq)qp(pq)(pq)q(pq)q(pq)q0 p(pq)p(pq)(pq)(pq)(pq)(pq)164析取范式与合取范式析取范式与合取范式（3）判断两个公式是否等值。例7：判断下列公式是否等值p(pq)(pq)pp(qq)(pq)(pq)所以两个公式等值65析取范式与合取范式析取范式与合取范式（4）应用主析取范式分析和解决实际问题。例8：某科研所要从3名科研骨干A，B，C中挑选12名出国进修。由于工作需要，选派时要满足以下条件：若A去，则C同去；若B去，则C不能去；若C不去，则A或B可以去。问所里应如何选派他们？662.2析取范式与合取范式析取范式与合取范式四、主析取范式、主合取范式主析取范式、主合取范式 4.说明（1）由公式的主析取范式求主合取范式（2）重言式与矛盾式的主合取范式A为重言式当且仅当A的主合取范式不包含任何极大项。A为矛盾式当且仅当A的主合取范式包含2n个极大项。A为可满足式当且仅当A的主合取范式包含的极大项少于2n个。67第一章第一章 数理数理逻辑一、命题与联结词二、命题公式及其赋值三、等值式四、析取范式与合取范式五、联结词的完备集六、推理的形式结构七、自然推理系统P68联结词的完的完备集集一、n n元真值函数元真值函数 1.定义2.注意称F:0，1n 0，1为n元真值函数。n个命题变项可构成(2n个2相乘)个不同的n元真值函数。二、联结词完备集联结词完备集1.定义设S是一个联结词集合，如果任何n（n=1）元真值函数都可以由仅含S中的联结词构成的公式表示，则称S是联结词完备集。69联结词的完的完备集集二、联结词完备集联结词完备集 2.定理S=、是联结词完备集。3.推论以下联结词集都是完备集：（1）S1 、（2）S2 、（3）S3 、（4）S4 、（5）S5 、70联结词的完的完备集集二、联结词完备集联结词完备集 4.定义1.12 1.135.定理设p、q为两个命题，复合命题“p与q的否定式”（“p或q的否定式”）称作p，q的与非式（或非式），记作pq(pq)。符号()称作与非联结词或非联结词）。pq为真当且仅当p与q不同时为真（pq为真当且仅当p与q同时为假）。都是联结词完备集：71例：给定命题公式(PQ)R，该公式在联结词的完备集,中的形式为 ，在,中的形式为 ，在中的形式为 ，在中的形式为 。2.2析取范式与合取范式析取范式与合取范式72第一章第一章 命命题逻辑一、命题与联结词二、命题公式及其赋值三、等值式四、析取范式与合取范式五、联结词的完备集六、推理的形式结构七、自然推理系统P73推理的形式推理的形式结构构一、推理推理 1.推理定义2.推理有效性定义（定义1.24）推理是指从前提出发推出结论的思维过程，而前提是已知命题公式集合，结论是从前提出发应用推理规则推出的命题公式。设A1，A2，Ak，B都是命题公式，若对于A1，A2，Ak，B 中出现的命题变项的任意一组赋值，或者A1 A2 Ak为假，或者当A1 A2 Ak为真时，B也为真，则称由前提A1，A2，Ak 推出B的推理是有效的或正确的，并称B是有效的结论。743.1推理的形式推理的形式结构构3.说明（1）推理的正确性与前提的排列次序无关，因而前提中的公式不一定是序列，而是一个有限公式集合，若这个集合极为，可将推B的推理记为B。若推理是正确的记为B，否则记为B。这里可以成B和 A1，A2，AkB为推理的形式结构。753.1推理的形式推理的形式结构构（2）设A1，A2，Ak，B中共出现n个命题变项，对于任一组赋值 ，前提和结论的取值情况有以下四种：1)A1A2Ak 为0，B为0；2)A1A2Ak 为0，B为1；3)A1A2Ak 为1，B为0；4)A1A2Ak 为1，B为1只要不出现3)中的情况，推理就是正确的，因此判断方法是判断是否会出现3)中的情况。763.1推理的形式推理的形式结构构（3）推理正确，并不能保证结论B一定为真，这与数学 中的推理不同。例1：判断下列推理是否正确：（1）p,pqq（2）p,qpq方法一：真值表法，分别计算出前提合取式以及结论的真值情况，查看 是否出现情况3)，如果不出现，则有效推理。方法二：简单推理法，首先判断结论为0时，各命题变项的取值情况，然 后，更据个变项取值求出前提合取式的真值，如果真值可以为1，则，推理不正确。773.1推理的形式推理的形式结构构4.定理命题公式A1，A2，Ak推B的推理正确当且仅当(A1A2Ak)B为重言式。如何证明该定理？5.判断推理是否正确的三种方法判断(A1A2Ak)B是否为重言式。783.1推理的形式推理的形式结构构例2:判断下列推理是否正确（1）若a能被4整除，则a能被2整除。a能被4整除，所以a能被2整除。（2）若a能被4整除，则a能被2整除。a能被2整除，所以a能被4整除。（3）若下午气温超过30摄氏度，则王小燕必去游泳。若她去游泳，她就不去看电影了。所以，若王 小燕没去看电影，下午气温必超过了30摄氏度。793.1推理的形式推理的形式结构构例2:判断下列推理是否正确（4）如果他是理科学生，他必学好数学。如果他不是 文科学生，他必是理科学生。他没学好数学。所 以他是文科学生。步骤：1)首先，将简单命题符号化，然后分别写出前提、结论。2)然后，根据判断推理是否正确的方法，判断推理。真值表法、等值演算法或主析取范式法803.1推理的形式推理的形式结构构1.定义2.九条重要的推理定律人们在研究的过程中，发现的一些重要的重言蕴含式，这些重要的重言蕴含式被称为推理定律。二、推理定律推理定律1)A（AB）附加律2)（A B）A化简律3)（AB）A B假言推理4)（AB）B A 拒取式813.1推理的形式推理的形式结构构5)（A B）B A 析取三段论6)（AB）（BC）AC假言三段论7)（AB）（BC）AC等价三段论8)（AB）（CD）(AC)(BD)（AB）（AB）(AA)B 构造性二难9)（AB）（CD）(B D)(A C)破坏性二难823.1推理的形式推理的形式结构构3.注意（1）出现的A、B、C等依然是元语言符号，它们代表的 是任意的命题公式，因而九条推理定律全是以模式 的形式出现的。（2）若一个推理的形式结构与某条推理定律对应的蕴含 式一致，则不用证明就可断定这个推理是正确的，只需说明用了某条推理定律即可。（3）24个等值式中的每一个都派生出两条推理定律。83第一章第一章 数理数理逻辑一、命题与联结词二、命题公式及其赋值三、等值式四、析取范式与合取范式五、联结词的完备集六、推理的形式结构七、自然推理系统P843.2自然推理系自然推理系统P1.定义3.2一个形式系统I由下面四个部分组成：一、形式语言系统，一、形式语言系统，形式演算系统形式演算系统（1）非空的字母表，记作A(I)。（2）A(I)中符号构造的合式公式集，记作E(I)。（3）E(I)中一些特殊的公式组成的公理集，记作Ax(I)。（4）推理规则集，记作R(I)。可以将I记为4元组。其中是I的形式语言系统，而为I的形式演算系统。853.2自然推理系自然推理系统P1.形式系统的分类（1）自然推理系统二、自然推理系统二、自然推理系统P（2）公理推理系统从任意给定的前提出发，应用系统中的推理规则进行推理演算，得到的最后命题公式是推理的结论（有时称为有效结论，它可是重言式，也可能不是）。只能从若干条给定的公理出发，应用系统中的推理规则进行推理演算，得到的结论是系统中的重言式，称为系统中的定理。我们介绍的我们介绍的是自然推理是自然推理系统系统P863.2自然推理系自然推理系统P2.定义(1)字母表二、自然推理系统二、自然推理系统P1)命题变项符号：p,q,r,。2)联结词符号：,。3)括号与逗号：（）,，。（2）合式公式同定义1.6873.2自然推理系自然推理系统P（3）推理规则1)前提引入规则：在证明的任何步骤上都可以引入前提。2)结论引入规则：在证明的任何步骤上所得到的结论都可以做为后继证明的前提。3)置换规则：在证明的任何步骤上，命题公式中的子公式都可以用与之等值的公式置换，得到公式序列中又一个公式。4)假言推理规则（或称分离规则）：ABA B883.2自然推理系自然推理系统P5)附加规则：AAB6)化简规则：A B A7)拒取式规则：A B B A8)假言三段论规则：AB BCAC893.2自然推理系自然推理系统P9)析取三段论规则：A BB A10)构造性二难推理规则：A B C D A C B D11)构造性二难推理规则：A B C D B D A C903.2自然推理系自然推理系统P12)合取引入规则：A B A B913.2自然推理系自然推理系统P例3:在自然推理系统P中构造下面推理的证明：（1）前提：pq,qr,ps,s 结论：r(p q)（2）前提：pr,qs,pq 结论：rs（3）前提：p r,st,sr,pq,t 结论：q923.2自然推理系自然推理系统P3.证明的两种方法二、自然推理系统二、自然推理系统P（1）附加前提证明法 前提：A1、A2、Ak。结论：AB转成 前提：A1、A2、Ak、A 结论：B933.2自然推理系自然推理系统P例4:用附加前提证明法证明下列推理：（1）前提：p(qr),sp,q 结论：sr（2）如果小张和小王去看电影，则小李也去看电影，小赵不去看电影或小张去看电影。小王去看电 影。所以，当小赵去看电影时，小李也去。943.2自然推理系自然推理系统P3.证明的两种方法二、自然推理系统二、自然推理系统P（2）归谬法 前提：A1、A2、Ak。结论：B转成 前提：A1、A2、Ak、B 结论：矛盾953.2自然推理系自然推理系统P例5:用归谬证明法证明下列推理：前提：p(rs)q),s,p 结论：q