离散数学 第五章 代数结构

1、离散数学课件 第五章 代数结构第1页，共52页，2022年，5月20日，11点8分，星期五 由于数学和其他科学的发展，人们需要对若干不是数的事物，用类似普通计算的方法进行相似的计算。如矩阵、向量等。 研究代数系统的学科称为“近世代数”或“抽象代数”。 第2页，共52页，2022年，5月20日，11点8分，星期五本章主要内容集合的概念1集合的表示方法2同态与同构6阿贝尔群与循环群4陪集与拉格朗日定理5集合的概念1集合的表示方法2群与子群3代数系统与性质1半群2第3页，共52页，2022年，5月20日，11点8分，星期五5-1 代数系统的引入定义5-1.1 如果 为An到B的一个函数，则称 为集合

2、A上的n元运算（operater）。如果 BA，则称 该n元运算在A上封闭。第4页，共52页，2022年，5月20日，11点8分，星期五代数系统的定义定义5-1.2 一个非空集合A连同若干个定义在该集合上的运算 f1,f2,fk 所组成的系统称为一个代数系统（代数结构），记为。代数结构由以下三个部分组成：非空集合S，称为代数结构的载体。载体S上的若干运算。一组刻划载体上各运算所满足性质的公理。代数系统常用一个多元序组来表示。第5页，共52页，2022年，5月20日，11点8分，星期五代数系统举例(1) R上的“+”、“”运算，构成一个代数系统R，+，；(2) (S)上的“”、“”、“”运算，构

3、成代数系统(S),，称集合代数；(3) 含有n个命题变元的命题集合A与A上的“”、“”、“”运算，构成代数系统A，称之为命题代数。第6页，共52页，2022年，5月20日，11点8分，星期五5-2 二元运算的性质定义 可以用 o 、*、 、 等符号表示二元或一元运算,称为算符。定义5-2.1 设*是定义在集合A上的二元运算，如果对于任意的x，yA，都有x*yA，则称二元运算*在A上是封闭的。第7页，共52页，2022年，5月20日，11点8分，星期五二元运算的主要算律定义 设o为S上的二元运算,(1)如果对于任意的x,yS,有xoy=yox,则称运算o在S上满足交换律。(2)如果对于任意的x,

4、y,zS 有(xoy)oz=xo(yoz),则称运算o在S上满足结合律。(3)如果对于任意的xS有xox=x,则称o运算在S上满足幂等律（等幂律）。第8页，共52页，2022年，5月20日，11点8分，星期五二元运算的主要算律（续）定义 设o和*为S上两个不同的二元运算,(1)如果对于任意的x,y,zS有(x*y)oz=(xoz)*(yoz)和zo(x*y)=(zox)*(zoy),则称o运算对*运算满足分配律。(2)如果o和*都可交换,并且对于任意的x,yS有xo(x*y)=x和x*(xoy)=x,则称o和*运算满足吸收律。第9页，共52页，2022年，5月20日，11点8分，星期五特殊元素

5、1：幺元（单位元）定义5-2.7 设是二元代数系统，（1）若存在elA，使得对任意aA，都有 el a = a，则称el是A中关于运算“”的一个左幺元（左单位元）（2）若存在erA，使得对任意aA，都有 a er = a，称er是A中关于运算“”的一个右幺元（右单位元）（3）若存在eA，对任意aA，都有 a e = e a = a，则称e是A中关于运算“”的一个幺元（单位元）第10页，共52页，2022年，5月20日，11点8分，星期五幺元的性质定理5-2.1 设*是定义在集合A上的一个二元运算，且在A中有关于运算的左幺元el和右幺元er，则el= er= e，且A中的幺元是唯一的。证明：（先

6、证左幺元el=右幺元er=e） el= el er = er= e （再证幺元e是唯一的） 设还有一个幺元e A,则 e = e e = e第11页，共52页，2022年，5月20日，11点8分，星期五特殊元素2：零元定义5-2.8 设是一个二元代数系统，（1）若存在lA，使得对任意aA，都有l a = l，则称l是A中关于运算“”的一个左零元；（2）若存在rA，使得对任意aA，都有a r = r，则称r是A中关于运算“”的一个右零元。 （3）若存在A，使得对任意aA，都有a = a =，则称是A中关于运算“”的一个零元；第12页，共52页，2022年，5月20日，11点8分，星期五零元的性质

7、定理5-2.2 设*是定义在集合A上的一个二元运算，且在A中有关于运算的左零元l和右零元r，则l = r= ，且A中的零元是唯一的。证明：（先证左零元l=右零元r= ） l= l r = r= （再证零元是唯一的） 设还有一个零元 A,则 = = 第13页，共52页，2022年，5月20日，11点8分，星期五幺元、零元举例例：代数A=a，b，c， 。 用下表定义：。abcaabbbabccaba则 b是左么元，无右么元； a是右零元，b是右零元；无左零元;运算：既不满足结合律，也不满足交换律。第14页，共52页，2022年，5月20日，11点8分，星期五幺元、零元举例（续）例:求出下列集合的幺

8、元，零元。 （1）I， I为整数集 则幺元为1，零元为0 （2）（A）, 对运算，是幺元， A是零元， 对运算，A是幺元 ，是零元。 （3）N，+ 有幺元0，无零元。第15页，共52页，2022年，5月20日，11点8分，星期五幺元、零元性质定理5-2.3 如果代数结构有关于 运算的零元 和幺元e ，且集合A中元素个数大于1，则e 。 证明：用反证法： 设幺元e =零元 ，则对于任意xA ，必有 x = e x = x = = e 于是，推出A中所有元素都是相同的，矛盾。 第16页，共52页，2022年，5月20日，11点8分，星期五特殊元素3：逆元定义5-2.9 设是二元代数系统，e是幺元，

9、aA，若存在一个元素bA，（1）使得： b a = e， 则称b是a的一个左逆元，记为al1；（2）使得： a b = e， 则称b是a的一个右逆元，记为ar1。 （3）使得： a b = b a = e， 则称a可逆，并称b是a的一个逆元，记为a1；第17页，共52页，2022年，5月20日，11点8分，星期五逆元的性质注： 一般地，一个元素的左逆元不一定等于它的右逆元。一个元素左、右逆元不一定同时存在。甚至一个元素的左（右）逆元不一定是唯一的。定理 设*为S上可结合的二元运算,e为该运算的单位元,对于xS如果存在左逆元yl和右逆元yr,则有yl = yr= y，且y是x的唯一的逆元。 第1

10、8页，共52页，2022年，5月20日，11点8分，星期五证明： 因为 yl*x = e ， x*yr = e， 故yl = yl*e = yl*(x*yr) = (yl*x)*yr = e*yr = yr令yl = yr = y,则y是x的逆元。设yS也是x的逆元,则y= y *e = y *(x*y) = (y*x)*y = e*y = y所以y是x唯一的逆元。第19页，共52页，2022年，5月20日，11点8分，星期五通过运算表观察二元运算的性质1）封闭性：表中的每个元素都属于A。2）可交换性：运算表关于主对角线是对称的。3）等幂性：运算表的主对角线上的每一元素与它所在行（列）的表头元

11、素相同。4）A中关于运算具有零元：该元素所对应的行和列中的元素都与该元素相同。5）A中关于运算具有幺元：该元素所对应的行和列依次与运算表的首行和首列相一致。6）A中关于运算具有幺元，a和b互逆：位于a行b列的元素以及b行a列的元素都是幺元。第20页，共52页，2022年，5月20日，11点8分，星期五例：P182 例题9，10，11，12第21页，共52页，2022年，5月20日，11点8分，星期五例：设X=e,a,b,c,d，*是X上的二元运算，*的运算表如下。从本例还可以看到a的逆元也是c, d。运算*满足可交换性，但不满足等幂性。*eabcdeeabcdaaaaeebbaaeecceec

12、cddeecc从表中可知， 是代数系统，e是关于*的幺元。X中无零元。表中 b*c=c*b=e；b*d=d*b=e，故c和d均为b的逆元，即b的逆元不唯一。原因在于运算*不满足结合律。第22页，共52页，2022年，5月20日，11点8分，星期五练习：指出下面运算的性质，并求出幺元,零元，可逆元素的逆元。1、在Q集合上， x,y Q，x*y=x+y-xy2、在I+集合上, x,y I+ ，x*y=lcm(x,y)1、满足交换律、结合律，不满足幂等律，幺元为0，零元为1，x的逆元x-1=x/(x-1) (x1)2、满足交换律、结合律、幂等律，幺元为1，无零元，只有1有逆元，其逆元为1。第23页，

13、共52页，2022年，5月20日，11点8分，星期五5-3 半群定义5-3.1 如果集合S上的二元运算是封闭的，则称代数系统为广群。定义5-3.2 如果集合S上的二元运算 是封闭的并且满足结合律，则称代数结构为半群。例：P186例题1，例题2第24页，共52页，2022年，5月20日，11点8分，星期五子半群定理5-3.1 设为一半群, BS且在B上封闭，那么也是一个半群，称为的子半群。例：乘法运算在某些集合上构成的子半群。第25页，共52页，2022年，5月20日，11点8分，星期五含幺半群（独异点）定义5-3.3 设代数结构为半群，若含有关于 运算的幺元,则称它为独异点，或含幺半群，有时也

14、记为。第26页，共52页，2022年，5月20日，11点8分，星期五独异点的性质运算表中任两行两列不相同定理5-3.3 设是一个独异点,则在关于运算的运算表中任何两行或两列都是不相同的。例:设I是整数集合，m是任意正整数， Zm是由模m的同余类组成的同余类集，在Zm上定义两个二元运算+m和m分别如下： 对于任意的i，jZm，有 i +mj=(i+j)(mod m) imj=(ij)(mod m) 试证明在这两个二元运算的运算表中任何两行或两列都是不相同的。第27页，共52页，2022年，5月20日，11点8分，星期五证明思路：1、证明运算的封闭性； Zm 0, 1, 2, , m1, 任意x,

15、yZm, 显然x +myZm, x myZm, 所以+m、m运算封闭性成立。2、证明运算满足结合律； 任意x,y,z Zm, 有 (xmy)mz (xy+z)(mod m)xm(ymz)所以+m满足结合律，同理可证m满足结合律。3、显然，0、1分别为+m和m的幺元。第28页，共52页，2022年，5月20日，11点8分，星期五 综上所述， 和 都是独异点。由定理5-3.3可知，这两个运算的运算表中任两行或两列都不相等。第29页，共52页，2022年，5月20日，11点8分，星期五独异点的性质定理5-3.4 设是一个独异点,如果对于任意a,bS ，且a,b均有逆元，则 a) (a-1)-1=a

16、b) ab 有逆元，且(ab)-1 =b-1 a-1 。证明: a)因a-1和a为互为逆元，直接得到结论。 b)必须证明两种情况： (ab)(b-1a-1) = e 和 (b-1a-1)(ab) = e 利用结合律容易得出。第30页，共52页，2022年，5月20日，11点8分，星期五子独异点定义5-3.3 设代数结构为半群，若BS且在B上封闭， B含有关于 运算的幺元,那么称为子独异点，或子幺半群。第31页，共52页，2022年，5月20日，11点8分，星期五独异点举例 设是一个非空有限集合，称为字母表，由中有限个字母组成的有序集合（即字符串）称为上的一个字，串中的字母个数m称为字长，m=0

17、时，称为空字，即为单位元，记为e。表示上的字的集合，上的连接运算定义为，=，则是一个代数系统，而且是一个独异点, 是在计算机科学中自动机理论及形式语言中最基本的结构。的任一子集就称为语言。 第32页，共52页，2022年，5月20日，11点8分，星期五5-4 群与子群定义5-4.1 称代数结构为群(groups),如果 （1） 中运算是封闭的； （2） 中运算是可结合的； （3） 中有幺元e； （4） 中每一元素x都有逆元x-1。第33页，共52页，2022年，5月20日，11点8分，星期五群举例例题1 R=0,60,120,180,240,300,*是R上的二元运算，a*b表示先旋转a再旋转

18、b的角度，并规定旋转360等于原来的状态。运算表如表5-4.1所示。验证代数结构为群。解题思路：需证明：（1）运算*封闭；（2）运算*是可结合的；（3）有幺元0;（4）每一元素x都有逆元x-1。第34页，共52页，2022年，5月20日，11点8分，星期五典型的群1、 2、 3、,其中Z6 =0，1，2，3，4，5，单位元是0；1、5互为逆元，2、4互为逆元，3的逆元为3，0的逆元为0。注：不是群，其不存在幺元，且每个元素也不存在逆元。 而存在幺元，除0以外，均不存在逆元，故其只是半群。第35页，共52页，2022年，5月20日，11点8分，星期五代数结构总图封闭广群半群独异点群结合含幺可逆

19、广群半群独异点群第36页，共52页，2022年，5月20日，11点8分，星期五有限群与无限群定义5-4.2 设 为一群。若G为无限集，则称为无限群；否则，称 为有限群，此时G的元素个数称为G的阶,记为|G|。第37页，共52页，2022年，5月20日，11点8分，星期五有限群举例第38页，共52页，2022年，5月20日，11点8分，星期五Klein四元群*eabceeabcaaecbbbceaccbaeKlein四元群: e为G中的单位元； 运算是可交换的； G中任何元素的逆元就是它自己； 在a,b,c三个元素中,任何两个元素运算的结果都等于另一个元素。第39页，共52页，2022年，5月2

20、0日，11点8分，星期五群的性质1阶数大于1的群中无零元定理5-4.1 设为群，那么当G e时, G无零元。证明: 设|G|1 且群有零元。那么群中任何元素x G，都有 x = x = e，所以，零元就不存在逆元，与是群的假设矛盾。第40页，共52页，2022年，5月20日，11点8分，星期五群的性质2群方程存在唯一解定理5-4.2 设为群，对于a,bG，必存在xG，使得关于x的方程axb有唯一解。证明: 1）先证解存在性； 设a的逆元a-1，令x = a-1 b （构造一个解） ax a(a-1 b)（a a-1） b e b b 2）再证解唯一性; 若另有解x1满足 ax1 b ，则 x1

21、 （ a-1 a ）* x1 a-1 （ a * x1 ） a-1 b x第41页，共52页，2022年，5月20日，11点8分，星期五群的性质3群满足消去律定理5-4.3 设为群，那么，对任意a,x,yG 如果 ax = ay，则 x = y ；（左乘a-1可证） 如果 xa = ya，则 x = y 。（右乘a-1可证） 第42页，共52页，2022年，5月20日，11点8分，星期五群的性质4幺元是群中唯一等幂元定义5-4.4 设为群，如果存在aG，有a a= a ，则称a为等幂元。 定理5-4.5 在群中，除幺元e之外，不可能有任何别的等幂元。证明: 因为e e = e ，所以e是等幂元

22、。 现设 aG， ae 且 a a= a 则有a = ea =(a-1a)a= a-1(aa)= a-1a= e 与假设 ae 矛盾。第43页，共52页，2022年，5月20日，11点8分，星期五子群及子群的性质定义5-4.5 设为群。如果SG，且为一群，则称为的子群；若S真包含于G，则为真子群。定理5-4.6 设为群，为G的子群，那么， 中的幺元e必定也是中的幺元。证明: 设中的幺元为e1 ，对于任意一个元素 xSG, 必有 e1 x = e x ， 因为群满足消去律，所以 e1 = e。第44页，共52页，2022年，5月20日，11点8分，星期五子群举例是群，H1=0,2,4,H2=0,

23、1,5,H3=0,3,问：,是的子群吗？解： 是的子群； 不是的子群； （因为运算不封闭） 是的子群。第45页，共52页，2022年，5月20日，11点8分，星期五平凡子群定义5-4.6 对任何群G都存在子群。G和e都是G的子群,称为G的平凡子群。 第46页，共52页，2022年，5月20日，11点8分，星期五子群的判定定理定理5-4.7 设为群，B为G的非空子集，如果 B是一个有限集,那么,只要运算 在B上封闭（即任意a,bB有a*bB), 必定是 的子群。定理5-4.8 设为群,S为G的非空子集,如果对于任意元素a,bS有ab-1S,那么, 必定是 的子群。第47页，共52页，2022年，5月20日，11点8分，星期五典型子群：生成子群定义 设G为群,aG,令 H=ak|kZ，即a的所有的幂构成的集合,则H是G的子群,称为由a生成的子群,记作。例1：整数加群,由2生成的子群是