《离散数学代数结构部分PPT演示课件》由会员分享，可在线阅读，更多相关《离散数学代数结构部分PPT演示课件（126页珍藏版）》请在金锄头文库上搜索。
1、第三部分代数结构 1 第五章代数系统 代数结构又称为代数系统 简称代数 是抽象代数的主要研究对象 代数系统的种类很多 它们在计算机科学的自动机理论 编码理论 形式语言 时序线路 开关线路计数问题以及计算机网络纠错码的纠错能力判断 密码学 计算机理论科学等方面有着非常广泛的应用 2 本部分主要内容二元运算及其性质 二元运算中的特殊元素幺元 零元 逆元 代数系统的定义及其性质 3 定义5 1设为集合 函数称为上的二元运算 简称为二元运算 5 1节二元运算及其性质 在整数集合上 对任意两个整数所进行的普通加法和乘法 都是集合上的二元运算 4 如何判断一个运算是否为集合上的二元运算 唯一性集合S中任意
2、的两个元素都能进行这种运算 并且结果要是唯一的 封闭性集合S中任意的两个元素运算的结果都是属于S的 就是说S对该运算是封闭的 5 例5 1设A x x n N 问在集合A上通常的乘法运算是否封闭 对加法运算呢 解 对于任意的所以乘法运算是封闭的 而对于加法运算是不封闭的 因为至少有 6 定义5 2设 是定义在集合A上的二元运算 如果对于任意的x y A 都有x y y x 则称该二元运算 是可交换的 例5 2设Q是有理数集合 是Q上的二元运算 对任意的a b Q a b a b a b 问运算 是否可交换 解 因为a b a b a b b a b a b a 所以运算 是可交换的 7 定义5
3、 1设为集合 函数称为上的二元运算 简称为二元运算 5 1节二元运算及其性质 在整数集合上 对任意两个整数所进行的普通加法和乘法 都是集合上的二元运算 8 定义5 2设 是定义在集合A上的二元运算 如果对于任意的x y A 都有x y y x 则称该二元运算 是可交换的 例5 2设Q是有理数集合 是Q上的二元运算 对任意的a b Q a b a b a b 问运算 是否可交换 解 因为a b a b a b b a b a b a 所以运算 是可交换的 9 定义5 3设 是定义在集合A上的二元运算 如果对于任意的x y z A 都有 x y z x y z 则称该二元运算 是可结合的 或者说运
4、算 在A上适合结合律 例5 3设A Z 是整数中的加法 则 在Z中适合结合律 是整数中的减法 则特取 而 运算 不满足结合律 10 定义5 4设 是定义在集合A上的一个二元运算 如果对于任意的x A 都有x x x 则称运算 是等幂的 例5 4设P S 是集合S的幂集 在P S 上定义的两个二元运算 集合的 并 运算 和集合的 交 运算 验证 是等幂的 解 对于任意的A P S 有A A A和A A A 因此运算 和 都满足等幂律 11 定义5 5设 和 是S上的两个二元运算 如果对任意的有 例5 5在实数集R上 对于普通的乘法和加法有 即乘法对加法是可分配的 12 定义5 6设 和 是定义在
5、集合A上的两个可交换二元运算 如果对于任意的x y A 都有 则称 运算和 满足吸收律 例5 6设集合N为自然数全体 在N上定义两个二元运算 和 对于任意x y N 有x y max x y x y min x y 验证运算 和 满足吸收律 13 解 对于任意a b N a a b max a min a b aa a b min a max a b a因此 和 满足吸收律 14 定义5 7设 是S上的二元运算 5 2节二元运算中的特殊元素 1 幺元 15 在自然数集N上加法的幺元是0 乘法的幺元是1 对于给定的集合和运算有的存在幺元 有的不存在幺元 16 17 定理5 1设 是S上的二元运算
6、 如果S中存在关于运算 的 幺元 则必是唯一的 所以幺元是唯一的 18 定理5 2设 是S上的二元运算 如果S中既存在关于运算 的左幺元 又存在关于运算的右幺元则S中必存在关于运算 的幺元e并且 19 定义5 8设 是S上的二元运算 2 零元 20 在自然数集N上普通乘法的零元是0 而加法没有零元 21 定理5 3设 是S上的二元运算 如果S中存在 关于运算 的 零元 则必是唯一的 所以零元是唯一的 22 定理5 4设 是S上的二元运算 如果S中既存在关于运算 的左零元又存在关于运算 的右零元 23 定义5 9设 是S上的二元运算 2 逆元 24 例5 8整数集Z上关于加法的幺元是0 对任意的
7、整数m 它关于加法的逆元是 m 因为 25 定理5 5设 是S上可结合的二元运算 e为幺元 如果S中元素x存在 关于运算 的逆元 则必是惟一的 所以对于可结合的二元运算 逆元是惟一的 26 定理5 6设 是S上可结合的二元运算 e为幺元 如果S中元素x既存在关于运算 的左逆元 又存在关于运算 的右逆元 则S中必存在x关于运算 的逆元并且 27 解 运算适合交换律 结合律和消去律 不适合幂等律 单位元是a 没有零元 且 运算适合交换律 结合律和幂等律 不适合消去律 单位元是a 零元是b 只有a有逆元 运算不适合交换律 适合结合律和幂等律 不适合消去律 没有单位元 没有零元 没有可逆元素 28 定
8、义5 10设S是非空集合 由S和S上若干个运算构成的系统称为代数系统 记作 5 3节代数系统 代数系统也简称为代数 例如 R是实数集 对于普通的加法和剩法运算 M是n阶方阵构成的集合 对于矩阵的加法和剩法运算 29 定义5 11设 都是封闭的 且B和S含有相同的代数常数 则称 30 定义5 12设 31 例5 11设 32 定义5 13设 定义5 14设 33 34 例5 14表示求两个数的最小公倍数的运算 则 解 零元是不存在的 只有惟一的逆元 35 例5 15在有理数集Q上定义二元运算 解 36 37 例5 16设有集合 解 讨论这5个集合对普通的乘法和加法运算是否封闭 38 例5 17设
9、 解 39 第六章几个典型的代数系统 本章讨论几类重要的代数结构 半群 群 环 域 格与布尔代数 40 定义6 1设 6 1节半群与群 是可结合的即 41 定义6 2若半群 例6 1 1 普通加法是 2 普通乘法是N Z Q和R上的二元运算 满足结合律且有幺元1 42 43 定义6 3设 例6 2 定义6 3设 44 定义6 4设 定义6 5设 45 例6 3设 证明G关于矩阵乘法构成一个群 故G关于矩阵乘法是Z上的代数运算 矩阵乘法满足结合律 故G关于矩阵乘法构成半群 在G中每个矩阵的逆元都是自己 所以G关于矩阵乘法构成一个群 46 定义6 6若群 例6 4 1 在中除0之外都没有逆元 所以
10、它仅是含幺半群而不是群 中每个元素都有逆元即它的相反数 且运算满足交换律 所以它们是交换群 0没有逆元 所以它们仅是有么半群而不是群 47 48 例6 5设G e a b c 为G上的二元运算 它由以下运算表给出 不难证明G是一个群 称该群为Klein四元群 49 定义6 7设 50 例6 6在群 解 51 定理6 1设 证明 略 52 定义6 8设 53 定义6 9 54 例6 7对于集合 列出其运算表如下表 从表中可以看出 运算满足封闭性 满足结合律和交换律 0是单位元 每个元都有逆元 这个群的阶数是6 元素0 1 2 3 4 5的次数分别为1 6 3 2 3 6 55 定理6 2设 下面
11、证明唯一性 从而唯一性得证 56 例6 8设 57 定理6 3 58 定理6 4设 59 60 定理6 5G为有限群 则G的运算表中的每一行 每一列 都是G中元素的一个置换 且不同的行 或列 的置换都不相同 定义6 10设 61 例6 9 例6 10群 62 定理6 6 子群判定定理1 设H是群 证明 必要性是显然的 63 定理6 7 子群判定定理2 设H是群 证明 必要性 充分性证明 64 定理6 8 子群判定定理3 设H是群 证明 必要性是显然的 65 例6 11设 66 定义6 11设 6 2节陪集与拉格朗日定理 例6 12设 解 H的右陪集为 67 定理6 9设H是群 68 定理6 1
12、0设 69 70 定理6 11设 证明 略 推论6 1 71 定理6 12设 72 定理6 13设 73 定义6 12群 定理6 14 拉格朗日定理 设 即子群的阶数一定是群的阶数的因子 根据定理6 11的推论有 74 推论6 2设 推论6 3设 根据定理6 11的推论有 75 定义6 13设 任何群G都有正规子群 因为G的两个平凡子群 76 定理6 15设 证明 略 77 例6 13设 78 例6 14设 79 定理6 16设 80 定义6 14设 6 3群的同态与同构 81 例6 13设 82 定义6 15设 83 定理6 17设 证明 略 84 定义6 16设 85 定理6 18 群同态
13、基本定理 设 86 定义6 17设 6 4循环群与置换群 87 88 定理6 19设 89 例6 16 例6 17设 90 定义6 18设 例6 18设 91 92 定义6 19设 例6 194元置换 93 定义6 20设 94 定理6 20 95 定义6 21 例6 20如图进行旋转 也可以围绕它的对称轴进行翻转 但经过旋转或翻转后仍要与原来的方格重合 方格中的数字可以改变 如果把每种旋转或翻转看作是作用在 96 97 98 99 定义6 22设 6 5环和域 100 例6 21 1 整数集 101 定理6 21设 2 3证明略 102 例6 22 103 定义6 23设 104 例6 23
14、 1 整数环 105 例6 22模6整数环 106 定义6 24设 107 定义6 22设 6 5环和域 108 例6 25设 109 110 111 定义6 25设 6 6格与布尔代数 112 例6 26设n是正整数 113 例6 27 1 对于偏序集 114 115 定理6 22设 116 定理6 23设 117 定义6 26设 定义6 27设 118 例6 28设格 119 定义6 28设 120 例6 29说明下图中的格是否为分配格 为什么 121 122 定义6 29设 123 定义6 30设 例6 30 例6 31 124 定义6 31设 125 定义6 32设 定义6 33如果一个格是有补分配格 则称它为布尔格或布尔代数 126
