《离散数学教程》PPT课件.ppt

离散数学 数学与信息科学学院 第一部分数理逻辑第二部分集合论第三部分图论第四部分抽象代数 离散数学 第一部分数理逻辑 数理逻辑是用数学方法研究推理中前提和结论之间的形式关系的学科 推理是由一个或几个判断推出一个新判断的思维形式 数学方法是指建立一套表意符号体系 对具体事物进行抽象的形式研究的方法 第一章命题逻辑第二章一阶谓词逻辑 第一部分数理逻辑 1 1命题和命题联结词1 2命题公式及其赋值1 3等值演算与联结词完备集1 4析取范式与合取范式1 5推理的形式结构1 6自然推理系统P 第一章命题逻辑 1 命题 能判断真假的陈述句 包含两层意思 1 必须是陈述句 2 能够确定 分辨 其真值 1 1命题和命题联结词 1 1命题和命题联结词 2 命题的真值 判断结果 注意 此处不纠缠具体命题的真假问题 只是将其作为数学概念来处理 真值 真用T或1表示 假用F或0表示 3 命题和真值的符号化 1 1命题和命题联结词 1 1命题和命题联结词 原子命题 不能被分解为更简单的陈述句复合命题 原子命题通过联结词联结而成 例 2是有理数是不对的 2是偶素数 2或4是素数 如果2是素数 则3也是素数 2是素数当且仅当3也是素数 p 2是有理数 q 2是偶数 r 2是素数 s 3是素数 t 4是素数 1 1命题和命题联结词 4 命题联结词 1 1命题和命题联结词 王化不但成绩好而且品德好 p q 1 1命题和命题联结词 1 1命题和命题联结词 开关坏了或灯泡坏了 p q 例 1 张晓婧爱唱歌或爱听音乐 2 张晓婧是内蒙人或是陕西人 3 张晓婧只能挑选202或203房间 1 1命题和命题联结词 注意 当排斥或两边的情况实际根本不可能同时发生的时候 排斥或也可抽象为 但为了方便起见一般不这样抽象 有位父亲对儿子说 如果我去书店 就一定给你买电脑报 问 在什么情况下 父亲算失信呢 1 1命题和命题联结词 注意 只要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命题和命题联结词 1 1命题和命题联结词 pq的逻辑关系为p与q互为充要条件 例 1 3是有理数当且仅当加拿大位于亚洲 2 两圆的面积相等 则他们的半径相等 反之亦然 1 1命题和命题联结词 例 今天第一节课上离散数学或数据结构 例 p 北京比天津人口多q 2 2 4r 乌鸦是黑色的 1 1命题和命题联结词 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 1 1命题和命题联结词 命题常元 表示具体确定内容的命题 命题变元 表示不确定具体内容的命题 1 2命题公式及其赋值 1 2命题公式及其赋值 同时约定 1 最外层的括号可以省去 2 不影响运算次序的括号也可以省去 1 2命题公式及其赋值 1 2命题公式及其赋值 1 2命题公式及其赋值 1 2命题公式及其赋值 1 2命题公式及其赋值 1 3命题公式的等值式 基本等值式 A B C为任意命题公式 1 3命题公式的等值式 1 3命题公式的等值式 因A B C可以代入任意的命题公式 故以上等值式称为等值式模式 由已知的等值式推演出另外一些等值式的过程为等值演算 1 3命题公式的等值式 等值演算的应用 1 验证等值式2 判定公式的类型3 解决工作生活中的判断问题 1 3命题公式的等值式 甲 已 丙3人根据口音对王教授是哪人进行了判断 甲说 王教授不是苏州人 是上海人已说 王教授不是上海人 是苏州人丙说 王教授既不是上海人 也不是杭州人结果3人中有一人全对 一人对一半 一人全错 问王教授是哪人 联结词的完备集 n个命题变元可以形成22n个不同的真值函数 对于每个真值函数 都可以找到许多与之等值的命题公式 而每个命题公式对应唯一的与之等值的真值函数 定义 设S是一个联结词集合 如果任何n n 1 元真值函数都可以由仅含S中的联结词构成的公式表示 则称S是联结词完备集 联结词的完备集 1 4析取范式与合取范式 定义 命题变元及其否定统称为文字 仅由有限个文字构成的析取式称为简单 质 析取式 仅由有限个文字构成的合取式称为简单 质 合取式 注意 单个文字既是简单析取式又是简单合取式 讨论 设A为含n个文字的简单析取式若A中同时含pi和 pi 则 若A为永真式 则 若A为永真式 则A中必同时含有pi和 pi 反之亦然 同理有 若A为简单合取式 A为永假式的充要条件是A中同时含有pi和 pi 定理1 一个简单析取式是重言式当且仅当它同时含有某个命题变元及其他的否定 一个简单合取式是矛盾式当且仅当它同时含有某个命题变元及其他的否定 1 4析取范式与合取范式 定义 由有限个简单合取式构成的析取式称为析取范式 由有限个简单析取式构成的合取式称为合取范式 析取范式与合取范式称为范式 注意 单个文字 简单析取式 简单合取式都既是析取范式又是合取范式 1 4析取范式与合取范式 定理2 一个析取范式是矛盾式当且仅当它的每个简单合取式为矛盾式 一个合取范式是重言式当且仅当它的每个简单析取式为重言式 定理3 任一命题公式都存在与之等值的析取范式和合取范式 范式的求法 消去公式中的蕴涵 等价和异或联结词 使用双重否定律和德摩根律 将公式中出现的否定词移到命题变元之前 利用分配律 结合律将公式化为合 析 取范式 范式形式不唯一 1 4析取范式与合取范式 定义 在含有n个命题变元的简单合 析 取式中 若每个命题变元和它的否定式不同时出现 而二者之一必出现且仅出现一次 且第i个命题变元或它的否定是出现在从左算起的第i位上 字典序 称这样的简单合 析 取式为极小 大 项 性质 n个变元可以形成2n个极小 大 项 每个极小 大 项有且仅有一个成真 假 赋值 每组赋值下仅有一个极小 大 项为真 假 所有极小 大 项的析 合 取为真 假 1 4析取范式与合取范式 将极小项的成真赋值对应的二进制数转化为十进制数为i 将对应的极小项记为mi 将极大项的成假赋值对应的二进制数转化为十进制数为i 将对应的极大项记为Mi 定义 设由n个命题变元构成的析 合 取范式中所有的简单合 析 取式都是极小 大 项 则称该析取范式为主析 合 取范式 1 4析取范式与合取范式 定理 任何命题公式都存在与之等值的主析取范式和主合取范式 并且是唯一的 1 4析取范式与合取范式 公式法 求析取范式 用同一律补进未出现的命题变元 消去永假或重复出现的变元和极小项 将极小项按下标从小到大排列 真值表法 列出公式及各极小项的真值表 将每组赋值下公式及极小项真值都为真的极小项进行析取 主析取范式的求法 1 公式法2 真值表法 1 4析取范式与合取范式 应用 1 求公式的成真 成假赋值成真赋值为析取范式中所含极小项的编码的二进制数成假赋值为合取范式中所含极大项的编码的二进制数 由主析取范式可以直接求主合取范式 1 求出主析取范式中未包含的极小项2 求出与1 中求出的极小项下标相同的极大项3 做2 中极大项之合取 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的主析取范式中至少含一个极小项 例 要在A B C中挑选2名出国进修 选派时满足下列条件 若A去 则C同去 若B去 则C不能去 若C不去 则A或B可以去问有几种选派方案 分别是什么 4 解决实际问题 1 4析取范式与合取范式 1 5推理的形式结构 注意 推理正确实际是排除前提真结论假的情况 推理是否正确与前提的排列顺序无关 推理正确并不能保证B一定为真 1 5推理的形式结构 推理的形式结构 1 5推理的形式结构 例 若下午温度超过30度 则王晓燕必去游泳 若她去游泳 她就不会去看电影 所以若王晓燕没去看电影 下午温度必超过了30度 p 温度超过30度q 王晓燕去游泳r 王晓燕去看电影 1 5推理的形式结构 1 5推理的形式结构 注意 以上都是蕴含式模式 若某推理的形式结构与某定律一致 则推理正确 成立的等值式可产生两条定律 推理定律可产生相应的推理规则 1 5推理的形式结构 1 6自然推理系统P 定义 一个形式系统I由以下4部分组成 非空的字母表 记作A I A I 中符号构成的合式公式集 记作E I E I 中特殊的公式组成的公理集 记作Ax I 推理规则集 记作R I 任给的前提 应用规则得到结论 可能真 任给的公理 应用规则得到结论 永真 1 6自然推理系统P 1 6自然推理系统P 例 若小王是理科生 则他的数学成绩一定很好 如果小王不是理科生 他一定是文科生 小王的数学成绩不好 所以小王是文科生 p 小王是理科生q 小王是文科生r 小王的数学成绩很好 1 6自然推理系统P 例 如果小张和小王去看电影 则小李也去看电影 小赵不去看电影或小张去看电影 小王去看电影 所以 当小赵去看电影时 小李也去 p 小张去看电影q 小王去看电影r 小李去看电影s 小赵去看电影 1 6自然推理系统P 2 归谬法将结论的否定作为前提引入 能推出矛盾来 则推理正确 例 如果马会飞或羊不吃草 则母鸡就会是飞鸟 如果母鸡是飞鸟 那么烤熟的鸭子还会跑 烤熟的鸭子不会跑 所以羊吃草 p 马会飞q 羊吃草r 母鸡是飞鸟s 烤熟的鸭子会跑 1 6自然推理系统P 所有的人总是要死的 苏格拉底是人 所以苏格拉底是要死的 p q r 第二章谓词逻辑 第二章谓词逻辑 2 1一阶逻辑命题符号化2 2一阶逻辑公式及解释2 3一阶逻辑等值式与置换规则2 4一阶逻辑前束范式2 5一阶逻辑的推理理论 2 1一阶逻辑命题符号化 1 个体词 所研究对象中可以独立存在的具体的或抽象的客体 事物 表示具体的或特定的客体 表示抽象或泛指的客体 个体变项的取值范围称为个体域 用D表示 宇宙间一切事物组成的称为全总个体域 2 谓词 用来刻划个体词性质及个体词之间相互关系的词 2是有理数x是无理数小王与小李同岁x与y具有关系L 是有理数 是无理数 与 同岁 与 具有关系L F G H L 2 1一阶逻辑命题符号化 3 量词 个体词之间的数量关系 1 全称量词 一切的 所有的 每一个 任意的 凡 都 记作 4 符号化 确定个体域 确定个体词 量词和谓词 确定联结词 2 1一阶逻辑命题符号化 例 所有的人都是要死的 有的人用左手写字 注意 全称量词的特性谓词必须作为蕴涵式的前件引入 存在量词的特性谓词必须作为合取式的合取项引入 同一命题 不同的个体域符号化的形式可能不同 未指明个体域即为全总个体域 2 1一阶逻辑命题符号化 例 在美国留学的学生未必都是亚洲人 有的兔子比所有的乌龟跑的快 对任意的整数x 都存在整数y使得x y 10 注意 多个量词出现时 顺序一般不能随便换 有些命题符号化形式不唯一 2 1一阶逻辑命题符号化 2 2一阶逻辑公式及解释 2 2一阶逻辑公式及解释 合式公式也称谓词公式 简称公式 2 2一阶逻辑公式及解释 2 2一阶逻辑公式及解释 2 2一阶逻辑公式及解释 2 2一阶逻辑公式及解释 定理 闭式在任何解释下都变成命题 2 2一阶逻辑公式及解释 2 2一阶逻辑公式及解释 定理 重言式的代换实例都是永真式 矛盾式的代换实例都是矛盾式 2 2一阶逻辑公式及解释 2 3一阶逻辑等值式与置换规则 第一组命题逻辑中等值式模式的代换实例都是一阶逻辑的等值式模式 第二组一阶逻辑中特殊的等值式 2 3一阶逻辑等值式与置换规则 D N F x x是奇数G x x是偶数 2 3一阶逻辑等值式与置换规则 2 3一阶逻辑等值式与置换规则 2 3一阶逻辑等值式与置换规则 2 4一阶逻辑前束范式 为了方便使用谓词公式进行定理证明和逻辑推理 需要把谓词公式变换为便于使用的规范形式 就是范式 定理1 任一谓词公式都可以化成为与之等值的前束范式 2 4一阶逻辑前束范式 2 4一阶逻辑前束范式 2 5一阶逻辑的推理理论 在一阶逻辑中 称永真的蕴涵式为推理定律 若一个推理的形式结构正是某条推理定律 则该推理显然是正确的 第一组命题逻辑推理定律的代换实例 第二组由基本等值式生成的推理定律 第三组以下重要定律 第四组消去量词和引入量词的推理规则 1 全称量词消去规则 UI 2 5一阶逻辑的推理理论 UI规则成立的条件 1 取代x的y应为任意不在A x 中约束出现的个体变项 2 用y取代A x 中自由出现的x时 必须将所有的自由出现x都取代 3 自由变元y也可替换为个体域中任意的个体常元c c为任意不在A x 中出现过的个体常项 2 5一阶逻辑的推理理论 含义 如果个体域的所有个体都具有性质A 则个体域中的任一个个体都具有性质A 2 存在量词消去规则 EI 含义 如果个体域存在有性质A的个体 则个体域中必有某一个个体具有性质A 2 5一阶逻辑的推理理论 ES规则成立的条件 1 c是个体域中使A为真的特定的个体常项 2 c不曾在A x 或前面的推导公式中出现过 3 A x 中除x外还有其他自由变元时 不能用此规则 2 5一阶逻辑的推理理论 3 全称量词引入规则 UG UG规则成立的条件 1 y在A y 中自由出现 且y取任何值时A均为真 2 x不在A y 中约束出现 含义 如果个体域的任意个体都具有性质A 则个体域中的所有个体都具有性质A 2 5一阶逻辑的推理理论 4 存在量词引入规则 EG EG规则成立的条件 1 c是个体域中某个确定的个体 2 代替c的x不在A c 中出现过 含义 如果个体域有某一个个体c具有性质A 则个体域中必存在具有性质A的个体 2 5一阶逻辑的推理理论 定义 一阶逻辑自然推理系统F的定义1 字母表 同一阶语言的字母表2 合式公式 同一阶语言合式公式的定义3 推理规则a 前提引入规则b 结论引入规则c 置换规则d 假言推理规则e 附加规则f 化简规则g 拒取式规则h 假言三段论规则i 析取三段论规则j 构造性二难规则k 合取引入规则l UI EI UG EG 2 5一阶逻辑的推理理论 例7 证明逻辑三段论所有的人总是要死的 苏格拉底是人 所以苏格拉底是要死的 2 5一阶逻辑的推理理论 2 5一阶逻辑的推理理论 例10 如果一个人怕困难就不会获得成功 每一个人或者获得成功或者是失败的 有些人未曾失败过 所以有些人不怕困难 个体域是人的集合 判断这个推理是否正确 例9 根据前提集合 同事之间总是有工作矛盾的 张平和李明没有工作矛盾 能得出什么结论 第二部分集合论 第三章集合代数第四章二元关系第五章函数 第三章集合代数 3 1集合的基本概念3 2集合的运算3 3集合恒等式 一 集合的概念集合 set 的含义 一个集合是作为整体识别的 确定的 互相区别的一些事物的聚集 全体或总体等 构成一个集合的每个事物 成为这个集合中的元素或成员 集合一般用A B C 表示 集合中的元素用a b c 表示 但这不是绝对的 因为一个集合可以作为另一个集合的元素 如果x是集合s的一个元素 记作 y不是集合s的元素 记作 3 1集合的基本概念 例1 1 偶素数集合 2 二进制的基数集合 3 英文字母的集合 4 全体实数的集合 5 自然数集合 6 整数集合 7 有理数集合 8 素数集合 3 1集合的基本概念 3 1集合的基本概念 集合的表示方法 1 列举法 枚举法 外延法 把集合的所有元素 元素较少时 写在一个花括号内 列出足够多的元素 元素很多或无穷时 以反映集合中元素的特征 如例1中的1 2 3 5可分别表示为 2 0 1 a b c z A B C Z 1 2 3 3 1集合的基本概念 2 描述法 概括法 将集合中的元素的性质用一个谓词公式来描述 S X P X 意义为 集合S由且仅由满足为此公式P X 的对象组成 即 当且仅当p a 为真 如例1中的4 6 7可表示为 3 文氏图用图形图像直观的描述集合之间的相互关系和有关运算 3 1集合的基本概念 几个常见集合的表示符号 N 自然数集合 N 0 1 2 3 I 整数集合 P 素数或质数集合 Q 有理数集合 R 实数集合 C 复数集合 3 1集合的基本概念 集合的特性 A 互异性 一个集合的个元素是可以区分开的 即每一元素只出现一次 B 无序性 集合中元素排列顺序无关紧要 即集合表示形式的不唯一性 例2 a b c b c a c a b a c b b a c c b a 3 1集合的基本概念 C 确定性 任一事物是否属于某一集合 回答是确定的 例3 好书 的全体 这不构成集合 注意 一个集合是已知的 指的是对任一元素 利用某种方法可以判断它是否是这个集合的元素 而不是把集合的每一个元素都给出来 3 1集合的基本概念 集合的元素可以是任何具体或抽象的事物 包括别的集合 但不能是本集合自身 例4 在一个住着一些人家的偏僻孤岛上 岛上只有一个理发师a a给且只给岛上所有不能自己理发的人理发 问谁给a理发 定义1 设A和B是两个集合 若A中的每一个元素都是B的元素 则称A是B的子集 也称B包含A 记作 3 1集合的基本概念 定义2 设A和B是任意两个集合 若A包含B且B包含A 则称A与B相等 记作A B 即 二 集合的关系 3 1集合的基本概念 定义3 若A是B的子集且 则称A为B的真子集 或称B真包含A 记作 B称为A的超集 集合的相等关系的性质 设A B C为3个集合 集合的包含关系的性质 3 1集合的基本概念 定义4 不包含任何元素的集合称为空集 记作或 3 1集合的基本概念 三 特殊集合 定义4 在一定范围内 如果所有集合均为某一集合的子集 则称该集合为全集 记作E 定义5 集合中元素的个数称为基数或势 用 A 表示 基数是有限数的集合称为有限集 否则称为无限集 全集是相对的 不同的问题有不同的全集 即使是同一个问题也可以取不同的全集 3 1集合的基本概念 3 1集合的基本概念 含n个元素的集合简称n元集 其含有k k n 个元素的子集称为它的k元子集 定义6 由集合S的所有子集组成的集合 称为集合S的幂集 记作P S 表示为 有限集S P S 2 S 例 A a b c d c 3 2集合的运算 一 集合的基本运算 3 2集合的运算 定义5 设A为集合 A的元素的元素构成的集合称为A的广义并 记作 A 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 集合运算的优先级 高级 广义并 广义交 绝对补 求幂集 同级按从右向左的顺序进行低级 并 交 相对补和对称差 同级按从左向右的顺序进行 3 2集合的运算 3 2集合的运算 文氏图可以用来描述集合间的关系及其运算 在文氏图中 全集用矩形表示 子集用圆形表示 阴影部分表示运算结果的集合 二 文氏图 3 2集合的运算 3 3集合恒等式 一 集合运算定律 以下列出集合性质中最主要的几条基本定律 对于全集E的任意子集A B C 有 3 3集合恒等式 1 基本定义法 根据集合相等的充要条件等式两边互为子集或由定义进行等价推理 2 公式法 利用已证明过的恒等式去证明另外的恒等式 若表达式中出现形为A B的差集时 用功能完备律先将运算 转化为运算 和 二 集合恒等式证明 3 3集合恒等式 3 3集合恒等式 3 3集合恒等式 3 3集合恒等式 小结 集合的概念集合的特性集合的表示方法 列举法 描述法 文氏图集合的运算 并 交 补 差 求幂集合间的关系 包含 相等集合恒等式的证明 定义法 公式法 成员表法 第四章二元关系 4 1有序对与笛卡儿积4 2二元关系4 3关系的运算4 4关系的性质4 5关系的闭包4 6划分和等价关系4 7偏序关系 定义1 由两个具有固定次序的个体a b组成的序列 称为序偶 记作 其中a b称为序偶的分量 定义2 设和是两个序偶 若a c且b d 则称这两个序偶相等 记作 区别 集合 a b b a a b 4 1有序对与笛卡儿积 例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 例4 设A a b B 0 1 C u v 则 4 1有序对与笛卡儿积 4 1有序对与笛卡儿积 4 1有序对与笛卡儿积 性质5 若A C B D 则A B C D 4 1有序对与笛卡儿积 其逆命题不成立 A B 成立 A B 成立 A 且B 不成立 A 且B 不成立 定义4 由n个具有给定次序的个体a1 a2 an组成的序列 称为有序n元组 记作 其中ai称为第i个分量 当且仅当ai bi i 1 2 3 n 有序n元组仍然是序偶 即 an 4 1有序对与笛卡儿积 定义5 设A1 A2 An是任意的n个集合 所有有序n元组组成的集合 称为集合A1 A2 An的笛卡儿积 并用表示 其中 i 1 2 n 4 1有序对与笛卡儿积 4 2二元关系 定义1 若一个集合满足以下条件之一 1 集合非空 且它的元素都是有序对 2 集合是空集则称该集合为一个二元关系 一 关系的定义 4 2二元关系 例2 任意两个集合A B 若 A n B m 求A到B共有多少不同的二元关系 4 2二元关系 二 特殊关系 例5 设A 2 3 4 B 2 3 4 5 6 定义A到B的二元关系R aRb当且仅当a整除b 求R MR R 4 2二元关系 三 关系的表示方法 4 2二元关系 一个有限集合A上的关系R还可以用一个称为R的关系图来表示 4 2二元关系 例6 设A a b c d e A上关系R 则R的关系图为 例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关系的运算 例 1 Z上的关系 3 空关系的逆是空关系 例3中R的逆关系R 1 4 3关系的运算 4 3关系的运算 例 1 R1 是 的兄弟 R2 是 的父亲 2 A 1 2 3 4 5 R S是A上的二元关系R S 4 3关系的运算 关系是以序偶为元素的集合 故可对关系进行集合的运算以产生新的关系 作为关系 绝对补运算是对全关系而言的 4 3关系的运算 2 A 1 2 3 4 5 R S是A上的二元关系R S 由此可知 合成关系不满足交换律 满足结合律 4 3关系的运算 定理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 定义5 设R为A上的关系 n为自然数 则R的n次幂定义为 R0 x A IA Rn 1 Rn R 4 3关系的运算 幂运算的求解 若R是列举法表示 可进行多次右复合 例 A a b c d R 例 设A a b c d R 则R0 R2 R3 R4 R0 R2 R3 R4 4 3关系的运算 若R用关系矩阵M表示 则Rn的关系矩阵是Mn 若R是用关系图G表示的 则可由G得Rn的关系图G G 与G的顶点集合相同 考察G中每个顶点x 若在G中从x出发经过n步长的路径到达顶点y 则在G 中加一条从x到y的边 当把所有顶点都考察完后 就得到G 4 3关系的运算 4 3关系的运算 定理10 幂运算满足指数定律 Rn Rm Rn m Rn m Rmn 幂运算的性质 定理11 设A为n元集 R是A上的关系 则存在s t N 使得Rs Rt 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上的非对称关系 空关系既是对称的又是反对称的 非空集合上的空关系是反自反的 对称的 反对称的 可传递的 空集合上的空关系则是自反的 反自反的 对称的 反对称的和可传递的 4 4关系的性质 非空集合上的全关系是自反的 对称的 和可传递的 例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 4 4关系的性质 根据定义可证明下面几个定理是成立的 4 4关系的性质 4 4关系的性质 可能有某种关系 既是对称的 又是反对称的 例4 S a b c S上的关系R 某种关系 既不是对称的 也不是反对称的 例5 S上的关系Q 定理5 设R在A上是反自反的和可传递的 则R必是反对称的 4 4关系的性质 例6 设A 1 2 3 A上的关系R 和S 都是A上的传递关系 传递性对并运算不一定保持 4 4关系的性质 关系的闭包运算是关系上的一元运算 他把给出的关系R扩充成一新关系Rc 使Rc具有一定的性质 且进行的扩充又是最小的 4 5关系的闭包 该定义表明 r R s R t R 是包含R的最小自反 对称 传递 关系 必要性 R r R 由定义1 1 知 r R 是自反的 故R是自反的 4 5关系的闭包 4 5关系的闭包 4 5关系的闭包 4 5关系的闭包 4 5关系的闭包 4 5关系的闭包 4 5关系的闭包 3 IA的自反 对称和传递闭包是什么 4 空关系的自反 对称和传递闭包是什么 例 A a b c d R 设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关系的闭包 4 5关系的闭包 4 5关系的闭包 4 5关系的闭包 4 6等价关系与划分 例 A 1 2 3 4 5 6 7 8 R x y A x y mod3 4 6等价关系与划分 4 6等价关系与划分 一个集合的划分往往不是唯一的 4 6等价关系与划分 4 6等价关系与划分 等价关系与划分一一对应 4 7偏序关系 4 7偏序关系 由以上定义可知 在具有偏序关系的集合中任取x y 有x y x y x与y不可比 例 A 1 2 3 是A上的整除关系 盖住关系的关系图称哈斯图 求法 1 省略关系图中每个结点处的自环 2 若x y且y盖住x 将代表y的结点放在代表x的结点之上 并在x与y之间连线 省去有向边的箭头 4 7偏序关系 若x y但y不盖住x 则省去x与y之间的连线 4 7偏序关系 4 7偏序关系 4 7偏序关系 B的最小元一定是B的下界 同时也是B的最大下界 B的最大元一定是B的上界 同时也是B的最小上界 一般的调度问题可以描述为 给定有穷的任务集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偏序关系 假设每项任务都可以在任何一台机器上进行加工 如果 满足下述三个条件 则称其为可行调度 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偏序关系 第五章函数 5 1函数的定义与性质5 2函数的复合与反函数 5 1函数的定义与性质 例1 F1 F2 定义2 设F G为函数 则F G F G G F 即满足条件 domF domG x domF 都F x G x 5 1函数的定义与性质 5 1函数的定义与性质 5 1函数的定义与性质 5 1函数的定义与性质 5 1函数的定义与性质 定义7 单调函数可以定义于一般的偏序集上 每个子集对应一个特征函数 不同的子集则对应不同的特征函数 故而可用特征函数来标记不同的子集 给定集合A和A上的等价关系R 就可以确定一个自然映射 不同的等价关系将确定不同的自然映射 5 1函数的定义与性质 算法的评价标准 时间复杂度 空间复杂度估计复杂度的方法是 选择一个基本运算 对于给定规模为n的输入 计算算法所做基本运算的次数 将这个次数表示为输入规模的函数 最坏情况下的复杂度w n 平均情况下的复杂度A n 算法分析的主要工作就是估计复杂度函数的阶 阶越高 增长越快 算法复杂度越高 效率越低 5 1函数的定义与性质 5 1函数的定义与性质 5 2函数的复合与反函数 5 2函数的复合与反函数 5 2函数的复合与反函数 5 2函数的复合与反函数 第四部分图论 第六章图的基本概念第七章一些重要的图 第六章图的基本概念 6 1图6 2通路 回路6 3图的连通性6 4图的矩阵表示6 5图的运算 用点表示事物 用点之间是否有连线表示事物之间是否有某种关系 这样构成的图 就是图论中的图 二元关系的关系图就是图 与几何学中的图形有本质区别 因此 先看无序积 定义1 设A B为集合 称 a b a A b B 为A与B的无序积 记作A B 为方便 将 a b 记为 a b 6 1图 定义2 图G 是有序二元组 其中V G 是有限非空集 V中元素称为G的顶点或结点 V称为G的顶点集 E G 是V G 中诸顶点之间边或弧的集合 E称为G的边集 图G的边可以是无方向的 用 vi vj 表示 称为无向边 只由无向边构成的图G称为无向图 图G的边可以是有方向的 用表示 称为有向边 只由有向边构成的图D称为有向图 6 1图 如果图G中既有有向边 又有无向边 则称图G为混合图 6 1图 D ek E 称vi为ek的起点 vj为ek的终点 并称vi邻接到vj或vj邻接于vi 若ek的终点是el的起点 则ek el相邻 6 1图 定义4 在无向图中 关联一对顶点的无向边若多于1条 则称这些边为平行边 平行边的条数为重数 在D中 关联一对顶点的有向边若多于1条 且始点 终点相同 则称这些边为平行边 含平行边的图为多重图 不含平行边 环的图为简单图 6 1图 6 1图 6 1图 必要条件 阶数相同 边数相同 度数相同的顶点数相同 6 1图 6 1图 6 1图 6 2通路与回路 定理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通路与回路 无向图顶点间的连通关系是V上的一个等价关系 他的所有等价类构成V的一个划分 任意两个顶点vi vj属于同一个等价类当且仅当他们有路连接 6 3图的连通性 6 3图的连通性 6 3图的连通性 当 v 是G的点割集 则称v是G的割点 若v是连通图G的一个割点 那么G v就是不连通或平凡图 6 3图的连通性 6 3图的连通性 6 3图的连通性 6 3图的连通性 定理3 一个有向图D是强连通图的充要条件是D中存在至少经过每个顶点一次的回路 6 3图的连通性 定理4 设D是n阶有向图 D是单向连通图当且仅当D中存在经过每个顶点至少一次的通路 6 3图的连通性 极大路径法 设G 为n阶无向图 E 设 l为G中一条路径 若此路径的始点或终点与通路外的顶点相邻 就将它们扩充到通路中来 继续这一过程 直到最后得到的通路的两个端点不与通路外的顶点相邻为止 设最后得到的路径为 l k 称其为极大路径 称使用此种方法证明问题的方法为极大路径法 邻接矩阵A的阶就是G的顶点数n 6 4图的矩阵表示 图的表示方法 1 用边的集合和边的集合表示 如G 2 用图形表示 顶点用小圆圈表示 边用线段或弧表示 3 用矩阵表示 邻接矩阵依赖于V中个元素的给定次序 对于V中各元素的不同给定次序 可以得到同一个图G的不同邻接矩阵 这些矩阵可以通过交换另一个矩阵的某些行或对应的列而得到 如果两个图有这样的邻接矩阵 则这两个图是同构的 6 4图的矩阵表示 若主对角线某元素不为0 则表示该对应顶点上有自环 零矩阵对应的图为零图 6 4图的矩阵表示 6 4图的矩阵表示 6 4图的矩阵表示 6 4图的矩阵表示 6 4图的矩阵表示 6 4图的矩阵表示 6 5图的运算 6 5图的运算 第七章欧拉图与哈密顿图 7 1欧拉图7 2哈密顿图7 3二部图7 4平面图7 5树 定义1 通过图G的每条边一次且仅一次行遍图中所有顶点的通路称为欧拉通路 通过图G的每条边一次且仅一次行遍图中所有顶点的回路称为欧拉回路 具有欧拉回路的图称为欧拉图 具有欧拉通路而无欧拉回路的图为半欧拉图 定理1 无向图G为欧拉图当且仅当G是连通图 且G中所有顶点的度数都是偶数 定理2 如果G是欧拉图 那么G可分成若干个边不重的回路 7 1欧拉图 定理3 具有一条连接顶点vi和vj的欧拉通路的充要条件是Vi和vj是G中仅有的具有奇数度的顶点 定理4 设连通图G 有k个度为奇数的顶点 则E G 可划分为k 2条简单通路 定理5 有向连通图D为欧拉图的充要条件是每个顶点的入度等于出度 7 1欧拉图 定理6 有向连通图D存在一条欧拉通路的充要条件是恰有两个奇度数顶点 其中的一个入度比出度大1 另一个的出度比入度大1 而其余顶点的入度等于出度 7 1欧拉图 7 1欧拉图 定义1 通过图G的每个顶点一次且仅一次的回路称为哈密顿回路 哈密顿通路是通过图G的每个顶点一次且仅一次的通路 具有哈密顿回路的图称为哈密顿图 具有哈密顿通路而不具有哈密顿回路的图称为哈密顿图 平凡图是哈密顿图 性质 1 连通 度大于等于22 哈密顿通路是度为n 1的基本通路 其回路长为n 7 2哈密顿图 7 2哈密顿图 7 2哈密顿图 例 在某次国际会议的预备会中 共有8人参加 他们来自不同的国家 已知他们中任何两个无共同语言的人中的每一个 与其余有共同语言的人数之和大于或等于8 问能否将这8人排在圆桌旁 使任何人都能与两边的人交谈 定理4 若D为n n 2 阶竞赛图 则D中具有哈密顿通路 带权图与货郎担问题 货郎担问题 设有n个城市 城市之间均有道路 道路的长度均大于或等于0 一个旅行商从某个城市出发 要经过每个城市一次且仅一次 最后回到出发的城市 问他如何走 才能使路线最短 7 5树 7 5 1无向树及其性质7 5 2生成树7 5 3根树及其应用 定义1 连通无回路的无向图称为无向树 简称树 用T表示 若无向图F至少有两个连通分图都是树 称F为森林 仅有一个顶点的树称为平凡树 悬挂点称为树叶 定理1 设G 是n阶m条边的无向图 下列各命题等价 1 G是树 2 G的任意两个顶点之间有唯一路径 7 5 1无向树及其性质 3 G中无回路且m n 1 4 G是连通且m n 1 5 G是连通的 且G中任何边均是割边 6 G中无回路 但若在G的任意两个不同的顶点间加一条边 则所得的图中恰有唯一的一个含有新边的圈 定理2 设T是n阶非平凡的无向树 则T中至少有两片树叶 7 5 1无向树及其性质 定义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生成树 7 5 2生成树 7 5 2生成树 定义4 设G 是无向连通带权图 T是G的一棵生成树 T中各条边带权之和称为T的权 记作W T 若生成树T0在所有生成树中有最小的权 则称T0是G的最小生成树 7 5 2生成树 7 5 2生成树 7 5 3根树及其应用 在根树中 由于有向边的方向一致 故在画的时候可以省去边的方向 设T为根树 若将T中层数相同的顶点都标定次序 可以将根树分成以下各类 若T的每个分支点至多有r个儿子 则称T为r叉树 又若r叉树是有序的 则称其为r叉有序树 若T的每个分支点恰好有r个儿子 则称T为r叉正则树 又若T是有序的 则称其为r叉正则有序树 若T为r叉正则树 且每个树叶的层数均为树高 则称T为r叉完全正则树 又若T是有序的 则称其为r叉完全正则有序树 7 5 3根树及其应用 2叉正则有序树的每个分支点的两个儿子导出的根子树分别称为左子树和右子树 在所有的r叉树中 2叉树最重要 7 5 3根树及其应用 在通信中 常用二进制编码表示符号 如 A B C D就可用00 01 10 11分别来表示 这叫做等长码表示方法 适用于出现的频率基本相同的情况 当出现的频率相差较大时 就需要非等长的编码 7 5 3根树及其应用 可用2叉树产生二元前缀码 设T是具有t片树叶的2叉树 则T的每个分支点有1 2个儿子 设V为T的分支点 若v有两个儿子 在由v引出的两条边上 左边标上0 右边标上1 若v只有一个儿子 由它引出的边上可以标0也可以标1 7 5 3根树及其应用 设v是T的任意一片树叶 从树根到v的通路上各边的标号 0或1 按通路上边的顺序放在v处 则t片树叶处t个符号串组成的集合为一个二元前缀码 定理1 由一棵给定的2叉正则树 可以产生惟一的一个二元前缀码 由产生的任一个前缀码都可以传输符号 但这些符号出现频率不同时 就要用各符号出现的频率为权 利用Huffman算法求最优2叉树 由最优2叉树产生的前缀码称为最佳前缀码 用最佳前缀码传输对应的各符号能使传输的二进制数位最省 即效率最高 7 5 3根树及其应用 7 4平面图及图的着色 7 4 1平面图的基本概念7 4 2欧拉公式7 4 3平面图的判断7 4 4平面图的对偶图7 4 5图中顶点的着色7 4 6地图的着色与平面图的点着色7 4 7边着色 定义1 若图G能以这样一来的方式画在曲面上 即除顶点处外无任何边交叉 则称图G可嵌入曲面S 若G可嵌入平面 则称G是可平面图或平面图 画出的无边相交的图称为G的平面迁入 无平面嵌入的图称为非平面图 7 4 1平面图的概念 定理1 若图G是平面图 则G的任何子图都是平面图 定理2 若图G是非平面图 则G的任何母图都是非平面图 推论 Kn n 5 和K3 n n 3 都是非平面图 定义2 设G是一个平面图 由图的边所包围的一个区域 其内部既不包含图的顶点 也不包含图的边 则称这样的区域为G的一个面 如果面的面积是有限的 则称该面为有限面 否则称该面为无限面 如果两个面的边界至少有一条公共边 则称这两个面是相邻的 否则是不相邻的 包围一个面的所有边组成的回路称为该面的边界 边界的长度成为面的次数 记作deg Ri 定理3 若图G是平面图 则在G中加平行边和环后都是平面图 7 4 1平面图的概念 定理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平面图的概念 7 4 2欧拉公式 定理6 设G是n n 3 阶m条边的极大平面图 则m 3n 6 7 4 2欧拉公式 7 4 3平面图的判断 定义1 设e u v 为图G的一条边 在G中删除e 增加新的顶点w 使u v均与w相邻 称为在G中插入2度顶点w 设w为G中一个2度顶点 w与u v相邻 删除w增加新边 u v 称为在G中消去2度顶点w 定义2 若两个图G1 G2同构 或反复插入或消去2度顶点后同构 则称G1 G2是同胚的 定理1 图G是平面图当且仅当G中既不含与K5同胚子图 也不含与K3 3同胚子图 定理2 图G是平面图当且仅当G中既没有可以收缩到K5的子图 也没有可以收缩到K3 3的子图 7 4 4平面图的对偶图 7 4 4平面图的对偶图 7 4 4平面图的对偶图 7 4 4平面图的对偶图 7 4 5图中顶点的着色 7 4 5图中顶点的着色 7 4 6地图的着色与平面图的点着色 定义1 连通无桥平面图的平面嵌入及其所有的面称为平面地图或地图 地图的面称为 国家 若两个国家的边界至少有一条公共边 则称这两个国家是相邻的 7 4 7边着色 7 3二部图 7 3 1二部图7 3 2支配集 点覆盖集与点独立集7 3 3边覆盖集与匹配7 3 4二部图中的匹配 7 3 1二部图 定理1 一个无向图G 是二部图当且仅当G中无奇数长度的回路 7 3 4二部图中的匹配 7 3 4二部图中的匹配 7 3 4二部图中的匹配 例 在某界大学本科毕业生分配的供求会上 有n个毕业生可从m m n 个单位选择自己的职业 已知每个毕业生至少愿意去r 1 r m 个单位工作 而每个单位至多看中了其中r 1名毕业生 愿意从中选择一名 问最多有多少个单位可以选择到满意的一名毕业生 第四篇抽象代数 第十章代数系统第十一章半群与群第十二章环与域第十三章格与布尔代数 代数系统 是指定义有若干运算的集合 例如 整数集合 在其上定义乘法和加法 就成为一个代数系统 用抽象方法研究各种代数系统的性质的理论学科叫 近世代数 所谓抽象方法 是指它并不关注组成代数系统的具体集合是什么 也不关注集合上的运算如何定义 而只假定这些运算遵循某组规则 如结合律 交换律 分配律等 根据这些来研究和讨论系统应有的性质 第十章代数系统 代数系统 是以研究数学 文字和更一般元素的运算的规律和由这些规律适合的公理而定义的各种数学结构的性质为中心问题 10 1二元运算及其性质10 2代数系统 第十章代数系统 10 1二元运算及其性质 验证一个运算是否为集合A上的运算 主要考虑两点 1 A中任何n个元素都可以进行这种运算 且运算结果是唯一的2 A对该运算是封闭的 10 1二元运算及其性质 例1 判断数的普通加法和乘法在下列集合上是否封闭 A 0 1 B 1 1 C p p是素数 D a b a b I E x x是复数且 x 1 例2 证明普通加法在A n 6整除n 18整除n2 上是封闭的 10 1二元运算及其性质 10 1二元运算及其性质 二元运算的性质 对有穷集合S上的一元和二元运算 除了可以用函数的表达式给出来以外 还可以用运算表给出来 10 1二元运算及其性质 10 1二元运算及其性质 10 1二元运算及其性质 10 1二元运算及其性质 如果x的逆元存在 则称x是可逆的 将x的逆元记为x 1 10 1二元运算及其性质 10 2代数系统 在某些代数系统中存在着一些特定的元素 它对系统的一元或二元运算起着重要的作用 如 单位元和零元 在定义代数系统的时候 如果把含有这样的特定元素也作为系统的性质 在这种情况下 称这些元素为该代数系统的特异元素或代数常数 也可以将其列在代数系统的表达式中 10 2代数系统 10 2代数系统 同类型的代数系统仅仅是构成成分相同 不一定具有相同的运算性质 在规定了一个代数系统的构成成分 即集合 运算及代数常数以后 如果再对这些运算所遵从的算律加以限制 那么满足这些条件的代数系统就具有完全相同的性质 从而构成了一类特殊的代数系统 10 2代数系统 据此将代数系统分类 然后研究每一类代数系统的共同性质 并将研究的结果运用到具体的代数系统中去 这种方法就是抽象代数的基本方法 也是代数结构课程的主要内容 10 2代数系统 任何代数系统V 其子代数一定存在 最大的子代数就是本身 若令V中所有代数常数构成的集合为B 且B对V中所有的运算都是封闭的 则B就构成了V的最小的子代数 最大 最小子代数都称为V的平凡子代数 若B S 则称B为V的真子代数 10 2代数系统 第十一章半群与群 11 1半群与独异点11 2群的定义与性质11 3子群11 4陪集与拉格朗日定理11 5正规子群与商群11 6群的同态与同构11 7循环群与置换群 11 1半群与独异点 该运算满足指数定律 该运算也满足指数定律 半群的子代数叫做子半群 独异点的子代数叫做子独异点 11 1半群与独异点 11 2群 定理2 每一循环群都是可交换群 定理1 每一循环独异点都是可交换的 10 2代数系统 定理4 设集合A上二元运算 是可结合的 若A中元素a是可逆的 则a是可消去元 定理5 设 S 是一个独异点 则在关于 的运算表中任何两行或任何两列都不是相同的 10 2代数系统