离散数学修订版耿素云清华大学课后答案

1、资料内容仅供您学习参考，如有不当之处，请联系改正或者删除第一章部分课后习题参考答案16设p、q的真值为0；r、s的真值为1,求下列各命题公式的真值.(l)pV(qAr)O0V(0A1)<=>0(2) (pr)八(fVs)O(OT)八(1V1)OOAlOO.(3) (AqAr)<-(pAqA-)<=>(1AlAl)i(0八0A0)<=>0(4) (»rAs)f(PAq)<=>(0Al)f(1AO)<=>0->00117.判断下面一段论述是否为真：“乃是无理数。并且，如果3是无理数，则后也是无理数.另外6能被2整除，

2、6才能被4整除。”答：P：万是无理数1q：3是无理数0r：我是无理数16能被2整除1t：6能被4整除0命题符号化为：P八(q-r)A(t-s)的真值为1,所以这一段的论述为真。19.用真值表判断下列公式的类型：(4) (pq)f(rqrp)(5) (pAr)('pAq)(6) (pfq)八(q-r)f(p->r)答：pqpfqrqrprqfrP(pfq)f(qfrP)所以公式类型为永真式(5)公式类型为可满足式(方法如上例)(6)公式类型为永真式(方法如上例)第二章部分课后习题参考答案3.用等值演算法判断下列公式的类型，对不是重言式的可满足式,再用真值表法求出成真赋值。(1尸(p

3、八q-q)(2)(p-(pVq)V(p-*r)(3)(pVq)(pAr)答：(2)(p-*(pVq)V(p-*r)<=>LpV(pVq)V5pVr)<=>VpVqVr<=>1所以公式类型为永真式3 / 29资料内容仅供您学习参考，如有不当之处，请联系改正或者删除(3)PqrpVqpAr(pVq)-*(pAr)000001001001010100011100100100101111110100min所以公式类型为可满足式4.用等值演算法证明下而等值式：(2)(pfq)A(p-*r)<=>(p-*(qAr)(4) (pA-'q)VCpAq)&

4、lt;=>(pVq)八(pAq)证明(2)(p-*q)A(p-*r)<=>(-»pVq)A("pVr)<=>"'pV(qAr)Op(qAr)(4) (pAq)V(pAq)<=>(pV(pAq)A(qV(pAq)<=>(pV-»p)A(pVq)A(qV-'p)ALqVq)<=>IA(pVq)A-1(pAq)Al<=>(pVq)A(pAq)5.求下列公式的主析取范式与主合取范式,并求成真赋值(1) (-1p-*q)(-'qVp)(2) -1(p-*q)AqA

5、r(3) (pV(qAr)一(pVqVr)解：(1)主析取范式(ip->q)-*(-»qvp)(pVq)V(,qvp)八rq)vLqVp)=(-»pA-»q)V(-1qAp)V(-1qA«p)V(pAq)V(pAq)=(-Aq)V(pA->q)V(paq)=m()vm2vm3U>E(0,2,3)主合取范式：(ip-*q)qvp)(pVq)VLqvp)O(p/rq)VLqVp)=(-»pv("1qvp)A(-»qv(qvp)01八(pVq)U>(pv-1q)0Ml<=>n(1)(2)主合取范

6、式为：(pq)/q八:r=(Vq)AqAr=(pA-»q)八q/r00所以该式为矛盾式.主合取范式为n(0,1,2,3,4,5,6,7)矛盾式的主析取范式为0(3)主合取范式为：(pV(qAr)f(pVqVr)O(pv(q/r)(pVqVr)OLpA(-1qVrr)V(pVqVr)OLpv(pvqvr)A(-'qv-»r)v(pvqvr)<>1A1O1所以该式为永真式。永真式的主合取范式为1主析取范式为£(0,1,2,3,4,5,6,7)第三章部分课后习题参考答案14.在自然推理系统P中构造下而推理的证明：(2)前提：p-q,-i(qAr)tr

7、结论：-1p(4)前提：q>p,q-s,st,tAr结论：p/q证明：(2)一i(q八r)前提引入-iqv-ir置换qfIr蕴含等值式r前提引入一iq拒取式pfq前提引入P(3)拒取式证明(4):t/r前提引入t化简律q“s前提引入s2t前提引入q“t等价三段论A(t->q)置换(q-t)化简q假言推理qfP前提引入P假言推理(11)p/q合取15在自然推理系统P中用附加前提法证明下面各推理:(1)前提：p->(q>r),s>p,q结论：s>r证明s附加前提引入sfp前提引入P假言推理p>(q>r)前提引入qfr假言推理Q前提引入r假言推理16在

8、自然推理系统P中用归谬法证明下而各推理：(1)前提:p>iq,>rVq,rAs结论：-ip证明：p结论的否定引入Pf'Q前提引入3 / 29资料内容仅供您学习参考，如有不当之处，请联系改正或者删除q假言推理一1rvq前提引入r化简律r/s前提引入r化筒律r八rr合取由于最后一步r八是矛盾式,所以推理正确.第四章部分课后习题参考答案3。在一阶逻辑中将下而将下面命题符号化，并分别讨论个体域限制为(a),(b)条件时命题的真值:(1)对于任意x,均有一一2二(x+、：2)(x7?).(2)存在x,使得x+5=9。其中(a)个体域为自然数集合.(b)个体域为实数集合.解：F(x)：

9、x2-2=(x+6(xr2).G(x)：x+5=90(1)在两个个体域中都解释为Vx尸(x),在Q)中为假命题，在(b)中为真命题。(2)在两个个体域中都解释为王G(x),在(a)(b)中均为真命题。4»在一阶逻辑中将下列命题符号化：(1)没有不能表示成分数的有理数.(2)在北京卖菜的人不全是外地人.解：(1)F(x):x能表示成分数H(x):x是有理数命题符号化为:-nBxC-tFCx)aH(X)(2)F(x):x是北京卖菜的人H(x)：x是外地人命题符号化为：Dx(f(x)-“(X)5.在一阶逻辑将下列命题符号化：(1)火车都比轮船快.(3)不存在比所有火车都快的汽车.解：(1)

10、F(X)：x是火车;G(x):x是轮船;H(x,y)：x比y快命题符号化为：VxVy(F(x)aG(y)-H(x,y)(2)(1)F(x)：x是火车;G(x):x是汽车；H(x,y):x比y快命题符号化为:力(G(y)aVx(F(x)fH(x,y)9.给定解释I如下：(a)个体域D为实数集合R.(b)D中特定元素£=0.(c)特定函数f(x,y)=xy,x,ye£)。(d)特定谓词P(x,y)：x=y,G(x,y)：x<y,x,yeD»(1)说明下列公式在I下的含义，并指出各公式的真值：(2)VxVy(G(x,y)t->F(x,y)VaV><

11、;F(/(x,y),a)TG(x,y)答：(D对于任意两个实数x,y,如果x(y,那么xHy.真值1.(2)对于任意两个实数x,如果x-y=O,那么xy,真值0。10o给定解释I如下：(a)个体域DK(N为自然数集合).(b)D中特定元素m二2.(c)D上函数=x+y,g(x,y)=xyo(d)D上谓词P(x,y)：x=y.说明下列各式在I下的含义，并讨论其真值。(1) VxF(g(x,a),x)(2) VxVy(F(f(x,a)»y)-*F(f(y,a),x)答：(1)对于任意自然数x,都有2x=x,真值0.(2)对于任意两个自然数x,y,使得如果x+2=y,那么y+2r.真值0.

12、11.判断下列各式的类型：(1)F(xy)T(G-y)TF(x,y).(3)VKSyF(x,y)-BxVyF(x,y)0解：(1)因为Pf(qf)=V(->“v)O1为永真式；所以Fx,y)一(G(x,y)-F(x,y),为永真式；(3)取解释I个体域为全体实数F(x,y)：x+y=5所以，前件为任意实数x存在实数y使x+y=5,前件真；后件为存在实数x对任意实数v都有x+y=5,后件假,此时为假命题再取解释I个体域为自然数N,F(x,y)：x+y=5所以，前件为任意自然数x存在自然数y使x+y=5,前件假。此时为假命题。此公式为非永真式的可满足式.13.给定下列各公式一个成真的解释,一

13、个成假的解释.(1)VX(F(x)vG(k)(2)3x(F(x)AG(x)AH(x)解：(D个体域：本班同学F(x)：x会吃饭，G(x)：x会睡觉。成真解释F(x)：x是泰安人，G(x)：x是济南人.(2)成假解释(2)个体域：泰山学院的学生F(x)：x出生在山东,G(x):x出生在北京，H(x)：x出生在江苏，成假解释.F(x)：x会吃饭,G(x)：x会睡觉，H(x)：x会呼吸.成真解释.第五章部分课后习题参考答案5。给定解释1如下：(a)个体域D二域，4;(b)/U)为，=4/(4)=3<c)F(x,丁)为取3,3)=F(4,4)=0,-(3,4)=万(4,3)=1。试求下列公式在I

14、下的真值.(1)V.r3yF(x,y)(3)VxVy(/(x,y).F(/(x),/(y)解:(1)Vx卞F(x,y)=Vx(F(x,3)vF(x,4)<=>(F(3,3)vF(3,4)a(F(4,3)v/(4,4)<»(0v1)a(1v0)<=>1(2)VWy(FUj)fF(/(x),/(y)=Va(F(x,3)fF(/(x),/(3)a(FU4)tF(/(x),/(4)oVx(S(x,3)tF(/(x),4)a(F(x,4)->F(/(x)3)=(F(3,3)tF(/(3),4)a(F(3,4)-2/(3),3)a(F(4,3)-F(/(4),

15、4)a(F(4,4)fF(/(4),3)<=>(0->F(4,4)a(F(3,4)fF(4,3)a(1->F(3,4)八(0一尸(3,3)<=>(00)a(1->1)A(11)A(0->0)0112.求下列各式的前束范式。(1)fVyG(x,)，)(5)3xJF(x1,x2)->(”(X1)-3x2G(xx2)(本题课本上有错误)解：(DVxF(x)tV)，G(x,y)oVxF(x)tVyG(r,y)=3xVy(F(x)-G(r,y)(5) 3x,F(X|,x2)->(7/(Xj)->-Bx2G(xl,x2)<=>B

16、xlF(xl,x2)->("(.)->Vx2-iG(x3,x2)=叫尸(再,匕)->Vx2(77(x3)-iG(x3,x2)=VxKw(E(X1,X4)一("*3)G*3，X2)15.在自然数推理系统F中，构造下面推理的证明：前提：上户(外TV>'(F(y)VG(y)tR(y),3aF(a)结论:3xR(x)(2)前提：Vx(F(x)-(G(a)AR(x),3xF(x)结论-x(F(x)AR(x)证明玉"(x)前提引入F(c)EI王F(x)tVy(F(y)vG(y)TR(y)前提引入Vy(F(y)vG(y)-R(y)假言推理(F(c

17、)VG(c)-R(c)UIF(c)VG(c)附加R(c)假言推理mxR(x)EG(2)mxF(x)前提引入F(c)EIVx(F(x)-(G(a)AR(x)前提引入F(c)-*(G(a)AR(c)UIG(a)AR(c)假言推理R(c)化简F(c)AR(c)合取引入二(F(x)AR(x)©EG第六章部分课后习题参考答案5.确定下列命题是否为真：(1) 0q0真(2) 0£0假(3) 0c0真(4) 0e(0M(5) a,bCa,b,c,a,b,c真(6) a,bea,b,c,a»b真(7)a,bqa,b,a,b)真(8)a,bea,b,a,b)假6.设a,b,c各不相

18、同，判断下述等式中哪个等式为真：(1)a,b,c,0二a,b),c)假(2) a,b,a=a,b)真(3) a,b=a,b)假(4) 0,0,a,b=0,0,a,b假8.求下列集合的弃集：(1) a,b»cP(A)=0,a,b,c»a,b,a,cb,c),a,b,c(2) 1,2,3P(A)=0,1,2,3,1,2,30P(A)=0,0)(4) 0,0P(A)=0,，2,3,1,314.化简下列集合表达式：(1)(aUb)Ab)-(aUb)(2)(AUBUO-(BUC)UA解：(i)(aUb)Ab)(aUb)=(aUb)Db)PT(aUb)=(AUB)nsub)db=0ab

19、=o(2)(aUbUo-(bUc»Ua=(aUbUon(bUc)Ua二(An(BUO)u(BUc)n(buo)ua=(Rd(bUc)U0Ua=(aD(bUO)Ua二a18.某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。已知6个会打网球的人都会打篮球或排球。求不会打球的人数。解:阿A二会打篮球的人),B二会打排球的人,C二会打网球的人)9 / 29资料内容仅供您学习参考，如有不当之处，请联系改正或者删除IAI=14,BI=12aAb=6,aAc=5,aAbCIc=2,C；=6,CcAljB如图所示。TT-厘土 必25

20、(5+4+2+3)-51=25-14-5-1=5不会打球的人共5人21.设集合人=1,2,2,3,1,3,0，计算下列表达式:(1)UA(2)0A(3)AUA(4)unA解：(1)UA=1,2U2,3U1,3U0=1,2,3,01(2)nA=i,2)n2,3)n1,3n01=0(3)nua=ih2n3n0=0(4)una=o27、设A,B,C是任意集合，证明(1) (AB)-C=ABuc(2) (AB)C=(A-C)(B-C)证明(1) (A-B)C=(aA-B)A-C=aA(bDc)+n(b=C)=ABuC(2) (A-C)-(B-C)=(Ap|C)n(Bp)c)二(AfiC)D(BlJC)

21、=(acicnB)u(Ancnc)=(AncnB)u0二An(BuC)二ABuC由(1)得证。第七章部分课后习题参考答案7。列出集合A=2,3,4)上的恒等关系L,全域关系Ea，小于或等于关系La,整除关系Da。解:1尸(2,2>,<3,3>,<4,4Ea=<2,2>,<2,3>,<2,4，<3,4>,<4,4),3,2，3,3，<4,2，(4,3»U=<2,2>,<2,3>,<2,4),<3,3>,<3,4>,<4,4)Da=(<2,4)1

22、3。设A=vl,2>,v2,4>,<3,3B=<1,3，(2,4),4,2>求A=B,ACB,domA,domB,dom(AJB)janAjanB,ran(AnB)>fid(AB).解：AB=<1,2>,<2,4>,<3,3，<1,3，4,2AnB=<2,4>doniA1>2,3domB=1,2,4dom(AVB)=1,2,3,4ranA=2,3,4)ranB=2>3,4ran(AnB)=4A-B=<L2>,3,3,fld(AB)=1,2,3)14o设R=0,lx0.2>>0

23、,3>,1,2，1,3，2,3)求RoR.RLRT0,1,RI,2解：RoR=(<0,2),<0,3),<1,3>R",=<l,0>,<2,0>,<3,0>,<2,R,<3,D,<3,2>rT0,l=<0,1>,(0,2，<0,3>,<b2>,1,3>)R1,2=ran(R|1,2)=2,316.设A=a,b,c,d).&R?为A上的关系，其中%=哂，色)&=*),(b,c),(byd),求&o&Ry耳r：g3。解：R：。

24、良二(a,d>,<a,c),<a,d)R二。R尸<c,d>)R.=R.oR.=(a,a),<a»b)，(a,d)R；二良。在二<b,b),<c>c>,(c,d>)R；二艮。艮'=<b,c)，<c,b>,<b,d>36.设A=1,2,3,4,在AxA上定义二元关系R,V<u,v>,<x,y>AxA»u,vR(x,y)<z>u+y=x+v.(1)证明R是AxA上的等价关系。(2)确定由R引起的对AxA的划分.(1)证明：:u,v>R(

25、x,y)<=>u+y=xyA<u,v>R<x>y)<=>u-v=xyV(u>v>AxA /U-V=U-V#/29资料内容仅供您学习参考，如有不当之处，请联系改正或者删除，(utv)Ru,v> .R是自反的任意的u,v>，x,y)WAXA如果(u,v)R<x,y),那么uv=x-y/.x-y=uv/.<x,y)R(u,v>，R是对称的任意的<u,v>,x,y>,<a,b)GAXA若(u,v>R<x,y>,x,y>R<a,b>贝lju-v=xy,xy

26、=a-b/.u-v=ab/.<u,v>R(a,b) .R是传递的R是AXA上的等价关系(2)n=<1,1>,<2,2>,<3,3>,<4,4),<2,1>,<3,2>,4,3,<3,1>,<4,2>,<4,1>),<1,2>,<2,3，<3,4>,<1，3>,(2,4),(b4)41o设人=1,2,3,4.R为AxA上的二元关系,Va,b>,(c,d)AxA,a,b>R(c,d><=>a+b=c+d(1)证明R

27、为等价关系。(2)求R导出的划分。(1)证明：V<atb>AxAa+b=a+b/.a,b>Ra,b> .R是自反的任意的<a,b，<c,d>GAXA设<&,b)R<c,d>,则a+b=c+d c+d=a+b/.(ctd>R(a,b> ,»R是对称的任意的a,b),c,d，<x,y>EAXA若(atb>R<c>d)，<c,dR<x,y)则a+b=c+d,c+d=x+ya+b=x+y/.<a,b>R<x,y) R是传递的 R是AXA上的等价关系(2)

28、n=(b1),<1,2，<2,1>,(b3>,<2,2>,3,1),(<1,4>t<4,1>,<2,3>,3,2>),29 / 29<2,4,<4,2，3,3,<3,4>,<4,3,<4,4>43。对于下列集合与整除关系画出哈斯图:(1) 1> 2,3, 4,6,8, 12,24)1,2,3,4, 5, 6, 7, 8,9, 10,11, 12)(2)1210695711(1) (2)的哈斯图。45o(a)(b)分别写出集合A和偏序关系Ry的集合表达式.解:下图是两个偏

29、序集(a) A=a, b,c,d,e, f, gRy 二,a, b>, a, c),、a, d/ ,a, e>,a, f>a, g>,b, d>, <b, e), (c, f) ,c, g) (b)A=a,b,c,d,Ry=a,b>,<a,c>,<a,d>,<a,e>,<a,f>,(d»f>t<e,f)kJIA46c分别画出下列各偏序集A,RY的哈斯图,并找出A的极大元、极小元、最大元和最小元.(1)A0,9b9c,d,c)Ry二a,d>,<a,c>,<a,b

30、，e>,b,e，(c,e),(d,e>=L.解:(2) A= (a, b, c, d,e ,Ry =c, d> 5A.(1)(2)项目(1)(2)极大元：ea,b,d,e极小元:aa,b,c,e最大元:e无最小元:a无第八章部分课后习题参考答案1.设f：NfN,且1,若X为奇数若X为偶数求f(0),f(0),f(1),f(1)J(0,2,4,6,),f(4.6,8),1(3,5,7).解：f(0)=0,f(0)=0,f(l)=bf(1)=1,f(0,2,4,6,)=N,f(4,6,8)=2,3,4)(3,5,7)=6,10,14。4。判断下列函数中哪些是满射的?哪些是单射的？

31、哪些是双射的？(1) f:NfN,f(x)=x?+2不是满射，不是单射(2) f:N->N,f(x)=(x)mod3,x除以3的余数不是满射，不是单射1,若x为奇数.、.、，(3) f:N>Ntf(x)=s中.“不是满射，不是单射0,右x为偶数(4)f:N>0,1.f(x)=,F业,是满射，不是单射1，若X为偶数(5)f:N-0->R,f(x)=lgx不是满射，是单射(6)f：R>R.f(x)=x2-2x15不是满射,不是单射5。设*=a,b,c,d,Y=L2,3,f=(a,1>,<b,2>,<c,3>,判断以下命题的真假:(1)f是

32、从X到Y的二元关系，但不是从X到Y的函数;对(2) f是从X到Y的函数，但不是满射，也不是单射的;错(3) f是从X到Y的满射，但不是单射;错（4）f是从X到Y的双射.错第十章部分课后习题参考答案(4) 断下列集合对所给的二元运算是否封闭：（1）整数集合Z和普通的减法运算.封闭，不满足交换律和结合律，无零元和单位元（2）非零整数集合Z和普通的除法运算。不封闭（3）全体实矩阵集合M“（r）和矩阵加法及乘法运算其中n>2a封闭均满足交换律，结合律，乘法对加法满足分配律；加法单位元是零矩阵，无零元；乘法单位元是单位矩阵，零元是零矩阵；（4）全体x实可逆矩阵集合关于矩阵加法及乘法运算，其中1）工

33、2。不封闭（5）正实数集合Ri和。运算，其中。运算定义为：Ba,bER1,a°b=ab-a-b不封闭因为。i=ix1-1-1=-1任R-（6） n6Z+,nZ=nz|z6Z.nZ关于普通的加法和乘法运算.封闭，均满足交换律，结合律，乘法对加法满足分配律加法单位元是0,无零元；乘法无单位元（>1）,零元是0；"=1单位元是1（7） A=%,%一，小h】工2.。运算定义如下：Va,beA,a°b=图闭不满足交换律，满足结合律，（8）S2x-11x6Z关于普通的加法和乘法运算。封闭均满足交换律，结合律，乘法对加法满足分配律（9）S=0,1,S是关于普通的加法和乘法

34、运算.加法不封闭，乘法封闭；乘法满足交换律，结合律（10）S=（xIx=2n6z'S关于普通的加法和乘法运算。加法不封闭，乘法封闭，乘法满足交换律,结合律5 .对于上题中封闭的二元运算判断是否适合交换律，结合律，分配律。见上题7 .设*为Z+上的二元运算X*Y=min（x,y）,即x和y之中较小的数.(1)求4*6,7*3。4,3(2)*在Z-上是否适合交换律，结合律，和事等律？满足交换律，结合律，和器等律(3)求*运算的单位元，零元及Z+中所有可逆元素的逆元.单位元无，零元1,所有元素无逆元8 .S=Qx。为有理数集，*为5上的二元运算,Va,b),(x,y)6S有<a,b)*

35、x,y)=<ax,ay+b)(l)*运算在s上是否可交换，可结合？是否为事等的？不可交换：vx,y>*<a,b>=<xa,xb+y>丰<a,b>*<x,y>可结合：«a,b>*<x,y>)*<ctd>=<ax,ay+b>*<c,d>=<axc,axd+(ay+b)><a,b)*(x,y>*vc,(I)=<a,b>*(xc,xd+y>=<axc,a(xd+y)+b>(<a,b>*<x,y>)*&l

36、t;c,d>=<a,b>*(<x,y>*<c,d>)不是寨等的(2) 大运算是否有单位元，零元？如果有请指出，并求S中所有可逆元素的逆元。设va,b>是单位元Yvx,y>WS,<a,b>*<x,y>=<x,y>*(a,b>=<x,y>贝I)<ax,ay+b>=<xa,xb+y>=<x,y>，解的va,b=<l,0>,即为单位。设<a,b是零元，v<x,y>WS,<a,b>*x,y>=<x,y>

37、*<a,b>=<a,b>贝ljax,ay+b>=<xa,xb+y)=(a,b>,无解。即无零元。v<x,y>eS,设<a,b>是它的逆元<a,b>*<x,y)=<x,y>*<a,b>=<l,0><ax,ay+b>=<xab+y>=<L0)a=l/x,b=-y/x所以当XWO时，x,y10.令S=a,b,S上有四个运算：*,°，-和分别有表10.8确定.*ab0ab.ababaaaaababaaabbaabbabaabab(a)(b)(c

38、)(d)(1)这4个运算中哪些运算满足交换律，结合律，塞等律？(a)交换律，结合律，塞等律都满足，零元为a,没有单位元；(b)满足交换律和结合律，不满足塞等律，单位元为a,没有零元/尸=h(c)满足交换律，不满足塞等律,不满足结合律。(Z?。)=a。a=。，(a。b)。b=a。b=aa。(b。b)不(a。b)。b没有单位元，没有零元(d)不满足交换律，满足结合律和塞等律没有单位元，没有零元(1)求每个运算的单位元，零元以及每一个可逆元素的逆元。见上16.设V=(N,+,)，其中+,分别代表普通加法与乘法，对下而给定的每个集合确定它是否构成V的子代数，为什么？(1) sM2n|nEZ)是(2)

39、S=2n+1|nEZ不是加法不封闭(3)S户1,0,1)不是，加法不封闭第十一章部分课后习题参考答案8。设S二0,1,2,3),管为模4乘法，即“Vx,y£S,xgy=(xy)modi问<s,®>是否构成群？为什么？解：(1)Vx,yes,x®y=(xy)mod4GS,是S上的代数运算。(2)Vx,V，z£S,设xy=4k+r0<r<3(xay)&z=(xy)mod4)®z=r®z=(rz)modi=(4kz+rz)mod4=(4k+r)z)mod4=(xyz)modl同理x®(y®

40、z)=(xyz)mod4所以，(x®y)®z=x®(y®z)，结合律成立。(3) VxGS,(x®l)=<l®x)=x,所以1是单位元。(4) r,=1,3-1=3,0和2没有逆元所以，S,管不构成群9.设Z为整数集合，在Z上定义二元运算。如下：”Vx,y£Z,xoy=x+y-2问Z关于。运算能否构成群？为什么？解：(l)Vx,yZ,xoy=x+y-2eZ,。是Z上的代数运算°(2)Vx,y,z£Z,(xoy)oz=(x+y2)oz=(x+y-2)+z-2=x+y+z-4同理(xoy)oz=xo(y

41、oz),结合律成立。(3)设e是单位元，Vx£Z,xo”eox=x,即x+e2=e+x2=x,e=2(4) VxCZ,设x的逆元是y,xoy=yox=e,即x+y-2=y+x2=2,所以，x"=y=4-x所以Z,。构成群llo 设T 0<0 1-1 00 1-10-1卜，证明G关于矩阵乘法构成一个群.解：(l)Vx,y£G,易知xyWG,乘法是Z上的代数运算c(2)矩阵乘法满足结合律1 0、(3)设是单位元，0)(4)每个矩阵的逆元都是自己。所以G关于矩阵乘法构成一个群.14.设G为群，且存在a£G,使得G=a"|kGZ)证明：G是交换群

42、。证明：Vx,y£G,设x=y=a1,则xy=aka=d"=a1aK=yx所以，G是交换群17.设G为群，证明e为G中唯一的塞等元。证明：设%eG也是事等元，则e；=.,即由消去律知.=e18o设G为群，a,b,cGG,证明abcI=IbcaI=IcabI证明：先证设(皿cp=e=(bca)k=e设(abc)；=e,贝ij(aOc)(aZ?c)(aZ?c)=e,即a(bca)bca)(bca)-(bca)a-=e左边同乘a7，右边同乘“得bca)bcabca)-bed)=(bac)k=aea=e反过来，设bac)k=e,WJ(abc)k=e.由元素阶的定义知，abcI=ib

43、caI,同理IbcaI=Icab|19.证明：偶数阶群G必含2阶元。证明：设群G不含2阶元，YaeG,当”=。时，。是一阶元，当awe时，”至少是3阶元，因为群G时有限阶的，所以。是有限阶的，设，是k阶的，则,尸也是k阶的，所以高于3阶的元成对出现的,G不含2阶元，G含唯一的1阶元e,这与群G是偶数阶的矛盾.所以，偶数阶群G必含2阶元20.设G为非Abel群，证明G中存在非单位元a和b,aWb,且ab二ba.证明：先证明G含至少含3阶元。若G只含1阶元,则G二e,G为Abel群矛盾；若G除了1阶元e外，其余元均为2阶元，则/=e,Pa、beG*a=a,bx=b,(ab=所以ab=albl=(b

44、a)l=ba,与G为Abel群矛盾：所以,G含至少含一个3阶元,设为明则。,且，="J。令b=a的证。21 .设G是必(R)上的加法群,n，2,判断下述子集是否构成子群.(1)全体对称矩阵是子群(2)全体对角矩阵是子群(3)全体行列式大于等于。的矩阵。不是子群(4)全体上(下)三角矩阵。是子群22 .设G为群,a是G中给定元素，a的正规化子N(a)表示G中与a可交换的元素构成的集合，即N(a)=xIxGGAxa=ax证明N(a)构成G的子群。证明:ea=ae,eeN(a)工(/)Vx,yeN(a),则ax=xa,ay=yaa(冷')=(x")y=x(ay)=x(y&

45、#171;)=(xy)a,所以町eN(。)由cix=xa,得=xxaxxae=eax,即xla=ax,所以x"eN(a)所以N(a)构成G的子群31.设外是群G：到&的同态，外是G二到G,的同态,证明9：。0二是G；到G,的同态。证明：有己知是G,到G二的函数，°二是G二到以的函数，则夕一夕二是G,到G,的函数.Va,b e G,(0。(p2)(ab)=%(帅)=%(0(a)。、)=(%3(«)(92S)=。例)()(/°gX。)所以：外仍是1到Gs的同态。33.证明循环群一定是阿贝尔群,说明阿贝尔群是否一定为循环群，并证明你的结论。证明：设G是

46、循环群，令G=(a>,令x =那么xy = a a1 = a"k = ad =)，x,g是阿贝尔群克莱因四元群，G=e,a,Acc方是交换群，但不是循环群,因为e是一阶元，a.b.c是二阶元.36。设b,z是5元置换，且T 2 3、2 1 44 55 3,5、2)(1)计算br,Q,r-1,b-b"2：(2)将q,/,b"rb表成不交的轮换之机(3)将中的置换表示成对换之积,并说明哪些为奇置换,哪些为偶置换.解：2 =4 52 L(JT =<44 5、2 5,53,2 3i2 1 55、4,-1(7T<7 =(5 42 = (1425) I =

47、(14253 )bb=(143)(25)(3) p=(14)(12)(15)奇置换,广=(14)(12)(15)(13)偶置换0-2=(14X13)(25)奇置换第十四章部分课后习题参考答案5、设无向图G有10条边,3度与4度顶点各2个，其余顶点的度数均小于3,问G至少有多少个顶点？在最少顶点的情况下，写出度数列、(G)、6(G)。解：由握手定理图G的度数之和为：2x10=203度与4度顶点各2个，这4个顶点的度数之和为14度。其余顶点的度数共有6度。其余顶点的度数均小于3,欲使G的顶点最少，其余顶点的度数应都取2,所以,G至少有7个顶点，出度数列为3,3,4,4,2,2,2,A(G)=4,J

48、(G)=2.7、设有向图D的度数列为2,3,2,3,出度列为1,2,b1,求D的入度列，并求以。),以。)，解:D的度数列为2,3,2,3,出度列为1,2,1,1,D的入度列为L1,1,2。(D)=3,J(D)=2,(。)=2,6+(D)=1,"(£>)=2,一(O)=18、设无向图中有6条边，3度与5度顶点各1个，其余顶点都是2度点，问该图有多少个顶点？解：由握手定理图G的度数之和为：2x6=12设2度点x个，则3xl+5xl+2.t=12,x=2,该图有4个顶点。14、下面给出的两个正整数数列中哪个是可图化的？对可图化的数列,试给出3种非同构的无向图，其中至少有两

49、个时简单图。(1)2,2,3,3,4,4,5(2)2,2,2,2,3,3,4,4解：(1)2+2+3+3+4+4+5=23是奇数,不可图化；(2)2+2+2+2+3+3+4+4=16,是偶数，可图化;18、设有3个4阶4条边的无向简单图G、Gz、G3,证明它们至少有两个是同构的。证明:4阶4条边的无向简单图的顶点的最大度数为3,度数之和为8,因而度数列为2,2,2,2:3,2,2,1；3,3,1,1。但3,3,1,1对应的图不是简单图。所以从同构的观点看，4阶4条边的无向简G?、G3至少有两个是同构的。20、已知n阶无向简单图G有m条边，试求G的补图G的边数7,。初，伽一1)解：m=-m221

50、、无向图G如下图(1)求G的全部点割集与边割集，指出其中的割点和桥：(2)求G的点连通度女(G)与边连通度G),边割集e2,e3,e3,e4,el,e2),(el,e4)el,e3)4e2,e4,e5攵(G)=G)=123、求G的点连通度k(G)、边连通度2(G)与最小度数6(G).28、设n阶无向简单图为3-正则图,且边数m与n满足2n-3=m向这样的无向图有几种非同构的情况？的阶数。m-nn+1)_1+Jl+8("?+?)解：m+m=-得77=2245、有向图D如图(1)求匕到匕长度为1，2,3,4的通路数；(2)求匕到均长度为1,2,3,4的回路数;(3)求D中长度为4的通路数：(4)求D中长度小于或等于4的回路数:(5)写出D的可达矩阵。解:有向图D的邻接矩阵为:0 0 0 010 10A= 0 0 0 0(0 110 10 ,010100;0 10 00 10 02 0I。0 2 0 0、2 0 2 00 2 0 02 0 2 00 0 0 4；0 04 0A4 = 0 04 00 04 00 04 00 44、04 A + T+T+A、2 1 20°,1 5、2 21 52 25 4,(1)匕到