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

第6章习题解答1习题6.11.通常数的乘法运算是否可以看作下列集合上的二元运算，说明理由。⑴A=1,2。⑵B=b|b是素数。⑶C=c|c是偶数。⑷D=2n|nN。解：⑴因为2×2＝4A，所以数的乘法运算不A上的二元运算。⑵因为2、3B，2×3＝6B，所以数的乘法运算不是B上的二元运算。⑶a,bC，a、b是偶数，a×b也是偶数，即a×bC且a×b的结果是唯一的，所以数的乘法运算是C上的二元运算。(4)a,bD,n,mN，使a＝2n，b＝2m，a×b=2n×2m=2n+m,n+mN，所以a×bD且运算结果唯一，故数的乘法运算是D上的二元运算。2.集合A=1,2,3,4，*和是A上的二元运算，其中运算*定义为a*b=ab−b，运算定义为ab=max(a,b)，试写出*和的运算表。解：*和的运算表如表6.12和表6.13所示。表6.12表6.13∗12341234100001123421234222343246833334436912444443.N7,＋7和N7,×7是代数系统，其中N7=0,1,2,3,4,5,6，运算＋7是模7加法，运算×7是模7乘法。试写出＋7和×7的运算表。解：＋7和×7的运算表如表6.14和表6.15所示。表6.14＋7012345600123456112345602234560133456012445601235560123466012345第6章习题解答2表6.15×7012345600000000101234562024613530362514404152635053164260654321习题6.21.设代数系统A,∗，其中A=a,b,c，∗是A上的二元运算，分别由下列表给出。试分别讨论交换性、幂等性、单位元和逆元。表6.3表6.4表6.5表6.6∗abc∗abc∗abc∗abcaabcaabcaabcaabcbbcabbacbabcbabcccabcccccabccccb解：*的交换性、幂等性、单位元和逆元如表6.16所示。表6.16交换律幂等律单位元逆元表6.3有无aa–1=a,b–1=c,c–1=b表6.4有无aa–1=a,b–1=b表6.5无有无无表6.6无无无无2.证明下列的公式⑴am∗an=am+n。⑵(am)n=amn。证明：设∗运算满足结合律，以下对于对任意的正整数n和m证明⑴和⑵两个结论。⑴对于任意的正整数m，对n用数学归纳法证明。当n=1时，am∗a1=am∗a=am+1设n=k时，结论成立，即am∗ak=am+k。下证n=k+1时，结论也成立，即am∗ak+1=am+k+1。am+(k+1)=a(m+k)+1=am+k∗a=(am∗ak)∗a=am∗(ak∗a)=am∗ak+1。所以am∗an=am+n。⑵对于任意的正整数m，对n用数学归纳法证明。第6章习题解答3当n=1时，(am)1=am=am·1。设n=k时，结论成立，即(am)k=amk。下证n=k+1时，结论也成立，即(am)k+1=am(k+1)。(am)k+1=(am)k∗am=amk∗am=amk+m=am(k+1)。所以，(am)n=amn。3.证明定理6.2.2注：设*是非空集合A上的二元运算，a为运算*的幂等元，对任意的正整数n，则an=a。证明：用数学归纳法证明。当n=1，2时，a1=a，a2=a*a=a设n=k时，结论成立，即ak=a，下证n=k+1时，结论也成立，即ak+1=a。ak+1=ak*a=a*a=a，所以，an=a，n为正整数。4.写出代数系统N7,＋7的幺元和零元，各元素的逆元。解：代数系统N7,＋7的运算表如表6.14所示。由表知幺元为0，无零元，0逆元是0，1和6，2和5，3和4互为逆元。5.写出代数系统N7,×7的幺元和零元，各元素的逆元。解：代数系统N7,×7的运算表如表6.15所示，由表知幺元为1，零元为0，0无逆元，1的逆元为1，6的逆元为6，2和4，3和5互为逆元。6.设A,∗是代数系统，A是有限集，那么⑴当运算∗在A上是封闭的时，其运算表有何特征?⑵当运算∗是可交换运算时，其运算表有何特征?解：代数系统A,∗，A是有限集。⑴当运算∗在A上是封闭的时，其运算表中各元素的运算结果都是集合A中的元素。⑵当运算∗是可交换运算时，运算表关于主对角线是对称的。7.设A=1,3,5,7,9，∗是A上的二元运算，其定义分别为：⑴a∗b=min(a,b)⑵a∗b=a⑶a∗b=ab+a问：哪些运算满足幂等律？解：⑴满足幂等律。因为aA,a∗a=min(a,a)=a。⑵满足幂等律。因为aA,a∗a=a。⑶不满足幂等律。因为1∗1＝1×1＋1＝2≠18.写出N10,×10的所有幂等元。解：因为0×100=0，1×101=1，5×105=5，6×106=6，所以，0,1,5,6为幂等元。9.设A=1,2,3,4，A上的二元运算∗定义为取最大值运算，即a,bA，有a∗b=max(a,b)证明∗是可结合的运算，并指出代数系统A,∗的幺元、零元和各元素的逆元。解：作∗运算表如表6.17所示，由表知，幺元为1，零元为4，1的逆元为1，其余元素无逆元。(a∗b)∗c=max(max(a,b),c)表6.17∗123411234222343333444444第6章习题解答4a∗(b∗c)=max(a,max(b,c))以上两式都是取a，b，c三者中得最大者，所以①a≥b≥c和a≥c≥b时，(a∗b)∗c=a＝a∗(b∗c)②b≥a≥c和b≥c≥a时，(a∗b)∗c=b＝a∗(b∗c)③c≥a≥b和c≥b≥a时，(a∗b)∗c=c＝a∗(b∗c)即a,b,cA，(a∗b)∗c=a∗(b∗c)，∗运算满足结合律。10.设Z,∗是代数系统，∗的定义分别为：⑴a∗b=|a+b|，⑵a∗b=ab，⑶a∗b=a+b−1，⑷a∗b=a+2b，⑸a∗b=2ab。问：哪些运算在Z上是封闭的？哪些运算是可交换的？哪些运算是可结合的？解：Z为整数集合，⑴因为①整数加法运算在Z上封闭，绝对值运算在Z上也封闭。②a,bZ，a∗b=|a+b|=|b+a|=b∗a③当a＝1，b＝2，c＝-3时，(a∗b)∗c=||a+b|+c|=0，a∗(b∗c)=|a+|b+c||=2，(a∗b)∗c≠a∗(b∗c)。所以，∗运算在Z上封闭，可交换，但不可结合。⑵因为①当b＜0时，a∗b=ab不一定是整数，例如a＝2，b＝-1，a∗b=2-1Z，②a,bZ，a∗b=ab，b∗a=ba，a∗b不一定等于b∗a，例如a＝2，b＝1时，a∗b=ab=2，b∗a=ba=1。a∗b≠b∗a。③当a=2，b=1，c=2，(a∗b)∗c=(ab)∗c=(21)∗2=22=4，a∗(b∗c)=a∗(bc)=2∗(12)=2，(a∗b)∗c≠a∗(b∗c)。所以∗运算在Z上不封闭，不可交换，不可结合。⑶因为①整数加法和减法运算在Z上封闭，②a,bZ，a∗b=a＋b-1=b＋a-1=b∗a③a,b,cZ，(a∗b)∗c=(a＋b-1)＋c-1=a＋b＋c-2=a＋(b＋c-1)-1。所以，∗运算在Z上封闭，可交换，可结合。⑷因为①整数加法和乘法运算在Z上封闭。②a,bZ，a∗b=a＋2b，b∗a=b＋2a。a∗b不一定等于b∗a，如a＝1，b＝2时。a∗b=a＋2b=5，b∗a=b＋2a=4，a∗b≠b∗a。③a,b,cZ，(a∗b)∗c=(a＋2b)＋2c，a∗(b∗c)=a＋2(b＋2c)=a＋2b＋4c，当a＝0，b＝0，c＝1时，(a∗b)∗c=2，a∗(b∗c)=4，(a∗b)∗c≠a∗(b∗c)。所以，∗运算在Z上封闭，不可交换，也不可结合。⑸因为①整数乘法运算在Z上封闭，②a,bZ，a∗b=2ab=2ba=b∗a③a,b,cZ，(a∗b)∗c=2(2ab)∗c=4abc=2a×2bc=2a(b∗c)=a∗(b∗c)。所以，∗运算在Z上封闭，可交换，也可结合。第6章习题解答511.在代数系统Z,∗中，Z是整数集合，运算∗定义为a∗b=a＋b＋ab，证明运算∗在Z上是封闭的，∗是可交换的和可结合的，并指出其幺元。证明：①因为整数加法和乘法在整数集合Z上封闭，所以，∗运算在Z上是封闭的。②因为a∗b=a＋b＋ab=b＋a＋ba=b∗a，所以，∗运算在Z上是可交换的。③因为a∗0=a＋0＋a×0=a=0＋a＋0×a=0∗a，即0为∗运算的幺元。12.A,*是代数系统，其中A=a,b,c,d，且有b=a2，c=a3，d=a4，证明运算*是可交换运算。证明：a*b=a*a2=a3=a2*a=b*aa*c=a*a3=a4=a3*a=c*aa*d=a*a4=a5=a4*a=d*ab*c=a2*a3=a5=a3*a2=c*bb*d=a2*a4=a6=a4*a2=d*bc*d=a3*a4=a7=a4*a3=d*c即x,yA，x*y=y*x，所以，*运算是可交换的运算。13.写出N5,＋5的幺元和各元素的逆元。解：iN5，i＋50=i＋0=i=0＋i=0＋5i即0为＋5的幺元。当i＋j=j＋i=0时，i与j互为逆元，即1和4，2和3互为逆元，0的逆元为0。14.写出N5,×5的幺元和各元素的逆元(如果有逆元)。解：iN5，i×51=i=1×5i，所以，1为×5的幺元。2×53＝3×52＝1，4×54＝1，所以，0无逆元，1和4的逆元为自身，2和3互为逆元。15.请构造一个含幺元的代数系统，且除幺元外，其它元素都没有逆元。解：令A=a,b,c，∗是A上的二元运算，∗的运算表如表6.18所示。根据运算表，a为幺元，a的逆元为a，b和c无逆元。16.Nk,＋k,×k是代数系统，证明×k对于＋k是可分配的。解：根据＋k和×k的定义，一方面，因为a×(b＋c－k)=a×(b＋c)－ak，akmodk=0，所以a×(b＋c－k)modk=a×(b+c)modk，故a×k(b＋kc)=a×(b＋kc)modk=kcbkkcbakcbkcbamod)(mod)(=a×(b＋c)modk另一方面，当a×b＜k时，a×kb也可以看成是a×b除以k，商为0的余数，则a×kb=a×bmodk(a×b除以k的余数)，于是对于a,b,cNk,可设a×b＝ek+m，a×c＝fk+n，e,f,m,n为自然数，0≤m,n＜k。则a×kb=a×bmodk=m，a×kc=a×cmodk=n。当m＋n＜k时，a×(b+c)modk=(a×bmodk)+(a×cmodk)=m＋n当m＋n≥k时，a×(b+c)modk=(a×bmodk)+(a×cmodk)－k=m＋n－k将以上两式合并成一个式子：a×(b＋c)modk=(a×bmodk)＋k(a×cmodk)a×k(b＋kc)=a×(b＋c)modk=(a×bmodk)＋k(a×cmodk)=(a×kb)＋k(a×kc)表6.18*abcaabcbbbbccbc第6章习题解答6所以×k对＋k满足左分配律。因为＋k和×k在Nk上可交换，所以有(b＋kc)×ka=a×k(b＋kc)=(a×kb)＋k(a×kc)＝(b×ka)＋k(c×ka)即×k对＋k满足右分配律。所以，×k对＋k满足分配律。习题6.3给定Z2,+2和Z3,+3，其中Z2=[0],[1]，Z3=[0],[1],[2]。表6.10和表6.11分别给出+2和+3的运算，为简便记[i]为i，试求Z2×Z3,∗。解：Z2×Z3=[0],[0],[0],[1],[0],[2],[1],[0],[1],[1],[1],[2]a1,b1,a2,b2Z2×Z3，a1,b1∗a2,b2=a1+2a2,b1+3b2，则二元运算∗的运算表如表6.19所示：表6.19∗[0],[0][0],[1][