几个典型的代数系统离散数学

1、几个典型的代数系统离散数学9/3/20221第1页，共61页，2022年，5月20日，9点2分，星期一1 半群与群DEFINITION 1. 设V=是代数系统，为二元运算，如果是可结合的，则称V为半群。如： (1) , , , , 都是半群，其中+表示普通加法。(2) 是半群，其中表示矩阵乘法。9/3/20222第2页，共61页，2022年，5月20日，9点2分，星期一可交换半群：半群V中的二元运算可交换。含幺半群（独异点）：半群V中的二元运算含有幺元。子半群：半群的子代数。子独异点：独异点的子代数。积半群：若V1, V2是半群，则V1V2是积半群。积独异点：若V1, V2是独异点，则V1V2

2、是积独异点。9/3/20223第3页，共61页，2022年，5月20日，9点2分，星期一(1) , , , , 都是可交换半群。(2) 不是可交换半群，因为矩阵乘法不适合交换律。(1)中除了外都是独异点，其中普通加法的幺元是0。(2) 是独异点，矩阵乘法的幺元是n阶单位矩阵E。, 都是的子半群，且 也是的子独异点，但不是的子独异点，因为幺元0Z，但0Z+。9/3/20224第4页，共61页，2022年，5月20日，9点2分，星期一DEFINITION 2. 设V1=, V2=为半群，: S1S2，且x, yS1，有：(x y)= (x) * (y)，则称为半群V1到V2的同态。设V1=, V2

3、=为独异点，: S1S2，且x, yS1，有：(x y)= (x) * (y)， (e1)= e2，则称为独异点V1到V2的同态。9/3/20225第5页，共61页，2022年，5月20日，9点2分，星期一EXAMPLE 1 设半群V1=，独异点V2=，其中 ，为矩阵乘法。令： ，则TS，且T对矩阵乘法是封闭的。 是V1=的子半群。9/3/20226第6页，共61页，2022年，5月20日，9点2分，星期一在中存在自己的幺元 ，因为也构成一个独异点，但它不是V2=的子独异点。V2中的幺元9/3/20227第7页，共61页，2022年，5月20日，9点2分，星期一令有： 是半群V1的自同态，但不

4、是满自同态，且同态象为9/3/20228第8页，共61页，2022年，5月20日，9点2分，星期一对于独异点V2=，还是同一个映射，根据前面的证明，对x, yS都有：(x y)= (x) (y)，但是而 不是独异点V2的幺元， 不是独异点V2的自同态。9/3/20229第9页，共61页，2022年，5月20日，9点2分，星期一DEFINITION 3. 设是代数系统，为二元运算。如果是可结合的，存在幺元eG，并且对G中的任意元素x都有x-1G，则称G为群。如，(1) , , 都是群，而 , 不是群，因为中的元素都没有逆元，而在中只有0有逆元0。(2) 不是群，因为不是所有的实矩阵都有逆矩阵。9

5、/3/202210第10页，共61页，2022年，5月20日，9点2分，星期一EXAMPLE 2 设G=a, b, c, e，为G上的二元运算，由下表给出，不难证明G是一个群。e a b ceabce a b ca e c bb c e ac b a e该运算的特点：e为G中的幺元；是可交换的；G中的任何元素的逆元就是它自己；在a, b, c三个元素中，任何两个元素运算的结果都等于另一个元素。称这个群为Klein四元群。9/3/202211第11页，共61页，2022年，5月20日，9点2分，星期一一些特殊的群：交换群：群G中的二元运算可交换。也叫阿贝尔(Abel)群。无限群：群G中有无限多个

6、元素。有限群：群G中有有限个元素。有限群G中的元素个数叫做G的阶，记作|G|。9/3/202212第12页，共61页，2022年，5月20日，9点2分，星期一如，(1) , , 都是阿贝尔群，Klein四元群也是阿贝尔群。(2) , 都是无限群， 是有限群，其阶是n，Klein四元群也是有限群，其阶是4。9/3/202213第13页，共61页，2022年，5月20日，9点2分，星期一定理1：设G为群，则G中的幂运算满足(1) 对xG，(x-1)-1=x.(2) 对x, yG，(xy)-1=y-1x-1.(3) 对xG，xnxm=xn+m.(4) 对xG，(xn)m=xnm. m, n是整数。9

7、/3/202214第14页，共61页，2022年，5月20日，9点2分，星期一定理2： 设G为群，对a, bG，方程ax=b和ya=b在G中有解，且有唯一解。 易证方程ax=b的唯一解是x=a-1b，而方程ya=b的唯一解是y=ba-1。9/3/202215第15页，共61页，2022年，5月20日，9点2分，星期一如，S=1, 2, 3，在群中有方程1, 2 x=1, 3，由定理2有x=a-1b=1,2-1 1,3=1,2 1,3=2,3。即为原方程的解。 1 2 3 1,2 1,3 2,3 1,2,31231,21,32,31,2,3 1 2 3 1,2 1,3 2,3 1,2,31 1,

8、2 1,3 2 3 1,2,3 2,32 1,2 2,3 1 1,2,3 3 1,33 1,3 2,3 1,2,3 1 2 1,2 1,2 2 1 1,2,3 2,3 1,3 31,3 3 1,2,3 1 2,3 1,2 22,31,2,33 2 1,3 1,2 11,2,32,31,31,2 3 2 1 同理可知，方程y1=2,3 的解是y=1,2,3。abab9/3/202216第16页，共61页，2022年，5月20日，9点2分，星期一定理3：设G为群，则G中适合消去律，即对a, b, cG，有：(1) 若ab=ac，则b=c.(2) 若ba=ca，则b=c.9/3/202217第17页

9、，共61页，2022年，5月20日，9点2分，星期一定理4： 设G为有限群，则G的运算表中的每一行（每一列）都是G中元素的一个置换，且不同的行（或列）的置换都不相同。 这就是说，在G的运算表的每一行里。G的每个元素都出现且仅出现一次，行不同，元素的排列顺序也不同。使用这个定理可以通过运算表很快地判断出哪些代数系统G=不是群。9/3/202218第18页，共61页，2022年，5月20日，9点2分，星期一DEFINITION 4. 设群，H是G的非空子集。如果H关于G中的运算*构成群，则称H为G的子群，记作HG。如，在群中，取2Z=2z|zZ，则2Z关于加法运算构成的子群。同样，0也是的子群。9

10、/3/202219第19页，共61页，2022年，5月20日，9点2分，星期一定理5：设G为群，H是G的非空子集，如果对x, yH，都有xy-1H，则H是G的子群。子群判定定理如，对xG，G为群，令H=xk | kZ，即x的所有次幂的集合。则H是G的子群。xm, xlH，有：xm(xl)-1=xmx-l=xm-lH。称这个子群是由元素x生成的子群，记作。9/3/202220第20页，共61页，2022年，5月20日，9点2分，星期一EXAMPLE 3 群（其中表示模6加法）中由2生成的子群包含2的各次幂，21=2，22=22=4，23=222=0 =0, 2, 4。同理有：=0，=0, 1,

11、2, 3, 4, 5，=0, 3， =0, 2, 4。9/3/202221第21页，共61页，2022年，5月20日，9点2分，星期一又如，设G为群，令C是与G中所有的元素都可交换的元素构成的集合，即C=a | aGxG(ax=xa)，则C是G的子群。 a, bC，要证明ab-1C，只要证明ab-1与G中所有的元素都可交换就行了。 xG，有：(ab-1)x =ab-1x =ab-1(x-1)-1)=a(x-1b)-1=a(bx-1)-1 =a(xb-1)=(ax)b-1=(xa)b-1 =x(ab-1) 。 C是G的子群。称C为群G的中心9/3/202222第22页，共61页，2022年，5月

12、20日，9点2分，星期一DEFINITION 5. 在群G中如果存在aG使得G=ak | kZ，则称G为循环群，记作G=，称a为G的生成元。如，是循环群，其生成元是1或-1，因为任何整数都可以由若干个1或若干个-1相加而得到。 也是循环群，其生成元是1或5，因为0, 1, 5中的每个数都可以由1或5作若干次模6加法而得到。 循环群都是阿贝尔群，但阿贝尔群不一定都是循环群。9/3/202223第23页，共61页，2022年，5月20日，9点2分，星期一循环群生成元的判定方法： 对无限阶循环群G=，G的生成元是a和a-1。 对n阶循环群G=e, a, a2, , an-1，G的生成元是at当且仅当

13、t与n是互质的。 是无限阶循环群，生成元是1和-1，-1是1的加法逆元。 是6阶循环群，1和5都与6互质，所以1和5是生成元。 12阶循环群G=e, a, , a11中，与12互质的数有1, 5, 7, 11，则G的生成元就是a, a5, a7, a11。9/3/202224第24页，共61页，2022年，5月20日，9点2分，星期一循环群G=的子群仍是循环群。若G是无限阶循环群，则G的子群除了e外都是无限阶；N阶循环群G=的子群的阶都是n的正因子。对于n的每个正因子d，G中只有一个d阶子群，就是由an/d生成的子群。9/3/202225第25页，共61页，2022年，5月20日，9点2分，星

14、期一DEFINITION 6. 设S=1, 2, , n，S上的任何双射函数: SS构成了S上n个元素的置换，称为n元置换。如，S=1, 2, 3，令: SS，且有(1)=2, (2)=3, (3)=1, 则将1, 2, 3分别置换成2, 3, 1。此置换常被记为：9/3/202226第26页，共61页，2022年，5月20日，9点2分，星期一一般的n元置换可记为：n个不同元素有n!种排列方法。所以S上有n!个置换。如，1, 2, 3上有3!=6种不同的置换，即9/3/202227第27页，共61页，2022年，5月20日，9点2分，星期一简记法： 设n元置换=(a1a2am), mn，则的映

15、射关系是：(a1)=a2, (a2)=a3, , (am-1)=am, (am)=a1，而其它的元素a都有(a)=a，称为m次轮换。任何n元置换都可表成不交的轮换之积。如，是1, 2, , 6上的置换，且除了3和4这两个保持不变的元素外，其它元素的映射关系为： (1)=6, (6)=1, (2)=5, (5)=2。 =(1 6)(2 5)9/3/202228第28页，共61页，2022年，5月20日，9点2分，星期一又如，也是1, 2, , 6上的置换，且则有=(1 4 3 2 5)。根据这种表法，1, 2, 3上的置换可记为：1=(1), 2=(1 2), 3=(1 3), 4=(2 3),

16、 5=(1 2 3), 6=(1 3 2)9/3/202229第29页，共61页，2022年，5月20日，9点2分，星期一 设S=1, 2, , n，S上的n!个置换构成集合Sn，其中恒等置换IS=(1)Sn，在Sn上规定二元运算，对任意n元置换, Sn，表示与的复合。 证明Sn关于置换的复合构成一个群。证明：(1) 设, Sn，与的复合显然也是S上的n元置换，即 Sn， Sn对运算是封闭的。(2) , , Sn，显然()=()，Sn对运算是可结合的。(3) , Sn，有IS = IS =，则恒等置换IS 是Sn中的幺元，且的逆置换 就是的逆元。 Sn关于置换的复合构成一个群。S上的n元对称群

17、9/3/202230第30页，共61页，2022年，5月20日，9点2分，星期一 n元对称群的任何子代数称为n元置换群。 如：S3=(1), (1 2), (1 3), (2 3), (1 2 3), (1 3 2)就是3元对称群。因为S3关于置换的复合运算不能交换，所以S3不是阿贝尔群。 S3有6个子群，即有6个3元置换群。 见P135。9/3/202231第31页，共61页，2022年，5月20日，9点2分，星期一2 环与域DEFINITION 7. 设是代数系统，R为集合，+, 为二元运算，如果(1) 为阿贝尔群；(2) 为半群；(3) 乘法对加法+适合分配律。则称是环。+可结合、可交换

18、，存在幺元，且任何元素都有逆元。可结合9/3/202232第32页，共61页，2022年，5月20日，9点2分，星期一如：(1) , , 都是环。(2) 是环。(3) 是模n的整数环。其中Zn =0, 1, , n-1，和分别表示模n的加法和乘法，即x, yZn，有：x y =(x+y) mod nx y =(xy) mod n9/3/202233第33页，共61页，2022年，5月20日，9点2分，星期一交换环：在环中，适合交换律。含幺环：在环中，有幺元。此时，通常把+幺元记作0，幺元记作1。可以证明+的幺元恰好是的零元。左（右）零因子：在环中，若a,bR, a0, b0，但ab=0，则a为

19、R中的左零因子。b为R中的右零因子。无零因子环：环R中既不含左零因子，也不含右零因子，即a,bR, ab=0a=0b=0.0为的零元9/3/202234第34页，共61页，2022年，5月20日，9点2分，星期一如：(1) , , , 都是交换环。不是交换环，因为矩阵乘法运算不可交换。(2) 它们都是含幺环。因为1是的幺元，也是的幺元。n阶单位矩阵E是环Mn(R)的乘法幺元。(3) , , 都是无零因子环。而不一定是无零因子环。如中有23=0，但2和3都不是0，所以不是无零因子环，而是无零因子环。9/3/202235第35页，共61页，2022年，5月20日，9点2分，星期一DEFINITIO

20、N 8. 若环是交换、含幺、和无零因子的，则称R为整环。 若环至少含有2个元素且是含幺和无零因子的，并且aR(a0)有a-1R，则称R为除环。 若环既是整环，又是除环，则称R是域。（至少含有2个元素、交换、含幺、无零因子、除0外都有逆元）9/3/202236第36页，共61页，2022年，5月20日，9点2分，星期一如：(1) 是整环但不是域。因为乘法可交换，1是幺元，且不含零因子，所以是整环。但除了1之外，任何整数都没有乘法的逆元，所以不是域。(2) 是域，即实数域。因为xR，x0，有：x-1=1/xR.9/3/202237第37页，共61页，2022年，5月20日，9点2分，星期一EXAM

21、PLE 4 设S为下列集合，+和为普通加法和乘法。(1) S=x | x=2nnZ.(2) S=x | x=2n+1nZ.(3) S=x | xZx0=N.(4)问S和+, 能否构成整环？能否构成域？为什么？9/3/202238第38页，共61页，2022年，5月20日，9点2分，星期一解：(1) 不是整环，也不是域。因为乘法幺元是1，而1S.(2) 不是整环，也不是域。因为不是群，S当然就不是环，+的幺元是0，而0S.(3) 不是群，因为除0以外任何正整数x的加法逆元是-x，而-xS. S当然就不是环，更不是整环和域。9/3/202239第39页，共61页，2022年，5月20日，9点2分，

22、星期一(4) S是域。x1, x2S，有：S对+和是封闭的。又乘法幺元1S，易证是整环。是域。9/3/202240第40页，共61页，2022年，5月20日，9点2分，星期一定理6：设是环，则：(1) aR，a0=0a=0.(2) a, bR，(-a)b=a(-b)=-(ab).(3) a, bR，(-a)(-b)=ab.(4) a, b, cR，a(b-c)=ab-ac. (b-c)a=ba-ca.在环中做加法和乘法只能遵从加法的交换律和结合律、乘法的结合律、乘法对加法的分配律，以及此定理中所给出的算律。9/3/202241第41页，共61页，2022年，5月20日，9点2分，星期一EXAM

23、PLE 5 设是环，a, bR，计算(a-b)2和(a+b)3.解：(a-b)2=(a-b)(a-b) =a2-ba-ab-b(-b) =a2-ba-ab+b2.(a+b)3=(a+b)(a+b)(a+b) =(a2+ba+ab+b2)(a+b) =a3+ba2+aba+b2a+a2b+bab+ab2+b3.幂运算分配律及定理6(2)定理6(3)及幂运算幂运算分配律及幂运算分配律及幂运算注：乘法没有交换律注：乘法没有交换律9/3/202242第42页，共61页，2022年，5月20日，9点2分，星期一3 格与布尔代数 格有两种等价的定义：一种是从偏序集的角度给出格的定义，这种定义可以借助哈斯(

24、Hasse)图来表示，因而比较直观、易于理解，这样定义的格称为偏序格；另一种是从代数系统的角度来给出格的定义，这种定义方法我们在上几节的群、环的定义中已有所体会，用代数系统的方法定义的格称为代数格。9/3/202243第43页，共61页，2022年，5月20日，9点2分，星期一 布尔代数是计算机科学最重要的基础理论之一，它在开关网络及数字电路的设计上有广泛深入的应用。 布尔代数是计算机科学工作者必备的基础知识，应掌握格与布尔代数的一般理论和方法。9/3/202244第44页，共61页，2022年，5月20日，9点2分，星期一DEFINITION 7. 设是偏序集，如果x, yS，x, y都有最

25、小上界和最大下界，则称S关于构成一个格。 可将求x, y的最小上界和最大下界看成x与y的二元运算和，即xy和xy。偏序格9/3/202245第45页，共61页，2022年，5月20日，9点2分，星期一EXAMPLE 6 设n为正整数，Sn为n的正因子的集合，D为整除关系，则构成格。 x, ySn，xy是x与y的最小公倍数，xy是x与y的最大公约数。 8421123612356101530如：9/3/202246第46页，共61页，2022年，5月20日，9点2分，星期一EXAMPLE 7 判断下图中偏序集是否构成格，为什么？abcdefabdeceabdfc解：都不是格。(1)中的a, b没有

26、下界。(2)中的b, d有上界c和e，但没有最小上界。(3)中的b, c有上界d, e, f，但没有最小上界。(1) (2) (3)9/3/202247第47页，共61页，2022年，5月20日，9点2分，星期一格的对偶原理： 设f 是含有格中的元素以及符号=, , , , 的命题，令f *是将f 中的改写成，改写成，改写成，改写成所得到的命题，称为f 的对偶命题。若f 对一切格为真，则f *也对一切格为真。9/3/202248第48页，共61页，2022年，5月20日，9点2分，星期一定理7： 设为格，则运算和适合交换律、结合律、幂等律和吸收律，即：(1) a, bL，有ab=ba, ab=

27、ba.(2) a, b, cL，有(ab)c=a(bc), (ab)c=a(bc).(3) aL，有aa=a, aa=a.(4) a, bL，有a(ab)=a, a(ab)=a.9/3/202249第49页，共61页，2022年，5月20日，9点2分，星期一证明：(1) ab和ba分别是a, b和b, a的最小上界，由于a, b=b, a，所以ab=ba。同理可证ab=ba.(2) 由最小上界的定义有： aa(bc), bbca(bc), cbca(bc). 由式和有： aba(bc). 再由式和有： (ab)ca(bc).同理可证： (ab)ca(bc).根据偏序关系的反对称性有：(ab)c

28、=a(bc).类似地可以证明：(ab)c=a(bc).9/3/202250第50页，共61页，2022年，5月20日，9点2分，星期一(3) 显然aaa，又由aa可得aaa。根据偏序关系的反对称性有：aa=a.同理可证：aa=a.(4) 显然a(ab)a。 又由aa, aba，可得： a(ab)a. 由式和可得：a(ab)=a.同理可证：a(ab)=a.9/3/202251第51页，共61页，2022年，5月20日，9点2分，星期一DEFINITION 8. 设是具有两个二元运算的代数系统，且对于*和适合交换律、结合律、吸收律，则可以适当定义S中的偏序，使得构成一个格，且a, bS，有ab=a

29、*b, ab=a b.代数格只要吸收律成立，则幂等律就一定成立。证： aS，有aa=a(a*(aa)=a. 同理可证a*a=a.9/3/202252第52页，共61页，2022年，5月20日，9点2分，星期一DEFINITION 9. 设是格，若a, b, cL，有a(bc)=(ab)(ac) a(bc)=(ab)(ac)成立，则称L为分配格。9/3/202253第53页，共61页，2022年，5月20日，9点2分，星期一DEFINITION 10. 在格中存在一个元素a，bL, ab(或ba)，则称a为格L的全下界（或全上界），记为0（或1）。 具有全上界和全下界的格称为有界格。记作.9/3/202254第54页，共61页，2022年，5月20日，9点2分，星期一DEFINITION 11. 设是有界格，aL，若存在bL，使得ab=0, ab=1，则称b为a的补元。 若格中每个元素都至少有一个补元，则称这个格为有补格。对分配格L来说，若aL有补元，