大学离散数学第一章

1、Discrete Mathematics 1 大学离散数学第一章 课课 程程 说说 明明 Discrete Math 离散数学离散数学 离散数学离散数学(Discrete mathematics)(Discrete mathematics)是研究离是研究离 散量的结构及其相互关系的数学学科，是现代数散量的结构及其相互关系的数学学科，是现代数 学的一个重要分支，它在各学科领域特别在计算学的一个重要分支，它在各学科领域特别在计算 机科学与技术领域有着广泛的应用。机科学与技术领域有着广泛的应用。 一、离散数学课程的特点一、离散数学课程的特点 2 大学离散数学第一章 计算机科学就是算法的科学，而计算机

2、所处计算机科学就是算法的科学，而计算机所处 理的对象是离散的数据，所以离散对象的处理就理的对象是离散的数据，所以离散对象的处理就 成了计算机科学的核心，而研究离散对象的科学成了计算机科学的核心，而研究离散对象的科学 恰恰就是离散数学。恰恰就是离散数学。 微积分和近代数学的发展为近代的工业革命微积分和近代数学的发展为近代的工业革命 奠定了基础。而离散数学的发展则是奠定了计算奠定了基础。而离散数学的发展则是奠定了计算 机革命的基础。机革命的基础。 3 大学离散数学第一章 离散数学课程是应计算机科学和技术发展的离散数学课程是应计算机科学和技术发展的 需要，综合了高等数学的多个分支而形成的。离需要，综

3、合了高等数学的多个分支而形成的。离 散数学也是计算机专业的许多专业课程如程序设散数学也是计算机专业的许多专业课程如程序设 计语言、数据结构、操作系统、编译技术、人工计语言、数据结构、操作系统、编译技术、人工 智能、数据库、算法设计与分析等必不可少的先智能、数据库、算法设计与分析等必不可少的先 行课程。行课程。 4 大学离散数学第一章 数据结构和算法分析与设计中含有大量离散结数据结构和算法分析与设计中含有大量离散结 构的内容。在形式证明、验证、密码学的研究与学构的内容。在形式证明、验证、密码学的研究与学 习中要有理解形式证明的能力。图论中的概念被用习中要有理解形式证明的能力。图论中的概念被用 于

4、计算机网络、操作系统和编译系统等领域。集合于计算机网络、操作系统和编译系统等领域。集合 论的概念被用在软件工程和数据库中。论的概念被用在软件工程和数据库中。 5 大学离散数学第一章 离散数学是计算机科学与技术专业的核心基础离散数学是计算机科学与技术专业的核心基础 课，在计算机科学与技术专业课程体系中起到重课，在计算机科学与技术专业课程体系中起到重 要的基础理论支撑作用。要的基础理论支撑作用。 6 大学离散数学第一章 课程的课程的特点是以离散量为研究对象，内容丰富，涉特点是以离散量为研究对象，内容丰富，涉 及面较宽。因此概念多、定理多、推理多并且内容较及面较宽。因此概念多、定理多、推理多并且内容

5、较 为抽象。但由于它是为后继专业知识的学习做必要的为抽象。但由于它是为后继专业知识的学习做必要的 数学准备，因此它研究的内容均比较基础，难度不大。数学准备，因此它研究的内容均比较基础，难度不大。 通过离散数学的学习，不但可以掌握处理离散结构的通过离散数学的学习，不但可以掌握处理离散结构的 描述工具和方法，为后续课程的学习创造条件，而且描述工具和方法，为后续课程的学习创造条件，而且 可以提高抽象思维和严格的逻辑推理能力。可以提高抽象思维和严格的逻辑推理能力。 7 大学离散数学第一章 二、关于离散数学的一些应用二、关于离散数学的一些应用 例例1 1 在日常生活中我们常常遇到离散数学的问题。如在日常

6、生活中我们常常遇到离散数学的问题。如 果你仔细留心一张世界地图，你会发现用一种颜色对果你仔细留心一张世界地图，你会发现用一种颜色对 一个国家着色，那么一共只需要四种颜色就能保证每一个国家着色，那么一共只需要四种颜色就能保证每 两个相邻的国家的颜色不同。这样的着色效果能使每两个相邻的国家的颜色不同。这样的着色效果能使每 一个国家都能清楚地显示出来。一个国家都能清楚地显示出来。 8 大学离散数学第一章 例例2 2 我国古代的河洛图上记载了三阶幻方，即把从我国古代的河洛图上记载了三阶幻方，即把从 一到九这九个数按三行三列的队行排列，使得每行，一到九这九个数按三行三列的队行排列，使得每行， 每列，以及

7、两条对角线上的三个数之和都是一十五。每列，以及两条对角线上的三个数之和都是一十五。 离散数学中有许多象幻方这样精巧的结构离散数学中有许多象幻方这样精巧的结构。 9 大学离散数学第一章 例例3 3 一个班级的学生共计选修一个班级的学生共计选修A A、B B、C C、D D、E E、F F六门六门 课程，其中一部分人同时选修课程，其中一部分人同时选修D D、C C、A A，一部分人同一部分人同 时选修时选修B B、C C、F F，一部分人同时选修一部分人同时选修B B、E E，还有一部还有一部 分人同时选修分人同时选修A A、B B，期终考试要求每天考一门课，六期终考试要求每天考一门课，六 天内考

8、完，为了减轻学生负担，要求每人都不会连续天内考完，为了减轻学生负担，要求每人都不会连续 参加考试，试设计一个考试日程表。参加考试，试设计一个考试日程表。 10 大学离散数学第一章 例例4 4 网络计划技术网络计划技术 我们还会遇到更复杂的调度和安排问题。例如我们还会遇到更复杂的调度和安排问题。例如 ，在生产原子弹的曼哈顿计划中，涉及到很多工序，在生产原子弹的曼哈顿计划中，涉及到很多工序 ，许多人员的安排，很多元件的生产，怎样安排各，许多人员的安排，很多元件的生产，怎样安排各 种人员的工作，以及各种工序间的衔接，从而使整种人员的工作，以及各种工序间的衔接，从而使整 个工期的时间尽可能短？这些都是

9、离散数学典型例个工期的时间尽可能短？这些都是离散数学典型例 子。子。 11 大学离散数学第一章 假日饭店的管理中，也严格规定了有关的工假日饭店的管理中，也严格规定了有关的工 序，如清洁工的第一步是换什么，清洗什么，第二序，如清洁工的第一步是换什么，清洗什么，第二 步又做什么，总之，他进出房间的次数应该最少。步又做什么，总之，他进出房间的次数应该最少。 库房和运输的管理也是典型的离散数学问题。库房和运输的管理也是典型的离散数学问题。 怎样安排运输使得库房充分发挥作用，进一步来说怎样安排运输使得库房充分发挥作用，进一步来说 ，货物放在什么地方最便于存取（如存储时间短的，货物放在什么地方最便于存取（

10、如存储时间短的 应该放在容易存取的地方）。应该放在容易存取的地方）。 12 大学离散数学第一章 一个通讯网络怎样布局最节省？美国的贝尔实验一个通讯网络怎样布局最节省？美国的贝尔实验 室和室和IBMIBM公司都有世界一流的离散数学家在研究这个公司都有世界一流的离散数学家在研究这个 问题，这个问题直接关系到巨大的经济利益。问题，这个问题直接关系到巨大的经济利益。 我们知道，用形状相同的方型砖块可以把一个地我们知道，用形状相同的方型砖块可以把一个地 面铺满（不考虑边缘的情况），但是如果用不同形状，面铺满（不考虑边缘的情况），但是如果用不同形状， 而又非方型的砖块来铺一个地面，能否铺满呢？这不而又非方

11、型的砖块来铺一个地面，能否铺满呢？这不 仅是一个与实际相关的问题，也涉及到很深的离散数仅是一个与实际相关的问题，也涉及到很深的离散数 学问题。学问题。 13 大学离散数学第一章 我们知道，用形状相同的方型砖块可以把一个我们知道，用形状相同的方型砖块可以把一个 地面铺满（不考虑边缘的情况），但是如果用不同地面铺满（不考虑边缘的情况），但是如果用不同 形状，而又非方型的砖块来铺一个地面，能否铺满形状，而又非方型的砖块来铺一个地面，能否铺满 呢？这不仅是一个与实际相关的问题，也涉及到很呢？这不仅是一个与实际相关的问题，也涉及到很 深的离散数学问题。深的离散数学问题。 14 大学离散数学第一章 航空调

12、度和航班的设定也是离散数学的问题。航空调度和航班的设定也是离散数学的问题。 对于城市的交通管理，交通规划，哪些地方对于城市的交通管理，交通规划，哪些地方 可能是阻塞要地，哪些地方应该设单行道，立交桥可能是阻塞要地，哪些地方应该设单行道，立交桥 建在哪里最合适，红绿灯怎样设定最合理，如此等建在哪里最合适，红绿灯怎样设定最合理，如此等 等，全是离散数学的问题。等，全是离散数学的问题。 15 大学离散数学第一章 三、离散数学课程的学习方法三、离散数学课程的学习方法: : 离散数学的特点是：离散数学的特点是： (1)(1)知识点集中，概念和定理多：知识点集中，概念和定理多： 离散数学是建立在大量概念之

13、上的逻辑推理学科，概念的离散数学是建立在大量概念之上的逻辑推理学科，概念的 理解是我们学习这门学科的核心。在每一章节列出若干定义和理解是我们学习这门学科的核心。在每一章节列出若干定义和 定理，接着就是这些定义定理的直接应用。掌握、理解和运用定理，接着就是这些定义定理的直接应用。掌握、理解和运用 这些概念和定理是学好这门课的关键。要特别注意概念之间的这些概念和定理是学好这门课的关键。要特别注意概念之间的 联系，而描述这些联系的则是定理和性质。联系，而描述这些联系的则是定理和性质。 16 大学离散数学第一章 (2)(2)方法性强：方法性强： 离散数学的证明题多，不同的题型会需要不同的证明离散数学的

14、证明题多，不同的题型会需要不同的证明 方法，同一个题也可能有几种方法。但是离散数学证明题方法，同一个题也可能有几种方法。但是离散数学证明题 的方法性是很强的，如果知道一道题用什么方法讲明，则很容的方法性是很强的，如果知道一道题用什么方法讲明，则很容 易可以证出来，否则就会事倍功半。因此在平时的学习中，要易可以证出来，否则就会事倍功半。因此在平时的学习中，要 勤于思考，对于同一个问题，尽可能多探讨几种证明方法，从勤于思考，对于同一个问题，尽可能多探讨几种证明方法，从 而学会熟练运用这些证明方法。同时要善于总结。而学会熟练运用这些证明方法。同时要善于总结。 17 大学离散数学第一章 在学习离散数学

15、的过程，对概念的理解是学习的重在学习离散数学的过程，对概念的理解是学习的重 中之重。中之重。 一开始必须准确、全面、完整地记住并理解所有的定义一开始必须准确、全面、完整地记住并理解所有的定义 和定理。具体做法是在进行完一章的学习后，用专门的时间和定理。具体做法是在进行完一章的学习后，用专门的时间 对该章包括的定义与定理实施强记。只有这样才可能对本课对该章包括的定义与定理实施强记。只有这样才可能对本课 程的抽象能够适应，并为后续学习打下良好的基础。程的抽象能够适应，并为后续学习打下良好的基础。 18 大学离散数学第一章 学数学就要做数学，离散数学的学习也不例外。学数学就要做数学，离散数学的学习也

16、不例外。 需要花费大量的时间做课后习题。需要花费大量的时间做课后习题。 在命题证明的过程中，最重要的是要掌握证明的思路和在命题证明的过程中，最重要的是要掌握证明的思路和 方法。解离散数学的题，方法是非常重要的，如果拿到一方法。解离散数学的题，方法是非常重要的，如果拿到一 道题，立即能够看出它所属的类型及关联的知识点，就不道题，立即能够看出它所属的类型及关联的知识点，就不 难选用正确的方法将其解决，反之则事倍功半。由此可见难选用正确的方法将其解决，反之则事倍功半。由此可见 ，在平常学习中，要善于总结和归纳，仔细体会题目类型，在平常学习中，要善于总结和归纳，仔细体会题目类型 和此类题目的解题套路。

17、和此类题目的解题套路。 19 大学离散数学第一章 因此，只要肯下功夫，人人都能有扎实的基因此，只要肯下功夫，人人都能有扎实的基 础，拥有足够的数学知识，特别是能大大提高本身础，拥有足够的数学知识，特别是能大大提高本身 的逻辑推理能力、抽象思维能力和形式化思维能力的逻辑推理能力、抽象思维能力和形式化思维能力 ，从而今后在学习任何一门计算机科学的专业主干，从而今后在学习任何一门计算机科学的专业主干 课程时，都不会遇上任何思维理解上的困难。课程时，都不会遇上任何思维理解上的困难。 20 大学离散数学第一章 强调：逻辑性、抽象性；强调：逻辑性、抽象性； 注重：概念、方法与应用注重：概念、方法与应用 2

18、1 大学离散数学第一章 1 熟读教材，熟读教材，准确理解各个概念和定理的含义（结合多个例子准确理解各个概念和定理的含义（结合多个例子 来理解），必要的推理过程要看懂、理解（它可以帮助你熟来理解），必要的推理过程要看懂、理解（它可以帮助你熟 悉和深刻理解定理的含义）。悉和深刻理解定理的含义）。 2 独立思考，大量练习。独立思考，大量练习。仅靠熟读教材并不能将书本上的知识仅靠熟读教材并不能将书本上的知识 变成你自己的知识，在熟读教材的基础上，必须通过大量练变成你自己的知识，在熟读教材的基础上，必须通过大量练 习，独立思考来真正获取知识。习，独立思考来真正获取知识。 3 注重抽象思维能力的培养。数学

19、与其他学科相比较具有注重抽象思维能力的培养。数学与其他学科相比较具有 较高的抽象性，而离散数学的抽象性特点更为显著，它有着较高的抽象性，而离散数学的抽象性特点更为显著，它有着 大量抽象的概念和抽象的推理，要学好这门课程必须具有较大量抽象的概念和抽象的推理，要学好这门课程必须具有较 好的抽象思维能力，才能深入地掌握课程内容。好的抽象思维能力，才能深入地掌握课程内容。 22 大学离散数学第一章 1.数理逻辑部分：数理逻辑部分： 2.集合论部分：集合论部分： 3.代数结构部分：代数结构部分： 4.图论部分：图论部分： 四、离散数学课程的内容四、离散数学课程的内容 23 大学离散数学第一章 数理逻辑是

20、用数学方法研究思维规律的一门学科。数理逻辑是用数学方法研究思维规律的一门学科。 所谓数学方法是指所谓数学方法是指: :用一套数学的符号系统来描述和用一套数学的符号系统来描述和 处理思维的形式与规律。因此处理思维的形式与规律。因此, ,数理逻辑又称为符号数理逻辑又称为符号 逻辑。逻辑。 数理逻辑和计算机的发展有着密切的联系，它为数理逻辑和计算机的发展有着密切的联系，它为 机器证明、自动程序设计、计算机辅助设计等计算机机器证明、自动程序设计、计算机辅助设计等计算机 应用和理论研究提供必要的理论基础。应用和理论研究提供必要的理论基础。 这一部分介绍数理逻辑中最基本的内容。这一部分介绍数理逻辑中最基本

21、的内容。 24 大学离散数学第一章 命题逻辑研究的是以原子命题为基本单位的命题逻辑研究的是以原子命题为基本单位的 推理演算，其特征在于，研究和考查逻辑形式时，推理演算，其特征在于，研究和考查逻辑形式时， 我们把一个命题只分析到其中所含的原子命题成我们把一个命题只分析到其中所含的原子命题成 分为止。通过这样的分析可以显示出一些重要的分为止。通过这样的分析可以显示出一些重要的 逻辑形式，这种形式和有关的逻辑规律就属于命逻辑形式，这种形式和有关的逻辑规律就属于命 题逻辑。题逻辑。 25 大学离散数学第一章 一、命题及其分类一、命题及其分类 1. 1. 命题与真值命题与真值 命题命题: : 判断结果唯

22、一的陈述句判断结果唯一的陈述句非真即假非真即假 注意：注意： 感叹句、祈使句、疑问句都不是命题感叹句、祈使句、疑问句都不是命题 陈述句中的悖论，判断结果不唯一确定的不是命题陈述句中的悖论，判断结果不唯一确定的不是命题 26 大学离散数学第一章 2 2 可见命题的真值是客观存在的，不以可见命题的真值是客观存在的，不以 我们是否知道而改变。我们是否知道而改变。 悖论的定义可以这样表述：由一个被承认是真的命悖论的定义可以这样表述：由一个被承认是真的命 题为前提，设为题为前提，设为B，进行正确的逻辑推理后，得出，进行正确的逻辑推理后，得出 一个与前提互为矛盾命题的结论非一个与前提互为矛盾命题的结论非B

23、；反之，以非；反之，以非B 为前提，亦可推得为前提，亦可推得B。那么命题。那么命题B就是一个悖论。当就是一个悖论。当 然非然非B也是一个悖论。也是一个悖论。 悖论（由真推出假，又由假推出真的陈述句）悖论（由真推出假，又由假推出真的陈述句） 假假 真真 真值不确定，在某些情况下是真的，真值不确定，在某些情况下是真的， 在某些情况下为假，在某些情况下为假， 即结果不唯一即结果不唯一 矛盾不可避免，所以这是一个悖论矛盾不可避免，所以这是一个悖论 命题的真值：判断的结果命题的真值：判断的结果 真命题与假命题真命题与假命题 真 假 27 大学离散数学第一章 例例 A A：李明既是三好学生又是足球队员。：

24、李明既是三好学生又是足球队员。 B B：张平或者正在钓鱼或者正在睡觉。：张平或者正在钓鱼或者正在睡觉。 C C：如果明天天气晴朗，那么我们举行运动会。：如果明天天气晴朗，那么我们举行运动会。 2. 2. 命题的分类命题的分类 （1 1）简单命题（也称原子命题）简单命题（也称原子命题） 不能被分解命题称为原子命题。不能被分解命题称为原子命题。 （2 2）复合命题）复合命题 由简单命题通过联结词联结而成的命题称为复合命题。由简单命题通过联结词联结而成的命题称为复合命题。 28 大学离散数学第一章 2 29 大学离散数学第一章 2 2 30 大学离散数学第一章 31 大学离散数学第一章 p p p

25、1 0 0 1 32 大学离散数学第一章 例例 设设 p p：上海是一个城市；：上海是一个城市； q q：每个自然数都是偶数。：每个自然数都是偶数。 则有则有: : p p：上海不是一个城市：上海不是一个城市; ; q q：并非每个自然数都是偶数。：并非每个自然数都是偶数。 33 大学离散数学第一章 34 大学离散数学第一章 p pq q的逻辑关系是的逻辑关系是p p与与q q同时成立，即当且仅当命题同时成立，即当且仅当命题p p和和q q均取均取 值为真时，值为真时，p pq q才取值为真。其他情况下才取值为真。其他情况下p pq q均为假。均为假。 pqpq 0 0 0 0 1 0 100

26、 111 例例 设设p p：我们去看电影。：我们去看电影。q q：房间里有十张桌子。则：房间里有十张桌子。则p p q表示表示“我们去看电影并且房间里有十张桌子。我们去看电影并且房间里有十张桌子。” 35 大学离散数学第一章 36 大学离散数学第一章 解解：（：（1 1）（）（3 3）首先将原子命题符号化首先将原子命题符号化 p p：吴颖用功。：吴颖用功。 q q：吴颖聪明。：吴颖聪明。 （1 1）符号化为：）符号化为： （2 2）符号化为：）符号化为： （3 3）符号化为：）符号化为： pq pq qp 37 大学离散数学第一章 （4 4）张辉与王丽都是三好生。）张辉与王丽都是三好生。 r

27、r：张辉是三好生。：张辉是三好生。 s s：王丽是三好生。：王丽是三好生。 符号化为：符号化为：rs （5 5）张辉与王丽是同学。）张辉与王丽是同学。 虽然也有联结词虽然也有联结词“与与”，但是是联结主语的，整，但是是联结主语的，整 个句子仍是简单陈述句，所以（个句子仍是简单陈述句，所以（5 5）是原子命题，符）是原子命题，符 号化为：号化为： t t：张辉与王丽是同学：张辉与王丽是同学 38 大学离散数学第一章 使用合取联结词时要注意两点：使用合取联结词时要注意两点： 描述合取式的灵活性与多样性描述合取式的灵活性与多样性 要求分清联结词要求分清联结词“与与”联结的复合命题与简单联结的复合命题

28、与简单 命题命题 39 大学离散数学第一章 当当p p和和q q中有一个取值为真时，中有一个取值为真时，pqpq取值为真。取值为真。 p qpq 000 011 101 111 40 大学离散数学第一章 例例 将下列命题符号化将下列命题符号化。 （1 1）张晓静爱唱歌或爱听音乐）张晓静爱唱歌或爱听音乐 （2 2）张小静只能挑选）张小静只能挑选202202或或203203房间。房间。 （3 3）张小静是江西人或安徽人。）张小静是江西人或安徽人。 注注: : 自然语言中的自然语言中的 “或或” 联结的两个命题可以具有相容联结的两个命题可以具有相容 性，也可以具有排斥性。前者称为相容或，后者称为排斥

29、性，也可以具有排斥性。前者称为相容或，后者称为排斥 或。析取联结词或。析取联结词指的是指的是“相容或相容或”。 41 大学离散数学第一章 （1 1）张晓静爱唱歌或爱听音乐）张晓静爱唱歌或爱听音乐 解解 令令 p p：张晓静爱唱歌；：张晓静爱唱歌； q q：张晓静爱听音乐：张晓静爱听音乐 命题中的命题中的“或或”是是“相容或相容或”，则命题可表示为，则命题可表示为pqpq。 （2 2）张小静只能挑选）张小静只能挑选202202或或203203房间。房间。 解解 令令 t t：张小静挑选：张小静挑选202202房间；房间； u u：张小静挑选：张小静挑选203203房间。房间。 在这个命题中的在这

30、个命题中的“或或”是排斥或，但是排斥或，但t t与与u u可能同时为真可能同时为真 ，所以如果将该命题也符号化为，所以如果将该命题也符号化为tutu，则与命题不符，所以，则与命题不符，所以 不能符号化为不能符号化为tutu。那么命题只可表示为。那么命题只可表示为 （ttu(u(tu) tu) 。42 大学离散数学第一章 命题中的命题中的“或或”是是“排斥或排斥或”，但是，但是r r和和s s不可能同时为真，则不可能同时为真，则 命题可表示为命题可表示为rsrs或（或（rrs(s(rs) rs) 。 （3 3）张小静是江西人或安徽人。）张小静是江西人或安徽人。 解解 令令 r r：张小静是江西人

31、；：张小静是江西人； s s：张小静是安徽人：张小静是安徽人 大学离散数学第一章 例例 将命题将命题“他可能是他可能是100100米或米或400400米赛跑的冠军。米赛跑的冠军。”符号化符号化。 解令解令 p p：他可能是：他可能是100100米赛跑冠军；米赛跑冠军； q q：他可能是：他可能是400400米赛跑冠军。米赛跑冠军。 则命题可表示为则命题可表示为pqpq。 44 大学离散数学第一章 例例 今天晚上我在家看电视或去剧场看戏。今天晚上我在家看电视或去剧场看戏。 令令p p：今天晚上我在家看电视。：今天晚上我在家看电视。 q q：今天晚上我去剧场看戏：今天晚上我去剧场看戏 命题可表示为

32、命题可表示为 （ppq(q(pq)pq) 或或 pqpq 例例 小元元只能拿一个苹果或一个梨小元元只能拿一个苹果或一个梨. . 命题可表示为命题可表示为 （ppq(q(pq)pq) p qp q 001 011 100 111 46 大学离散数学第一章 47 大学离散数学第一章 pq， pq， pq， 48 大学离散数学第一章 （5）-（9）叙述的都是）叙述的都是a能被能被2 整除是整除是a能被能被4整除的必要条件，都符整除的必要条件，都符 号化为号化为rs。（。（10）叙述的都是）叙述的都是a能被能被4 整除是整除是a能被能被2整除的必要条件，整除的必要条件， 符号化为符号化为sr。 49

33、大学离散数学第一章 p q q，真值为，真值为1 1 另一种说法：另一种说法： 若若4不是奇数，则不是奇数，则5不是奇数。不是奇数。 qp，真值为，真值为1 1或者或者 p q q，真值为，真值为1 1 q qp，真值为，真值为1 1 pq q，真值为，真值为0 0 （ p） （ q q）即）即 pq q或或 q q p ，真值为，真值为0 0 50 大学离散数学第一章 （6 6）除非）除非2+2=52+2=5，否则地球是静止不动的。，否则地球是静止不动的。 （7 7）只有地球是静止不动的，才有）只有地球是静止不动的，才有2+2=5.2+2=5. 令令p: 2+2=5p: 2+2=5，q:q:

34、地球是静止不动的，地球是静止不动的， pq q，真值为，真值为0 0 pq q，真值为，真值为1 1 51 大学离散数学第一章 p qp q 001 010 100 111 pqpqqp 52 大学离散数学第一章 53 大学离散数学第一章 例例 将下列命题符号化，并求它们的真值。将下列命题符号化，并求它们的真值。 （1 1）2+3=52+3=5当且仅当当且仅当1919是素数。是素数。 （2 2）2+3=52+3=5当且仅当当且仅当1919不是素数。不是素数。 （3 3）2+352+35当且仅当当且仅当1919是素数。是素数。 （4 4）2+352+35当且仅当当且仅当1919不是素数。不是素数

35、。 解：令解：令p: 2+3=5 p: 2+3=5 ，q q：1919是素数，是素数， pq q，真值为，真值为1 1 pq q，真值为，真值为0 0 pq q，真值为，真值为0 0 pq q，真值为，真值为1 1 54 大学离散数学第一章 上述五种联结词，组成联结词集上述五种联结词，组成联结词集， ， ，应注意到：应注意到： （1 1） 是一元联结词，其余四个是二元联结词是一元联结词，其余四个是二元联结词 （2 2）使用多个联结词可以组成更复杂的符合命题）使用多个联结词可以组成更复杂的符合命题 （3 3）求复合命题的真值时，要注意联结词的优先顺序）求复合命题的真值时，要注意联结词的优先顺序：

36、（）、：（）、 ， ， ，对同一优先级，从左到右，对同一优先级，从左到右 复合命题的真值只取决于构成它的各原子命题的真值，而与这些原子复合命题的真值只取决于构成它的各原子命题的真值，而与这些原子 命题的内容含义无关。命题的内容含义无关。 例例 令令p p：北京比天津人口多。：北京比天津人口多。 q q：2+2=4.2+2=4. r r：乌鸦是白色的。：乌鸦是白色的。 求下列复合命题的真值。求下列复合命题的真值。 （1 1） pqpqr 55 大学离散数学第一章 一一 、命题变项和合式公式、命题变项和合式公式 1.1.命题常项命题常项: :又称命题常元，即简单命题，真值是确定的。又称命题常元，即

37、简单命题，真值是确定的。 相当于常数相当于常数 2. 2.命题变项：又称命题变元，简称变项，（不是命题）。命题变项：又称命题变元，简称变项，（不是命题）。 相当于变量相当于变量 常项与变项均用常项与变项均用p p, , q q, , r r, , , , 等表示等表示. . 大学离散数学第一章 57 大学离散数学第一章 例例1 1 下列符号串是否为命题公式。下列符号串是否为命题公式。 （1 1） p(qprp(qpr）；）； （2 2）（）（pqpq）（ （qrqr） 解解 （1 1） 不是命题公式。不是命题公式。 （2 2） 是命题公式。是命题公式。 设设A A是合式公式，是合式公式，B B

38、是是A A中一部分，若中一部分，若B B也是合式公式，也是合式公式， 则称则称B B为为A A的子公式。的子公式。 大学离散数学第一章 59 大学离散数学第一章 60 大学离散数学第一章 61 大学离散数学第一章 定义定义1.9 1.9 将命题公式将命题公式A A在所有赋值下取值情况列成表，称为在所有赋值下取值情况列成表，称为A A的真值的真值 表。表。 构造真值表的步骤：构造真值表的步骤： （1 1）找出公式中所含的全体命题变项）找出公式中所含的全体命题变项p p1 1,p,p2 2, , p pn n（若无下标就按字典顺序（若无下标就按字典顺序 排列），列出排列），列出2 2n n个赋值，本书规定，赋值从个赋值，本书规定，赋值从00 00 0 0开始，直到开始，直到11 11 1 1为为 止。止。 （2 2）按从低到高的顺序写出公式的各个层次。）按从低到高的顺序写出公式的各个层次。 （3 3）对应各个赋值计算出各层次的真值，直到最后计算出公式的真值。）对应各个赋值计算出各层次的真值，直到最后计算出公式的真值。 如果两个公式的真值表对所有赋值最后一列都相同，即最后结果都相如果两个公式的真值表对所有赋值最后一列都相同，