《离散数学》课后习题解答--第7章.doc

第7章 习题解答 -  PAGE 15 - 习题 7.1 1. 设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)+6 a*(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)?2 a*(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,5y，a*b=max(a,b)。 解：对于A中任意元素a ，都有 1*a=a*1=max(a,1)=a 所以1是独异点A,*的幺元。由于A,*的子独异点必须与A,*有相同的幺元，因此，A,*的所有子独异点分别为í1y,*，í1,2y,*，í1,3y,*，í1,4y,*，í1,5y,*，í1,2,3y,*，í1,2,4y,*，í1,2,5y,*，í1,3,4y,*，í1,3,5y,*，í1,4,5y,*，í1,2,3,4y,*，í1,2,3,5y,*，í1,2,4,5y,*，í1,3,4,5y,*，A,*。 本题的难度并不大，主要目的是通过本题进一步牢记：“子独异点必须与独异点有相同的幺元”的要求。 3.在独异点N10,×10中，取其子集A=í0,2,4,6,8y，说明A,×10是独异点，但不是N10,×10的子独异点。 解：由于A是由N10中所有偶数作为元素构成的集合；任意两个偶数的乘积是偶数，偶数被10除后，其余数必为小于10的偶数；由此可知，模10的乘法运算×10对于A是封闭的。×10是可结合运算。 在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=í0y，A2=í0,4y，A3=í0,2,4,6y，A4=í0,1,2,3,4,5,6,7y，则N8,+8的所有子半群为 A1,+8，A2,+8，A3,+8，A4,+8 6. A,*是半群，其中A=ía,by，且a*a=b。证明 ⑴ *是可交换运算。 ⑵ b=b2。 证明：⑴因为a*b=a*a2=a3=a2*a=b*a，所以*是可交换运算