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