第八章半群和群

离散数学第八章半群和群2020/2/92期中测验1.用推理规则论证下列问题:我或者去北京,或者去广州.如果去北京,就去长城.去了长城,就不能参加运动会.所以,如果我参加了运动会,那么我去了广州.2.符号化下列命题,并推证其结论:任何人如果他喜欢步行,他就不喜欢乘汽车.每一个人或者喜欢乘汽车,或者喜欢骑自行车.有的人不爱骑自行车.因而有的人不爱步行.3.求的主析取范式和主合取范式SRQP2020/2/93期中测验4.证明5.求由a,b,c,d四个字符构成的n位符号串中，a,b,c至少出现一次的符号串的数目。6.给定集合S={1,2,3,4,5},找出S上的等价关系R,使等价关系R能产生划分{{1,2},{3},{4,5}}.7.设R是实数集，若定义证明S是一个偏序。R是全序吗？)()()()(BABAABBA.]1,0[RX,,Xgf.0)()(],1,0[,xgxfxSgf2020/2/948.1半群和独异点定义8.1.1设为代数系统，其中*为二元运算，若运算*满足结合律，即对都有则称是一个半群。定义8.1.2设是一个半群，若S关于*有单位元e，即若存在使得对任都有则称为一个独异点。有时记为,S,S,,,Scba)()(cbacba,Se,SaaeaaeeS,,,S,S2020/2/958.1半群和独异点定义8.1.2若半群(独异点)中的运算*是可交换的，即若对都有则称为可交换半群(独异点)。例8.1.1(1)都是可交换独异点,其中。,S,,Sbaabba,0,,I,1,,I,0,,mmN1,,mmN},1,,2,1,0{mNm,mod)(mjijimmjijimmod)(,S2020/2/968.1半群和独异点证可结合性：设即同理可证：所以,mod)(rmyxrkmyxzyxmm)(zmyxm)mod)((mzyxmod))((mzrmod)(mzkmyxmod))((mzyxzyxmmmod))(()()()(zyxzyxmmmm2020/2/978.1半群和独异点(2)不是半群(3)和是可交换独异点(4)是不可交换独异点。定义8.1.4设是一个半群，T为S的非空子集，若对任有则称为的子半群定义8.1.5设是一个独异点，T为S的非空子集,若对任有且则称为的子独异点。,I,),(AAA,),(AAA1,,,S,,Tba,Tba,TeS,,,,Tba,Tba,TeeT,,eS,,,S2020/2/988.1半群和独异点例8.1.3是的子独异点,但不是定理8.1.1设为可交换独异点，T为S中所有幂等元的集合，则为的子独异点。证由得又所以定义8.1.6的子独异点称为变换独异点,dO,I,vEeS,,eS,,,T,,Tbaabaa22,)()(baba22baTbaba,2eeTeAAA1,,2020/2/998.1半群和独异点定义8.1.7设和是两个半群,函数若有则称h为从到的半群同态。定义8.1.8设和是独异点,函数若有且则称h为从到的独异点同态,1S.:21SSh,,1Sba)()()(bhahbah,2S11,,eS22,,eS21:SSh,,1Sba)()()(bhahbah,1S,2S,)(21eeh11,,eS22,,eS2020/2/9108.1半群和独异点定理8.1.2半群与同态。证定义其中所以,S,SS,)(,:aSfahSShbabfSSfaa)(,:))((cbah)))(()((cbhah)()()(bhahbah))((cffba))((cffba)(cbfa)(cba)(cfbacba)(2020/2/9118.1半群和独异点例8.1.5考虑半群其中从到的同态如下：其中,,S},,{cbaS*abcaabcbbcaccab,S,SSafah)(bfbh)(cfch)(ccfbbfaafaaa)(,)(,)(acfcbfbafbbb)(,)(,)(bcfabfcafccc)(,)(,)(2020/2/9128.1半群和独异点定理8.1.3任意独异点都同构于某一变换独异点证由定理8.1.2知为从到的半群同态且所以h为从到的独异点同态又若即于是h是单射。因此同构于eS,,aSfahSSh)(,:,S,SSSefeh1)(eS,,SSS1,,),()(bhahbaffeS,,SSh1,),(ebea)()(efefbaba2020/2/9138.2群的定义和性质定义8.1.8设是独异点,其单位元为e.若对任存在使得即G中每个元素关于*都是可逆的，则称为群。定义8.1.9若群中的二元运算*是可交换的，则称为可交换群，也称为阿贝尔群。例8.2.1(1)是阿贝尔群(2)是阿贝尔群(3)是阿贝尔群(4)和都不是群,G,Ga,Aa,eaaaa,G,G,G,ImmN,},0{Q,N,I2020/2/9148.2群的定义和性质定理8.2.1设是半群，若(1)使得有(2)对使得则是群证先证因为故存在使得,G,Gel,Gaaael,Ga,Gallleaa,G,Galleaa,Gal,Galleaa)()(llaaaalealaa)(llaaellaeallaaaa)(lelaa)(aaalaaaal)(ael2020/2/9158.2群的定义和性质例8.2.2考虑其中则是半群，且(1)是的左单位元(2)但无单位元,故不是群,,G}0{,00QbabaG,,G0011,G,00Gba0011001100aaba,G2020/2/916作业习题8.149习题8.21(1)(3)32020/2/9178.2群的定义和性质定理8.2.2设是半群，若方程和在G中都有解，则是群证(1)取设为的一个解c为的解，即有则即为的左单位元(2)设为的一个解,则即为a的左逆元,G,,Gbabxabay,G,Galeaay,Gbbxabelle,G,Galaleaylleaala)(caelcael)(cab,bca2020/2/9188.2群的定义和性质定理8.2.3设是有限半群,若且即G中消去律成立,则是群证设先证方程在G中有解令则由于消去律成立,故当时,于是有,因此,G,,Gyxyxyaxayxayax,G},,,{21naaaG,,Gbabxa},,,,{21naaaaaaGGGjijiaaaa||||GGGG,Ga2020/2/9198.2群的定义和性质由于故使得即是方程的解类似地可证方程在G中有解由定理8.2.2便知是群定理8.2.4设是群，则(1)(2)方程和在G中有唯一解(3)G中消去律成立,Gb),1(nkkbaakkabxabay,G,G,,Gba111)(abba,,Gbabxabay2020/2/9208.2群的定义和性质证(1)由知(2)存在性唯一性:若c也是在G中的解,即有则ebeb1)()(11abba111)(abba)(1baabxacec,bcabaab)(11)()(11baab11)(abbaeaea1bbebaa)(111aeacaa)(1)(1caa2020/2/9218.2群的定义和性质(3)设若对有同理可证,,Gyx,Gayaxayxayaxyx)()(11yaaxaayaaxaa)()(11yexe2020/2/9228.2群的定义和性质设是群，a的整数次幂可归纳定义如下：(1)(2)(3)容易证明：任定义8.2.3设是群，。若则称a的阶是无限的；否则称使的最小正整数n为a的阶，通常记为|a|。,G,Gaea0Nnaaann,1Inaann,)(1,nmnmaaamnnmaa,,Inm,GGa,,eaInnean2020/2/9238.2群的定义和性质例8.2.3(1)在群中，i的阶都是无限的(2)在群中，|0|=1，|1|=4，|2|=2，|3|=4。单位元是群中阶为1的唯一元素,I},0{Ii44,N2020/2/9248.2群的定义和性质定理8.2.5设是群，且|a|=n,则当且仅当n|k证必要性若设则有由|a|=n知，r=0。充分性若n|k，则使于是,Ga.eak),0(,nrrqnkkae,Iq,qnkkarqnarqnaarqnaa)(rraaeqnaqna)(eeq,Geak2020/2/9258.2群的定义和性质定理8.2.6设是群，且|a|=n，则特别地，证设则由定理8.2.5知又所以,G,Ga,Ik),(nknakaa1,mak.eakmkmn|mnkn),(mnkknkn),(),(),(nknka),(nkknaeenkk),(),(|nknm),(nknm2020/2/9268.2群的定义和性质定理8.2.7设是有限群，则证中必有两个相等设为故,G,||nG,Gana||,Ga132,,,,naaaa)11(njiaajieaijnija||2020/2/9278.3子群和群同态定理8.3.1设是群，H是G的非空子集。若也是群，则称为的子群，记作。若H是G的真子集，则称为的真子群,记作平凡子群：和例8.3.1(1)是的真子群(2)是的真子群,G,H,H,GGH,H,G.GH,Q,R,I,Q,G},{e2020/2/9288.3子群和群同态定理8.3.1设是群，则(1)H的单位元就是G的单位元(2)a在H的逆元就是a在G中的逆元证(1)设和分别为a在H和G中的单位元，则(2)设和分别为a在H和G中的逆元，则,G,GH,HaHeGeHHHeeeGHeeGHee,Ha1Ha1GaeaaH111GHaa1Gaa2020/2/9298.3子群和群同态定理8.3.2设是群，H是G的非空子集，则当且仅当(1)(2)证必要性显然充分性.只需证H有单位元.因取由(2)知再由(1)知故是群,,GGHHbaHba,,HaHa1,,H.Ha.1HaHaae1,HGH2020/2/9308.3子群和群同态定理8.3.3设是群，H是G的非空子集，则当且仅