离散数学教程PPT课件.ppt

离散数学 数学与信息科学学院 1 第一部分数理逻辑第二部分集合论第三部分图论第四部分抽象代数 离散数学 2 第一部分数理逻辑 数理逻辑是用数学方法研究推理中前提和结论之间的形式关系的学科 推理是由一个或几个判断推出一个新判断的思维形式 数学方法是指建立一套表意符号体系 对具体事物进行抽象的形式研究的方法 3 第一章命题逻辑第二章一阶谓词逻辑 第一部分数理逻辑 4 1 1命题和命题联结词1 2命题公式及其赋值1 3等值演算与联结词完备集1 4析取范式与合取范式1 5推理的形式结构1 6自然推理系统P 第一章命题逻辑 5 1 命题 能判断真假的陈述句 包含两层意思 1 必须是陈述句 2 能够确定 分辨 其真值 1 1命题和命题联结词 6 1 1命题和命题联结词 7 2 命题的真值 判断结果 注意 此处不纠缠具体命题的真假问题 只是将其作为数学概念来处理 真值 真用T或1表示 假用F或0表示 3 命题和真值的符号化 1 1命题和命题联结词 8 1 1命题和命题联结词 9 原子命题 不能被分解为更简单的陈述句复合命题 原子命题通过联结词联结而成 例 2是有理数是不对的 2是偶素数 2或4是素数 如果2是素数 则3也是素数 2是素数当且仅当3也是素数 p 2是有理数 q 2是偶数 r 2是素数 s 3是素数 t 4是素数 1 1命题和命题联结词 10 4 命题联结词 1 1命题和命题联结词 11 王化不但成绩好而且品德好 p q 1 1命题和命题联结词 12 1 1命题和命题联结词 开关坏了或灯泡坏了 p q 13 例 1 张晓婧爱唱歌或爱听音乐 2 张晓婧是内蒙人或是陕西人 3 张晓婧只能挑选202或203房间 1 1命题和命题联结词 注意 当排斥或两边的情况实际根本不可能同时发生的时候 排斥或也可抽象为 但为了方便起见一般不这样抽象 14 有位父亲对儿子说 如果我去书店 就一定给你买电脑报 问 在什么情况下 父亲算失信呢 1 1命题和命题联结词 15 注意 只要p 就q 因为p 所以q p仅当q 只有q 才p 除非q才p 除非q 否则非p 都可抽象为p q p q可以没有任何内在联系 例 1 如果3 3 6 那么雪是白的 2 除非我能工作完成了 我才去看电影 3 只要天下雨 我就回家 4 我回家仅当天下雨 p q的逻辑关系为q是p的必要条件或p是q的充分条件 1 1命题和命题联结词 16 1 1命题和命题联结词 pq的逻辑关系为p与q互为充要条件 例 1 3是有理数当且仅当加拿大位于亚洲 2 两圆的面积相等 则他们的半径相等 反之亦然 17 1 1命题和命题联结词 例 今天第一节课上离散数学或数据结构 18 例 p 北京比天津人口多q 2 2 4r 乌鸦是黑色的 1 1命题和命题联结词 19 5 语句形式化 1 1命题和命题联结词 例 2是有理数是不对的 2是偶素数 2或4是素数 如果2是素数 则3也是素数 2是素数当且仅当3也是素数 p 2是有理数 q 2是偶数 r 2是素数 s 3是素数 t 4是素数 p不对 q且r r或t 如果r 则s r当且仅当s 20 1 1命题和命题联结词 21 命题常元 表示具体确定内容的命题 命题变元 表示不确定具体内容的命题 1 2命题公式及其赋值 22 1 2命题公式及其赋值 同时约定 1 最外层的括号可以省去 2 不影响运算次序的括号也可以省去 23 1 2命题公式及其赋值 24 1 2命题公式及其赋值 25 1 2命题公式及其赋值 26 1 2命题公式及其赋值 27 1 2命题公式及其赋值 28 1 3命题公式的等值式 29 基本等值式 A B C为任意命题公式 1 3命题公式的等值式 30 1 3命题公式的等值式 31 因A B C可以代入任意的命题公式 故以上等值式称为等值式模式 由已知的等值式推演出另外一些等值式的过程为等值演算 1 3命题公式的等值式 32 等值演算的应用 1 验证等值式2 判定公式的类型3 解决工作生活中的判断问题 1 3命题公式的等值式 甲 已 丙3人根据口音对王教授是哪人进行了判断 甲说 王教授不是苏州人 是上海人已说 王教授不是上海人 是苏州人丙说 王教授既不是上海人 也不是杭州人结果3人中有一人全对 一人对一半 一人全错 问王教授是哪人 33 联结词的完备集 n个命题变元可以形成22n个不同的真值函数 对于每个真值函数 都可以找到许多与之等值的命题公式 而每个命题公式对应唯一的与之等值的真值函数 定义 设S是一个联结词集合 如果任何n n 1 元真值函数都可以由仅含S中的联结词构成的公式表示 则称S是联结词完备集 34 联结词的完备集 35 1 4析取范式与合取范式 定义 命题变元及其否定统称为文字 仅由有限个文字构成的析取式称为简单 质 析取式 仅由有限个文字构成的合取式称为简单 质 合取式 注意 单个文字既是简单析取式又是简单合取式 讨论 设A为含n个文字的简单析取式若A中同时含pi和 pi 则 若A为永真式 则 36 若A为永真式 则A中必同时含有pi和 pi 反之亦然 同理有 若A为简单合取式 A为永假式的充要条件是A中同时含有pi和 pi 定理1 一个简单析取式是重言式当且仅当它同时含有某个命题变元及其他的否定 一个简单合取式是矛盾式当且仅当它同时含有某个命题变元及其他的否定 1 4析取范式与合取范式 37 定义 由有限个简单合取式构成的析取式称为析取范式 由有限个简单析取式构成的合取式称为合取范式 析取范式与合取范式称为范式 注意 单个文字 简单析取式 简单合取式都既是析取范式又是合取范式 1 4析取范式与合取范式 定理2 一个析取范式是矛盾式当且仅当它的每个简单合取式为矛盾式 一个合取范式是重言式当且仅当它的每个简单析取式为重言式 38 定理3 任一命题公式都存在与之等值的析取范式和合取范式 范式的求法 消去公式中的蕴涵 等价和异或联结词 使用双重否定律和德摩根律 将公式中出现的否定词移到命题变元之前 利用分配律 结合律将公式化为合 析 取范式 范式形式不唯一 1 4析取范式与合取范式 39 定义 在含有n个命题变元的简单合 析 取式中 若每个命题变元和它的否定式不同时出现 而二者之一必出现且仅出现一次 且第i个命题变元或它的否定是出现在从左算起的第i位上 字典序 称这样的简单合 析 取式为极小 大 项 性质 n个变元可以形成2n个极小 大 项 每个极小 大 项有且仅有一个成真 假 赋值 每组赋值下仅有一个极小 大 项为真 假 所有极小 大 项的析 合 取为真 假 1 4析取范式与合取范式 40 将极小项的成真赋值对应的二进制数转化为十进制数为i 将对应的极小项记为mi 将极大项的成假赋值对应的二进制数转化为十进制数为i 将对应的极大项记为Mi 定义 设由n个命题变元构成的析 合 取范式中所有的简单合 析 取式都是极小 大 项 则称该析取范式为主析 合 取范式 1 4析取范式与合取范式 定理 任何命题公式都存在与之等值的主析取范式和主合取范式 并且是唯一的 41 1 4析取范式与合取范式 公式法 求析取范式 用同一律补进未出现的命题变元 消去永假或重复出现的变元和极小项 将极小项按下标从小到大排列 真值表法 列出公式及各极小项的真值表 将每组赋值下公式及极小项真值都为真的极小项进行析取 主析取范式的求法 1 公式法2 真值表法 42 1 4析取范式与合取范式 应用 1 求公式的成真 成假赋值成真赋值为析取范式中所含极小项的编码的二进制数成假赋值为合取范式中所含极大项的编码的二进制数 由主析取范式可以直接求主合取范式 1 求出主析取范式中未包含的极小项2 求出与1 中求出的极小项下标相同的极大项3 做2 中极大项之合取 43 1 4析取范式与合取范式 3 判断两公式是否等值若A B共含有n个命题变元 按n个命题变元求出A与B的主析取范式A B 若A B 则A B 2 判断公式的类型设A含有n个命题变元 A为重言式当且仅当A的主析取范式含全部2n个极小项 A为矛盾式当且仅当A的主析取范式不含任何极小项 此时记为0 A为可满足式当且仅当A的主析取范式中至少含一个极小项 44 例 要在A B C中挑选2名出国进修 选派时满足下列条件 若A去 则C同去 若B去 则C不能去 若C不去 则A或B可以去问有几种选派方案 分别是什么 4 解决实际问题 1 4析取范式与合取范式 45 1 5推理的形式结构 注意 推理正确实际是排除前提真结论假的情况 推理是否正确与前提的排列顺序无关 推理正确并不能保证B一定为真 46 1 5推理的形式结构 推理的形式结构 47 1 5推理的形式结构 48 例 若下午温度超过30度 则王晓燕必去游泳 若她去游泳 她就不会去看电影 所以若王晓燕没去看电影 下午温度必超过了30度 p 温度超过30度q 王晓燕去游泳r 王晓燕去看电影 1 5推理的形式结构 49 1 5推理的形式结构 50 注意 以上都是蕴含式模式 若某推理的形式结构与某定律一致 则推理正确 成立的等值式可产生两条定律 推理定律可产生相应的推理规则 1 5推理的形式结构 51 1 6自然推理系统P 定义 一个形式系统I由以下4部分组成 非空的字母表 记作A I A I 中符号构成的合式公式集 记作E I E I 中特殊的公式组成的公理集 记作Ax I 推理规则集 记作R I 任给的前提 应用规则得到结论 可能真 任给的公理 应用规则得到结论 永真 52 1 6自然推理系统P 53 1 6自然推理系统P 54 例 若小王是理科生 则他的数学成绩一定很好 如果小王不是理科生 他一定是文科生 小王的数学成绩不好 所以小王是文科生 p 小王是理科生q 小王是文科生r 小王的数学成绩很好 1 6自然推理系统P 55 例 如果小张和小王去看电影 则小李也去看电影 小赵不去看电影或小张去看电影 小王去看电影 所以 当小赵去看电影时 小李也去 p 小张去看电影q 小王去看电影r 小李去看电影s 小赵去看电影 1 6自然推理系统P 56 2 归谬法将结论的否定作为前提引入 能推出矛盾来 则推理正确 例 如果马会飞或羊不吃草 则母鸡就会是飞鸟 如果母鸡是飞鸟 那么烤熟的鸭子还会跑 烤熟的鸭子不会跑 所以羊吃草 p 马会飞q 羊吃草r 母鸡是飞鸟s 烤熟的鸭子会跑 1 6自然推理系统P 57 所有的人总是要死的 苏格拉底是人 所以苏格拉底是要死的 p q r 第二章谓词逻辑 58 第二章谓词逻辑 2 1一阶逻辑命题符号化2 2一阶逻辑公式及解释2 3一阶逻辑等值式与置换规则2 4一阶逻辑前束范式2 5一阶逻辑的推理理论 59 2 1一阶逻辑命题符号化 1 个体词 所研究对象中可以独立存在的具体的或抽象的客体 事物 表示具体的或特定的客体 表示抽象或泛指的客体 个体变项的取值范围称为个体域 用D表示 宇宙间一切事物组成的称为全总个体域 60 2 谓词 用来刻划个体词性质及个体词之间相互关系的词 2是有理数x是无理数小王与小李同岁x与y具有关系L 是有理数 是无理数 与 同岁 与 具有关系L F G H L 2 1一阶逻辑命题符号化 61 3 量词 个体词之间的数量关系 1 全称量词 一切的 所有的 每一个 任意的 凡 都 记作 4 符号化 确定个体域 确定个体词 量词和谓词 确定联结词 2 1一阶逻辑命题符号化 62 例 所有的人都是要死的 有的人用左手写字 注意 全称量词的特性谓词必须作为蕴涵式的前件引入 存在量词的特性谓词必须作为合取式的合取项引入 同一命题 不同的个体域符号化的形式可能不同 未指明个体域即为全总个体域 2 1一阶逻辑命题符号化 63 例 在美国留学的学生未必都是亚洲人 有的兔子比所有的乌龟跑的快 对任意的整数x 都存在整数y使得x y 10 注意 多个量词出现时 顺序一般不能随便换 有些命题符号化形式不唯一 2 1一阶逻辑命题符号化 64 2 2一阶逻辑公式及解释 65 2 2一阶逻辑公式及解释 66 合式公式也称谓词公式 简称公式 2 2一阶逻辑公式及解释 67 2 2一阶逻辑公式及解释 68 2 2一阶逻辑公式及解释 69 2 2一阶逻辑公式及解释 70 定理 闭式在任何解释下都变成命题 2 2一阶逻辑公式及解释 71 2 2一阶逻辑公式及解释 72 定理 重言式的代换实例都是永真式 矛盾式的代换实例都是矛盾式 2 2一阶逻辑公式及解释 73 2 3一阶逻辑等值式与置换规则 第一组命题逻辑中等值式模式的代换实例都是一阶逻辑的等值式模式 第二组一阶逻辑中特殊的等值式 74 2 3一阶逻辑等值式与置换规则 75 D N F x x是奇数G x x是偶数 2 3一阶逻辑等值式与置换规则 76 2 3一阶逻辑等值式与置换规则 77 2 3一阶逻辑等值式与置换规则 78 2 4一阶逻辑前束范式 为了方便使用谓词公式进行定理证明和逻辑推理 需要把谓词公式变换为便于使用的规范形式 就是范式 79 定理1 任一谓词公式都可以化成为与之等值的前束范式 2 4一阶逻辑前束范式 80 2 4一阶逻辑前束范式 81 2 5一阶逻辑的推理理论 在一阶逻辑中 称永真的蕴涵式为推理定律 若一个推理的形式结构正是某条推理定律 则该推理显然是正确的 第一组命题逻辑推理定律的代换实例 第二组由基本等值式生成的推理定律 第三组以下重要定律 82 第四组消去量词和引入量词的推理规则 1 全称量词消去规则 UI 2 5一阶逻辑的推理理论 83 UI规则成立的条件 1 取代x的y应为任意不在A x 中约束出现的个体变项 2 用y取代A x 中自由出现的x时 必须将所有的自由出现x都取代 3 自由变元y也可替换为个体域中任意的个体常元c c为任意不在A x 中出现过的个体常项 2 5一阶逻辑的推理理论 84 含义 如果个体域的所有个体都具有性质A 则个体域中的任一个个体都具有性质A 2 存在量词消去规则 EI 含义 如果个体域存在有性质A的个体 则个体域中必有某一个个体具有性质A 2 5一阶逻辑的推理理论 85 ES规则成立的条件 1 c是个体域中使A为真的特定的个体常项 2 c不曾在A x 或前面的推导公式中出现过 3 A x 中除x外还有其他自由变元时 不能用此规则 2 5一阶逻辑的推理理论 86 3 全称量词引入规则 UG UG规则成立的条件 1 y在A y 中自由出现 且y取任何值时A均为真 2 x不在A y 中约束出现 含义 如果个体域的任意个体都具有性质A 则个体域中的所有个体都具有性质A 2 5一阶逻辑的推理理论 87 4 存在量词引入规则 EG EG规则成立的条件 1 c是个体域中某个确定的个体 2 代替c的x不在A c 中出现过 含义 如果个体域有某一个个体c具有性质A 则个体域中必存在具有性质A的个体 2 5一阶逻辑的推理理论 88 定义 一阶逻辑自然推理系统F的定义1 字母表 同一阶语言的字母表2 合式公式 同一阶语言合式公式的定义3 推理规则a 前提引入规则b 结论引入规则c 置换规则d 假言推理规则e 附加规则f 化简规则g 拒取式规则h 假言三段论规则i 析取三段论规则j 构造性二难规则k 合取引入规则l UI EI UG EG 2 5一阶逻辑的推理理论 89 例7 证明逻辑三段论所有的人总是要死的 苏格拉底是人 所以苏格拉底是要死的 2 5一阶逻辑的推理理论 90 2 5一阶逻辑的推理理论 例10 如果一个人怕困难就不会获得成功 每一个人或者获得成功或者是失败的 有些人未曾失败过 所以有些人不怕困难 个体域是人的集合 判断这个推理是否正确 例9 根据前提集合 同事之间总是有工作矛盾的 张平和李明没有工作矛盾 能得出什么结论 91 第二部分集合论 第三章集合代数第四章二元关系第五章函数 92 第三章集合代数 3 1集合的基本概念3 2集合的运算3 3集合恒等式 93 一 集合的概念集合 set 的含义 一个集合是作为整体识别的 确定的 互相区别的一些事物的聚集 全体或总体等 构成一个集合的每个事物 成为这个集合中的元素或成员 集合一般用A B C 表示 集合中的元素用a b c 表示 但这不是绝对的 因为一个集合可以作为另一个集合的元素 如果x是集合s的一个元素 记作 y不是集合s的元素 记作 3 1集合的基本概念 94 例1 1 偶素数集合 2 二进制的基数集合 3 英文字母的集合 4 全体实数的集合 5 自然数集合 6 整数集合 7 有理数集合 8 素数集合 3 1集合的基本概念 95 3 1集合的基本概念 集合的表示方法 1 列举法 枚举法 外延法 把集合的所有元素 元素较少时 写在一个花括号内 列出足够多的元素 元素很多或无穷时 以反映集合中元素的特征 如例1中的1 2 3 5可分别表示为 2 0 1 a b c z A B C Z 1 2 3 96 3 1集合的基本概念 2 描述法 概括法 将集合中的元素的性质用一个谓词公式来描述 S X P X 意义为 集合S由且仅由满足为此公式P X 的对象组成 即 当且仅当p a 为真 如例1中的4 6 7可表示为 3 文氏图用图形图像直观的描述集合之间的相互关系和有关运算 97 3 1集合的基本概念 几个常见集合的表示符号 N 自然数集合 N 0 1 2 3 I 整数集合 P 素数或质数集合 Q 有理数集合 R 实数集合 C 复数集合 98 3 1集合的基本概念 集合的特性 A 互异性 一个集合的个元素是可以区分开的 即每一元素只出现一次 B 无序性 集合中元素排列顺序无关紧要 即集合表示形式的不唯一性 例2 a b c b c a c a b a c b b a c c b a 99 3 1集合的基本概念 C 确定性 任一事物是否属于某一集合 回答是确定的 例3 好书 的全体 这不构成集合 注意 一个集合是已知的 指的是对任一元素 利用某种方法可以判断它是否是这个集合的元素 而不是把集合的每一个元素都给出来 100 3 1集合的基本概念 集合的元素可以是任何具体或抽象的事物 包括别的集合 但不能是本集合自身 例4 在一个住着一些人家的偏僻孤岛上 岛上只有一个理发师a a给且只给岛上所有不能自己理发的人理发 问谁给a理发 101 定义1 设A和B是两个集合 若A中的每一个元素都是B的元素 则称A是B的子集 也称B包含A 记作 3 1集合的基本概念 定义2 设A和B是任意两个集合 若A包含B且B包含A 则称A与B相等 记作A B 即 二 集合的关系 102 3 1集合的基本概念 定义3 若A是B的子集且 则称A为B的真子集 或称B真包含A 记作 B称为A的超集 103 集合的相等关系的性质 设A B C为3个集合 集合的包含关系的性质 3 1集合的基本概念 104 定义4 不包含任何元素的集合称为空集 记作或 3 1集合的基本概念 三 特殊集合 105 定义4 在一定范围内 如果所有集合均为某一集合的子集 则称该集合为全集 记作E 定义5 集合中元素的个数称为基数或势 用 A 表示 基数是有限数的集合称为有限集 否则称为无限集 全集是相对的 不同的问题有不同的全集 即使是同一个问题也可以取不同的全集 3 1集合的基本概念 106 3 1集合的基本概念 含n个元素的集合简称n元集 其含有k k n 个元素的子集称为它的k元子集 定义6 由集合S的所有子集组成的集合 称为集合S的幂集 记作P S 表示为 有限集S P S 2 S 例 A a b c d c 107 3 2集合的运算 一 集合的基本运算 108 3 2集合的运算 定义5 设A为集合 A的元素的元素构成的集合称为A的广义并 记作 A 109 3 2集合的运算 A x z z A x z 若A A1 A2 An 则 A A1 A2 An 定义6 设A为非空集合 A的所有元素的公共元素构成的集合称为A的广义交 记作 A A x z z A x z 若A A1 A2 An 则 A A1 A2 An 例 A a b c a b e B a C a c d 110 集合运算的优先级 高级 广义并 广义交 绝对补 求幂集 同级按从右向左的顺序进行低级 并 交 相对补和对称差 同级按从左向右的顺序进行 3 2集合的运算 111 3 2集合的运算 文氏图可以用来描述集合间的关系及其运算 在文氏图中 全集用矩形表示 子集用圆形表示 阴影部分表示运算结果的集合 二 文氏图 112 3 2集合的运算 113 3 3集合恒等式 一 集合运算定律 以下列出集合性质中最主要的几条基本定律 对于全集E的任意子集A B C 有 114 3 3集合恒等式 115 1 基本定义法 根据集合相等的充要条件等式两边互为子集或由定义进行等价推理 2 公式法 利用已证明过的恒等式去证明另外的恒等式 若表达式中出现形为A B的差集时 用功能完备律先将运算 转化为运算 和 二 集合恒等式证明 3 3集合恒等式 116 3 3集合恒等式 117 3 3集合恒等式 118 3 3集合恒等式 119 小结 集合的概念集合的特性集合的表示方法 列举法 描述法 文氏图集合的运算 并 交 补 差 求幂集合间的关系 包含 相等集合恒等式的证明 定义法 公式法 成员表法 120 第四章二元关系 4 1有序对与笛卡儿积4 2二元关系4 3关系的运算4 4关系的性质4 5关系的闭包4 6划分和等价关系4 7偏序关系 121 定义1 由两个具有固定次序的个体a b组成的序列 称为序偶 记作 其中a b称为序偶的分量 定义2 设和是两个序偶 若a c且b d 则称这两个序偶相等 记作 区别 集合 a b b a a b 4 1有序对与笛卡儿积 122 例3 设A a b c B 1 0 则 4 1有序对与笛卡儿积 定义3 设集合A B 以A的元素作为第一元素 B的元算作为第二元素的有序对构成的集合称为A与B的笛卡儿积 记作A B 符号化为A B x A y B 性质1 A A 123 例4 设A a b B 0 1 C u v 则 4 1有序对与笛卡儿积 124 4 1有序对与笛卡儿积 125 4 1有序对与笛卡儿积 126 性质5 若A C B D 则A B C D 4 1有序对与笛卡儿积 其逆命题不成立 A B 成立 A B 成立 A 且B 不成立 A 且B 不成立 127 定义4 由n个具有给定次序的个体a1 a2 an组成的序列 称为有序n元组 记作 其中ai称为第i个分量 当且仅当ai bi i 1 2 3 n 有序n元组仍然是序偶 即 an 4 1有序对与笛卡儿积 128 定义5 设A1 A2 An是任意的n个集合 所有有序n元组组成的集合 称为集合A1 A2 An的笛卡儿积 并用表示 其中 i 1 2 n 4 1有序对与笛卡儿积 129 4 2二元关系 定义1 若一个集合满足以下条件之一 1 集合非空 且它的元素都是有序对 2 集合是空集则称该集合为一个二元关系 一 关系的定义 130 4 2二元关系 例2 任意两个集合A B 若 A n B m 求A到B共有多少不同的二元关系 131 4 2二元关系 二 特殊关系 132 例5 设A 2 3 4 B 2 3 4 5 6 定义A到B的二元关系R aRb当且仅当a整除b 求R MR R 4 2二元关系 三 关系的表示方法 133 4 2二元关系 一个有限集合A上的关系R还可以用一个称为R的关系图来表示 134 4 2二元关系 例6 设A a b c d e A上关系R 则R的关系图为 135 例3 设A 1 2 3 4 5 6 B a b c d R 求domR ranR 解 domR 2 3 4 6 ranR a b d 4 3关系的运算 136 例 1 Z上的关系 3 空关系的逆是空关系 例3中R的逆关系R 1 4 3关系的运算 137 4 3关系的运算 例 1 R1 是 的兄弟 R2 是 的父亲 2 A 1 2 3 4 5 R S是A上的二元关系R S 138 4 3关系的运算 关系是以序偶为元素的集合 故可对关系进行集合的运算以产生新的关系 作为关系 绝对补运算是对全关系而言的 139 4 3关系的运算 2 A 1 2 3 4 5 R S是A上的二元关系R S 由此可知 合成关系不满足交换律 满足结合律 140 4 3关系的运算 141 定理8 关系矩阵的乘法满足结合律 即MR1 MR2MR3 MR1MR2 MR3 4 3关系的运算 定理9 设R1是一个由A1到A2的关系 R2是一个由A2到A3的关系 Rn是一个由An到An 1的关系 Ai都是有限集 它们的关系矩阵分别是MR1 MR2 MRn 则合成关系R1R2 Rn的关系矩阵MR1R2 Rn MR1MR2 MRn 142 定义5 设R为A上的关系 n为自然数 则R的n次幂定义为 R0 x A IA Rn 1 Rn R 4 3关系的运算 幂运算的求解 若R是列举法表示 可进行多次右复合 例 A a b c d R 143 例 设A a b c d R 则R0 R2 R3 R4 R0 R2 R3 R4 4 3关系的运算 144 若R用关系矩阵M表示 则Rn的关系矩阵是Mn 若R是用关系图G表示的 则可由G得Rn的关系图G G 与G的顶点集合相同 考察G中每个顶点x 若在G中从x出发经过n步长的路径到达顶点y 则在G 中加一条从x到y的边 当把所有顶点都考察完后 就得到G 4 3关系的运算 145 4 3关系的运算 定理10 幂运算满足指数定律 Rn Rm Rn m Rn m Rmn 幂运算的性质 定理11 设A为n元集 R是A上的关系 则存在s t N 使得Rs Rt 146 4 4关系的性质 定义1 设R A A 若 x x A R 则称R是自反的 若 x x A R 则称R是反自反的 若 x x A R y y A R 则称R是非自反的 定义2 设R A A 若 x y x y A R R 则称R是A上的对称关系 若 x y x y A R R x y 则称R是A上的反对称关系 否则 则称R是A上的非对称关系 147 空关系既是对称的又是反对称的 非空集合上的空关系是反自反的 对称的 反对称的 可传递的 空集合上的空关系则是自反的 反自反的 对称的 反对称的和可传递的 4 4关系的性质 148 非空集合上的全关系是自反的 对称的 和可传递的 例2 S a b c S上的关系R1 R2 R3 例3 在集合S a b c d 上的关系R 判断R的性质 4 4关系的性质 定理 设R是A上的二元关系 那么R是传递的当且仅当R R R 149 4 4关系的性质 根据定义可证明下面几个定理是成立的 150 4 4关系的性质 151 4 4关系的性质 152 可能有某种关系 既是对称的 又是反对称的 例4 S a b c S上的关系R 某种关系 既不是对称的 也不是反对称的 例5 S上的关系Q 定理5 设R在A上是反自反的和可传递的 则R必是反对称的 4 4关系的性质 153 例6 设A 1 2 3 A上的关系R 和S 都是A上的传递关系 传递性对并运算不一定保持 4 4关系的性质 154 关系的闭包运算是关系上的一元运算 他把给出的关系R扩充成一新关系Rc 使Rc具有一定的性质 且进行的扩充又是最小的 4 5关系的闭包 155 该定义表明 r R s R t R 是包含R的最小自反 对称 传递 关系 必要性 R r R 由定义1 1 知 r R 是自反的 故R是自反的 4 5关系的闭包 156 4 5关系的闭包 157 4 5关系的闭包 158 4 5关系的闭包 159 4 5关系的闭包 160 4 5关系的闭包 161 4 5关系的闭包 3 IA的自反 对称和传递闭包是什么 4 空关系的自反 对称和传递闭包是什么 例 A a b c d R 162 设R r R s R t R 的关系矩阵分别为M Mr Ms Mt 则Mr M EMs M M Mt M M2 M3 设R r R s R t R 的关系矩阵分别为G Gr Gs Gt 则 考察G中的每个顶点 若没有环就加上一个 得到Gr 考察G中每条边 若有xi到xj的单向边 i j 则加xj到xi的反向边 得Gs 考察G中每个顶点xi 找出从xi出发的所有2步 3步 n步长的路径 n为G中的顶点数 设路径的终点为xj1 xj2 xjk 若没有从xi到xjl l 1 2 k 的边 就加上这条边 考察完所有的顶点后 得到Gt 4 5关系的闭包 163 4 5关系的闭包 164 4 5关系的闭包 165 4 5关系的闭包 166 4 6等价关系与划分 例 A 1 2 3 4 5 6 7 8 R x y A x y mod3 167 4 6等价关系与划分 168 4 6等价关系与划分 169 一个集合的划分往往不是唯一的 4 6等价关系与划分 170 4 6等价关系与划分 等价关系与划分一一对应 171 4 7偏序关系 172 4 7偏序关系 由以上定义可知 在具有偏序关系的集合中任取x y 有x y x y x与y不可比 例 A 1 2 3 是A上的整除关系 173 盖住关系的关系图称哈斯图 求法 1 省略关系图中每个结点处的自环 2 若x y且y盖住x 将代表y的结点放在代表x的结点之上 并在x与y之间连线 省去有向边的箭头 4 7偏序关系 若x y但y不盖住x 则省去x与y之间的连线 174 4 7偏序关系 175 4 7偏序关系 176 4 7偏序关系 B的最小元一定是B的下界 同时也是B的最大下界 B的最大元一定是B的上界 同时也是B的最小上界 177 一般的调度问题可以描述为 给定有穷的任务集T和m台机器 T上存在偏序关系 如果t1 t2 那么t1完成以后t2才能开始工作 t T l t 表示完成任务t所需的时间d t 表示任务t的截止时间 l t d t Z 设开始时间为0 T 0 1 2 D 表示对任务集T的一个调度方案 t 表示任务t的开始时间 D 表示完成所有任务的最终时间 4 7偏序关系 178 假设每项任务都可以在任何一台机器上进行加工 如果 满足下述三个条件 则称其为可行调度 t T t l t d t i 0 i D t t T t i t l t m t t T t t t l t t 4 7偏序关系 179 第五章函数 5 1函数的定义与性质5 2函数的复合与反函数 180 5 1函数的定义与性质 例1 F1 F2 定义2 设F G为函数 则F G F G G F 即满足条件 domF domG x domF 都F x G x 181 5 1函数的定义与性质 182 5 1函数的定义与性质 183 5 1函数的定义与性质 184 5 1函数的定义与性质 185 5 1函数的定义与性质 定义7 186 单调函数可以定义于一般的偏序集上 每个子集对应一个特征函数 不同的子集则对应不同的特征函数 故而可用特征函数来标记不同的子集 给定集合A和A上的等价关系R 就可以确定一个自然映射 不同的等价关系将确定不同的自然映射 5 1函数的定义与性质 187 算法的评价标准 时间复杂度 空间复杂度估计复杂度的方法是 选择一个基本运算 对于给定规模为n的输入 计算算法所做基本运算的次数 将这个次数表示为输入规模的函数 最坏情况下的复杂度w n 平均情况下的复杂度A n 算法分析的主要工作就是估计复杂度函数的阶 阶越高 增长越快 算法复杂度越高 效率越低 5 1函数的定义与性质 188 5 1函数的定义与性质 189 5 2函数的复合与反函数 190 5 2函数的复合与反函数 191 5 2函数的复合与反函数 192 5 2函数的复合与反函数 193 第四部分图论 第六章图的基本概念第七章一些重要的图 194 第六章图的基本概念 6 1图6 2通路 回路6 3图的连通性6 4图的矩阵表示6 5图的运算 195 用点表示事物 用点之间是否有连线表示事物之间是否有某种关系 这样构成的图 就是图论中的图 二元关系的关系图就是图 与几何学中的图形有本质区别 因此 先看无序积 定义1 设A B为集合 称 a b a A b B 为A与B的无序积 记作A B 为方便 将 a b 记为 a b 6 1图 196 定义2 图G 是有序二元组 其中V G 是有限非空集 V中元素称为G的顶点或结点 V称为G的顶点集 E G 是V G 中诸顶点之间边或弧的集合 E称为G的边集 图G的边可以是无方向的 用 vi vj 表示 称为无向边 只由无向边构成的图G称为无向图 图G的边可以是有方向的 用表示 称为有向边 只由有向边构成的图D称为有向图 6 1图 197 如果图G中既有有向边 又有无向边 则称图G为混合图 6 1图 198 D ek E 称vi为ek的起点 vj为ek的终点 并称vi邻接到vj或vj邻接于vi 若ek的终点是el的起点 则ek el相邻 6 1图 定义4 在无向图中 关联一对顶点的无向边若多于1条 则称这些边为平行边 平行边的条数为重数 在D中 关联一对顶点的有向边若多于1条 且始点 终点相同 则称这些边为平行边 含平行边的图为多重图 不含平行边 环的图为简单图 199 6 1图 200 6 1图 201 6 1图 必要条件 阶数相同 边数相同 度数相同的顶点数相同 202 6 1图 203 6 1图 204 6 1图 205 6 2通路与回路 206 定理1 在n阶图G中 若从顶点vi到vj vi vj 存在通路 则从vi到vj存在长度小于或等于 n 1 的通路 推论 在n阶图G中 若从顶点vi到vj vi vj 存在通路 则从vi到vj一定存在长度小于或等于 n 1 的初级通路 定理2 在n阶图G中 若存在从顶点vi到自身的回路 则一定存在长度小于或等于n的回路 推论 在n阶图G中 若存在从顶点vi到自身的简单回路 则一定存在长度小于或等于n的初级回路 6 2通路与回路 207 无向图顶点间的连通关系是V上的一个等价关系 他的所有等价类构成V的一个划分 任意两个顶点vi vj属于同一个等价类当且仅当他们有路连接 6 3图的连通性 208 6 3图的连通性 209 6 3图的连通性 210 当 v 是G的点割集 则称v是G的割点 若v是连通图G的一个割点 那么G v就是不连通或平凡图 6 3图的连通性 211 6 3图的连通性 212 6 3图的连通性 213 6 3图的连通性 214 定理3 一个有向图D是强连通图的充要条件是D中存在至少经过每个顶点一次的回路 6 3图的连通性 定理4 设D是n阶有向图 D是单向连通图当且仅当D中存在经过每个顶点至少一次的通路 215 6 3图的连通性 极大路径法 设G 为n阶无向图 E 设 l为G中一条路径 若此路径的始点或终点与通路外的顶点相邻 就将它们扩充到通路中来 继续这一过程 直到最后得到的通路的两个端点不与通路外的顶点相邻为止 设最后得到的路径为 l k 称其为极大路径 称使用此种方法证明问题的方法为极大路径法 216 邻接矩阵A的阶就是G的顶点数n 6 4图的矩阵表示 图的表示方法 1 用边的集合和边的集合表示 如G 2 用图形表示 顶点用小圆圈表示 边用线段或弧表示 3 用矩阵表示 217 邻接矩阵依赖于V中个元素的给定次序 对于V中各元素的不同给定次序 可以得到同一个图G的不同邻接矩阵 这些矩阵可以通过交换另一个矩阵的某些行或对应的列而得到 如果两个图有这样的邻接矩阵 则这两个图是同构的 6 4图的矩阵表示 若主对角线某元素不为0 则表示该对应顶点上有自环 零矩阵对应的图为零图 218 6 4图的矩阵表示 219 6 4图的矩阵表示 220 6 4图的矩阵表示 221 6 4图的矩阵表示 222 6 4图的矩阵表示 223 6 4图的矩阵表示 224 6 5图的运算 225 6 5图的运算 226 第七章欧拉图与哈密顿图 7 1欧拉图7 2哈密顿图7 3二部图7 4平面图7 5树 227 定义1 通过图G的每条边一次且仅一次行遍图中所有顶点的通路称为欧拉通路 通过图G的每条边一次且仅一次行遍图中所有顶点的回路称为欧拉回路 具有欧拉回路的图称为欧拉图 具有欧拉通路而无欧拉回路的图为半欧拉图 定理1 无向图G为欧拉图当且仅当G是连通图 且G中所有顶点的度数都是偶数 定理2 如果G是欧拉图 那么G可分成若干个边不重的回路 7 1欧拉图 228 定理3 具有一条连接顶点vi和vj的欧拉通路的充要条件是Vi和vj是G中仅有的具有奇数度的顶点 定理4 设连通图G 有k个度为奇数的顶点 则E G 可划分为k 2条简单通路 定理5 有向连通图D为欧拉图的充要条件是每个顶点的入度等于出度 7 1欧拉图 229 定理6 有向连通图D存在一条欧拉通路的充要条件是恰有两个奇度数顶点 其中的一个入度比出度大1 另一个的出度比入度大1 而其余顶点的入度等于出度 7 1欧拉图 230 7 1欧拉图 231 定义1 通过图G的每个顶点一次且仅一次的回路称为哈密顿回路 哈密顿通路是通过图G的每个顶点一次且仅一次的通路 具有哈密顿回路的图称为哈密顿图 具有哈密顿通路而不具有哈密顿回路的图称为哈密顿图 平凡图是哈密顿图 性质 1 连通 度大于等于22 哈密顿通路是度为n 1的基本通路 其回路长为n 7 2哈密顿图 232 7 2哈密顿图 233 7 2哈密顿图 例 在某次国际会议的预备会中 共有8人参加 他们来自不同的国家 已知他们中任何两个无共同语言的人中的每一个 与其余有共同语言的人数之和大于或等于8 问能否将这8人排在圆桌旁 使任何人都能与两边的人交谈 定理4 若D为n n 2 阶竞赛图 则D中具有哈密顿通路 234 带权图与货郎担问题 货郎担问题 设有n个城市 城市之间均有道路 道路的长度均大于或等于0 一个旅行商从某个城市出发 要经过每个城市一次且仅一次 最后回到出发的城市 问他如何走 才能使路线最短 235 7 5树 7 5 1无向树及其性质7 5 2生成树7 5 3根树及其应用 236 定义1 连通无回路的无向图称为无向树 简称树 用T表示 若无向图F至少有两个连通分图都是树 称F为森林 仅有一个顶点的树称为平凡树 悬挂点称为树叶 定理1 设G 是n阶m条边的无向图 下列各命题等价 1 G是树 2 G的任意两个顶点之间有唯一路径 7 5 1无向树及其性质 237 3 G中无回路且m n 1 4 G是连通且m n 1 5 G是连通的 且G中任何边均是割边 6 G中无回路 但若在G的任意两个不同的顶点间加一条边 则所得的图中恰有唯一的一个含有新边的圈 定理2 设T是n阶非平凡的无向树 则T中至少有两片树叶 7 5 1无向树及其性质 238 定义1 设T是无向图G的子图并且为树 则称T为G的树 若T是G的树且为生成子图 则称T是G的生成树 T中的边称为树枝 图G中不在T中的边称作相应生成树T的弦 并称导出子图G E G E T 为T的余树 记作 定理1 无向图G具有生成树当且仅当G是连通图 推论1 设G为n阶m条边的无向连通图 则m n 1 7 5 2生成树 239 7 5 2生成树 240 7 5 2生成树 241 定义4 设G 是无向连通带权图 T是G的一棵生成树 T中各条边带权之和称为T的权 记作W T 若生成树T0在所有生成树中有最小的权 则称T0是G的最小生成树 7 5 2生成树 242 7 5 2生成树 243 7 5 3根树及其应用 在根树中 由于有向边的方向一致 故在画的时候可以省去边的方向 244 设T为根树 若将T中层数相同的顶点都标定次序 可以将根树分成以下各类 若T的每个分支点至多有r个儿子 则称T为r叉树 又若r叉树是有序的 则称其为r叉有序树 若T的每个分支点恰好有r个儿子 则称T为r叉正则树 又若T是有序的 则称其为r叉正则有序树 若T为r叉正则树 且每个树叶的层数均为树高 则称T为r叉完全正则树 又若T是有序的 则称其为r叉完全正则有序树 7 5 3根树及其应用 245 2叉正则有序树的每个分支点的两个儿子导出的根子树分别称为左子树和右子树 在所有的r叉树中 2叉树最重要 7 5 3根树及其应用 246 在通信中 常用二进制编码表示符号 如 A B C D就可用00 01 10 11分别来表示 这叫做等长码表示方法 适用于出现的频率基本相同的情况 当出现的频率相差较大时 就需要非等长的编码 7 5 3根树及其应用 247 可用2叉树产生二元前缀码 设T是具有t片树叶的2叉树 则T的每个分支点有1 2个儿子 设V为T的分支点 若v有两个儿子 在由v引出的两条边上 左边标上0 右边标上1 若v只有一个儿子 由它引出的边上可以标0也可以标1 7 5 3根树及其应用 248 设v是T的任意一片树叶 从树根到v的通路上各边的标号 0或1 按通路上边的顺序放在v处 则t片树叶处t个符号串组成的集合为一个二元前缀码 定理1 由一棵给定的2叉正则树 可以产生惟一的一个二元前缀码 由产生的任一个前缀码都可以传输符号 但这些符号出现频率不同时 就要用各符号出现的频率为权 利用Huffman算法求最优2叉树 由最优2叉树产生的前缀码称为最佳前缀码 用最佳前缀码传输对应的各符号能使传输的二进制数位最省 即效率最高 7 5 3根树及其应用 249 7 4平面图及图的着色 7 4 1平面图的基本概念7 4 2欧拉公式7 4 3平面图的判断7 4 4平面图的对偶图7 4 5图中顶点的着色7 4 6地图的着色与平面图的点着色7 4 7边着色 250 定义1 若图G能以这样一来的方式画在曲面上 即除顶点处外无任何边交叉 则称图G可嵌入曲面S 若G可嵌入平面 则称G是可平面图或平面图 画出的无边相交的图称为G的平面迁入 无平面嵌入的图称为非平面图 7 4 1平面图的概念 定理1 若图G是平面图 则G的任何子图都是平面图 定理2 若图G是非平面图 则G的任何母图都是非平面图 推论 Kn n 5 和K3 n n 3 都是非平面图 251 定义2 设G是一个平面图 由图的边所包围的一个区域 其内部既不包含图的顶点 也不包含图的边 则称这样的区域为G的一个面 如果面的面积是有限的 则称该面为有限面 否则称该面为无限面 如果两个面的边界至少有一条公共边 则称这两个面是相邻的 否则是不相邻的 包围一个面的所有边组成的回路称为该面的边界 边界的长度成为面的次数 记作deg Ri 定理3 若图G是平面图 则在G中加平行边和环后都是平面图 7 4 1平面图的概念 252 定理4 平面图G中所有面的次数之和等于边数的2倍 定义3 设G是简单平面图 若在G的任意不相邻的顶点u v之间加边 u v 所得图为非平面图 则称G为极大平面图 定理5 极大平面图是连通的 定理6 设G为n阶极大平面图 则G中不可能存在割点和桥 定理7 设G为n阶简单连通的平面图 G为极大连通平面图当且仅当G的每个面的次数均为3 定义4 若在非平面图G中任意删除一条边 所得图为平面图 则称G为极小非平面图 7 4 1平面图的概念 253 7 4 2欧拉公式 254 定理6 设G是n n 3 阶m条边的极大平面图 则m 3n 6 7 4 2欧拉公式 255 7 4 3平面图的判断 定义1 设e u v 为图G的一条边 在G中删除e 增加新的顶点w 使u v均与w相邻 称为在G中插入2度顶点w