离散数学概论 第2版 习题及答案 第8章

习题册第8章1、设A=P({a,b})，写出A上的和∼运算的运算表，是否满足封闭性。答：由运算表可知和∼对于A都满足封闭性。2、设代数系统<A,*>，A中任意元素x和y,x*y=x+y+5xy,(1)判断*运算是否满足交换律和结合律，并说明理由.(2)求出*运算的单位元、零元和所有可逆元素的逆元.答：(1)*运算可交换，可结合.任取A中元素x,yx*y=x+y+5xy=y+x+5yx=y*x,任取A中元素x,y,z(x*y)*z=(x+y+5xy)+z+5(x+y+5xy)z=x+y+z+5xy+5xz+5yz+25xyzx*(y*z)=x+(y+z+5yz)+5x(y+z+5yz)=x+y+z+5xy+5xz+5yz+25xyz(x*y)*z=x*(y*z)(2)设*运算的单位元和零元分别为e和θ，则对于任意x有x*e=x成立，即x+e+5xe=x则e=0由于*运算可交换，所以0是幺元。对于任意x有x*θ=θ成立，即x+θ+5xθ=θx+5xθ=0θ=-1/5对于任意x，设x的逆元为y,则有x*y=0成立，即x+y+5xy=0(5x+1)y=-xy=-x/(5x+1)(x≠-1/5)因此当x≠-1/5时，-x/(5x+1)是x的逆元。3、设*是集合A上可结合的二元运算，且a,bA,若a*b=b*a，则a=b。试证明：（1）aA,a*a=a，即a是等幂元；（2）a,bA,a*b*a=a;（3）a,b,cA,a*b*c=a*c。证明：（1）aA,记b=a*a。因为*是可结合的，故有b*a=(a*a)*a=a*(a*a)=a*b。由已知条件可得a=a*a。（2）a,bA,因为由（1），a*(a*b*a)=(a*a)*(b*a)=a*(b*a),(a*b*a)*a=(a*b)*(a*a)=(a*b)*a=a*(b*a)。故a*(a*b*a)=(a*b*a)*a，从而a*b*a=a。（3）a,b,cA,（a*b*c）*（a*c）=（（a*b*c）*a）*c=(a*(b*c)*a)*c且(a*c)*(a*b*c)=a*(c*(a*b*c))=a*(c*(a*b)*c))。由（2）可知a*(b*c)*a=a且c*(a*b)*c=c，故（a*b*c）*（a*c）=(a*(b*c)*a)*c=a*c且(a*c)*(a*b*c)=a*(c*(a*b)*c))=a*c，即（a*b*c）*（a*c）=(a*c)*(a*b*c)。从而由已知条件知，a*b*c=a*c。4、证明代数系统(N3,+3)到(N6,+6)单一同态。证明：今构造映射函数如下：f(0)=0,f(1)=2,f(2)=4,试证明f是同态映射。函数f写成f(k)=2k，f(a+3b)=2(a+3b)=2(a+b-3[(a+b)/3])=2a+2b-6[(2a+2b)/6]=2a+62b=f(a)+6f(b)所以代数系统(N3,+3)到(N6,+6)存在同态映射f,f为单一同态。5、设<A,*>为半群，aA。令Aa={ai|iI+}。试证<Aa,*>是<A,*>的子半群。证明：b，cAa，则存在k,lI+，使得b=ak,c=al。从而b*c=ak*al=ak+l。因为k+lI+，所以b*cAa，即Aa关于运算*封闭。故<Aa,*>是<A,*>的子半群。6、Z上的二元运算*定义为：a,bZ，a*b=a+b-2。试证：<Z,*>为独异点。证明：（1）a,bZ，a+b-2Z，满足封闭性。（2）a,b,cZ，(a*b)*c=(a*b)+c-2=(a+b-2)+c-2=a+b+c-4,a*(b*c)=a+(b*c)-2=a+(b+c-2)-2=a+b+c-4。故(a*b)*c=a*(b*c)，从而*满足结合律。（3）记e=2。对aZ，a*2=a+2-2=a=2+a-2=2*a.。故e=2是Z关于运算*的单位元。综上所述，<Z,*>为独异点。设（A,*）是一个独异点，使得对于A中每个x，x*x=e，其中e是单位元，证明（A，*）是阿贝尔群。证明：每个xA逆元均为自己，(A,*)是群。a*b=a*e*b=a*((a*b)*(a*b))*b=(a*a)*(b*a)*(b*b)=e*(b*a)*e=b*a(可交换)。8、设<G,>是一个群，则对于a,b∈G，必有唯一的x∈G，使得ax=b。证明：因为a-1*b∈G，且a*(a-1*b)=(a*a-1)*b=e*b=b，所以对于a,b∈G，必有x∈G，使得ax=b。若x1,x2都满足要求。即ax1=b且ax2=b。故ax1=ax2。由于*满足消去律，故x1=x2。从而对于a,b∈G，必有唯一的x∈G，使得ax=b。设<A,>是群，A中元素a,b，且a的阶数是2，b的阶数是3，如果a*b=b*a，证明a*b是6阶元素。证明：由于a*b=b*a，所以(a*b)6=a6*b6=e现再证6是使(a*b)6=e的最小正整数。根据定理7.3.8：设<A,*>为群，a是A中元素，且a的阶数为k，若an=e，n是k的整数倍。若a*b是k阶元素，k只能是6的因子，即ｋ只能是2，3，6。由于(a*b)2＝a2*b2＝ｅ*b2＝b2≠ｅ；(a*b)3＝a3*b3＝a3*e＝a≠ｅ；由此可知其阶数为6。10、证明代数系统（｛1,i,-1,-i｝，·）和代数系统（｛｝,o）是否都是群，·是复数乘法，o是矩阵乘法，并且判别是否同构。解：（1）写出（｛1,i,-1,-i｝，·）的运算表·1i-1-i11i-1-iii-1-i1-1-1-i1i-i-i1i-1通过运算表可以看出具有封闭性，复数乘法满足结合性，幺元为1，i与-i互为逆元，-1逆元等于本身，所以（｛1,i,-1,-i｝，·）是群。写出（｛｝,o）的运算表·通过运算表可以看出具有封闭性，矩阵乘法满足结合性，幺元为，每个元素的逆元等于本身，所以（｛1,i,-1,-i｝，·）是群。根据运算表得到（｛1,i,-1,-i｝，·）中e=1,（｛｝,o），e=且（｛1,i,-1,-i｝，·）中i与-i互逆，而（｛｝,o）每个元素都是自己的逆，因此不同构。11、设群G的运算表如表所示，求出每个元素的阶数，并构造所有子群。解：通过运算表可以看出a为幺元。分别找出其他元素的阶数，b阶数为6，b的逆元为f,f阶数也为6。c阶数为3，c的逆元e，所以e阶数也为3。d阶数为2。子群：一阶子群{a},二阶子群{d1,d2}={a,d},三阶子群{c1,c2,c3}={c,e,a},六阶子群{a,b,c,d,e,f}。12、设群<B,*>为群<A,*>的子群，它是群<A,*>的正规子群(a)(a∈A→aBa-1B)。证明充分性：假设对任意aA，有aBa-1B，再证aB=Ba。令a*baB。因aBa-1B，则对某个b1B，有a*b*a-1=b1于是a*B=(a*B*a-1)*a=b1*a可见b1*aBa故aBBa只要注意：a-1Ba=a-1B(a-1)-1B，可类似地证明BaaB，于是aB=Ba。必要性：假设对每个aG，有aBBa且a*B*a-1aBa-1。则因aB=Ba，必存在b1B，使得a*B=b1*a于是a*B*a-1=(b1*a)*a-1=b1因此a*B*a-1B，故aBa-1B。设A={1,-1,i,-i},对于复数的乘法运算，证明<A,*>是循环群。解：幺元为1，(-1)2=1,-1是二阶元素，i2=-1，i3=-i，i4=1，所以i为四阶元素，(-i)2=-1，(-i)3=i，(-i)4=1，所以-i为四阶元素，由上述可得i和-i都是生成元，所以<A,*>是循环群。I上的二元运算*定义为：a,bI，a*b=a+b-2。试问<I,*>是循环群吗？解：<I,*>是循环群。因为<I,*>是无限阶的循环群，则它只有两个生成元。1和3是它的两个生成元。因为an=na-2(n-1)，故1n=n-2(n-1)=2-n。从而对任一个kI,k=2-(2-k)=12-k，故1是的生成元。又因为1和3关于*互为逆元，故3也是<I,*>的生成元。15、证明群(N12,+12)和群(N13-{0},×13)同构,并写出同构映射,并写出群(N13-{0},×13)所有的子群。(1)群(N12,+12)的生成元为1，(N13-{0},×13)的生成元为,2，20=1,21=2,22=4,23=8,24=3,25=6,26=12,27=11,28=9,29=5,210=10,211=7,212=1，根据定理k阶循环群同构于(Nk,+k)，f(k)=ak，a为生成元，可得群(N12,+12)和群(N13-{0},×13)同构。(2)设置函数f：N12→N13-{0}，f(k)=ak=2kf(0)=20=1，f(1)=21=2，f(2)=22,...,f(11)=211可得证f(i+j)=2i+j=2i×132j=f(i)×13f(j)。根据(N12,+12)的子群{0},{0,6},{0,4,8},{0,3,6,9},{0,2,4,6,8,10},N12(N13-{0},×13)的子群群{20},{20,26},{20,24,28},{20,23,26,29},{20,22,24,26,28,210},N13-{0}。16、求循环群C12={e,a,a2,…,a11}中H={e,a4,a8}的所有右陪集。解：因为|C12|=12，|H|=3，所以H的不同右陪集有4个：H，{a,a5,a9},{a2,a6,a10},{a3,a7,a11}。17、设e是奇数阶交换群<G,*>的单位元，则G的所有元素之积为e。证明：设G=<{e,a,a,…,a},*>，n为正整数。因为G的阶数为奇数2n+1，所以由拉格朗日定理知G中不存在2阶元素，即除了单位元e以外，G的所有元素的阶都大于2。故对G中的任一非单位元a，它的逆元a不是它本身，且G中不同的元素有不同的逆元。由此可见，G中的2n个非单位元构成互为逆元的n对元素。因为G是交换群，故G的所有元素之积可变成单位元和n对互为逆元的元素之积的积，从而结果为e。18、6阶群必有3阶子群。证明设<A,>是是6阶群，e是幺元。A中元素的阶数可能为1，2，3或6。如果A中有6阶元a，即o(a)=6，则G是6阶循环群，a2为3阶元素，得知({a2,a4,a6}，*)为3阶子群。如果A中有3阶元a，({a,a2,a3}，*)为3阶子群。如果非幺元都是2阶元素，则为克莱因群，克莱因群一定是可交换群，在A中任取两个不同的非幺元的a和b,令H={e,a,b,a*b}，通过验证可知，*对于H是封闭的，(H,*)是(A，)的4阶子群，而(A，*)是6阶群，根据Lagrange定理，这是不可能的。得证6阶群必有3阶子群。19、在4次对称群中找出一个4阶置换循环群，并在该4阶置换循环群中找出2阶子群。解：（1）根据定理每一个n阶有限群和一个n次置换群同构。所以构造一个4阶循环群+4012300123112302230133012相对应将标题与各行构造置换*f0f1f2f3f0f0f1f2f3f1f1f2f3f0f2f2f3f0f1f3f3f0f1f2由运算表可知，f1为该群生成元。所以4阶置换群{f0,f1,f2,f3}为循环群。（2）找出其中2阶元素f2，由{f0,f2}构造了2阶子群。20、判断下列集合和给定运算是否构成环、整环和域,如果不构成,说明理由.(1)运算为实数加法和乘法。(2)A={5z|z∈Z},运算为实数加法和乘法。(3)A={x|x≥0∧x∈Z},运算为实数加法和乘法。解(1)不是环,因为关于乘法不封闭。(2)是环,不是整环和域,因为乘法没有么元。(3)不是环,因为正整数关于加法的负元不存在。21设<A,+,×>是环，对于A中每一个a，都有a2=a，证明如果A中元素个数大于2，那么<A,+,×>不可能是整环。证明：反正法，如果<A,+,×>是整环，且有三个及以上的元素，则存在A中有元素a,a≠0，a≠1，且a2=a，即a≠0，a-1≠0，且a×(a-1)=0,这与整群中的无零因子条件矛盾，所以那么<A,+,×>不可能是整环。构造一个仅有3个元素的域。解：(N3,+3,×3)是一个仅有三个元素的域，(N3,+3)为可交换群，(N3-{0},×3)为可交换群，×3对于+3满足可分配，所以是域。第9章1、下列各集合对于整除关系都构成偏序集，判断哪些偏序集是格。(1)A={1,2,3,4,7} (2)A={1,2,3,6,24}解：(1)设R是A上的整除关系。R={<x,y>|x∈L∧y∈L∧x整除y}={<1,2>,<1,3>,<1,4>,<1,7>,<2,4>}∪IA它的盖住关系为：COVA＝{<1,2>,<1,3>,<1,7>,<2,4>}。因为{3,7}无上界，因而无最小上界，<A,R>不是格。(2)设R是A上的整除关系。R={<1,2>,<1,3>,<1,6>,<1,24>,<2,6>,<2,12>,<3,6><3,24><6,24>}∪IA它的盖住关系为：COVA＝{<1,2>,<1,3>,<2,6>,<3,6>,<6,24>}。<A,R>是格。2、求下列命题的对偶命题。(1)a∨(b∧c)≤(a∨b)∧(a∨c)(2)(a∨b)∧c≥a∨(b∧c)解：(1)a∧(b∨c)≥(a∧b)∨(a∧c)(2)(a∧b)∨c≤a∧(b∨c)3、设<A,≤>是格，对任意a,b∈A，都有a∨(a∧b)=aa∧(a∨b)=a解：先证明:a∨(a∧b)=a。因为a≤a∧b和a≤a，可见a是a∧b和a的下界，故a≤a∨a∧b。另一方面，根据glb的定义，有a∨a∧b≤a。因此a∨(a∧b)=a。类似可证a∧(a∨b)=a。4、设<A,≤>是格，a,b,c∈A，满足a≤b≤c，证明a∨b=b∧c。证明：由定理，a≤b得到a∨b=bb≤c得到b∧c=b所以，a∨b=b=b∧c。5、设<A,∨,∧>，是格，a,b,c,dA。试证：若ab且cd，则a∧cb∧d。证明：因为ab，cd，所以a=a∧b,c=c∧d。从而(a∧c)∧(b∧d)=((a∧c)∧b)∧d=(b∧(a∧c))∧d=((b∧a)∧c)∧d=a∧(c∧d)=a∧c，所以a∧cb∧d。6、证明：在同构意义下，4