离散数学5-3-4.ppt

主要内容代数系统的基本概念1半群与含幺半群（独异点）2群（阿贝尔群与循环群）3子群与陪集4同态与同构5环与域61定义1：是一个代数系统，S为非空集合，*是定义在S上 的二元运算：–*是封闭的代数系统称为广群；–*可结合的广群称为半群；–含有幺元的半群，称为独异点（含幺半群）；–* 可交换的（含幺）半群，称为交换（含幺）半群 例： 是代数系统，但不是半群 因为-在R上封闭，但不可结合； 是半群，而且含有幺元1 所以也是独异点，是可交换的独异点2定理1：是半群，BS，且*在B上封闭，则是 半群通常称是的子半群证明：要证明是半群，只要证*在B上封闭、可结合 ∵是半群，∴*在S上可结合，而 BS ∴a,b,c B，有 a*(b*c)=(a*b)*c， 即*在B上可结合 又∵已知*在B上封闭 ∴是半群 例： 是半群，∵区间 (0,1)  R，且•在(0,1)上封闭，∴是的子半群3定理2：是半群，若S是有限集,则必有aS，使a*a=a证明：对 bS ∵是半群，*在S上封闭，∴b*b  S记 b2=b*b， 则 b2*b=(b*b)*b=b*(b*b)=b*b2记 b3=b2*b=b*b2 …… 记 bn=bn-1*b=b*bn-1 ……∵S是有限集，∴根据鸽巢原理，存在 j>i，使得bi=bj记 p=j-i (则 p≥1)，则 j=p+i∴bi = bj = bp+i = bp * bi ，∴ bi * b = bp * bi * b∴bi+1 = bp * bi+1 …… br = bp * br (r ≥i )∵p ≥1， ∴总可以找到 k ≥1 使得kp ≥i∴bkp = bp * bkp = bp * (bp * bkp) = b2p * bkp = … = bkp * bkp∵ *在S上封闭， ∴bkp S令 a = bkp，则 a * a = a4定理3：是独异点，则在关于*的运算表中，任何两 行或两列都是不同的。

证明：令e是的幺元，则a，bS，且a ≠b， ∵e * a = a ≠ b = e * b ，∴任意两列都不同 ∵a * e = a ≠ b = b * e ，∴任意两行都不同* …… e …… a …… b …...e …… e …… a …… b …...a …… a …… …… …...b …… b …… …… …...5定理4：是独异点， a，bS，且都有逆元，则(1) (a -1) -1=a ；(2) a * b有逆元，且 (a * b) -1 = b -1 * a -1证明：令e是的幺元， (1) ∵ a-1 * a = e = a * a-1 ，∴a -1与 a 互为逆元， ∴ (a -1) -1=a (2) ∵(a * b) * (b -1 * a -1) = a *( b * b-1) * a-1 = a * e * a-1 = a * a-1 = e (b -1 * a -1) * (a * b) = b -1 * (a -1 * a) * b = b * e * b-1 = b * b-1 = e ∴ (a * b) -1 = b -1 * a -16例1：是半群， 其中 a * a = b，求证：(1) a * b = b * a ；(2) b * b = b 。

证明： (1) a * b = a * (a * a) = (a * a) * a = b * a (2) b * b = b * (a * a) = (b * a) * a ∵ 是半群，∴* 在{a,b}上封闭， ∴ b * a = a 或者 b * a = b 若 b * a = a ，则 b * b = a * a = b 若 b * a = b，则 b * b = b * a = b7作业•P190 （5）8主要内容代数系统的基本概念1半群与含幺半群（独异点）2群（阿贝尔群与循环群）3子群与陪集4同态与同构5环与域69定义1：每个元素都有逆元的独异点，称为群定义2：若群还满足交换律，则称为交换群（阿贝尔群）定义3：是群，若G是有限集，称是有限群； G中元素的个数称为该有限群的阶数，记为 | G |； 若G无限，则称为无限群定义4：是群，a是G中任意元素，nN，定义元素a的 幂为：a0 = e，a1 = a，……， an+1 = an * a， a-n = ( a-1) n (其中a-1是a的逆元)显然，a m * a k = a m + k ，( a m ) k = a m k（m,k  I）1. 群的概念10定义5：是群，a是G中任意元素，若存在nZ+， 使an = e，则称元素 a 的阶是有限的，最小的正整数n称 为元素a的阶；若不存在这样的正整数n，则称元素a具有 无限阶。

解：e1 = e，∴e的阶是1 a2 = a * a = b ， a3 = a2 * a = b * a = e ∴a的阶是3 同理，b的阶也是3 a3k = e* e a b e a bea babb ee a例：11例1：判断，，，， 是否是群？ 解： Ø，幺元是1，只有幺元有逆元，其它元素没逆元 ， ∴不是群； Ø，幺元是0，x+(-x)=0，每个元素都有逆元， ∴是群 Ø和不是群，因为无逆元； Ø是群， ∵Ø  A=A=A  Ø ∴Ø是幺元 AP(S)，有A  A= Ø ∴A-1=A， 每个元素都有逆元12例2：集合Zm是模m的同余类组成的同余类集，即 Zm ={ [0], [1], [2], …, [m-1] }，[i]Zm，[j]Zm，定义运 算： [i]+m[j]=[(i+j) mod m]，[i]×m[j]=[(i×j) mod m]， 判断当m=4时代数系统,是否为群？证明：m=4时，运算表：封闭、可结合、 有幺元[0]、 每个元素都有逆元 [0]-1=[0] x≠0时，[x]-1=[4-x] ∴是群，阶数是4+4 [0] [1] [2] [3][0] [0] [1] [2] [3] [1] [1] [2] [3] [0][2] [2] [3] [0] [1] [3] [3] [0] [1] [2]13小结：–{群}  {独异点}  {半群}  {广群}  {代数系统}–半群在广群基础上还要求运算可结合；–独异点在半群基础上要求存在幺元；–群在独异点基础上要求每个元素都有逆元。

×4 [0] [1] [2] [3] [0] [0] [0] [0] [0][1] [0] [1] [2] [3][2] [0] [2] [0] [2] [3] [0] [3] [2] [1]封闭、可结合、 有幺元[1]、 但元素[0]、[2]没有逆元 ∴不是群142. 群的性质1) 群中无零元 证明：设是群， 若 | G | = 1，则G的唯一元素是幺元，∴无零元； 若 | G | > 1，设有幺元e、零元，则  ≠ e xG，x *  =  * x =  ≠ e ∴ 无逆元 这与是群相矛盾， ∴中无零元152) 是群， a,bG，必存在唯一的xG，使得 a * x = b证明： aG，设a的逆元为a-1 ∵是群， ∴ *在G上是封闭的， ∴ a-1*bG 令 x = a-1 * b，则a * (a-1 * b) = (a * a-1) * b = e * b = b ∴ 存在x，使得 a * x = b 设另有x1G，使得 a * x1 = b，则有x = a-1 * b = a-1 * (a * x1) = (a-1 * a) * x1= e * x1 = x1 ∴ x = x1 ∴ 使 a * x = b 成立的 x 是唯一的。

说明： 证明存在性时，只要找出一个满足条件的即可； 证明唯一性时，通常设另一个满足条件的，再证两个相等163) 是群， a,b,cG，若 a * b = a * c 或 b * a = c * a ，则 b = c （消去律）证明略（两边同时与a-1进行*运算即可）4) 在群中，只有幺元 e 是等幂元 证明：∵e*e=e， ∴ e是等幂元 设有另一个等幂元a，则 a * a = a ∵ e * a = a = a * a ，由消去律，得 a = e5) 在有限群中，每个元素都具有有限阶，且阶数至 多是 | G |利用鸽巢原理证明）17定义6：S是一个集合，从S到S的一个双射，称为S的一个置换例：设 S={a, b, c, d} f (a) = b,f (b) = c, f ( c ) = d,f (d) = a 是S的一个置换 f (a) = d, f (b) = a, f ( c ) = b, f (d) = c 是S的另一个置换 这两个置换可表示为：a b c db c d ad a b c186) 在群的运算表中的每一行或每一列都是G的元素的一个置换 。

证明： (1) G中任一元素b，在G的每一行中必出现 对x G，由封闭性，得 x-1 * b  G， ∵ x * ( x-1 * b) = ( x * x-1) * b = b ∴对x行，必定在 x-1 * b列上出现元素 b ∴任一元素 b 在每一行中都会出现 (2) G中每个元素在每行中只出现一次（反证法） 设cG，在对应于a的那行中出现两次， 则必有b1G ，b2G ，且b1≠b2，使得 a * b1 = a * b2 = c， 由消去律，得b1=b2，产生矛盾， ∴假设错由(1)(2)可知运算表的每一行都是G的一个置换， 同理，每一列也是G的一个置换19例3：构造一个三阶群 解：设e是幺元，G={e,a,b}， 构造三阶群的运算表如下：构造方法：先写出幺元对应的行和列的运算结果再按置换要求，填写其他运算结果* e a be a bea babb ee a203. 循环群定义7：是群，若存在aG，使得G中任意元素都由 a的 幂组成，则称为循环群；元素a称为它的生成元 例：令A={2i | iI}，则是循环群，2是生成元 例：是 循环群，∵是群，0是幺元，10=0 、11=1、12 = 1+1 = 2、13 = 12+1 = 1+1+1 = 3、……、1n = n、……1-1 = -1、1-2 = (1-1)2 = 1-1+1-1 = (-1)+(-1) = -2、……、1-n = -n、…...∴1是的生成元21同时：∵(-1)0=0 、(-1)1=-1、(-1)2 = (-1)+(-1) = -2、……、 (-1) n = - n、…… (-1)-1 = 1、(-1)-2 = (-1-1)2 = (-1)-1+(-1)-1 = 1+1 = 2、……、 (-1)-n = n、…... ∴ -1也是的生成元可见，一个循环群的生成元可以是不唯一的。

22定理1：任何一个循环群必是交换群证明：设是循环群，a是生成元，则 x,yG，必有m,n  I， 使得 x = am，y = an， x * y = am * an = am+n = an+m = an * am = y * x∴是交换群23定理2：是有限循环群， a为生成元，若 | G | = n， 则 an = e 且G = { 。