离散数学代数结构部分.ppt

第三部分代数结构 第五章代数系统 代数结构又称为代数系统 简称代数 是抽象代数的主要研究对象 代数系统的种类很多 它们在计算机科学的自动机理论 编码理论 形式语言 时序线路 开关线路计数问题以及计算机网络纠错码的纠错能力判断 密码学 计算机理论科学等方面有着非常广泛的应用 本部分主要内容二元运算及其性质 二元运算中的特殊元素幺元 零元 逆元 代数系统的定义及其性质 定义5 1设为集合 函数称为上的二元运算 简称为二元运算 5 1节二元运算及其性质 在整数集合上 对任意两个整数所进行的普通加法和乘法 都是集合上的二元运算 如何判断一个运算是否为集合上的二元运算 唯一性集合S中任意的两个元素都能进行这种运算 并且结果要是唯一的 封闭性集合S中任意的两个元素运算的结果都是属于S的 就是说S对该运算是封闭的 例5 1设A x x n N 问在集合A上通常的乘法运算是否封闭 对加法运算呢 解 对于任意的所以乘法运算是封闭的 而对于加法运算是不封闭的 因为至少有 定义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 所以运算 是可交换的 定义5 1设为集合 函数称为上的二元运算 简称为二元运算 5 1节二元运算及其性质 在整数集合上 对任意两个整数所进行的普通加法和乘法 都是集合上的二元运算 定义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 所以运算 是可交换的 定义5 3设 是定义在集合A上的二元运算 如果对于任意的x y z A 都有 x y z x y z 则称该二元运算 是可结合的 或者说运算 在A上适合结合律 例5 3设A Z 是整数中的加法 则 在Z中适合结合律 是整数中的减法 则特取 而 运算 不满足结合律 定义5 4设 是定义在集合A上的一个二元运算 如果对于任意的x A 都有x x x 则称运算 是等幂的 例5 4设P S 是集合S的幂集 在P S 上定义的两个二元运算 集合的 并 运算 和集合的 交 运算 验证 是等幂的 解 对于任意的A P S 有A A A和A A A 因此运算 和 都满足等幂律 定义5 5设 和 是S上的两个二元运算 如果对任意的有 例5 5在实数集R上 对于普通的乘法和加法有 即乘法对加法是可分配的 定义5 6设 和 是定义在集合A上的两个可交换二元运算 如果对于任意的x y A 都有 则称 运算和 满足吸收律 例5 6设集合N为自然数全体 在N上定义两个二元运算 和 对于任意x y N 有x y max x y x y min x y 验证运算 和 满足吸收律 解 对于任意a b N a a b max a min a b aa a b min a max a b a因此 和 满足吸收律 定义5 7设 是S上的二元运算 5 2节二元运算中的特殊元素 1 幺元 在自然数集N上加法的幺元是0 乘法的幺元是1 对于给定的集合和运算有的存在幺元 有的不存在幺元 定理5 1设 是S上的二元运算 如果S中存在关于运算 的 幺元 则必是唯一的 所以幺元是唯一的 定理5 2设 是S上的二元运算 如果S中既存在关于运算 的左幺元 又存在关于运算的右幺元则S中必存在关于运算 的幺元e并且 定义5 8设 是S上的二元运算 2 零元 在自然数集N上普通乘法的零元是0 而加法没有零元 定理5 3设 是S上的二元运算 如果S中存在 关于运算 的 零元 则必是唯一的 所以零元是唯一的 定理5 4设 是S上的二元运算 如果S中既存在关于运算 的左零元又存在关于运算 的右零元 定义5 9设 是S上的二元运算 2 逆元 例5 8整数集Z上关于加法的幺元是0 对任意的整数m 它关于加法的逆元是 m 因为 定理5 5设 是S上可结合的二元运算 e为幺元 如果S中元素x存在 关于运算 的逆元 则必是惟一的 所以对于可结合的二元运算 逆元是惟一的 定理5 6设 是S上可结合的二元运算 e为幺元 如果S中元素x既存在关于运算 的左逆元 又存在关于运算 的右逆元 则S中必存在x关于运算 的逆元并且 解 运算适合交换律 结合律和消去律 不适合幂等律 单位元是a 没有零元 且 运算适合交换律 结合律和幂等律 不适合消去律 单位元是a 零元是b 只有a有逆元 运算不适合交换律 适合结合律和幂等律 不适合消去律 没有单位元 没有零元 没有可逆元素 定义5 10设S是非空集合 由S和S上若干个运算构成的系统称为代数系统 记作 5 3节代数系统 代数系统也简称为代数 例如 R是实数集 对于普通的加法和剩法运算 M是n阶方阵构成的集合 对于矩阵的加法和剩法运算 定义5 11设 都是封闭的 且B和S含有相同的代数常数 则称 定义5 12设 例5 11设 定义5 13设 定义5 14设 例5 14表示求两个数的最小公倍数的运算 则 解 零元是不存在的 只有惟一的逆元 例5 15在有理数集Q上定义二元运算 解 例5 16设有集合 解 讨论这5个集合对普通的乘法和加法运算是否封闭 例5 17设 解 第六章几个典型的代数系统 本章讨论几类重要的代数结构 半群 群 环 域 格与布尔代数 定义6 1设 6 1节半群与群 是可结合的即 定义6 2若半群 例6 1 1 普通加法是 2 普通乘法是N Z Q和R上的二元运算 满足结合律且有幺元1 定义6 3设 例6 2 定义6 3设 定义6 4设 定义6 5设 例6 3设 证明G关于矩阵乘法构成一个群 故G关于矩阵乘法是Z上的代数运算 矩阵乘法满足结合律 故G关于矩阵乘法构成半群 在G中每个矩阵的逆元都是自己 所以G关于矩阵乘法构成一个群 定义6 6若群 例6 4 1 在中除0之外都没有逆元 所以它仅是含幺半群而不是群 中每个元素都有逆元即它的相反数 且运算满足交换律 所以它们是交换群 0没有逆元 所以它们仅是有么半群而不是群 例6 5设G e a b c 为G上的二元运算 它由以下运算表给出 不难证明G是一个群 称该群为Klein四元群 定义6 7设 例6 6在群 解 定理6 1设 证明 略 定义6 8设 定义6 9 例6 7对于集合 列出其运算表如下表 从表中可以看出 运算满足封闭性 满足结合律和交换律 0是单位元 每个元都有逆元 这个群的阶数是6 元素0 1 2 3 4 5的次数分别为1 6 3 2 3 6 定理6 2设 下面证明唯一性 从而唯一性得证 例6 8设 定理6 3 定理6 4设 定理6 5G为有限群 则G的运算表中的每一行 每一列 都是G中元素的一个置换 且不同的行 或列 的置换都不相同 定义6 10设 例6 9 例6 10群 定理6 6 子群判定定理1 设H是群 证明 必要性是显然的 定理6 7 子群判定定理2 设H是群 证明 必要性 充分性证明 定理6 8 子群判定定理3 设H是群 证明 必要性是显然的 例6 11设 定义6 11设 6 2节陪集与拉格朗日定理 例6 12设 解 H的右陪集为 定理6 9设H是群 定理6 10设 定理6 11设 证明 略 推论6 1 定理6 12设 定理6 13设 定义6 12群 定理6 14 拉格朗日定理 设 即子群的阶数一定是群的阶数的因子 根据定理6 11的推论有 推论6 2设 推论6 3设 根据定理6 11的推论有 定义6 13设 任何群G都有正规子群 因为G的两个平凡子群 定理6 15设 证明 略 例6 13设 例6 14设 定理6 16设 定义6 14设 6 3群的同态与同构 例6 13设 定义6 15设 定理6 17设 证明 略 定义6 16设 定理6 18 群同态基本定理 设 定义6 17设 6 4循环群与置换群 定理6 19设 例6 16 例6 17设 定义6 18设 例6 18设 定义6 19设 例6 194元置换 定义6 20设 定理6 20 定义6 21 例6 20如图进行旋转 也可以围绕它的对称轴进行翻转 但经过旋转或翻转后仍要与原来的方格重合 方格中的数字可以改变 如果把每种旋转或翻转看作是作用在 定义6 22设 6 5环和域 例6 21 1 整数集 定理6 21设 2 3证明略 例6 22 定义6 23设 例6 23 1 整数环 例6 22模6整数环 定义6 24设 定义6 22设 6 5环和域 例6 25设 定义6 25设 6 6格与布尔代数 例6 26设n是正整数 例6 27 1