离散习题(附答案)(7)

第7章习题解答-1-习题7.11.设Z是整数集合，Z上的二元运算*定义为：a*b=ab+2(a+b+1)。证明代数系统Z,*是半群。证明：由于任意两个整数经加、减、乘运算后，其结果仍然是整数。所以运算*对于是封闭的。现证*是可结合运算。由于(a*b)*c=(ab+2(a+b+1))*c=(ab+2(a+b+1))c+2(ab+2(a+b+1)+c+1)=abc+2ac+2bc+2c+2ab+4a+4b+2c+6=abc+2(ab+bc+ca)+4(a+b+c)+6a*(b*c)=a*(bc+2(b+c+1))=a(bc+2(b+c+1))+2(a+bc+2(b+c+1)+1)=abc+2ab+2ac+2a+2a+2bc+4b+4c+6=abc+2(ab+bc+ca)+4(a+b+c)+6所以(a*b)*c=a*(b*c)。由此证得*是可结合运算，Z,*是半群。在证明*是可结合运算时，还可先把*的定义改写如下：a*b=ab+2(a+b+1)=ab+2a+2b+2=a(b+2)+2(b+2)−2=(a+2)(b+2)−2从而有(a*b)*c=((a+2)(b+2)−2)*c=(((a+2)(b+2)−2)+2)(c+2)−2=(a+2)(b+2)(c+2)−2a*(b*c)=a*((b+2)(c+2)−2)=(a+2)(((b+2)(c+2)−2)+2)−2=(a+2)(b+2)(c+2)−2于是(a*b)*c=a*(b*c)。显然，上述证明方法，不仅简明清晰，而且可以对运算过程和运算结果有较好的把握和预测，避免了盲目性。2.写出独异点A,*的所有子独异点，其中A=1,2,3,4,5，a*b=max(a,b)。解：对于A中任意元素a，都有1*a=a*1=max(a,1)=a所以1是独异点A,*的幺元。由于A,*的子独异点必须与A,*有相同的幺元，因此，A,*的所有子独异点分别为1,*，1,2,*，1,3,*，1,4,*，1,5,*，1,2,3,*，1,2,4,*，1,2,5,*，1,3,4,*，1,3,5,*，1,4,5,*，1,2,3,4,*，1,2,3,5,*，1,2,4,5,*，1,3,4,5,*，A,*。本题的难度并不大，主要目的是通过本题进一步牢记：“子独异点必须与独异点有相同的幺元”的要求。3.在独异点N10,×10中，取其子集A=0,2,4,6,8，说明A,×10是独异点，但不是N10,×10的子独异点。解：由于A是由N10中所有偶数作为元素构成的集合；任意两个偶数的乘积是偶数，偶数被10除后，其余数必为小于10的偶数；由此可知，模10的乘法运算×10对于A是封闭的。×10是可结合运算。第7章习题解答-2-在A,×10中，由于6×100=0×106=0；6×102=2×106=2；6×104=4×106=4；6×106=6×106=6；6×108=8×106=8。所以6是A,×10的幺元，A,×10是独异点。由于独异点N10,×10的幺元为1，因此A虽是N10的子集，且A,×10是独异点，但A,×10不是N10,×10的子独异点。4.Z是由所有整数组成的集合，对于下列*运算，哪些代数系统Z,*是半群?⑴a*b=ab⑵a*b=a⑶a*b=a+ab⑷a*b=max(a,b)解：⑴不是半群。因为运算*不满足结合律。例如，(2*3)*2=23*2=(23)2=26，而2*(3*2)=2*32=29，所以(2*3)*2≠2*(3*2)。⑵是半群。*的封闭性是显然的，由于(a*b)*c=a*c=a,a*(b*c)=a*b=a，所以*是可结合运算，Z,*是半群。⑶不是半群，因为运算*不满足结合律。易见(a*b)*c=(a+ab)*c=a+ab+(a+ab)c=a+ab+ac+abc而a*(b*c)=a*(b+bc)=a+a(b+bc)=a+ab+abc所以(a*b)*c≠a*(b*c)，*不是可结合运算。⑷是半群。*的封闭性是显然的，由于(a*b)*c=a*(b*c)=max(a,b,c)，所以*是可结合运算，Z,*是半群。5.写出N8,＋8的所有子半群。解：令A1=0，A2=0,4，A3=0,2,4,6，A4=0,1,2,3,4,5,6,7，则N8,+8的所有子半群为A1,+8，A2,+8，A3,+8，A4,+86.A,*是半群，其中A=a,b，且a*a=b。证明⑴*是可交换运算。⑵b=b2。证明：⑴因为a*b=a*a2=a3=a2*a=b*a，所以*是可交换运算。⑵由于有限半群必有等幂元，在半群A中，仅有两个元素a和b，而a*a=b，所以b是等幂元，由此证得b=b2。7.集合A=0,2,4，说明对于模6乘法×6，A,×6是独异点，但A,×6不是N6,×6的子独异点。解：容易验证×6对于A是封闭的，且满足结合律，A中元素4是A,×6的幺元，因为4×60=0，4×62=2，4×64=4所以A,×6是独异点；由于1是N6,6的幺元。而1A,，因此A,6不是N6,6的子独异点。8.Z是整数集合，运算*定义为a*b=a+b+ab。证明Z,*是独异点。第7章习题解答-3-证明：*对于Z的封闭性是显然的。下面证明*是可结合运算，由于(a*b)*c=(a+b+ab)*c=a+b+ab+c+(a+b+ab)c=a+b+c+ab+ac+bc+abca*(b*c)=a*(b+c+bc)=a+b+c+bc+a(b+c+bc)=a+b+c+ab+ac+bc+abc所以有(a*b)*c=a*(b*c)由此可知*是可结合运算。又由于0*a=a*0=0+a+a·0=a所以0是幺元，Z,*是独异点。9.A,*是半群，对于A中任意两个不同的元素a和b都有a*b≠b*a，证明a*b*a=a。证明：由题设可知，当a≠b时，必有a*b≠b*a，也即当a*b=b*a时，必有a=b。由于A,*是半群，*是可结合运算，所以对于A中任意元素a，都有(a*a)*a=a*(a*a)由此可知a*a=a又由于(a*b*a)*a=a*b*(a*a)=a*b*a，而a*(a*b*a)=(a*a)*b*a=a*b*a，所以有(a*b*a)*a=a*(a*b*a)，由此证得a*b*a=a。习题7.21.下面代数系统哪些是群，哪些是交换群？⑴设Mmn(R),+，其中，Mmn(R)是所有元素为实数的mn矩阵集，+是矩阵的加法。⑵设A,*，其中，A=1,2,3,4,6,12，*是求最大公因数运算。⑶设Mmn(R),*，其中，Mmn(R)是所有元素为实数的mn矩阵集，*是矩阵的乘法。解：⑴是群，且是交换群。⑵是半群，且是交换半群。但不是群，因没有单位元。⑶不是群，当m≠n时，甚至不是代数系统。当m=n时，是一个半群，且有单位元，但对不可逆的矩阵，它没有逆元素。2.如果群G,*的每个元素都适合方程x2=e，则G,*是交换群，其中e是G,*的单位元。证明：任取a,bG，则a*bG，于是(a*b)*(a*b)=(a*b)2=ea*b=e*(a*b)*e=b2*(a*b)*a2=b*(b*a)*(b*a)*a=b*e*a=b*a所以G,*是交换群。也可以如下证明：由(a*b)*(a*b)=(a*b)2=e=e*e=a2*b2=(a*a)*(b*b)根据定理7.2.5，G,*是交换群。3.设R是实数集，R上的二元运算*定义为：a*b=a+b+ab。⑴证明R,*是独异点，并写出其幺元和零元。⑵设A是所有不等于−1的实数构成的集合，即A=R−−1，证明A,*是群。证明：⑴由于实数经加法和乘法运算后，其运算结果仍为实数，所以运算*对于R是封闭的。第7章习题解答-4-再证明*是可结合运算。由于a*b=a+b+ab=a(b+1)+(b+1)−1=(a+1)(b+1)−1从而有(a*b)*c=((a+1)(b+1)−1)*c=(((a+1)(b+1)−1)+1)(c+1)−1=(a+1)(b+1)(c+1)−1a*(b*c)=a*((b+1)(c+1)−1)=(a+1)(((b+1)(c+1)−1)+1)−1=(a+1)(b+1)(c+1)−1于是(a*b)*c=a*(b*c)。所以*是可结合运算。在R,*中，对于任何实数a，都有0*a=a*0=0+a+0·a=a故0是R,*中的幺元，R,*是独异点。对于R,*中任何实数a，都有(−1)*a=a*(−1)=(−1)+a+(−1)·a=−1即−1是R,*中的零元。⑵首先证明*对于A是封闭的。由于a*b=(a+1)(b+1)−1所以当a和b为不等于−l的实数时，a+1≠0，b+1≠0，也即有(a+1)(b+1)≠0，由此可知a*b=(a+1)(b+1)−1≠−1因此*对于A是封闭的。0是A,*中的幺元。现证明A中的每一个元素都有逆元。对于A中任意元素a(a是不等于−1的实数)，都有a*(11a−1)=(a+1)(11a−1+1)−1=0由于0是幺元，所以a的逆元是11a−1。综上证明，A,*是群。4.集合A=1,2,3,4，A上的二元运算*定义如下，哪些代数系统A,*是群?⑴a*b=a+b；⑵*是模5乘法；⑶a*b=ab。解：⑴不是群。因为普通加法对于A是不封闭的。⑵是群。因为A=N5−0，5是素数，所以A,5是群。(3)不是群。因为*不是封闭运算。也不是可结合运算。5.证明Z,+是群。证明：由于任意两个整数相加仍然是整数，所以加法对于整数集Z是封闭的；加法满足结合律；0是幺元；任意整数i的逆元是−i。由此可知Z,+是群。6.证明群中不存在零元。证明：因为零元没有逆元，所以群中不存在零元。7.设G,*是群，如果对于群G中任意元素a,b，都有(a*b)−1=a−1*b−1，证明G,*是阿贝尔群。第7章习题解答-5-证明：由群的性质和定理7.1.5可知(b*a)−1=a−1*b−1由题设可知(a*b)−1=a−1*b−1所以有(a*b)−1=(b*a)−1由逆元的惟一性可知a*b=b*a，G,*是阿贝尔群。8.设G,*是群，如果对于群G中任意元素a,b，都有(a*b)3=a3*b3和(a*b)5=a5*b5，证明G,*是阿贝尔群。证明：由题设可知(a*b)3=a3*b3，则a*b*a*b*a*b=a*a*a*b*b*b从左边消去a和右边消去b后可得b*a*b*a=a*a*b*b即(b*a)2=a2*b2又由题设可知(a*b)5=a5*b5，则a*b*a*b*a*b*a*b*a*b=a*a*a*a*a*b*b*b*b*b从左边消去a和右边消去b后可得(b*a)4=a4*b4由已证得(b*a)2=a2*b2，所以有a2*b2*a2*b2=a4*b4再从左边消去a2和右边消去b2后可得b2*a2=a2*b2又由于(b*a)2=a2*b2=b2*a2利用已知结果知a*b=b*a所以G,*是阿贝尔群。9.设G,*是偶数阶群，证明在G中必存在非幺元a，使得a*a=e。证明：显然，满足等式a*a=e的元素a是—个以自身为逆元的元素，即a=a−1。对于G中元素g，如果g*g≠e，也即g≠g−1，那么g和其逆元g−1应成对地在G出现，所以在G中满足条件g≠g−1的元素有偶数个；由于G是偶数阶群，所以G中有偶数个元素。由此可知，G中以自身为逆元的元素(即a=a−1)也有偶数个。易知，幺元e是以自身为逆元的元素，所以除幺元外，G中至少有一个元素a，是以自身为逆元，即G中存在元素a，a≠e且a*a=e。10.设G,*是群，e是幺元，如果对于G中任意元素a，都有a*a=e，证明G,*是阿贝尔群。证明：对于群G中任意元素a,b