离散数学第1章课件

1、1,离散数学,教材： 屈婉玲、耿素云、，离散数学（修订版）， 高等教育出版社。,2, 赠2010级同学,任课教师：计算教研室 帕力旦 电 话：天才 在 于 勤 奋 , 知识 在 于 积 累 .,离散数学,3,用一组基本的指令来编制一个计算机程序,非常类似于从一组公理来构造一个数学证明。 D.E.Knuth,绪 言,离散数学是计算机科学中基础理论的核心 课程, 它以研究离散量的结构和相互关系为主 要目标, 其研究对象一般是有限个或可数个元 素组成的集合, 所以它充分地描述了计算机科 学离散性的特点.,4,5,6,7,离散数学的基础核心知识单元,集合和基本逻辑是最基础的，

2、再上是函数关系和树图，还有基本计数和证明技术。这些是最基础的，所有同学都要掌握的。,8,支撑核心知识单元-核心内容,这是承接上面来的，上面讲基本计数，这里讲高级计数；上面讲树图，这里讲特殊的图，像环图，带权图等，各种建模的方法图，所以他是下面基本知识的拓展。,9,支撑核心知识单元-核心内容,代数结构是建立代数模型，一般的离散数学建模是关系模型，数据库就是这样；而代数模型则体现在编码系统，也就是元素之间不仅仅是关系，而是通过运算把他联结起来,是学生必须掌握的 .,10,扩展知识单元,像形式系统，完全用公理系统来建立逻辑体系，要求推理是在系统内来建立，这对学生的思维训练是非常必要的。还有像集合基数

3、、计算理论、初等数论，作为选修课内容。,11,课程的设计,我们这个课程主要是以数学为工具进行计算机科学与技术研究（主要是建模），然后用数学的语言来表达事物的状态、关系和过程，经过推导形成解释和判断。它的特点是高度抽象、高精确、具有普遍意义。,12,计算机科学技术人才所需要的能力结构,获取知识的能力，系统的认知能力，理论分析能力，还有创造性思维和研究能力，至于实践能力要由其他课程实现，见下图,13,14,离散数学课程设置： 计算机专业核心课程 信息类专业必修课程,15,离散数学的后继课程： 数据结构、编译技术、 算法分析与设计、人工智能、 数据库、,16,离散数学课程的学习方法: 强调：逻辑性、

4、抽象性； 注重：概念、方法与应用,17,参考教材：,1、离散数学（左孝琳、李为槛、刘永才， 上海科技文献版） 2、离散数学-计算机数学基础学习（陈德人，浙大版） 3、Discrete Mathematics（ Forth:Richard Johnsonbaugh),18,教学内容:,数理逻辑（Mathematics Logic)（16） 集合论(Sets)（12） 代数结构（Algbra Structure)（8） 图论（Graph Theory)（12）,19,第一篇 数理逻辑,研究人的思维形式和规律的科学称为逻辑学，由于研究的对象和方法各有侧重而又分为形式逻辑、辨证逻辑和数理逻辑。 数理逻

5、辑是应用数学方法研究推理的科学。数理逻辑又叫符号逻辑，因为它的主要工具是符号体系。数理逻辑的核心是把逻辑推理符号化，即变成象数学演算一样完全形式化了的逻辑演算。,20,数理逻辑部分内容,第1章 命题逻辑基本概念 第2章 命题逻辑的等值演算 第3章 命题逻辑的推理理论 第4 章 一阶（谓词）逻辑基本概念 第5章 一阶（谓词）逻辑等值演算与推理,21,数理逻辑是用数学方法研究形式逻辑演绎推理规则的科学，它是一门数学，是一门研究演绎推理规则的数学，在学习此部分时，主要要掌握如下几个要点： 思维的形式化 指派法 公式推理 公理系统 范式 自动定理证明,22,第1章 命题逻辑,1.1 命题及联结词 1.

6、2 命题公式及其赋值,23,1.1 命题符号化及联结词,1.命题: 判断结果惟一的陈述句。简言之，命题是非真即假的陈述句。 （并不要求该陈述句恒为真） 命题的真值: 判断的结果,24,命题与真值,1.命题判断结果只能有两种情况，一种是正确的判断，一种是错误的判断。称判断结果正确的命题为真命题（真值为真），一般用1(或T)表示；称判断结果错误的命题是假命题（真值为假），用0(或F)表示。,因而又可以称命题是具有唯一真值的陈述句。,25,例 下列句子中那些是命题？ (1) 是无理数. (2) 2 + 5 8. (3) x + 5 3. (4) 你有铅笔吗？ (5) 这只兔子跑得真快呀！ (6) 请

7、不要讲话！ (7) 我正在说谎话.,真命题,假命题,真值不确定,疑问句,感叹句,祈使句,悖论,(3)(7)都不是命题,26,例 2 一个人说：“我正在说谎”。,分析：他是在说谎还是在说真话呢？如果他讲真话，那么他所说的是真， 也就是他在说谎。 我们得出结论如果他讲真话，那么他是在说谎；另一方面，如果他是说谎，那么他说的是假； 因为他承认他是说谎， 所以他实际上是在说真话，我们得出结论如果他是说谎，那么他是讲真话。 从以上分析， 我们得出他必须既非说谎也不是讲真话。这样，陈述句“我正在说谎”事实上不能指定它的真假，所以不是命题。 这种陈述句叫悖论。,27,总 结 从以上的分析可以看出，判断一个句

8、子是否为命题，首先要看它是否为陈述句，然后再看它的真值是否唯一确定。 注意：真值是否唯一确定与我们是否知道它的真值是两回事。,28,命题的分类,简单命题(原子命题)： 简单陈述句构成的命题 复合命题： 由简单命题与联结词按一定规则复合 而成的命题,29,原子命题,复合命题与命题联结词,2.原子命题和复合命题 若一个命题不能分解成更简单的命题, 则这个命题称之为本原命题或原子命题。 原子命题是最基本的命题，常用大写字母P 、Q 、 R 表示。将表示命题的符号放在该命题的前面，称为命题符号化。 例如:P：2是素数。 Q：雪是黑色的。 此时，P是真命题，Q是假命题。,30,由简单命题和联结词(和、且

9、、或、如果则等)复合而成的一个陈述句称为复合命题。 例如： P： 明天下雪 Q：明天下雨 是两个命题，利用联结词“不”、“并且”、 “或”等可分别构成新命题： “明天不下雪”； “明天下雪并且明天下雨”； “明天下雪或者明天下雨”等。,31,即 ： “非P”； “P并且Q”； “P或Q”等。 在代数式x+3 中， x 、 3 叫运算对象， +叫运算符，x+3 表示运算结果。在命题演算中， 也用同样术语。联结词就是命题演算中的运算符，叫逻辑运算符或叫命题联结词。常用的命题联结主要有 5 个。,32,1 否定词 ,设P表示命题，则P不真 是另一命题，记为 P 读为 非P,33,例: (a) P:

10、3是偶数。 则P： 3是偶数。 (b) Q: 4 是质数。 则Q： 4 不是质数。或 “说4 是质数是不对的”。 (c) R: 我们都是汉族人。 则R: 我们不都是汉族人。 (d) S: 今天下雨并且今天下雪。 则 S:今天不下雨或者今天不下雪。,34,2 合取词 ,若 P,Q 表示命题， 则 P并且Q 也是命题， 记为 PQ,35,例1 2是素数和偶数解：设P：2是素数 Q：2是偶数 则P Q：2是素数和偶数。 由于p，q的真值均为1，所以p q的真值为1。,36,例2 如果用p表示“李平聪明”，q表示“李平用功”。将下列命题符号化:(1)李平既聪明又用功。 (2)李平虽然聪明，但不用功。

11、(3)李平不但聪明，而且用功。 (4)李平不是不聪明，而是不用功。,p q,p q,p q, ( p) q,37,课堂练习： 将下列命题符号化:(1) 8能被2整除，但不能被6整除。 (2) 5是奇数，6是偶数。 (3) 2与3的最小公倍数是6。 (4) 王丽和王鹃是亲姐妹。,38,总 结 使用联结词应注意： 其一是的灵活性。日常语言中的“既，又”、“不但，而且”、“虽然，但是”、“一面，一面.”等都应符号化为。 其二，不要见到“与”或“和”就使用联结词。,39,3 析取词 ,若 P,Q 表示命题则 P或者Q 也是命题 记为 PQ,40,例 1：今晚我写字或看书 用 P: 今晚我写字, Q:

12、今晚我看书。 则可符号化为： PQ,注意 自然语言中的“或” 的含义有两种： 一是“可兼或”，另一种是“排斥或” 析取式PQ表示的是一种可兼或， 即允许P与Q同时为真。,这个例子中的“或”是“可兼或”, 因为它不排除今晚既看书又写字这种情况。,41,例 将下列命题符号化 (1) 2或4是素数. (2) 2或3是素数. (3) 4或6是素数.,PQ,PQ,PQ,42,(4) 小元元只能拿一个苹果或一个梨. 令 t :小元元拿一个苹果，u:小元元拿一个梨， (tu) (tu). (5) 王晓红生于1975年或1976年. 令v :王晓红生于1975年,w:王晓红生于1976年, (vw)(vw),

13、43,4 蕴涵词 ,若 P,Q 表示命题则 P蕴涵Q 也是命题， 记为 PQ,44,在使用蕴涵联结词时，除了注意其表示的基本逻辑关系外，还应注意两点： 在自然语言中，“如果P，则Q”中的P与Q往往有某种内在的联系，这样的蕴含式叫实质蕴含。但在数理逻辑中“PQ”中的P与Q不一定有什么内在联系，这样的蕴含式叫。形式蕴含 在数学中，“如果P，则Q”往往表示前件P为真，后件Q为真的推理关系，但在数理逻辑中，当前件P为假时，PQ为真。,45,关于 PQ 真值表的说明,在日常生活中当P=0时，PQ 没有实际意义。 故人们只考虑 P=1 的情形。但在PQ 真值表中规定: 当 P=0 时,不管 Q 如何 PQ

14、 的真值都为1. 有没有道理呢？ 例如,张三对李四说:我去图书馆一定帮你借那本书. 可以将这句话表为命题 PQ(P表示:张三去图书馆,Q 表示:张三借那本书).后来张三因有事未去图书馆,即 P=0,此时按规定 PQ 为真. 我们应理解为张三讲了 真话,即他要是去图书馆我们相信他一定会为李四借 书.这种理解也称为善意推定.,46,例2：将下列命题符号化，并判断其真值 1）.若2+24，则太阳从东方升起。 2）.若2+24 ，则太阳从东方升起。 3）.若2+24 ，则太阳从西方升起。 4）.若2+24 ，则太阳从西方升起。,解 设 ：P: 2+24 ，则其真值为1；q:太阳从东方升起，则其真值为1

15、；r:太阳从西方升起，则其真值为0； 则(1)符号化为pq，该蕴涵式的真值为1。 (2)符号化为 pq ，该蕴涵式的真值为1。 (3)符号化为pr ，该蕴涵式的真值为0。 (4)符号化为 pr ，该蕴涵式的真值为1。,47,总 结 蕴含式PQ基本逻辑关系是，Q是P的必要条件，或P是Q的充分条件。有多种等价方式表达：“只要P，就Q”、 “因为P，所以Q”、 “P仅当Q”、 “只有Q才P”、 “除非P才Q”等。 给定命题PQ, 我们把QP, P Q, Q P分别叫做命题PQ的逆命题 、反命题和逆反命题.,48,例 设 p:天冷，q:小王穿羽绒服， 将下列命题符号化 (1) 只要天冷，小王就穿羽绒服

16、. (2) 因为天冷，所以小王穿羽绒服. (3) 若小王不穿羽绒服，则天不冷. (4) 只有天冷，小王才穿羽绒服. (5) 除非天冷，小王才穿羽绒服. (6) 除非小王穿羽绒服，否则天不冷. (7) 如果天不冷，则小王不穿羽绒服. (8) 小王穿羽绒服仅当天冷的时候.,pq,pq,pq,pq,qp,qp,qp,qp,49,5 当且仅当 ,若 P,Q 表示命题,则 PQ, 也是命题, 即P等价蕴含Q,50,例 求下列复合命题的真值 (1) 2 + 2 4 当且仅当 3 + 3 6. (2) 2 + 2 4 当且仅当 3 是偶数. (3) 2 + 2 4 当且仅当 太阳从东方升起. (4) 2 +

17、 2 4 当且仅当 美国位于非洲. (5) 函数 f (x) 在x0 可导的充要条件是它在 x0 连续. 它们的真值分别为 1，0，1，0，0.,51,PQ 当且仅当 PQ QP,证:只须证 PQ为假(真)当且仅当 PQ,QP均为假. 从PQ的真值表看出 PQ为假 当且仅当 Q真P假和P真Q假 即 PQ为假 当且仅当 QP,PQ 均为假,52,例： 将下列命题符号化，并讨论它们的真值:(1) 雪是白色的当且仅当法国的首都是里昂。 (2) n是奇数的充分必要条件是n2是奇数。 (3) 若两圆O1，O2的面积相等，则它们的半径相 等。反之，若O1，O2的半径相等，则它们的 面积相等。 (4) 设角

18、1与角2是对顶角，则角1等于角2。反 之，若角1等于角2，则它们是对顶角。,53,五个逻辑运算符强弱顺序,逻辑运算符结合力的强弱顺序约定为： , 没有括号时按上述先后顺序执行. 相同运算符按从左至右顺序执行括号可省去. 最外层的括号总可以省去. 例如 PPQSQR 与 (P)(P)(Q(S)(Q)R) 运算顺序完全一样,而前者不加一个括号. 请大家特别注意先后的习惯.,54,例2：分别将下列复合命题符号化： (a) 设P：他有理论知识, Q：他有实践经验。 则“他既有理论知识又有实践经验” 可表示为： (b) 设P: 明天下雨, Q: 明天下雪, R: 我去学校。 则 (i) “如果明天不是雨

19、夹雪则我去学校” (ii) “如果明天不下雨并且不下雪则我去学校” (iii) “如果明天下雨或下雪则我不去学校”,PQ,(PQ)R,PQR,PQ R,55,(iv)“当且仅当明天不下雪并且不下雨时我才去学校” (c)设P: 小学生会编程序, Q: 小学生会用个人计算机。 用逻辑符表达“说小学生编不了程序, 或说小学生用不了个人计算机, 那是不对的”。,PQ R,( PQ),56,(d) 用逻辑符表达“若不是他生病或出差了, 我是不会同意他不参加学习”。 设P: 他生病了, Q: 他出差了, R: 我同意他不参加学习。 则上句可译为,或 PQ R,(PQ) R,57,命题符号化自然语言翻译为逻

20、辑式,命题符号化的含义是:把所考虑的命题的有关语言翻译为只含逻辑符号的逻辑式. 命题符号化的重要性在于:它是用命题演算解决实际问题的先决条件.,58,1.2 命题公式及赋值分类,命题变项与合式公式 公式的赋值 真值表 命题的分类 重言式 矛盾式 可满足式,59,命题变项与合式公式,以真,假为变域的变元称为命题变元; T(True) 和 F(False) 称为命题常元. 定义： 合式公式 (命题公式) 递归定义如下： (1) 单个命题常项或变项 p,q,r,pi ,qi ,ri ,0,1 是合式公式 (2) 若A是合式公式，则 (A)也是合式公式 (3) 若A, B是合式公式，则(AB), (A

21、B), (AB), (AB)也是合式公式 (4) 只有有限次地应用(1)(3)形成的符号串才是合式公式,60,合式公式的层次,定义 (1) 若公式A是单个的命题变项, 则称A为0层公式. (2) 称A是n+1(n0)层公式是指下面情况之一： (a) A=B, B是n层公式； (b) A=BC, 其中B,C分别为i层和j层公式，且 n=max(i, j)； (c) A=BC, 其中B,C的层次及n同(b)； (d) A=BC, 其中B,C的层次及n同(b)； (e) A=BC, 其中B,C的层次及n同(b).,61,合式公式的层次 (续),例如 公式 p 0层 p 1层 pq 2层 (pq)r 3层 (pq) r)(rs) 4层,62,公式的赋值,A中仅出现 p, q, r, , 给A赋值123是指 p=1, q=2 , r=3 i=0或1. 含n个变项的公式有2n个赋值.,定义 给公式A中的命题变项 p1, p2, , pn指定 一组