大连理工Chapter5(代数结构)(2008-3-8)(1).ppt

2020 2 19 1 离散数学 代数结构 DiscreteMathematics AlgbraStructures 徐喜荣大连理工大学电信学院计算机系 2020 2 19 2 数学早已确立了其在人类文明中的基础地位 恩格斯说过 一个学科成熟的标志 就是数学的介入 这充分体现出了数学的重要性 自然科学和工程领域中数学知识无处不在 甚至在人文学科中数学也扮演着越来越重要的角色 在工程领域 数学的影响可能更为直接 毫不夸张的说 飞机能上天 汽车能上路 没有数学是绝对不行的 内容简介 2020 2 19 3 21世纪信息社会的两个主要特征 计算机无处不在 数学无处不在 21世纪信息社会对科技人才的要求 会 用数学 解决实际问题 会用计算机进行科学计算 内容简介 2020 2 19 4 离散数学是现代数学的一个重要分支 是计算机科学与技术的理论基础 所以又称为计算机数学 人们已公认 高科技本质上是数学技术 因此 计算机科学与技术说到底根本是数学技术 事实上 从计算机产生到以后它的每一步发展都离不开数学 内容简介 2020 2 19 5 离散数学是计算机科学与技术专业的核心 骨干课程 一方面 它给后继课 例如数据结构 编译系统 操作系统 数据库原理和人工智能等 提供必要的数学基础 内容简介 2020 2 19 6 另一方面 通过学习离散数学 培养和提高了学生的抽象思维和逻辑推理能力 为学生今后继续学习和工作 参加科学研究 处理离散信息 从事计算机软件的开发和设计以及计算机的其他应用打好数学基础 内容简介 2020 2 19 7 第一篇数理逻辑第一章命题逻辑第二章谓词逻辑第二篇集合论第三章集合与关系第四章函数第三篇代数系统第五章代数结构第六章格与布尔代数第四篇图论第七章图论 主要内容 2020 2 19 8 第三篇代数系统 代数结构是近世代数或抽象代数学研究的中心问题 是数学中最重要的 基础的分支之一 是在初等代数学的基础上产生和发展起来的 它起始于19世纪初 形成于20世纪30年代 2020 2 19 9 第三篇代数系统 挪威数学家阿贝尔 N H Abel 法国数学家伽罗瓦 E Galois 英国数学家德 摩根 A DeMorgan 和布尔 G Boole 等人都做出了杰出贡献 荷兰数学家范德瓦尔登 B L VanDerWaerden 根据德国数学家诺特 A E Noether 和奥地利数学家阿廷 E Artin 的讲稿 于1930年和1931年分别出版了 近世代数学 一卷和二卷 标志着抽象代数的成熟 2020 2 19 10 代数结构是以研究数字 文字和更一般元素的运算的规律和由这些运算适合的公理而定义的各种数学结构的性质为中心问题 它对现代数学如拓扑学 泛函分析等 以及一些其他科学领域 如计算机科学 编码理论等 都有重要影响和广泛地应用 第三篇代数系统 2020 2 19 11 第五章代数结构 本章给出代数结构的一般定义与实例 讨论代数结构的基本性质 在正式给出代数结构的定义之前 先来说明什么是在一个集合上的运算 因为运算这个概念是代数结构中不可缺少的概念 2020 2 19 12 定义5 1 1设S是个非空集合且函数f Sn S 则称f为一个n元运算 其中n是自然数 称为运算的元数或阶 当n 1时 称f为一元运算 当n 2时 称f为2元运算 等等 5 1运算 代数系统与特异元素 2020 2 19 13 注意 n元运算是个闭运算 因为经运算后产生的象仍在同一个集合中 封闭性表明了n元运算与一般函数的区别之处 此外 有些运算存在幺元或零元 它在运算中起着特殊的作用 称它为S中的特异元或常数 5 1运算 代数系统与特异元素 2020 2 19 14 运算的例子很多 例如 在数理逻辑中 否定是谓词集合上的一元运算 合取和析取是谓词集合上的二元运算 在集合论中 并与交是集合上的二元运算 在整数算术中 加 减 乘运算是二元运算 除运算便不是二元运算 因为它不满足封闭性 5 1运算 代数系统与特异元素 2020 2 19 15 讨论代数结构时 主要限于一元和二元运算 将用 等符号表示一元运算符 用 等符号表示二元运算符 一元运算符常常习惯于前置 顶置或肩置 如 x x x 二元运算符习惯于前置 中置或后置 如 xy x y xy 有了集合上运算的概念后 可定义代数结构 5 1运算 代数系统与特异元素 2020 2 19 16 定义5 1 2设S是个非空集合且fi是S上的ni元运算 其中i 1 2 m 由S及f1 f2 fm组成的结构 称为代数结构 记作 5 1运算 代数系统与特异元素 2020 2 19 17 此外 集合S的基数即 S 定义为代数结构的基数 如果S是有限集合 则代数结构是有限代数结构 否则便说是无穷代数结构 有时 要考察两个或多个代数结构 这里就有个是否同类型之说 请看下面定义 5 1运算 代数系统与特异元素 2020 2 19 18 定义5 1 3设两个代数结构和 如果fi和gi 1 i m 具有相同的元数 则称这两个代数结构是同类型的 5 1运算 代数系统与特异元素 2020 2 19 19 判定两个代数结构是否同类型 主要是对其运算进行考察 有时还需要在代数结构中集合的某个子集上讨论其性质 引出子代数结构的概念 5 1运算 代数系统与特异元素 2020 2 19 20 定义5 1 4是一代数结构 且非空集T S在运算f1 f2 fm下是封闭的 且T含有与S中相同的特异元 则称为代数结构的子代数 记为 5 1运算 代数系统与特异元素 2020 2 19 21 例5 1 1设R是实数集合 且 和 是R上的普通加法和乘法运算 则是一代数结构 因为运算 和 在R中是封闭的 显然 是无穷代数结构 5 1运算 代数系统与特异元素 2020 2 19 22 例5 1 2设S是非空集合 PS是它的幂集 对任意集合A B PS PS上的运算 和 定义如下 A B A B B A A B A B则是一代数结构 因为 显然 和 是闭运算 例5 1 l和例5 1 2中给出的两个代数结构是同类型的 即与是同类型的 5 1运算 代数系统与特异元素 2020 2 19 23 例5 1 3设 是由有限个字母组成的集合 称为字母表 由 中的字母组成的有序集合 称为 上的串 串中的字母个数m称为该串的长度 m 0时 叫做空串 用 表示 用 表示 上的串集合 在 上定义一个连接运算 用 表示 例如 则 那么是一个代数结构 如果令 则也是一个代数结构 5 1运算 代数系统与特异元素 2020 2 19 24 例5 1 4设有一台字长为8位的计算机 它以定点加 减 乘 除以及逻辑加和逻辑乘为运算指令 并分别用01 02 06表示 则在计算机中由28个不同数字所组成集合S同该机器中运算指令构成一代数结构 5 1运算 代数系统与特异元素 2020 2 19 25 声明 记号即为一代数结构 除特别指明外 运算符f1 f2 fm均为二元运算 根据需要对S及f1 f2 fm可置不同的集合符和运算符 5 1运算 代数系统与特异元素 2020 2 19 26 下面讨论一般代数结构的基本性质 也即是结构中任何运算所具有的性质 对于代数结构性质的考察方法不是一个一个研究各个结构 而是列举一组性质 把那些被选出的性质看成是公理 并且从这些公理推导出有效结论 这些结论对于满足这些公理的任何代数结构也都必定成立 5 1运算 代数系统与特异元素 2020 2 19 27 1 结合律给定 运算 满足结合律或者 是可结合的 即 z x y z S x y z x y z 5 1运算 代数系统与特异元素 2020 2 19 28 例5 1 5 给定 且对任意a b A有a b b 证明运算 是可结合的 证明因为对任意a b c A 有 a b c b c c a b c a c c故 a b c a b c 5 1运算 代数系统与特异元素 2020 2 19 29 2 交换律给定 运算 满足交换律或者 是可交换的 即 x y x y S x y y x 5 1运算 代数系统与特异元素 2020 2 19 30 例5 1 6 给定 其中Q为有理数集合 并且对任意a b R有a b a b a b b a b a 问运算 是否可交换 解因为a b a b a b b a b a b a 所以 运算 是可交换的 5 1运算 代数系统与特异元素 2020 2 19 31 如果一代数结构中的运算 是可结合和可交换的 那么 在计算a1 a2 am时可按任意次序计算其值 特别当a1 a2 am a时 则a1 a2 am am 称am为a的m次幂 m称a的指数 5 1运算 代数系统与特异元素 2020 2 19 32 下面给出am的归纳定义 设有且a S 对于m I 其中I 表示正整数集合 可有 1 a1 a 2 am 1 am a由此利用归纳法不难证明指数定律 1 am an am n 2 am n amn这里 m n I 类似地定义某代数结构中的负幂和给出负指数定律 5 1运算 代数系统与特异元素 2020 2 19 33 3 分配律一个代数结构若具有两个运算时 则分配律可建立这两个运算之间的某种联系 给定 运算 对于 满足左分配律 或者 对于 是可左分配的 即 x y x x y z S x y z x y x z 运算 对于 满足右分配律 或者 对于 是可右分配的 即 x y x x y z S y z x y x z x 5 1运算 代数系统与特异元素 2020 2 19 34 类似地可定义 对于 满足左或右分配律 若 对于 既满足左分配律又满足右分配律 则称 对于 满足分配律或是可分配的 同样可定义 对于 满足分配律 5 1运算 代数系统与特异元素 2020 2 19 35 由定义不难证明下面定理 定理5 1 1给定且 是可交换的 如果 对于 满足左分配律或者右分配律 则 对于 满足分配律 5 1运算 代数系统与特异元素 2020 2 19 36 例5 1 7给定 其中B 0 1 表5 1 1分别定义了运算 和 问运算 对于 是可分配吗 对于 呢 表5 1 1 解可以验证 对于 是可分配的 由定理5 1 1得到 但 对于 并非如此 因为 1 0 1 1 0 1 1 5 1运算 代数系统与特异元素 2020 2 19 37 形如表5 1 1的表常常被称为运算表或复合表 由运算符 行表头元素 列表头元素及复合元素四部分组成 当集合S的基数很小 特别限于几个元素时 代数结构中运算常常用这种表给出 其优点是简明直观 一目了然 5 1运算 代数系统与特异元素 2020 2 19 38 4 吸收律给定 则 对于 满足左吸收律 x y x y S x x y x 对于 满足右吸收律 x y x y S x y x x 若 对于 既满足左吸收律又满足右吸收律 则称 对于 满足吸收律或者可吸收的 5 1运算 代数系统与特异元素 2020 2 19 39 类似地定义 对于 满足左 右吸收律和吸收律 若 对于 是可吸收的 且 对于 也是可吸收的 则称 和 是互为吸收的 或 和 同时满足吸收律 5 1运算 代数系统与特异元素 2020 2 19 40 例5 1 8给定 其中N是自然数集合 和 定义如下 对任意a b N有 a b max a b a b min a b 试证 和 互为吸收的 证明因为a a b max a min a b a b aa a b max a min a b a b a故 和 是互为吸收的 5 1运算 代数系统与特异元素 2020 2 19 41 5 等幂律与等幂元给定 则 是等幂的或 满足等幂律即 x x S x x x 给定 且x S 则x是关于 的等幂元 x x x 5 1运算 代数系统与特异元素 2020 2 19 42 不难证明下面定理 定理5 1 2若x是中关于 的等幂元 对于任意正整数n 则xn x 5 1运算 代数系统与特异元素 2020 2 19 43 例5 1 9给定 其中PS是集合S的幂集 和 分别为集合的并和交运算 验证 和 是等幂的 证明对任意A PS 有A A A和A A A 故 和 都是等幂的 5 1运算 代数系统与特异元素 2020 2 19 44 6 幺元或单位元给定且 el er e S 则el 为关于 的左幺元 x x S el x x er 为关于 的右幺元 x x S x er x 若e既为 的左幺元又为 的右幺元 称e为关于 的幺元 亦可定义如下 e为关于 的幺元 x x S e x x e x 5 1运算 代数系统与特异元素 2020 2 19 45 例5 1 10给定 表5 1 2 表5 1 3和表5 1 4分别给出 的不同定义的运算表 试指出左幺元 右幺元及幺元 表5 1 2 5 1 3 5 1 4 解 如表5 1 2所定义 是 的幺元 如表5 1 3所定义 和 是 的右幺元 如表5 1 4所定义 是 的左幺元 5 1运算 代数系统与特异元素 2020 2 19 46 定理5 1 3给定且el和er分别关于 的左 右幺元 则el er e 且幺元e唯一 证明由题设可得el el er er e 下面再证幺元e是唯一的 若还有一幺元e1 S 则e1 e1 e e 即只有一个幺元 5 1运算 代数系统与特异元素 2020 2 19 47 5 1运算 代数系统与特异元素 7 零元给定及 l r S l为关于 的左零元 x x S l x l r为关于 的右零元 x x S x r r 为关于 的零元 x x S x x 2020 2 19 48 5 1运算 代数系统与特异元素 例5 1 11在例5 1 10中 试指出左 右零元及零元 解 如表5 1 2所定义 是 的零元 如表5 1 3所定义 和 都是 的左零元 如表5 1 4所定义 是 的右零元 2020 2 19 49 5 1运算 代数系统与特异元素 定理5 1 4给定且 l和 r分别为关于 的左零元和右零元 则 l r 且零元 是唯一的 证明可仿定理5 1 3证明 2020 2 19 50 5 1运算 代数系统与特异元素 定理5 1 5给定且 S 1 如果 e S 其中 和e分别为关于 的零元和幺元 则 e 证明用反证法 假设 e 则对任意x S 有x e x x e 可见S中的所有元素都是相同的 这与 S 1矛盾 2020 2 19 51 5 1运算 代数系统与特异元素 8 逆元给定且么元e S 则 x为关于 的左逆元 y y S x y e x为关于 的右逆元 y y S y x e x关于 的可逆 y y S y x x y e 给定及么元e x y S 则 y为x的左逆元 y x e y为x的右逆元 x y ey为e的逆元 y x x y e 2020 2 19 52 5 1运算 代数系统与特异元素 显然 若y是x的逆元 则x也是y的逆元 因此称x与y互为逆元 通常x的逆元表示为x 1 一般说来 一个元素的左逆元不一定等于该元素的右逆元 而且 一个元素可以有左逆元而没有右逆元 同样可以有右逆元而没有左逆元 一个元素的左或者右逆元还可以不唯一 2020 2 19 53 5 1运算 代数系统与特异元素 例5 1 8给定 其中S 且 的定义如表5 2 5所示 试指出该代数结构中各元素的左 右逆元情况 2020 2 19 54 5 1运算 代数系统与特异元素 解 是么元 的左逆元和右逆元都是 即 与 互为逆元 的左逆元是 而右逆元是 有两个左逆元 和 的右逆元是 但 没有左逆元 2020 2 19 55 5 2半群 独异点与群 在本节中将讨论具有一个二元运算的抽象代数 半群 独异点与群 半群与群在形式语言 快速加法器设计 纠错码制定和自动机理论中都有卓有成效的应用 2020 2 19 56 5 2半群 独异点与群 定义5 2 1给定代数结构 若 满足结合律 则称为半群 即半群就是由集合及其定义的一个可结合的二元运算组成的代数结构 2020 2 19 57 5 2半群 独异点与群 定义5 2 2给定 若是半群且 有么元 或者 满足结合律且拥有么元 则称为独异点 可以看出 独异点是含有么元的半群 因此又将独异点叫做含么半群 有时为了强调么元e 独异点表为 2020 2 19 58 5 2半群 独异点与群 例1 给定和 其中N为自然数集合 和 为普通加法和乘法 易知和都是半群 而且还是独异点 因为0是 的么元 1是 的么元 如果半群中的集合S是有限的 则称半群为有限半群 对于有限半群可以给出下面有趣定理 2020 2 19 59 5 2半群 独异点与群 定理5 2 1为有限半群 x x S x x x 本定理告诉我们 有限半群存在等幂元 证明因为为半群 则 是可结合的 故对任意y S有 y y y2 S y2 y y3 S 又因为S是限集合 所以必存在j i 使得yi yj令p j i 则yi yp yi所以 对于q i有 yq yp yq 1 2020 2 19 60 5 2半群 独异点与群 因为p 1 故总有k 1 使得 kp i对于ykp S 则由 1 有 ykp yp ykp yp yp ykp y2p ykp ykp ykp因此 存在x ykp S 使得 x x x 2020 2 19 61 5 2半群 独异点与群 定义5 2 3给定半群 若 是可交换的 则称是可交换半群 类似地可定义可交换独异点 2020 2 19 62 5 2半群 独异点与群 例 给定和 其中PS是集合S的幂集 和 为集合上的交运算和并运算 可知和是可交换半群 不仅如此 它们还都是可交换独异点 因为 与S分别是它们的么元 2020 2 19 63 5 2半群 独异点与群 定义5 2 4给定半群和g S 以及自然数集合N 则g为的生成元 x x S n n N x gn 此时也说 元素g生成半群 而且称该半群为循环半群 类似地 可定义独异点的生成元g和循环独异点 并且规定g0 e 2020 2 19 64 5 2半群 独异点与群 定理5 2 2每个循环独异点都是可交换的 证明令为循环独异点且g为其生成元 则对任意a b M 存在m n N 使得a gm b gn 于是a b gm gn gm n gn m gmn gm b a可见 是可交换的 故是可交换的 显然 每个循环半群也是可交换的 2020 2 19 65 5 2半群 独异点与群 例 给定 其中N是自然数集合 为普通加法 则是无穷循环独异点 0是么元 1是生成元 2020 2 19 66 5 2半群 独异点与群 定义5 2 7给定半群 及非空集合T S 若T对 封闭 则称为的子半群 类似地 定义独异点的子独异点 应注意的是e P 2020 2 19 67 5 2半群 独异点与群 定理5 2 2给定半群及任意a S 是循环子半群 证明因为是半群 故对任意a S ai S 其中i I 则 a a2 a3 S 显然 a是的生成元 故是循环子半群 2020 2 19 68 5 2半群 独异点与群 定理5 2 3给定可交换独异点 若P为其等幂元集合 则为子独异点 证明显然 e P 令a b P 于是a a a b b b 又因为 是可交换的 故 a b a b a b b a a b b a a b a a a b a b可见 a b P 即P对于 是封闭的 因而 是的子独异点 2020 2 19 69 5 2半群 独异点与群 定理5 2 4设为独异点 则关于 的运算表中任两列或任两行均不相同 证明因为对任意的a b M且a b时 总有e a a b e b和a e a b b e因此 在 的运算表中不可能有两列或两行是相同的 2020 2 19 70 5 2半群 独异点与群 定理5 2 5给定独异点 对任意a b M且a b均有逆元 则 1 a 1 1 a 2 a b有逆元 且 a b 1 b 1 a 1 证明 1 因为a 1是a的逆元 且a a 1 a 1 a e 故 a 1 1 a 2 因为 a b b 1 a 1 a b b 1 a 1 a e a 1 a a 1 e 同理 b 1 a 1 a b e 故 a b 1 b 1 a 1 2020 2 19 71 5 2半群 独异点与群 下面介绍群的概念及性质 定义5 2 9给定独异点 若中每个元素均可逆 称该独异点为群 2020 2 19 72 5 2半群 独异点与群 群是独异点的特例 群对运算满足 1 封闭性 2 具有结合律 3 含有幺元 4 每个元素均可逆 群 独异点 半群和代数系统之间的关系是 2020 2 19 73 5 2半群 独异点与群 例5 2 1 给定和 其中 I和Q分别是整数集合和有理数 和 是一般的加法和乘法 可知 1 是群 0是幺元 每个元素的逆元是 i 2 不是群 1是幺元 0无逆元 3 是群 2020 2 19 74 5 2半群 独异点与群 例5 2 2 设G a b c 在G上定义运算 如下表 则是群 a是幺元 b和c互为逆元 2020 2 19 75 5 2半群 独异点与群 定义5 2 10给定群 若G是有限集 则称是有限群 并且把G的基数称为该有限群的阶数 若集合G是无穷的 则称为无穷群 例5 2 3 和都是无穷群 由群的定义 群具有半群和独异点的性质 除外还有自己独特的性质 下面讨论如下 2020 2 19 76 5 2半群 独异点与群 定理5 2 6 群的性质1 若是群 并且其元素个数大于1 那么中无零元 2020 2 19 77 5 2半群 独异点与群 证明 若 为的零元 又知道 G 1 则由代数系统中的知识 e 对任意x G 均有 x 取x e 则有 e e 故 无逆元 这与假设矛盾 2020 2 19 78 5 2半群 独异点与群 定理5 2 7 群的性质2 群中一元一次方程a x b和y a b总有解 证明 事实上 其解可以构造为 x a 1 b y b a 1 2020 2 19 79 5 2半群 独异点与群 定理5 2 8 群的性质3 群中具有消去律 即若a b a c 或b a c a 则b c 2020 2 19 80 5 2半群 独异点与群 证明 b e b a 1 a b a 1 a b a 1 a c a 1 a c e c cb b e b a a 1 b a a 1 c a a 1 c a a 1 c e c则b c 2020 2 19 81 5 2半群 独异点与群 然而 具有消去律的半群 独异点未必就是群 例如 是半群也是独异点并且具有消去律 然而它不是群 幺元1外的元素无逆元 2020 2 19 82 5 2半群 独异点与群 定理5 2 9 群的性质4 群中幺元以外的元素均不等幂 2020 2 19 83 5 2半群 独异点与群 证明 假设存在幺元以外一个元素a 满足a a a 则a e a a 1 a a a 1 a a a 1 a e 与假设矛盾 2020 2 19 84 5 2半群 独异点与群 下面介绍子群 定义5 2 11设是群 若G的非空子集S关于运算 也构成群 则称为的子群 记为 任何一个群至少有两个子群 和自身 称为的平凡子群 关于子群 有以下定理 2020 2 19 85 5 2半群 独异点与群 定理5 2 11 子群性质1 子群保持群的幺元 2020 2 19 86 5 2半群 独异点与群 证明 因为是群 故有幺元e1 是群 有幺元e 所以 g S 有e1 g g 但 故e1 g g在中也成立 从而有e1 g g e g 由群的消去律得 e1 e 2020 2 19 87 5 2半群 独异点与群 定理5 2 12 子群的判定定理1 设是群 S是G的有限非空子集合 如果S关于运算封闭 那么是的子群 2020 2 19 88 5 2半群 独异点与群 证明 b S 由S对运算 的封闭性 知b1 b2 b3 bj 都是S中的元素 又因为S是有限非空子集 所以b的幂次序列中一定有相同元素 不妨设bi bj 并有bi bi bj i 但bi e bi bi bj i 由消去律 得bj i e 即除封闭性而保持结合性外 还具有幺元 考虑bj i e 若j i 1 则b e b 1 e 若j i 1则bj i 1 b e 对 b S都满足b 1 bj i 1 故是群 因而是的子群 2020 2 19 89 5 2半群 独异点与群 如果S是G的无限子群 则结论不能成立 例如 是群 N对 封闭 但不是子群 因为自然数在加法下没有逆元 相反数不属于N 因为任一自然数形成的加法幂序列中没有相同元 2020 2 19 90 5 2半群 独异点与群 定理5 2 13