《离散数学第五版第一章(耿素云、屈婉玲、张立昂编著)》由会员分享，可在线阅读，更多相关《离散数学第五版第一章(耿素云、屈婉玲、张立昂编著)（95页珍藏版）》请在金锄头文库上搜索。
1、1离散数学2教材及参考书(1) 教材n耿素云，屈婉玲，张立昂：离散数学(第三版)，清 华大学出版社3教材及参考书(2) 参考书n耿素云：离散数学(修订版)， 高等教育出版社n屈婉玲，耿素云，张立昂：离散数学题解（ 修订版），清华大学出版社n李盘林，李丽双，李洋，王春立：离散数学 ，高等教育出版社4学习目的v初步掌握现代数学的观点和方法；v初步掌握处理离散结构和方法，提高计算机系 统设计和程序设计的逻辑数字的能力； v初步掌握计算机在进行数的处理时的方法和计 算； v培养学习抽象思维和缜密思考的能力； 5首都师范大学教育技术系离散数学第一章 命题逻辑6第一章 命题逻辑一、 命题与联结词 二、 命
2、题公式及其赋值 三、等值式 四、析取范式与合取范式 五、联结词的完备集 六、推理的形式结构 七、自然推理系统P7命题与联结词一、命题定义：能判断真假的陈述句，被称为命题。说明：1)命题的真值：作为命题所表达的判断只有两个结果：正确 和错误，此结果称为命题的真值。 命题是正确的，称此命题的真值为真；命题是错误的，称此 命题的真值为假。真值为真的命题称为真命题 ；真值为假的命题称为假命题 。 任何命题的真值都是唯一的。2)其它类型的句子，如疑问句、祈使句、感叹句均没有真假 意义，因为均不是命题。 在数理逻辑中，命题的真值的真和假，有时分别用1和0来 表达，也有时分别用T和F来表达。 8命题与联结词
3、如何判断命题：1)首先判断其是否为陈述句2)其次判断其是否有唯一真值例1：判断下列句子是否为命题，真值如何？（1）10是整数。（2）北京是我们祖国的首都。真命题 真命题 （3）雪是黑的。 （4）x大于y。（5）向右看齐！（6）你吃饭了吗？ 疑问句 非命题 祈使句 非命题 真值不唯一 非命题 假命题9命题与联结词例1： 判断下列句子是否为命题，真值如何？（7）本命题是假的 。（8）我正在说谎。悖论 非命题 悖论 非命题 （9）2014年元旦是晴天。是命题 真假未定10命题与联结词三、原子命题（简单命题）定义：不能被分解为更简单的命题的命题，称为原子命题。四、复合命题定义：由若干个原子命题用命题联
4、结词联结而成的命题， 称为复合命题。 二、命题符号化本书中用小写字母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.否定 符号： pp0 11 0真值表：定义1.1：设p为命题，复合命题“非p”（或“p的否定”）称为p的否定 式，记作 p ，符
5、号称为否定联结词。规定 p为真当且 仅当p为假。说明：1) 是一元联结词 2) 念作“等值”，表示该符号两边的两个命题在任何 情况下真值相同。 性质： pp13命题与联结词2.合取 符号： 定义1.2：设p，q为二命题，复合命题“p并且q”（或“p与q”）称为p与 q的合取式，记作pq ，符号称为合取联结词。并规定pq为 真当且仅当p与q同时为真时为真。真值表：P QP Q0 0 00 1 01 0 01 1 1注意 ：1)自然语言中的“既，又”，“不但，而且”，“ 虽然，但是”，“一面，一面”等联结次可 符号化为 。 2)不要见到“与”或“和”就使用联结词 。14命题与联结词例4：将下列命题
6、符号化。（1）吴颖既用功又聪明。（2）吴颖不仅用功而且聪明。（3）吴颖虽然聪明，但不用功。（4）张辉与王丽都是三好学生。（5）张辉与王丽是同学。p:吴颖用功。q:吴颖聪明。r:张辉是三好学生。s:王丽是三好学生。t:张辉与王丽是同学。p q p q p qp q s15命题与联结词真值表：3.析取 符号： 定义1.3：设p，q为二命题，复合命题“p或q” 称为p与q的析取式，记 作p q ，符号称为析取联结词。并规定pq为假当且仅当p 与q同事为假。P QP Q0 0 00 1 11 0 11 1 1注意 ：1)自然语言中的“或”具有二义性，用它做联结的命题有时具有 相容性，有时具有排斥性，对
7、应的联结词分别称为相容或和 排斥或16命题与联结词例5：将下列命题符号化。（1）张明正在睡觉或游泳。（2）李强是位排球队员或是足球队员。（3）他昨晚做了二十或三十道题。（4）张静只能挑选202或203房间。或表示约数，不能用析取p:张明正在睡觉。 q:张明正在游泳 pq 排斥或p:李强是位排球队员。 q:李强是位足球队员 pq 相容或p:张静挑选202房间。 q:张静挑选203房间 （ p q）（p q） p q不正确17命题与联结词4.蕴含 符号： 定义1.4：设p，q为二命题，复合命题“如果p，则q” 称为p与q的蕴含 式，记作p q ，并称p是蕴含式的前件，q为蕴含式的后件， 符号 称为
8、蕴含联结词。并规定p q为假当且仅当p为真q 为假。真值表：P QP Q0 0 10 1 11 0 01 1 1p 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)在数学或其它自然科学中，
9、“如果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+2 4，则太阳从东方升起。（5）若2+2=4，则太阳从西方升起。 （6）若2+2 4，则太阳从西方升起。 p qq p s t s rs rs
10、 t20命题与联结词5.等价 符号： 定义1.5：设p，q为二命题，复合命题“p当且仅当q” 称为p与q的等价 式，记作p q ，符号 称为等价联结词。并规定p q 为真当且仅当p与q同时为真或同时为假。真值表：P Q P Q0 0 10 1 01 0 01 1 1p q 的逻辑关系为q与p的互为充 分必要条件。21命题与联结词例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 q22命题与联结词6.说明 1)由联结词集
11、 中的一个联结词联结一个或 两个原子命题组成的复合命题是简单的复合命题，可以称他 们为基本的复合命题。2)多次使用联结词集中的联结词，可以组成更为复杂的复合命 题。求复杂复合命题的真值时，还要规定联结词的先后顺序 。将括号也算在内，这个顺序为 ，对 同一优先级的联结词，先出现者先运算。3)我们只关心复合命题中命题之间的真值关系，而不关心命题 的内容。例如: ( (PQ)R)(RP)Q)可写成:(PQR)RPQ 但有时为了看起来清楚醒目, 也可以保留某些原可省去的括号。23例 8 将下列命题符号化 设P表示“他有理论知识”, Q表示“他有实践经验”, 则“他既有 理论知识又有实践经验”可译为:
12、。 设P: 明天下雨, Q: 明天下雪, R: 我去学校。 则(i) “如果明天不是雨夹雪则我去学校”可写成 ;(ii) “如果明天不下雨并且不下雪则我去学校”可写成 ;(iii) “如果明天下雨或下雪则我不去学校”可写成 ;(iv) “当且仅当明天不下雪并且不下雨时我才去学校 ;命题与联结词24命题与联结词例9：求式子的真值。p:0 q:0 r:0 p:1 q:0 r:1 p:0 q:1 r:025第一章 命题逻辑一、 命题与联结词 二、 命题公式及其赋值 三、等值式 四、析取范式与合取范式 五、联结词的完备集 六、推理的形式结构 七、自然推理系统P26等值式一、等值1.定义2.12.注意设
13、A、B是两个命题公式，若A，B构成的等价式AB为重 言式，则称A与B是等值的，记作AB。不是联结符，它是用来说明A与B的等值，要与区分清楚。3.如何判断两个命题公式是否等值？方法一：通过真值表比较在各相同赋值情况下，真值是否相同。方法二：将A，B构成 AB等价式，判断其是否为重言式。27等值式例1：判断下面两个公式是否等值：(pq)P Q 0 0 00 1 01 0 01 1 10 10 10 11 1pq (pq) (pq) (pq)pq28等值式例2：判断下面公式是否等值：(pq) (p q) qp q0 0 00 1 01 0 01 1 10 00 01 10 1(pq)(pq)(pq)
14、(pq)29等值式p q r 0 0 0 1110 0 1 111 0 1 0 1110 1 1 1111 0 0 0011 0 1 0011 1 0 0011 1 111 1(pq)(pr)(p(qr)(pq)(pr)(p(qr)(pq)(pr)(p(qr)30等值式二、16组重要的等值式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)A A(AB)A6.德摩根律 (AB)AB (AB)AB8.零律A11A009.同一律 A0AA1A10.排中律 AA132等值式11.矛盾律 A 012.蕴涵等值式A A B13.等价等值式AB (AB)(BA)14.假言易位AB B A15.等价否定
