北大离散数学chap6

第六章几个典型的代数系统第一节半群与群内容：半群，群，子群。重点：1、半群，可交换半群，独异点的定义，2、群，交换群(阿贝尔群)的定义及性质，3、群的阶的定义，4、循环群，生成元的定义及例子，5、子群的定义及判定。一、半群。1、定义：满足结合律的代数系统称为半群。,S例1、(1)，，，，,Z,N,Z,Q,R都是半群。(2)(),nMR是半群。(3)是半群，其中表示集合的对称(),PA差运算。一、半群。1、定义：满足结合律的代数系统称为半群。,S(4)是半群，其中,nZ表示模0,1,2,,1nZn，n的加法。可交换半群2、独异点(含幺半群)：记作,,Se如例1中除了不是独异点外，其余的均是,Z独异点，分别记作,,0N，,,0Z，,,0Q,,0R，(),,nMRE(),,PA，,,0nZ，。3、半群中元素幂nx。定义运算的幂，xS，nx指的是：1xx1nnxxx(为正整数)n0xenmnmxxx()nmnmxx(为非负整数)mn、4、子半群。半群的子代数叫子半群，独异点的子代数叫子独异点。例如：，都是的子半群，,Z,N,Z且,N,Z是的子独异点。二、群。1、定义。代数系统满足：,G①结合律，②有幺元，③任意元有逆元，则称为群。,G例2、(1),Z,Q,R，，都是群，因任意元素的逆元存在，x()x,Z,N而，不是群，,Z没有幺元，,N除0外，其余元素都没有逆元。(2)(),nMR不是群，因不是所有的阶矩阵都可逆。n(3)(),PA是群，为幺元，()xPA1xx()xx，(4),nZ是群，0为幺元，nxZ1000xxnxx，2、交换群(也称阿贝尔()Abel群)。如例2中的,Z,Q,R(),PA,nZ，，，都是阿贝尔群。，例3、Klein四元群。,,,Geabc，运算由下表给出：3、群的阶。有限群群无限群有限群G的阶，记G。例如：,nZ的阶为n，Klein四元群的阶为4。4、群中元素的幂nx。对于群G，定义：1()nnxx则可以把独异点中的关于的定义扩充为：nx0xe1nnxxx为非负整数)(n1()nnxx为正整数)(n有关幂的两个公式：mnmnxxx()mnmnxx(,)mnZ5、群中元素x的阶(或周期)。群中元素的阶成立的最小正整数——使Gxkxek。xkxk有限，记的阶无限(不存在以上的)例如：Klein四元群中，的阶都是2，记,,abc2abc。的阶为1，记e1e。例4、60,1,2,3,4,5Z，求模6的加群6,Z中各元素的阶。解：因2220，即320，所以23。同理可得：1632435601，，，。6、群的性质。(1),xyG11()xx111()xyyx，，。(2)若1G，则中无零元。G(3)中消去律成立，即G若，则，abacbc若，则。bacabc6、群的性质。(4)幺元是群中唯一的幂等元。不同行(列)的排列不同。(5),abGG，方程和在中有唯一解。axbyab(6)有限群的运算表中，每一行(每一列)都是G中元素的一个排列。例5、证明是阿贝尔群当且仅当对G,abG222()abab，。证明：设为阿贝尔群，G则,abG，有abba，故2()()()()ababababab22()()()aabbaabbab例5、证明是阿贝尔群当且仅当对G,abG222()abab，。证明：反之，设,abG222()abab，，即()()()()ababaabb，即()()ababaabb，由消去律，得baab，G故为阿贝尔群。例6、如果中的每一个元素都满足Ga2ae，则是阿贝尔群。G证明：,abG，1()abab由题设知，1aa，1bb，从而111()ababbaba，所以是阿贝尔群。G例7、设群不是阿贝尔群，则中存在两个GG非幺元的元素,abababba，，使得。证明：(1)先证存在aG，使1aa。事实上，若aG，都有1aa，即2ae由例6知，是阿贝尔群，与题设矛盾。G(2)再证结论成立。设，，aG1aa令1ba，则非幺元，且,abab，但abba。三、子群。1、定义：设群，是的非空子集，,GHG若为群，则称为的子群，记作,HHGHG。例8、(1)群,Z，令22ZzzZ，则2,Z是,Z的子群，同样，0,也是的子群。,Z三、子群。1、定义：设群，是的非空子集，,GHG若为群，则称为的子群，记作,HHGHG。例8、(2)Klein四元群，,,,Gabce有5个子群：e,ea,eb,ecG，，，，其余均为真子群。其中和是平凡子群，eG2、判定。定理：设为群，是的非空子集，若对任意GHG,xyH，都有，则是的子群。1xyHHG例9、设和都是群的子群，1H2HG证明也是的子群。12HHHG证明：(1)先证H非空。因为的子群，故，12,HHG1eH2eH，从而，12eHH因此，非空。H例9、设和都是群的子群，1H2HG证明也是的子群。12HHHG因都是的子群，故，12,HHG11xyH12xyH从而，112xyHH证明：(2),xyH，则且1,xyH2,xyH，由判定定理知，为H的子群。G思考：若12,HH为群的子群，问G12HH是的子群吗？G3、生成子群，中心。(1)生成子群：设为群，，记GxGkxxkZ例10、60,1,2,3,4,5Z，群中由2生成的子群6,Z220,2,4kkZ同理，420,2,4，30,3，15G，00。3、生成子群，中心。(1)生成子群：设为群，，记GxGkxxkZ(2)中心：设为群，G记()CaaGxGaxxa，称为群的中心。CG四、循环群。1、定义：群中若存在使得GaGkGakZ，则称为循环群，记，称为的生成元。GGaaG在循环群中，生成元的阶与群的阶一样。GaaGnana阶循环群循环群无限阶循环群(的阶无限)循环群都是阿贝尔群。循环群的子群都是循环群。2、循环群的典型例子。例11、是循环群，其生成元为1和－1，,Z因为任何整数都可由若干个1或者若干个－1相加而得到。是无限阶循环群，其子群除了,Z0外都是无限阶循环群，如2,3,,,ZZnZ，其中,2,,0,,2,nZnzzZnnnn例12、是阶循环群，，,nZn0,1,2,,1nZn中与互质的数均可作为生成元。nZn阶循环群的子群的阶都是的正因子，nGan对于的每个正因子，在中只有一个ndGd阶子群，就是由生成的子群。nda如：120,1,2,,11Z，其生成元有1,5,7,11(均与12互质)。即1215711Z12的正因子有1,2,3,4,6,12，则的子群有：12Z121100122160,6123140,4,81阶子群2阶子群3阶子群12的正因子有1,2,3,4,6,12，则的子群有：12Z124130,3,6,9126120,2,4,6,8,101212110,1,2,,114阶子群6阶子群12阶子群第二节环与域内容：环，域。了解：环与域的定义及例子。一、环。定义：设是代数系统，为集合，,,RR为二元运算，若,(1)为阿贝尔群。,R(2)为半群。,R(3)乘法对加法+适合分配律。则称是环。,,R例1、,,Z,,Q,,R，，都是环。(),,nMR是环。,,nZ是模的整数环。n其中表示模的加法和乘法，,n()modxyxyn()modxyxyn，。二、域。定义：环满足：,,F(1)至少两个元素，F(2)含有幺元，,F(3)是可交换的，,F(4)除加法幺元外，其余元素均有逆元，,F则称,,F为域。例2、，都是域，,,Q,,R但不是域，,,Z因为不是除0外，其余元素都有逆元。,Z(),,nMR不是域，因(),nMR不是可交换的。5,,Z是域，但6,,Z不是域。，但不存在乘法的逆元，使(64Za441aa)令2,,SxxababQ，则为域。,,S第三节格与布尔代数内容：格，格的性质，布尔代数。重点：格与布尔代数的有关概念及例子。一、格的概念。定义：设是偏序集，如果对,xyS,S°，都有最小上界(记)和最大下界(记,xyxyxy)，则称S关于构成一个格。°格也记作,L°,,L。例1、设为正整数，表示的所有正因子的nnSn集合，表示整除关系，则D,nSD构成格。(,)xyxy的最小公倍数,xy的最大公约数,xy如：81,2,4,8S61,2,3,6S301,2,3,5,6,10,15,30S,nxyS,xyxy，361,2,3,4,6,9,12,18,36S下图给出了格8,SD，，，6,SD30,SD36,SD8,SD81426,SD6321下图给出了格8,SD，，，6,SD30,SD36,SD30,SD1030515261336,SD364916121823例2、判断下图中的偏序集是否构成格，并说明理由。(1)dceafb(2)eabdc(3)fdebac二、格的性质。1、对偶原理：设是含有格中的元素以及符号f,,,,氨的命题，令*f是将中的f,,,氨分别改写成,,,卑所得到的命题，称为f切格为真。f*f也对一对一切格为真，则的对偶命题。若2、性质：设为格，则运算和,L°适合交换律，结合律，幂等律和吸收律，即,,abcL，有(1)交换律abba，abba(2)结合律()()abcabc，()()abcabc2、性质：设为格，则运算和,L°适合交换律，结合律，幂等律和吸收律，即,,abcL，有(3)幂等律aaa，aaa(4)吸收律()aaba，()aaba三、分配格，有界格，有补格。1、分配格——满足分配律的格。2、有界格——有全上界，全下界的格。全上界记为1，全下界记为0，有界格也记为,,,0,1L三、分配格，有界格，有补格。4、有补分配格——有补格且是分配格。3、有补格——有界格,,,0,1L，若对aL存在的补元(记)，使a'a'0aa，'1aa，则称为有补格。例3、所有的有限格(指格中的元素有限个)都是有界格。如例1中，格中的全上界为，全下界为1。,nSDn但和不是有补格(思考：为什么？)8,SD36,SD是有补格，6,SD互为补元，互为补元。1,62,3是有补格，30,SD互为补元，2与15，3与10，1,305与6互为补元。例4、判断下图中所表示的格是否有补格。(1)1acb0不是有补格(2)1ca0b是有补格(3)ba0c1是有补格5、有补分配格中任意元素的补元是唯一的。四、布尔代数。1、定义：有补分配格称布尔代数，记为,,,',0,1L，其中“'”表示求补运算。例5、(1)开关代数0,1,,,,0,1是布尔代数，其中为与运算，为或运算，为非运算。例5、(2)集合代数(),,,~,,PsS是布尔代数。,abab,,abc,ab,ac,bcabc以下分别是,,,,SabSabc的图2、性质。设,,,',0,1L为布尔代数，则(1)aL，，(')'aa(2),abL，，()'''abab德摩根律()'''abab3、有限布尔代数的表示定理。对每个有限布尔代数,,,',0,1L，都存在一个有限集合，使得S(),,,~,,PsS与其同构。由这个