离散数学及其应用DiscreteMathematics

1、2022-3-7重庆邮电大学 理学院 12022-3-7重庆邮电大学 理学院 离散数学类课程地位： 计算机相关专业核心课程 信息类部分专业必修课程 其它部分专业的选修课程离散数学的后继课程： 数据结构、操作系统、 算法分析与设计、人工智能、 数据库、C+语言，22022-3-7重庆邮电大学 理学院 学习该课程的目的： 一方面，它给后继课，如数据结构、编译系统、操作系统、数据库原理、软件工程与方法学、计算机网络、程序设计等，提供必要的数学基础（逻辑、关系、代数系统、图论等）； 另一方面，通过学习离散数学，可以培养和提高自己的抽象思维和逻辑推理能力，为以后的软、硬件学习和研究开发工作，打下坚实的理

2、论基础。32022-3-7重庆邮电大学 理学院 教学要求： 通过该课程的学习，学生应当了解并掌握计算机科学中普遍采用的离散数学中的一些基本概念、基本思想、基本方法。自学要求： 通过反复看书及做课后习题，来加深对该课程中的一些基本概念的理解，逐步提高自己的抽象思维和逻辑推理能力。42022-3-7重庆邮电大学 理学院 离散数学课程的学习方法： 强调：逻辑推理、抽象思维； 注重：概念、方法与应用离散数学的学习要领： 概念（正确）熟练掌握大量的基本概念（多、散） 判断（准确）根据概念对属性进行判断（巧） 推理（可靠）根据多个结论推出新的论断（难）5课程主要内容 第一部分 数理逻辑：命题逻辑、谓词逻辑

3、。 第二部分 集合论：集合、关系、函数。 第三部分 代数系统：二元运算、代数系统、半群、群。 第四部分 图论：图的基本概念、 路与圈、最短路、欧拉图、 哈密尔顿图、树、平面图。2022-3-7重庆邮电大学 理学院 6离散数学与计算机的关系（简要）第一部分 数理逻辑 计算机是数理逻辑和电子学相结合的产物，本章是智能科学中的知识表示、知识推理的基础。 第二部分 集合论 集合是一种重要的数据结构关系，关系数据库的理论基础函数，所有计算机语言中不可缺少的一部分。 第三部分 代数系统 计算机编码和纠错码理论数字逻辑设计基础计算机使用的各种运算，信息安全的密码学需要代数系统为基础。第四部分 图论 数据结构

4、、操作系统、编译原理计算机网络原理的基础。 2022-3-7重庆邮电大学 理学院 7课程教学学时与作业课程学时： 64学时：主要讲述第一部分数理逻辑、第二部分集合与关系，第三部分代数系统（讲到群的定义及其性质）；第四部分图论。 48学时：主要讲述第一部分数理逻辑（主要讲命题逻辑）、第二部分集合与关系；第四部分图论。成绩构成： 30%的平时成绩+70%期末考试成绩。 2022-3-7重庆邮电大学 理学院 8第一章 命题逻辑 数理逻辑是研究推理（即研究人类思维的形式结构和规律）的科学，起源于17世纪，它采用数学符号化的方法，因此也称为符号逻辑。 从广义上讲，数理逻辑包括四论、两演算即集合论、模型论

5、、递归论、证明论和命题逻辑演算、谓词逻辑演算，但现在提到数理逻辑，一般是指命题逻辑和谓词逻辑。本书也只研究这两个逻辑演算。2022-3-7重庆邮电大学 理学院 9 数理逻辑的创始人是Leibniz，为了实现把推理变为演算的想法，他把数学引入了形式逻辑。其后，又经多人努力，逐渐使得数理逻辑成为一门专门的学科。 上个世纪30年代以后，数理逻辑进入一个崭新的发展阶段，逻辑学不仅与数学结合，还与计算机科学等密切关联。 1931年Godel不完全性定理的提出，以及递归函数可计算性的引入，促使了1936年Turing机的产生，十年后，第一台电子计算机问世。2022-3-7重庆邮电大学 理学院 10 数理逻

6、辑与计算机学、控制论、人工智能的相互渗透推动了其自身的发展，模糊逻辑、概率逻辑、归纳逻辑、时态逻辑等都是目前比较热门的研究领域。 本章和下一章我们只从简单语义出发，对数理逻辑中的命题逻辑与谓词逻辑等作一简单的、直接的、非形式化的介绍，不涉及公理系统。2022-3-7重庆邮电大学 理学院 11第一章 命题逻辑1. 命题及其表示 命题：是指具有确定真值的陈述句或者能够判断真假的陈述句。 命题的真值：命题的判断结果。真值只取两个值： 真（1或T）、假（0或F）。 真命题：真值为真的命题。 假命题：真值为假的命题。判断命题的两个步骤： 1、是否为陈述句？ 2、是否有确定的、唯一的真值？1.1节 命题及

7、联结词2022-3-7重庆邮电大学 理学院 12注意: 感叹句、祈使句、疑问句都不是命题。 陈述句中的悖论以及判断结果不惟一确定的也不是命题。例1.1 下列句子中那些是命题？ （1）重庆是直辖市。（2）教师是人类灵魂的工程师。（3）4是素数。（4）1+12。（5）2100年的春节是晴天。（6）火星上有生物。（7）请安静！（8）今天天气多好啊!（9）现在是几点钟?（10）我正在说假话。（11）3x y 2022-3-7重庆邮电大学 理学院 13 （1）、（2）、（3）、（4）、（5）和（6）都是命题。其中 （1）、（2）、（4）是真命题，（3）是假命题。 至于（5）和（6）真假值是确定的，只是现

8、在无法知道，因此它是命题。 （7）、（8）、（9）、（10）、（11）都不是命题。原因在于（7）是祈使句，（8）是感叹句，（9）是疑问句，而（10）是悖论，即若(10)的真值为真，即“我正在说假话”为真，也就是我说的是假话，因此（10）又是错误的；反之，若（10）的真值为假，即“我正在说假话”为假，也就是我在说真话，因此 （10）的真值应为真。 像（10）这样既不为真又不为假的陈述句不是命题，这种陈述句称为悖论。凡是悖论都不是命题。（11）中的x、y 的值不确定，某些x、y使为真，某些x、y使为假，即的真假随x、y的变化而变化。因此，的真假无法确定，所以不是命题。 2022-3-7重庆邮电大学

9、 理学院 14练习 判断下列句子是否为命题？1. 100是自然数。2. 太阳从西方升起。3. 北京是中国的首都。4. 重庆是中国最大的城市。5. 关门!6. 你去哪里?7. How do you do ?8. 凡石头均可炼成金。9. x+3910.皇马中国之行没有提升国家队的水平。2022-3-7重庆邮电大学 理学院 15命题表示 在本书中，用大写的英文字母P,Q,R,P1,P2,P3，1，2等表示命题,用“1(或者T）”、“0（或者F）”分别表示真值的真、假。 如 P：太阳从东边升起。 Q：5是负数。 1：2008北京举办奥运会 。 其真值依次为1、0、1。2022-3-7重庆邮电大学 理学

10、院 16命题的分类简单/原子命题：不能再分解为更简单的陈述句的陈述句称为原子命题。 复合命题：由简单命题通过联结词联结而成的陈述句。如：命题“如果2是素数，则3也是素数”通过“如果，则” 组合而成，是复合命题，而“2是素数”和“3是素数”是简单命题。2022-3-7重庆邮电大学 理学院 172. 命题联结词 在日常语言中，一些简单的陈述句，可以通过某些联结词联结起来，组成较为复杂的语句。 例如可以说：“如果下星期日是晴天，那么我就去春游。”这里就是用：“如果，那么”把两个陈述句“下星期日是晴天”和“我去春游”联结起来组成的一个新复合命题。 在日常语言中还有许多联结词，如“不”、“并且”、“或者

11、”、“当且仅当”，“只要就”，“除非否则”等都是联结词。 使用它们可以将一个命题加以否定或将两个命题连接起来得到新的复合命题。 下面介绍常用的5种常用的联结词。2022-3-7重庆邮电大学 理学院 18（1）否定联结词 设P为命题，复合命题“非P”（或“P的否定”）称为P的否定式，记作 P，符号 称为否定联结词。 运算规则：一元运算PP10012022-3-7重庆邮电大学 理学院 19（2）合取联结词 设P,Q为二命题变元，复合命题“P并且Q”（或“P与Q”）称为P与Q的合取式，记作P Q，符号称为合取联结词。 运算规则：二元运算PQP Q000 0 10 10 0 1112022-3-7重庆

12、邮电大学 理学院 20合取运算特点： 只有参与运算的二命题全为真时，运算结果才为真，否则为假。自然语言中、“并且”、“既又”、“不但而且”、“虽然但是”等都可以符号化为 例如：将下列命题符号化 (1) 北京不仅是中国的首都而且是一个故都。2022-3-7重庆邮电大学 理学院 解：设P：北京是中国的首都；Q：北京是一个故都；则原命题符号 化为： PQ。 21（2）小丽既聪明，又能干。 解：设P：小丽聪明；Q：小丽能干； 则原命题符号化为： PQ。（3）小刚聪明但不努力。 解：设P：小刚聪明；Q：小刚努力； 则原命题符号化为： PQ。（4）小刚和小明是同学。 解：这是一个原子命题，不能分解为更细的

13、命题。2022-3-7重庆邮电大学 理学院 22（3）析取联结词 设P,Q为二个命题变元，复合命题“P或Q” 称为P与Q的析取式， 记作P Q，符号称为析取联结词。 运算规则：二元运算。PQP Q00 0 0111011112022-3-7重庆邮电大学 理学院 23说明：联结词析取的意义与日常所使用的“或”意思并不完全相同。 在日常生活中，“或”实际上分为 “排斥或”和“可兼或”。 还有一种是描述模糊数据。 本书将析取表示“可兼或”。“排斥或”用等价的联结词代替。2022-3-7重庆邮电大学 理学院 24例：（1）今天晚上我在家看电视或听音乐。解：设P：今天晚上我在家看电视； Q：今天晚上我在

14、家听音乐； 则原命题符号化为： P Q 。（可兼或） （2）从重庆到北京的T10次列车是中午1点或1点半开。解：该命题中的“或”不是“可兼或”，不能用联结词析取。我们用 一种等价形式来代替。 设P：重庆到北京的T10次列车是中午1点开； Q：重庆到北京的T10次列车是中午1点半开； 则原命题符号化为： (PQ) (PQ). （排斥或）2022-3-7重庆邮电大学 理学院 25（3）小刚是山东或山西人。 解：设P：小刚是山东人；Q：小刚是山西人； 则原命题符号化为： (PQ) (PQ).（排斥或）（4）小刚是有20或30岁。 解：这是一个原子命题，这里的“或”表示一个模糊数据。 在遇到含有“或”

15、的命题符号化时，要分清它是“可兼或”、“排 斥或”、还是表示模糊数的“或”，析取联结词表示“可兼或”。 2022-3-7重庆邮电大学 理学院 26（4）单条件联结词 设P,Q为二个命题变元,复合命题“如果P,则Q” 称为P与Q的单条件（蕴涵式），记作PQ，并称P为单条件的前件，Q为单条件的后件，符号称为单条件结词。 运算规则：二元运算 与自然语言的不同：前件与后件可以没有任何内在联系！PQP Q0010111001112022-3-7重庆邮电大学 理学院 27说明：PQ 的逻辑关系：Q 为 P 的必要条件 “如果 P，则 Q ” 的不同表述法很多： “若P，就Q” “只要P，就Q” “P仅当Q

16、” “只有Q才P” “除非Q,才P”或“除非Q, 否则非P” .等等。当P为假时，无论Q是什么，PQ均为真。常出现的错误：不分充分与必要条件！2022-3-7重庆邮电大学 理学院 28例如：（1） 如果天下雨，那么我们在室内活动。 解：设P：天下雨；Q：我们在室内活动； 原命题符号化为：PQ 。 （2）只要天下雨，我们就在室内活动。 解：设P：天下雨；Q：我们在室内活动； 原命题符号化为：PQ 。 （3）因为天下雨，所以我们在室内活动。 解：设P：天下雨；Q：我们在室内活动； 原命题符号化为： PQ 。 在实际的语言中，很多联结词可以转化为用单条件，但是要注意前件和后件的关系。2022-3-7重庆邮电大学 理学院 29（4）只有天下雨，我们才在室内活动。 解：设P：天下雨；Q：我们在室内活动； 原命题符号化为：QP 。（5） 仅当天下雨，我们在室内活动。 解：设P：天下雨；Q：我们在室内活动； 原命题符号化为：QP 。（6） 除非天下雨，否则我们不在室内活动。 解：设P：天下雨；Q：我们在室内活动； 原命题符号化为：QP ，或者 P Q 。2022-3-7重庆邮电大学 理学院 30（5）双条件联结词 设P,Q为二个命题变元，复合命题“P当且仅当Q” 称为P与Q的双