离散数学是研究离散数量关系和离散结构数学模型的数学.ppt

1,屈婉玲 耿素云 张立昂,2,前 言,离散数学是研究离散数量关系和离散结构数学模型的数学分支的统称.是计算机科学与技术专业的核心基础课程.,“离散”和“连续”之间的对立与统一是数学发展的重要动力之一.古代数学主要讨论整数等离散与离散化了的数量关系，因而，那时数学被看成是研究上述数量关系的科学.但随着数学理论的发展，处理离散数量关系的数学工具在刻画和处理某类事务方面显得无能为力，因此出现了处理连续数量关系的数学工具：微积分.,3,近代数学主要以研究连续数量关系及其数学结构、数学模型，并取得了极其辉煌的成果，这一特征一直延续至今，仍在现代数学中占据支配地位（人们现在仍在学习微积分等经典数学理论）.,4,然而，近半个世纪以来，计算机的飞速发展与广泛应用，极大地冲击了现代数学.由于计算机是一个离散结构，它只能处理离散或离散化了的数量关系，因此，无论是计算机科学本身，还是与计算机科学极其应用密切相关的现代科学领域，都面临如何更有效地处理离散的对象和离散的数量关系，如何对离散结构建立数学模型以及如何将已用连续数量关系建立起来的数学模型离散化，从而可由计算机来加以处理.,5,计算机科学以研究计算领域中的一些普遍规律为其基本任务，在此过程中，涉及和应用了很多现代数学，所以需要以近代数学作为工具.离散数学的内容一直随着计算机科学的发展而不断得到扩充与更新.同时，离散数学也促进了计算机技术和计算机科学的发展.在计算机发展初期，人们利用布尔代数理论研究开关电路，建立了一套完整的数理逻辑理论，对计算机逻辑设计起了很大作用.,于是，人们开始从新认识离散数量关系的研究意义，重新重视讨论离散数量关系的数学分枝，并取得新的发展.,6,此外，在计算机科学中普遍采用离散数学中的基本概念、基本思想和方法.例如，集合论的概念和方法，抽象代数的概念和方法等，在计算机科学的各个领域随处都能碰到.所有这些都使得离散数学在计算机科学中的地位和作用越来越重要，成了必不可少的工具.因此有人把离散数学称为“计算机数学”.,7,离散数学的内容涵盖很广，到目前为止，它包括的主要内容有：集合论、数理逻辑、抽象代数、图论、自动机理论等.它们广泛应用于计算机科学的研究中，也大量应用于数据结构、操作系统、数据库理论等后续课程中.在物理、化学、生物等自然科学以及经济、教育等社会科学中，也正在获得广泛应用，有人预计，未来社会将有越来越多的人学习离散数学，就像当今人们学习微积分一样.,8,第一部分 数理逻辑 第一章 命题逻辑的基本概念 第二章 命题逻辑等值演算 第三章 命题逻辑的推理理论 第四章 一阶逻辑基本概念 第五章 一阶逻辑等值演算与推理,第二部分 集合论 第六章 集合代数 第七章 二元关系 第八章 函 数,第三部分 代数结构 第九章 代数系统 第十章 群 与 环 第十一章 格与布尔代数,第四部分 图论 第十四章 图的基本概念 第十五章 欧拉图与哈密顿图 第十六章 树 第十七章 平面图 第十八章 二分图,主要内容,9,主要内容 命题逻辑基本概念 命题逻辑等值演算 命题逻辑推理理论 一阶逻辑基本概念 一阶逻辑等值演算与推理,第一部分 数理逻辑,10,数理逻辑 是用数学的方法来研究人类推理过程的一门数学学科.,其显著特征是符号化和形式化，即把逻辑所涉及的“概念、判断、推理”用符号来表示，用公理体系来刻划, 并基于符号串形式的演算来描述推理过程的一般规律.,又称符号逻辑、现代逻辑.,11,第一章 命题逻辑的基本概念,主要内容 命题与联结词 命题及其分类 联结词与复合命题 命题公式及其赋值,12,命题与真值 命题：判断结果唯一的陈述句 命题的真值：判断的结果 真值的取值：真与假 真命题与假命题 注意： 感叹句、祈使句、疑问句都不是命题 陈述句中的悖论，判断结果不唯一确定的不是命题,1.1 命题与联结词,13,例1 下列句子中那些是命题？ (1) 是有理数. (2) 2 + 5 = 7. (3) x + 5 3. (4) 你去教室吗？ (5) 这个苹果真大呀！ (6) 请不要讲话！ (7) 2050年元旦下大雪. (8) 我说的这句话假.,假命题,命题概念,真命题,不是命题,不是命题,不是命题,不是命题,命题，但真值现在不知道,不是命题（悖论）,14,命题分类：简单命题（也称原子命题）与复合命题 简单命题符号化 用小写英文字母 p, q, r, , pi, qi, ri (i1)表示简单命题 用“1”表示真，用“0”表示假 例如，令 p： 是有理数，则 p 的真值为0， q：2 + 5 = 7，则 q 的真值为1,命题分类,15,否定、合取、析取联结词,定义1.1 设 p为命题，复合命题“非p”(或“p的否定”)称为p的否定式，记作p，符号称作否定联结词. 规定p 为真当且仅当p为假.,可用下表来规定否定词“”的意义:,16,定义1.2 设p,q为两个命题，复合命题“p并且q”(或“p与 q”)称为p与q的合取式，记作pq，称作合取联结词. 规定pq为真当且仅当p与q同时为真.,可用下表来规定合取词“”的意义：,17,定义1.3 设p, q为两个命题，复合命题“p或q”称作p与q的析取式，记作pq，称作析取联结词. 规定pq为假当且仅当p与q同时为假.,可用下表来规定析取词“”的意义：,18,例2 将下列命题符号化. (1) 吴颖既用功又聪明. (2) 吴颖不仅用功而且聪明. (3) 吴颖虽然聪明，但不用功. (4) 张辉与王丽都是三好生. (5) 张辉与王丽是同学.,合取联结词的实例,19,解 令p:吴颖用功, q:吴颖聪明 (1) pq (2) pq (3) pq (4) 设p:张辉是三好生, q:王丽是三好生 pq (5) p:张辉与王丽是同学 (1)(3) 说明描述合取式的灵活性与多样性 (4)(5) 要求分清 “与” 所联结的成分,合取联结词的实例,20,例3 将下列命题符号化 (1) 2 或 4 是素数. (2) 2 或 3 是素数. (3) 4 或 6 是素数. (4) 小元元只能拿一个苹果或一个梨. (5) 王小红生于 1975 年或 1976 年.,析取联结词的实例,21,解 (1) 令p:2是素数, q:4是素数, pq (2) 令p:2是素数, q:3是素数, pq (3) 令p:4是素数, q:6是素数, pq (4) 令p:小元元拿一个苹果, q:小元元拿一个梨 (pq)(pq) (5) p:王小红生于 1975 年, q:王小红生于1976 年, (pq)(pq) 或 pq (1)(3) 为相容或，即当 p 和 q 均真时，确认 pq为真.在日常生活中，“或”在有的场合下不同于上述意义.,析取联结词的实例,22,例如“人固有一死，或重于泰山，或轻于鸿毛”. 其中的“或”是排斥的，即当发现有人的死既重于泰山又轻于鸿毛时，上述论断被认为假. 这里的“或”用表示不合适.可用下表规定的新联结词“排斥或” 表示之.,23,(4)(5) 为排斥或,但是，像上述场合一样的许多场合下，两个析取命题事实上不可能同时为真，即上表的末行根本无需定义，这时用代替就没有问题，并且能使语句的表示简化. 例如“a 0或a=0或a0a=0a0a=0a0”. 符号化时(5)可有两种形式，而(4)则不能,24,蕴涵联结词,定义1.4 设p, q为两个命题，复合命题“如果p, 则q”称作p与q的蕴涵式，记作pq，并称p是蕴涵式的前件，q为蕴涵式的后件，称作蕴涵联结词. 规定：pq为假当且仅当p为真q为假.,可用下表来规定该蕴涵词“ ”的意义：,25,(1) pq 的逻辑关系：q为 p 的必要条件 (2) “如果 p, 则 q” 有很多不同的表述方法： 若p，就q 只要p，就q p仅当q 只有q 才p 除非q, 才p 或 除非q，否则非p， (3) 当 p 为假时，pq恒为真，称为空证明 (4) 常出现的错误：不分充分与必要条件,26,例4 设 p：天冷，q：小王穿羽绒服，将下列命题符号化 (1) 只要天冷，小王就穿羽绒服. (2) 因为天冷，所以小王穿羽绒服. (3) 若小王不穿羽绒服，则天不冷. (4) 只有天冷，小王才穿羽绒服. (5) 除非天冷，小王才穿羽绒服. (6) 除非小王穿羽绒服，否则天不冷. (7) 如果天不冷，则小王不穿羽绒服. (8) 小王穿羽绒服仅当天冷的时候.,蕴涵联结词的实例,pq,注意： pq 与 qp 等值（真值相同）,pq,pq,qp,qp,pq,qp,qp,27,注意: 上述规定的蕴涵词称为实质蕴涵，因为它不要求pq中的p，q有什么关系，只要p，q为命题，pq就有意义. 例如“如果2+2=5，那么雪是黑的”，就是一个有意义的命题，且据定义其真值为“真”.,28,定义1.5 设 p, q为两个命题，复合命题“p当且仅当q”称作p与q的等价式，记作pq，称作等价联结词. 规定pq为真当且仅当p与q同时为真或同时为假. pq 的逻辑关系：p与q互为充分必要条件,等价联结词,可用下表来规定该双向蕴涵词“ ”的意义：,29,例5 求下列复合命题的真值 (1) 2 + 2 4 当且仅当 3 + 3 6. (2) 2 + 2 4 当且仅当 3 是偶数. (3) 2 + 2 4 当且仅当 太阳从东方升起. (4) 2 + 2 4 当且仅当 美国位于非洲. (5) 函数 f (x) 在 x0 可导的充要条件是 它在 x0 连续.,1,0,1,0,0,30,本小节中p, q, r, 均表示命题.,联结词集为, , , , ，p, pq, pq, pq, pq为基本复合命题. 其中要特别注意理解pq的涵义. 反复使用, , , , 中的联结词组成更为复杂的复合命题. 设 p: 是无理数，q: 3是奇数， r: 苹果是方的， s: 太阳绕地球转 则复合命题 (pq) (rs) p) 是假命题.,小 结,联结词的运算顺序：, , , , , 同级按先出现者先运算.,31,1.2 命题公式及其赋值,命题变项与合式公式 命题变项 合式公式 合式公式的层次 公式的赋值 公式赋值 真值表,32,命题变项与合式公式,命题常项：表示具体命题及表示常命题的统称 命题常项 命题变项（命题变元）：以“真、假”或“1，0”为取值范围的变元，它未指出符号所表示的具体命题 . 常项与变项均用 p, q, r, , pi, qi, ri, , 等表示.,定义1.6 合式公式（简称公式）的递归定义： (1) 单个命题变项和命题常项是合式公式, 称作原子命题公式 (2) 若A是合式公式，则 (A)也是 (3) 若A, B是合式公式，则(AB), (AB), (AB), (AB)也是 (4) 只有有限次地应用(1)(3) 形成的符号串才是合式公式,约定公式最外层和不影响运算次序的括号可省去.,33,合式公式的层次,定义1.7 (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). (3) 若公式A的层次为k, 则称A为k层公式. 例如 公式 A=p, B=p, C=pq, D=(pq)r, E=(pq) r) (rs) 分别为0层，1层，2层，3层，4层公式.,34,定义1.8 设p1, p2, , pn是出现在公式A中的全部命题变项, 给p1, p2, , pn各指定一个真值, 称为对A的一个赋值或解释. 若使A为1, 则称这组值为A的成真赋值; 若使A为0, 则称这组 值为A的成假赋值. 几点说明： A中仅出现 p1, p2, , pn，给A赋值=12n是指 p1=1, p2=2, , pn=n, i=0或1, i之间不加标点符号 A中仅出现 p, q, r, , 给A赋值123是指 p=1, q=2 , r=3 含n个命题变项的公式有2n个赋值. 如 000, 010, 101, 110是(pq)r的成真赋值 001, 011, 100, 111是成假赋值.,公式赋值,35,定义1.9 将命题公式A在所有赋值下取值的情况列成表, 称作 A的真值表. 构造真值表的步骤: (1) 找出公式中所含的全部命题变项p1, p2, , pn(若无下角标 则按字母顺序排列), 列出2n个全部赋值, 从000开始, 按 二进制加法, 每次加1, 直至111为止. (2) 按从低到高的顺序写出公式的各个层次. (3) 对每个赋值依次计算各层次的真值, 直到最后计算出公式 的真值为止.,真值表,36,例6 写出下列公式的真值表, 并求它们的成真赋值和成假 赋值: (1) (pq) r (2) (qp) qp (3) (pq) q,真值表,37,(1) A = (pq) r,成真赋值:000,001,010,100,110; 成假赋值:011,101,111,真值表1,38,(2) B(qp)qp,成真赋值:00,01,10,11; 无成假赋值,真值表2,39,(3) C (pq)q的真值表,成假赋值:00,01,10,11; 无成真赋值,真值表3,40,语句形式化要注意以下几个方面：, 要准确确定原子命题，并将其形式化., 要选用恰当的联结词，尤其要善于识别自然语言中的联结词（有时它们被省略），否定词的位置要放准确., 必要时可以进行改述，即改变原来的叙述方式，但要保证表达意思一致., 需要的括号不能省略，而可以省略的括号，在需要提高公式可读性时亦可不省略., 要注意语句的形式化未必是唯一的.,用我们已有的符号语言，可以将许多自然语言语句形式化，下面我们用一些例子来说明，语句形式化须注意的地方，以及如何理解形式化了的语句.,41,（1）我和他既是兄弟又是同学. 令p：我和他是兄弟，q：我和他是同学.,（3）狗急跳墙. 令p：狗急了，q：狗跳墙.,（2）我和他之间至少有一个要去边疆. 令p：我去边疆，q：他去边疆.,例 将下列语句形式化，并表示为命题公式：,表示为pq,表示为pq,表示为pq,42,（4）风雨无阻，我去上学. 令 p：天刮风，q：天下雨，r：我去上学.,（5）ABC与ABC 全等的充要条件是 ABC与ABC 的三边对应相等. 令p： ABC与ABC 全等， q：ABC与ABC 的三边对应相等.,还可表示为(pqr)(pqr)(pqr)(pqr) .,表示为(pqr)(pqr)(pqr)(pqr) ,表示为 pq,43,（1）pq （是偶数或是奇数）,（3）rsq （若是不等于2的质数，则为奇数）,（2）prs （若是偶质数，则 =2）,（5）rqs （是质数当且仅当是奇数或=2）,（4）(qs)r （若“是奇数与=2之一真”不能成立，则非质数）,例：设p表示“是偶数”，q表示“是奇数”，r表示“是质数”，s表示“=2”，那么，可如下理解各命题公式：,44,第一章 习题课,主要内容 命题、真值、简单命题与复合命题、命题符号化 联结词, , , , 及复合命题符号化 命题公式及层次 真值表及应用 基本要求 深刻理解各联结词的逻辑关系, 熟练地将命题符号化 会求复合命题的真值 深刻理解合式公式的概念 熟练地求公式的真值表，并用它求公式的成真赋值与成假赋值,45,作业 习题一：1，2，4，8，9，10.,46,1. 将下列命题符号化 (1) 豆沙包是由面粉和红小豆做成的. (2) 苹果树和梨树都是落叶乔木. (3) 王小红或李大明是物理组成员. (4) 王小红或李大明中的一人是物理组成员. (5) 由于交通阻塞，他迟到了. (6) 如果交通不阻塞，他就不会迟到. (7) 他没迟到，所以交通没阻塞. (8) 除非交通阻塞，否则他不会迟到. (9) 他迟到当且仅