第8章 代数结构,本章学习目标,在计算机科学里，很多的知识和代数结构的理论有关系，比如：加法器、纠正码、形式语言和推理机等等，因此，学好该部分内容，为学习其他计算机课程打下了基础。通过本章学习，读者应该掌握以下内容： （1） 二元运算的相关概念和性质 （2） 半群和独异点的概念及其判定 （3） 群和子群的概念及其性质 （4） 阿贝尔群和循环群的概念和性质 （5）置换群和陪集的概念相关定理 （6）同态与同构的概念及其判定,第8章 代数结构,8.1 二元运算及其性质 8.2 代数系统 8.3 半群和独异点 8.4 群与子群 8.5 阿贝尔群和循环群 8.6 置换群与伯恩赛德定理 8.7 陪集和拉格朗日定理 8.8 同态与同构,第8章 代数结构,8.1 二元运算及其性质,定义8.1 对于集合A，一个从An到B的映射，称为集合A上的一 个n元运算。如果BA，则称该n元运算是封闭的。,定义8.2 设*是定义在集合A上的二元运算，如果对于任意的 x，yA，都有x*yA，则称二元运算*在A上是封闭的。,定义8.3 设*是定义在集合A上的二元运算，如果对于任意的x， yA，都有x*y=y*x,则称二元运算*在A上是可交换的。,第8章 代数结构,8.1 二元运算及其性质,定义8.4 设*是定义在集合A上的二元运算，如果对于任意的 x，y，zA，都有（x*y）*z=x*（y*z），则称该二元运算*是 可结合的。,定义8.5 设 *、是定义在集合A上的两个二元运算，如果 对于任意的a，b，cA，都有 a*（bc）=（a*b）（a*c） （bc）*a=（b*a）（c*a） 则称运算 * 对于运算是可分配的。,第8章 代数结构,8.1 二元运算及其性质,定义8.6 设*，#是定义在集合A上的两个可交换二元运算，如 果对于任意的a，bA，都有 a*（a#b）=a a#（a*b）=a 则称运算*和运算#满足吸收律。,第8章 代数结构,8.1 二元运算及其性质,定义8.7 设 * 是定义在集合A上的一个二元运算，如果有一个 元素elA，对于任意的元素xA，都有el*x=x，则称el为A中 关于运算 * 的左么元；如果有一个元素erA，对于任意的元 素xA都有x*er=x，则称er为A中关于运算 * 的右么元；如果A 中的某一个元素e，它既是左么元又是右么元，则称e为A中关 于运算*的么元。显然，对于任意元素xA，有el*x=x*er=x。,第8章 代数结构,8.1 二元运算及其性质,定理8.1 设*是定义在集合A上的一个二元运算，且在A中有 关于运算*的左么元el和右么元er，则el=er=e，且A中的么元是 唯一的。,定义8.8 设 * 是定义在集合A上的一个二元运算，如果有一个 元素lA，对于任意的元素xA都有l*x=l，则称l为A 中关于运算 * 的左零元；如果有一个元素rA,对于任意的元 素xA，都有x*r=r,则称r为A中关于运算 * 的右零元；如 果A中的一个元素，它既是左零元又是右零元，则称为A中 关于运算 * 的零元。显然，对于任一元素aA，有 *a=a*=。,第8章 代数结构,8.1 二元运算及其性质,定理8.2 设 * 是定义在集合A上的一个二元运算，且在A中 存在关于运算 * 的左零元和右零元。那么，左右零元相等， 且A中的零元是唯一的。,定理8.3 设是一个代数系统，且集合A中元素的个数大 于1。如果该代数系统中存在么元和零元。则它们必然相等。,第8章 代数结构,8.1 二元运算及其性质,定义8.9 设代数系统，* 是定义在集合A上的一个二元 运算，且e是A中关于运算 * 的么元。如果对于A中的任一元素 a，存在着A中的某个元素b，使得b*a=e，那么b为a的左逆元； 同理，如果a*b=e成立，那么称b为a的右逆元；如果一个元素b ，它既是a的左逆元又是a的右逆元，那么就称b是a的一个逆元。,第8章 代数结构,8.1 二元运算及其性质,例8.10 设Q是有理数集合，作笛卡尔积S=QQ，*是S上的二 元运算。对于*=，求 * 运算的幺元和 逆元。 解 根据上面的运算规则 *=， 可以知道，运算 * 是由普通乘法和普通加法分别构成序偶的两 个元素。 对于任意元素， *=,第8章 代数结构,8.1 二元运算及其性质,和 *= 因此，元素为该运算的幺元。 对于任意元素，当x0时 *= *= 故，当x0时，为元素的逆元，当x=0时，任 何元素和0相乘都等于0，因此，没有逆元。,第8章 代数结构,8.2 代数系统,定义8.10 设有一个非空集合A，有若干个定义在该集合上的k 个运算f1，f2， ，fk，如果这k个运算都是封闭的，那么有集 合A连同这些运算所组成的系统就称为一个代数系统，记作。 例8.12 正整数集合I+以及在该集合上的普通加法运算 + 组成一 个代数系统。,第8章 代数结构,8.2 代数系统,定义8.11 设有一个非空集合A，连同若干个定义在该集合上的 运算f1，f2， ，fk，所组成的系统就称为一个代数系统，记作 。,定义8.12 设是一个代数系统，若定义在 该集合上的运算f1，f2，fk都满足封闭性，那么称为广群。,第8章 代数结构,8.3 半群和独异点,定义8.13 一个代数系统，其中P是非空集合，*是P上 的一个二元运算。如果满足： （1）运算 * 是封闭的。 （2）运算 * 是可结合的，即对任意的a，b，cP，满足 （a*b）*c=a*（b*c） 则称代数系统为半群。,第8章 代数结构,8.3 半群和独异点,例8.15 对于给定某集合A，在该集合上定义运算为： xy=max（x，y），验证是否构成半群。 解 对于任意的x，y，zA， （xy）z=max（max（x，y），z） x（yz）=max（x，max（y，z） 由于两个式子最后的结果都是x，y，z中的最大数，因此， （xy）z=x（yz） 所以，满足封闭性和可结合性。 故，是半群。,第8章 代数结构,8.3 半群和独异点,定理8.5 设是一个半群，B是P的子集，且 * 在B上是封 闭的，那么也是一个半群。通常称是半群的子半群。,定义8.14 设是半群，e是幺元，如果eP，则称是独异点。,定理8.6 设是一个独异点，则在关于运算*的算表中 任何两行或两列都是不相同的。,第8章 代数结构,8.4 群与子群 8.4.1 群,定义8.15 设是一个代数系统，其中G是非空集合，*是 G上一个二元运算，如果满足下面的条件： （1）运算 * 是封闭的。 （2）运算是可结合的。 （3）存在么元e。 （4）对于每一个元素xG，存在着它的逆元x-1。 则称是一个群。,第8章 代数结构,8.4 群与子群 8.4.1 群,例8.17 对于来说，Z是全体整数构成的集合，+是普通 加法，我们知道，+对于Z来说是封闭的，可结合的，0Z是 幺元，且对任意元素xZ，都有-xZ，使得x+(-x)=0，因此 ，满足上面所有的条件，所以，是一个群。 同理，也是群。 但是就不是群。因为1是的幺元，但是对于0R 就没有逆元。,第8章 代数结构,8.4 群与子群 8.4.2 群的性质,性质8.1 群中不可能有零元。 性质8.2 （等幂性）群中不存在除了幺元以外的等幂元。 性质8.3 （逆元唯一性）设是一个群，对于a，bG， 必存在唯一的xG，使得a*x=b。 性质8.4 （消去性）设是一个群，对于任意的a，b， cG，如果有a*b=a*c或者b*a=c*a，则必有b=c。 性质8.5 （互异性）群的运算表中没有任何两行(或两列)是完 全相同的。,第8章 代数结构,8.4 群与子群 8.4.3 子群,定义8.17 设是一个群，S是G的非空子集，如果也构成群，则称是的一个子群。,定理8.8 群中的幺元是它每个子群的幺元。,定义8.18 设是一个群，是的子群，如果 S=e，或者S=G，则称为的平凡子群。,第8章 代数结构,8.4 群与子群 8.4.3 子群,例8.19 设群，对任一个xG，另P=m|m*x=x*m， mG，试证：是的子群。 证明：本题可分两步证明，第一步证明P是G的子集，第二步证 明是群。 对于任意的元素mP一定有mG，因此P是G的子集； 由于P是G的子群，因此，在上满足封闭性和可结合性； 因为eG，e*x=x*e，因此eP，有幺元存在； 对于xG，存在x-1，使得x*x-1=x-1*x，可得，x-1P 综上所述，根据群的定义，可知是群，且是的子群。,第8章 代数结构,8.5 阿贝尔群和循环群 8.5.2 循环群,定义8.19 设为群，若在G中存在一个元素x，使得G中的 任意元素都由x的幂组成，则称该群为循环群，元素a称为循环群 G的生成元。,定理8.12 任何一个循环群必定是阿贝尔群。,定义8.20 设是一个群，e是该群的幺元，元素aG，若 存在整数k，使得ak=e 成立的最小正整数，称为元素a的阶（或 周期）；若不存在整数k，使得ak=e 成立，则称元素a的周期为。,第8章 代数结构,8.6 置换群与伯恩赛德定理 8.6.1 置换群,定义8.21 有限非空集合S到它自己的一个双射函数f：SS叫 做S的一个置换。当|S|=n，就称f是一个n元置换。,定理8.21 设S是非空有限集，Sn是所有S的置换的集合，*是置换 的左复合运算。则是一个群。通常称它为集合S的对称 群。,第8章 代数结构,8.6 置换群与伯恩赛德定理 8.6.1 置换群,定义8.22 对称群的子群叫做S的置换群。,定义8.23 设是集合S的置换，若存在元素1，2， rS，使得(a1)=a2，(a2)=a3，(ar)=(a1)，且S的其 他元素在置换下的像与原像相等，则称置换是一个轮换。记 为=(a1a2a3ar)。,第8章 代数结构,8.6 置换群与伯恩赛德定理 8.6.1 置换群,定义8.24 设=(a1a2a3ar)，=(blb2bs)是集合S的两个轮 换。如果a1，a2，a3，arbl，b2，bs=，则称和 是不相杂的。,定理8.22 集合S的两个不相杂轮换的复合运算是可交换的。,定理8.23 集合S上的置换可以惟一地分解成若干不相杂轮换 的复合。,第8章 代数结构,8.6 置换群与伯恩赛德定理 8.6.2 伯恩赛德定理(Burnside),定理8.24 设S是非空集合是S上的对称群，又设 是S的一个置换群，构造一个S上的二元关系R=|a，bS ，(存在)(G并且(a)=b)，则由该式子定义的二元关系是 等价关系。,定义8.25 设有集合S，对任意元素aS，若在S的一个置换下 a并不改变，即（a）=a，则元素a叫做置换下的一个不变元。,第8章 代数结构,8.7 陪集和拉格朗日定理 8.7.1 陪集,定义8.26 设是一个群，A、BP(G)（即：A，B是G的子 集）且A，B，记AB=a*b|aA，bB和A-1=a-1|aA ，分别称为A，B的积和A的逆。,定义8.27 设是群的一个子群，aG，则集合 aP称为由a所确定的集合P在G中的左陪集，简称P关于a的左陪 集，记为aP。,第8章 代数结构,8.7 陪集和拉格朗日定理 8.7.1 陪集,例8.25 根据前边的讨论，我们知道是一个群，是 的子群，其中Z是由整数构成的集合，R是实数构成的集 合，+是普通加法。 对于aR，aZ是Z关于a的左陪集，其含义是 aZ=a+b|bZ 对于该群来说，的陪集aZ是由的每一个数 值在坐标轴上平移a个单位构成的。,第8章 代数