离散数学是研究离散数量关系和离散结构数学模型的数学.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 i 1 表示简单命题用 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的合取式 记作p q 称作合取联结词 规定p q为真当且仅当p与q同时为真 可用下表来规定合取词 的意义 17 定义1 3设p q为两个命题 复合命题 p或q 称作p与q的析取式 记作p q 称作析取联结词 规定p q为假当且仅当p与q同时为假 可用下表来规定析取词 的意义 18 例2将下列命题符号化 1 吴颖既用功又聪明 2 吴颖不仅用功而且聪明 3 吴颖虽然聪明 但不用功 4 张辉与王丽都是三好生 5 张辉与王丽是同学 合取联结词的实例 19 解令p 吴颖用功 q 吴颖聪明 1 p q 2 p q 3 p q 4 设p 张辉是三好生 q 王丽是三好生p q 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是素数 p q 2 令p 2是素数 q 3是素数 p q 3 令p 4是素数 q 6是素数 p q 4 令p 小元元拿一个苹果 q 小元元拿一个梨 p q p q 5 p 王小红生于1975年 q 王小红生于1976年 p q p q 或p q 1 3 为相容或 即当p和q均真时 确认p q为真 在日常生活中 或 在有的场合下不同于上述意义 析取联结词的实例 22 例如 人固有一死 或重于泰山 或轻于鸿毛 其中的 或 是排斥的 即当发现有人的死既重于泰山又轻于鸿毛时 上述论断被认为假 这里的 或 用 表示不合适 可用下表规定的新联结词 排斥或 表示之 23 4 5 为排斥或 但是 像上述场合一样的许多场合下 两个析取命题事实上不可能同时为真 即上表的末行根本无需定义 这时用 代替 就没有问题 并且能使语句的表示简化 例如 a 0或a 0或a0 a 0 a0 a 0 a 0 符号化时 5 可有两种形式 而 4 则不能 24 蕴涵联结词 定义1 4设p q为两个命题 复合命题 如果p 则q 称作p与q的蕴涵式 记作p q 并称p是蕴涵式的前件 q为蕴涵式的后件 称作蕴涵联结词 规定 p q为假当且仅当p为真q为假 可用下表来规定该蕴涵词 的意义 25 1 p q的逻辑关系 q为p的必要条件 2 如果p 则q 有很多不同的表述方法 若p 就q只要p 就qp仅当q只有q才p除非q 才p或除非q 否则非p 3 当p为假时 p q恒为真 称为空证明 4 常出现的错误 不分充分与必要条件 26 例4设p 天冷 q 小王穿羽绒服 将下列命题符号化 1 只要天冷 小王就穿羽绒服 2 因为天冷 所以小王穿羽绒服 3 若小王不穿羽绒服 则天不冷 4 只有天冷 小王才穿羽绒服 5 除非天冷 小王才穿羽绒服 6 除非小王穿羽绒服 否则天不冷 7 如果天不冷 则小王不穿羽绒服 8 小王穿羽绒服仅当天冷的时候 蕴涵联结词的实例 p q 注意 p q与 q p等值 真值相同 p q p q q p q p p q q p q p 27 注意 上述规定的蕴涵词称为实质蕴涵 因为它不要求p q中的p q有什么关系 只要p q为命题 p q就有意义 例如 如果2 2 5 那么雪是黑的 就是一个有意义的命题 且据定义其真值为 真 28 定义1 5设p q为两个命题 复合命题 p当且仅当q 称作p与q的等价式 记作p q 称作等价联结词 规定p q为真当且仅当p与q同时为真或同时为假 p q的逻辑关系 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 p q p q p q p q为基本复合命题 其中要特别注意理解p q的涵义 反复使用 中的联结词组成更为复杂的复合命题 设p 是无理数 q 3是奇数 r 苹果是方的 s 太阳绕地球转则复合命题 p q r s p 是假命题 小结 联结词的运算顺序 同级按先出现者先运算 31 1 2命题公式及其赋值 命题变项与合式公式命题变项合式公式合式公式的层次公式的赋值公式赋值真值表 32 命题变项与合式公式 命题常项 表示具体命题及表示常命题的统称命题常项命题变项 命题变元 以 真 假 或 1 0 为取值范围的变元 它未指出符号所表示的具体命题 常项与变项均用p q r pi qi ri 等表示 定义1 6合式公式 简称公式 的递归定义 1 单个命题变项和命题常项是合式公式 称作原子命题公式 2 若A是合式公式 则 A 也是 3 若A B是合式公式 则 A B A B A B A B 也是 4 只有有限次地应用 1 3 形成的符号串才是合式公式 约定公式最外层和不影响运算次序的括号可省去 33 合式公式的层次 定义1 7 1 若公式A是单个命题变项 则称A为0层公式 2 称A是n 1 n 0 层公式是指下面情况之一 a A B B是n层公式 b A B C 其中B C分别为i层和j层公式 且n max i j c A B C 其中B C的层次及n同 b d A B C 其中B C的层次及n同 b e A B C 其中B C的层次及n同 b 3 若公式A的层次为k 则称A为k层公式 例如公式A p B p C p q D p q r E p q r r s 分别为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赋值 1 2 n是指p1 1 p2 2 pn n i 0或1 i之间不加标点符号A中仅出现p q r 给A赋值 1 2 3 是指p 1 q 2 r 3 含n个命题变项的公式有2n个赋值 如000 010 101 110是 p q r的成真赋值001 011 100 111是成假赋值 公式赋值 35 定义1 9将命题公式A在所有赋值下取值的情况列成表 称作A的真值表 构造真值表的步骤 1 找出公式中所含的全部命题变项p1 p2 pn 若无下角标则按字母顺序排列 列出2n个全部赋值 从00 0开始 按二进制加法 每次加1 直至11 1为止 2 按从低到高的顺序写出公式的各个层次 3 对每个赋值依次计算各层次的真值 直到最后计算出公式的真值为止 真值表 36 例6写出下列公式的真值表 并求它们的成真赋值和成假赋值 1 p q r 2 q p q p 3 p q q 真值表 37 1 A p q r 成真赋值 000 001 010 100 110 成假赋值 011 101 111 真值表1 38 2 B q p q p 成真赋值 00 01 10 11 无成假赋值 真值表2 39 3 C p q q的真值表 成假赋值 00 01 10 11 无成真赋值 真值表3 40 语句形式化要注意以下几个方面 要准确确定原子命题 并将其形式化 要选用恰当的联结词 尤其要善于识别自然语言中的联结词 有时它们被省略 否定词的位置要放准确 必要时可以进行改述 即改变原来的叙述方式 但要保证表达意思一致 需要的括号不能省略 而可以省略的括号 在需要提高公式可读性时亦可不省略 要注意语句的形式化未必是唯一的 用我们已有的符号语言 可以将许多自然语言语句形式化 下面我们用一些例子来说明 语句形式化须注意的地方 以及如何理解形式化了的语句 41 1 我和他既是兄弟又是同学 令p 我和他是兄弟 q 我和他是同学 3 狗急跳墙 令p 狗急了 q 狗跳墙 2 我和他之间至少有一个要去边疆 令p 我去边疆 q 他去边疆 例将下列语句形式化 并表示为命题公式 表示为p q 表示为p q 表示为p q 42 4 风雨无阻 我去上学 令p 天刮风 q 天下雨 r 我去上学 5 ABC与 A B C 全等的充要条件是 ABC与 A B C 的三边对应相等 令p ABC与 A B C 全等 q ABC与 A B C 的三边对应相等 还可表示为 p q r p q r p q r p q r 表示为 p q r p q r p q r p q r 表示为p q 43 1 p q 是偶数或 是奇数 3 r s q 若 是不等于2的质数 则 为奇数 2 p r s 若 是偶质数 则 2 5 r q s 是质数当且仅当 是奇数或 2 4 q s r 若 是奇数与 2之一真 不能成立 则 非质数 例 设p表示 是偶数 q表示 是奇数 r表示 是质数 s表示 2 那么 可如下理解各命题公式 44 第一章习题课 主要内容命题 真值 简单命题与复合命题 命题符号化联结词 及复合命题符号化命题公式及层次真值表及应用基本要求深刻理解各联结词的逻辑关系 熟练地将命题符号化会求复合命题的真值深刻理解合式公式的概念熟练地求公式的真值表 并用它求公式的成真赋值与成假赋值 45 作业习题一 1 2 4 8 9 10 46 1 将下列命题符号化 1 豆沙包是由面粉和红小豆做成的 2 苹果树和梨树都是落叶乔木 3 王小红或李大明是物理组成员 4 王小红或李大明中的一人是物理组成员 5 由于交通阻塞 他迟到了 6 如果交通不阻塞 他就不会迟到 7 他没迟到 所