离散数学代数系统.ppt

代 数 系 统,第六章,6.1 代数运算及代数系统,二元代数运算：设A是非空集合,如R*=R0上的乘法, 除法运算: f : An A称为A上的n元运算, n为运算阶.,函数 f : AA是集合A上的一元代数运算,简称一元运算; 如集合 R0上的求倒数运算；,函数 f : A2A 称为A 上二元代数运算.,一、代数运算的概念,集合的封闭性：给定集 A,如Z对加、减、乘法封闭, 对除法不封闭.,如果对A上的元素进行某种运算后,运算结果仍在A中, 则称集A对该种运算封闭。,二、常见二元运算：,(1) 设Mn(R)表示所有n阶实矩阵的集合, 则矩阵加法和乘法运算是Mn(R)上的二元运算, 且封闭;,(2) S为任意集合, P(S)为其幂集, 则, ,都是P(S)上的二元运算, 且封闭；,(3) S为集合, S s 是S上的所有函数的集合, 则合成运算 o 是 S s上的二元运算.,三、二元运算的性质：,(1) 设是定义在集A上的二元运算,若对任意的x, yA都有yx=xy, 则说具有可交换性；,(2) 如果对任意的x,y,zA, 都有(xy)z=x(yz), 则说具有可结合性；,(3) 设, 是A上的两个二元运算, 如果对任意的x, y, zA,x(yz) = (xy) (xz),(yz)x = (yx) (zx),则说对具有可分配性.,(4) 设, 是A上的两个可交换二元运算, 如果对于任意的x,y,zA,都有,x(xy) = x,x(xy) = x,则称运算对满足吸收律.,如：N上定义两个二元运算, 如下,xy = max(x, y),xy = min(x, y),则对满足吸收律.,(5) 是A上的一个二元运算,如果x,xx=x,则说是等幂的,(6) 如果() xy = xz 且 x, 是指集A关于运算 的零元，有y = z,() yx = zx 且 x,有y = z,则是满足消去律.,四、集A的特殊元：,(1) 幺元： 是集A上的二元运算, 如果elA且xA,有elx = x, 则el为A中关于的左幺元；,如何定义右幺元 er (自己叙述一遍！),如果A中的一个元素e, 既是左幺元又是右幺元,则e为A中关于的幺元.,可以证明：幺元是唯一的.,证明：反证,若有两个幺元e, e, 则由幺元的定义知e = ee = e矛盾.,(2) 零元：如果有一个元素lA, 使得xA, l x = l , 则l称为左零元；,右零元呢？ (r),零元呢？ ( ),类似于幺元, 可证A中零元 唯一.,(3) 逆元：是A上的一个运算, e是幺元, 如果对于A中元素a, 存在bA, 使得ba = e,则称b为a的左逆元；,右逆元呢？,逆元呢？ (a1),可证：逆元存在则唯一 (要求可结合),证明：设b,c为a的两个不同逆元,则,ba = ab = e ca = ac = e,从而 b=b e=b(ac),=(ba)c=ec=c 矛盾.,(4) 幂等元： 是A上的二元运算,对于xA,如果有x x = x, 则x是A中的幂等元,如幺元和零元.,五、代数系统：非空集合S与S上的k 个运算 f1, f2, fk 组成的系统, 称为代数系统, 记作： ,如, ,6.2 同态与同构,同态：V1 = , V2 = 是两个代数系统, 其中fi , i(i=1,2, n)都是二元运算。,x, yA, f (xfi y) = f (x) i f (y)(i=1, n),如果存在映射 f : AB 满足：,如： (只要定义f : R+R, f (ab) = lgab = lga+lgb = f (a)+f (b),当n =1时，设V1= ，V2= 是两个代数系统。,如果存在 f : AB. 使 x, yA，,f (x y) = f (x) f (y),则称 f 是V1到V2的一个同态映射。,同态象：设V1 = V2 = , 则称 是V1在 f 下的同态象.,f,(1) 如果f : AB是满射,则说f为V1到V2满同态的,(2) 如果f是单射, 则说f 为V1到V2单同态的,(3) 如果f是双射, 则说f为V1与V2同构, 记作,(4) 当V1=V2时, 则说f 是V1的自同态(自同构),例6.1 ,是两个代数系统, f :RR, 且xR,f (x) = 2x, 验证 f 是到的同态,并且是单同态.,验证：任取 x, yR,由于f (x+y) = 2x+y = 2x2y = f (x) f (y),所以f是到的自同态；,其次, 对任取的x, yR,当xy时, 2x 2y, 即 f (x) f (y), f 为单射, 从而f 是单自同态,例6.2 设A = a,b,c,d,B = 0,1,2,3 且 f : AB, f (a) = 0, f (b) = 1, f (c)=2, f (d) = 3,代数系统 , 中运算 ,+4定义如下：,验证： ,f,验证：首先由f 定义知f 既是单射又是满射,从而双射,其次通过研究运算表知：,x, yA,f (xy) = f (x)+4f (y),从而f 是从到 的同构.,同态与同构的意义,(1) V1 = 与V2 = 同态, 则V1中所具有的运算性质,可以保持在同态象中；,(2) 对于满同态,V1的运算在V2中仍保持；,(3) 如果V1 V2,则它们的性质完全相同, 可以看成一个东西不加区别 (代数角度).,6.3 同余关系与商代数,模n同余关系：Z是整数集, 在Z中定义关系,R = | x, yZ x y(modn),其中, x y(modn)的含义是xy可以被n整除.,不难验证: R是Z上的等价关系(自反、对称、传递), 我们称该等价关系为模n同余关系.,由同余关系R可得商集：,Z/R = 0,1, , n1, 记作：Zn.,一、模 n 同余关系的概念,同余关系与剩余类：设代数系统V = , 是集A上的二元运算,(1) R是A上的等价关系；,(2) a1,a2,b1,b2A,(a1Ra2)(b1Rb2) (a1b1)R(a2b2),则称R是A上对运算的同余关系, 或称V上的同余关系。,如果集A上存在关系R满足：,由同余关系将A划分的等价类称为剩余类.,二、一般同余关系的定义,例6.3 设代数系统,A = a,b,c,d, 见下列运算表：,再规定A上的一个关系：,R = , , , ,则可验证： (1) R是等价关系,(2) x, y, u, vA,如果(xRy)(uRv), 则(xu)R(yv),(验证方法：在R中任取2个元素，如, ; , 等加以验证),例6.4 代数系统中,Z是整数集, 是一元运算, 且zZ, zz = z2(modm),m为一自然数.,设R是Z上的模m同余关系,可以证明： R是Z上的同余关系,(2) 对任意的z1, z2Z, 如果z1Rz2,即z1 z2(modm),(1) R显然是等价关系,证明：,往证：z1z1 = z12(modm)与z2z2 = z22(modm) 具有R关系,即z12(modm)Rz22(modm), 这是因为：,z1z2(modm)z1=a1m+ro, z2=a2m+ro,其中0rom1,三、同余关系的判定：与是两个代数系统。,证明：(1) R是等价关系,f：AB是同态映射。,利用f 规定A上的二元关系R：aRb当且仅当 f (a)=f (b)，则R是同余关系。,由同态映射的定义知：,f (xu) = f (x) f (u),f (yv) = f (y) f (v),所以 f (xu) = f (yv), 即(xu)R(yv),(2) x, y, u, vA，如果xRy, uRv，则 (xu)R(yv)。,这是因为：xRy即f (x)=f (y); uRv即f (u)=f (v).,商代数：V = 是一个代数系统, 是二元运算。,A/R = xR | xA,在A/R中规定二元运算：xR, yRA/R,xR yR = xyR,则称为V关于R的商代数, 记作 V/R.,R是V中的同余关系, A/R是A关于R的商集。,四、同余关系的应用,6.4 群,半群：代数系统V = 中, 是非空集合A上的二元运算, 且在A中是可结合的,即x, y, zA,(xy) z = x (yz),一、几个基本概念,常见半群：(1) ,(2) ,(3) ,但 ,不是半群.,只要验证运算是否可结合！,(4) ,(5) ,(6) ,含幺半群：V = 是半群且含有幺元, 即存在元eA, 使得aA, ae = ea = a。,如： ,幺元为n阶单位阵, ,幺元为0, , 幺元为0, , 幺元为0,含幺半群又称独异点.,子半群：是半群, B A, 且运算在B上仍封闭, 则是的子半群.,子独异点：含幺元e的子半群,如： 是 的子独异点,平凡子独异点：V = 是独异点, ,V称为平凡子独异点.,可交换半群：V = 是半群, 且是可交换的.,如, 等,半群中的幂：在含幺元半群V = 中, 规定：,xA ,x0 = e ,x1 = xx0 ,x2 = xx1 ,xn+1 = xxn ,则有 xm+n = xm xn,(xm)n = xmn,独异点的性质：是独异点, 则的运算表中没有任何两行或两列相同.,证明： 任取a,b (ab)所在行,由于A中含有幺元e,我们比较a行,b行中e列的元素,a e = a,b e = b,因为： ab,所以ae be,从而a行与b行不同,同理可证任两列不同.,群：设含幺元半群且对任何元素xG都有逆元x1G (即逆元运算封闭).,如：(1) Q = Q0,“ ”普通乘法,(2) 幺元为1,但 是独异点, 不是群.,有限群： G是有限集的群。,|G|为有限群的阶数,二、群的定义有典型群,交换群：群中, 满足交换律, 又称阿贝尔群.,如：,子 群：设群, H是G的非空子集,如：是的子群.,如果H 关于G中的运算构成群, 则称 为的子群, 记作：HG.,稍后还要专门介绍循环群，置换群，对称群。,子群的判定方法：设为群, H是G的非空子集, 如果对任意的x, yH都有xy1H, 则H是G的子群, 即HG.,三、群的性质：设 是一个群,则,(1) G中幺元唯一,(2) 逆元唯一,(3) 满足消去律, 即 a,b,cG,如果ab = ac, 或者ba = ca, 则有b = c.,(4) G中一定没有零元,(5) 对任意的a,bG,必存在唯一的xG,使 ax = b (或者xa = b),(6) 对任意a, bG,(ab)1 = b1 a1,(a1)1 = a,证明：设有两个幺元e, e,则e = ee = e,证明：设元素x有两个逆元y, z, 即,xy = yx = e,zx = xz = e,从而y = ye = y(xz) = (yx)z,(1) G中幺元唯一,(2) 逆元唯一,= ez = z,证明：如果ab = ac,由(2)知a存在唯一逆元a1,则 a1(ab) = a1(ac),(a1a)b = (a1a)c,所以 eb = ec,b = c,(3) 满足消去律, 即 a,b,cG,如果ab = ac, 或者ba = ca, 则有b = c.,证明：如果|G| = 1,则它的唯一元素必是幺元；,(4) G中一定没有零元,与 中每个元素可逆矛盾.,如果|G| 1,假设有零元, 则对于任何xG,有x = x = e,这说明G中任何元素x不可能成为的逆元。,证明：任取a,bG,由于G对逆元素封闭, 故a有逆元a1, 且a1G,因为a1bG,令x = a1b,则ax = a(a1b),(5) 对任意的a,bG,必存在唯一的xG,使 ax=b (或者xa = b),= (aa1) b = eb = b,证明：先证(ab)1 = b1 a1, 这是因为：,(b1a1)(ab) = b1(a1(ab) = b1(a1a)b),所以(a b)1 = b1 a1,= b1(eb),= b1b = e,(ab)(b1a1) = a(b(b1a1),再证(a1)1 = a 这是因为：,a1 a = e,从而(a1)1 = a,(6) 对任意a,bG,(ab)1 = b1 a1,(a1)1 = a,a a1 = e,=a(bb1)a1)=e,元素a的周期：是群,aG,使an = e成立的最小正整数n称为a的周期(或阶).,如：幺元e的周期为1,中,非零整数的周期是无限的.,周期的性质：设是群,若aG有有限周期r, 则,(1) ak = e 当且仅当k是r的倍数,(2) a1的周期亦为r,(3) r |G|,四、循环群,证明：(充分性) 设k = nr,则ak = anr = (ar)n = en = e,(必要性) 如果ak = e,反设k不是r的倍数,则,(1) ak = e 当且仅当k是r的倍数,= (ar)1 = e1 = e,证明：反证, 如果r |G|,则a,a2,ar均为G中 不同元素与|G| r矛盾.,(2) a1的周期亦为r,(3) r |G|,循环群：在群中,如果存在元素aG,使得,G = ak | k Z,记作 G = (a) a为(G, )的生成元,例如：在N4 = 0, 1, 2, 3中引入运算+4：,x,y N4 ,x +4y = x+y,则得一循环群, 生成元为1.,循环群的性质,(1) 每个循环群必是阿贝尔群 (即可交换群),(2) 有限循环群,若|G| = n,则存在aG,使：G = a, a2, a3, ,an1, an = e,证明(2)：假设存在某个正整数m, mn使am = e,那么,由于是一个循环群, 所以G中的任何元素都能写成ak(kZ), 而且k = mq+r, q是某个整数, 0rm,这就有：ak = amq+r = (am)qar = ear = a r,这就有，ak = a r从而G中每个元素都可以表示成ar(0rm),再证a, a2, an互不相同. 反设ai = a j, 其中1ijn, 则有aji = e,而且1jin, 这与前面证明的矛盾, 所以a, a2, an互不相同.,由于|G| = n,所以an = e, 从而G中元素为,a, a2, a3, an1, an = e,这样,G中最多只有m个不同的元素,与|G| = n 相矛盾,所以 am = e(mn)不可能.,n 元置换：设S = x1, x2,xn, S上的任何双射函数：SS构成S上n个元素的置换,称为n元置换.,记作：,五、置换群与对称群,如：(1) S = 1,2,3,令：SS且(1) = 2, (2) = 3, (3) = 1, 则有一个置换：,(2) 称,为恒等置换,记作Is,注：当| s | = n时, S上有n!个置换,把它们构成的集合记作：Sn,置换的运算,(1) 设S = x1, x2, xn上有置换：,P =,则称,为P的逆置换,记作: P1.,(2) 设 S = x1, x2, xn上有两个置换：,P1 =,则称 P =,为P1与P2的合成,P2 =,显然: Is = Is = , 这说明: Is是中的幺元.,记作：P= P2 P1.,置换群：可以证明Sn关于合成运算和上述逆运算构成一个群, 称之为置换群。,的任何一个子群也称为置换群, 统称为S上的置换群.,解： (1) 先写出所有的置换, 共3! = 6个,例6.5 设S = 1,2,3, 写出S上所有的置换群,(2) 再列出S3 = pe,p1,p2,p4,p5上关于合成运算 的运算表,pe,p1,p2,p3,p4,p5,p1,p2,pe,p5,p3,p4,p2,pe,p1,p5,p3,p4,p3,p4,p5,pe,p1,p2,p4,p5,p3,p2,pe,p1,p5,p3,p4,p1,p2,pe,(3) 最后写S上的置换群 (检验封闭性),都是S上的置换群.,对称群：称为n元对称群.,例6.6 设G为群,xG, 问H = xk | kZ是否为G的子群.,解： 首先HG,其次任取H中的两个元素xm, xl, m, lZ,则 xm (xl)1 = xm (x 1)l,= xml H,注：称H为由x生成的子群, 记作：.,6.5 环 与 域,环：设是具有两个二元运算和的代数系统,(1) 是交换群 (或阿贝尔群 )；,(2) 是半群；,(3) 运算对运算是可分配的；,则称是环.,如果：,一、环的概念,例如：(1) Rx = 实系数多项式关于通常意义下多项式的加法和乘法构成一个环, 当然是环.,(2) 是环,(3) 整数环, 有理数环, 实数环, 复数环,(4) S的子集环,(5) 模n的整数环,其中：Zn = 0,1,n1,x, yZn,x y = x+y(modn),x y = xy(modn),交换环：在环中, 运算是可交换的.,含幺环：在环中, 运算有幺元.,注：为了区别运算的幺元与的幺元, 通常记的幺元为, 记的幺元为e。,所以a, b, cA, a(bc) = (ab) (ac),a (c) = (a) (ac),即 a c = (a) (ac),从而必有a = , 即 对是零元.,证明：由环的意义, 对是可分配的,如果为运算的幺元, 取b = , 则有：,可以证明：的幺元 恰好是的零元.,左(右)零因子：在环中,如果存在a,bA, a,b, 但ab = , 则称a为A的