《离散数学代数系统》由会员分享，可在线阅读，更多相关《离散数学代数系统（73页珍藏版）》请在金锄头文库上搜索。
1、 6.1 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为
2、任意集合, 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, zAx(yz) = (xy) (xz)(yz)x = (yx) (zx)则说对具有可分配性.(4) 设, 是A上的两个可交换二元运算, 如果对于任意的x,y,zA,都有x(
3、xy) = xx(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中关于的幺元.可以证明：幺
4、元是唯一的.证明：反证,若有两个幺元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上的二元
5、运算,对于xA,如果有x x = x, 则x是A中的幂等元,如幺元和零元.五、代数系统：非空集合S与S上的k 个运算 f1, f2, fk 组成的系统, 称为代数系统, 记作：如, , 6.2 6.2 同态与同构同态与同构同态：V1 = , V2 = 是两个代数系统, 其中fi , i(i=1,2, n)都是二元运算。x, yA, f (xfi y) = f (x) i f (y)(i=1, n)则称f 是V1到V2的一个同态映射, 也说V1与 V2 同态, 记作V1f V2或V1V2. f 如果存在映射 f : AB 满足：如： (只要定义f : R+R, f (ab) = lgab = l
6、ga+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同态的性质：设V1 = V2 = ,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 (
7、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定义如下： abcd abcd bcda cdab dabca b c d+40 1 2 30 1 2 30 1 2 3 1
8、 2 3 0 2 310 3 0 1 2验证： f验证：首先由f 定义知f 既是单射又是满射,从而双射,其次通过研究运算表知： x, yA,f (xy) = f (x)+4f (y)从而f 是从到 的同构. 同态与同构的意义(1) V1 = 与V2 = 同态, 则V1中所具有的运算性质,可以保持在同态象中；(2) 对于满同态,V1的运算在V2中仍保持；(3) 如果V1 V2,则它们的性质完全相同, 可以 看成一个东西不加区别 (代数角度).6.3 6.3 同余关系与商代数同余关系与商代数模n同余关系：Z是整数集, 在Z中定义关系R = | x, yZ x y(modn)其中, x y(modn
9、)的含义是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, 见下列运算表：abcd a
10、adc bacd cdab ddbaa 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关
11、系,即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
12、(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 6.4 群群半群：代数系统V = 中, 是非空集合A上的二元运算, 且在A中是可结合的,即x, y, zA(xy) z = x (yz)一、几个基本概念常见半群：(1) (2) (3) 但 ,不是半群.只要验证运算是否可结合！(4) (5) (6) 含幺半群：V = 是半群且含有幺元, 即存 在元eA, 使得aA, ae =
13、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)所在行,由于
14、A中含有幺元e,我们比较a行,b行中e列的元素a e = ab 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
