离散数学(屈婉玲)答案

第一章部分课后习题参考答案16p、q0；r、s1，求下列各命题公式的真值。（1）p∨(q∧r) 0∨(0∧1) 0（2r）∧﹁q∨) （1）∧∨) 0∧1（3（p∧q∧r）p∧q∧﹁) （1∧1∧1）∧0∧)(4)（r∧s）→(p∧q) （0∧1）→(1∧0) 0→012．判断下面一段论述是否为真是无理数。并且，如果362整除，642答：p: 是无理数1q: 3是无理数0

也是无2r: 是无理数12s: 62整除1t: 64整除0命题符号化为：p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。19．用真值表判断下列公式的类型：（4）(p→q)→(q→p)（5）(p∧r) (p∧q)pqp→qqpq→ppqp→qqpq→p(p→q)→(0011111011011110010011110011q→p)所以公式类型为永真式等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值.(1) (p∧q→q)(2)(p→(p∨q))∨(p→r)(3)(p∨q)→(p∧r)答：(2)（p→(p∨q)）∨(p→r)(p∨(p∨q))∨(p∨r)p∨p∨q∨r1所以公式类型为永真式(3)Pqrp∨qp∧r（p∨q）→(p∧r)000001001001010100011100100100101111110100111111所以公式类型为可满足式4.(2)(p→q)∧(p→r)(p→(q∧r))(4)(p∧q)∨(p∧q)(p∨q)∧(p∧q)证明（2）(p→q)∧(p→r) (p∨q)∧(p∨r)p∨(q∧r))p→(q∧r)（4）(p∧q)∨(p∧q)(p∨(p∧q))∧(q∨(p∧q)(p∨p)∧(p∨q)∧(q∨p)∧(q∨q)1∧(p∨q)∧(p∧q)∧1(p∨q)∧(p∧q)5.求下列公式的主析取范式与主合取范式，并求成真赋值(1)(p→q)→(q∨p)(2)(p→q)∧q∧r(3)(p∨(q∧r))→(p∨q∨r)解：（1）主析取范式(p→q)→(qp)(pq)(qp)(pq)(qp) (pq)(qp)(qp)(pq)(pq) (pq)(pq)(pq)mmm0 2 3∑(0,2,3)主合取范式：(p→q)→(qp)(pq)(qp)(pq)(qp)(p(qp))(q(qp))1(pq)1(pq) M1∏(1)(2)主合取范式为：(p→q)qr(pq)qr(pq)qr0所以该式为矛盾式.主合取范式为∏(0,1,2,3,4,5,6,7)矛盾式的主析取范式为0(3)主合取范式为：(p(qr))→(pqr)(p(qr))→(pqr)(p(qr))(pqr)(p(pqr))((qr))(pqr))111所以该式为永真式.永真式的主合取范式为1主析取范式为∑(0,1,2,3,4,5,6,7)第三章部分课后习题参考答案14. P中构造下面推理的证明：(2)前提：pq,(qr),r结论：p(4)前提：qp,qs,st,tr结论：pq2）r) 前提引入①置换③q

②蕴含等值式④r 前提引入q ③④拒取式⑥pq 前提引入⑦￢p ⑤⑥拒取式证明4：①tr 前提引入②t ①化简律③qs 前提引入④st 前提引入⑤qt ③④等价三段论⑥（qt）(tq)⑤置换⑦（qt） ⑥化简⑧q ②⑥假言推理⑨qp 前提引入⑩p ⑧⑨假言推理(11)pq ⑧⑩合取P中用附加前提法证明下面各推理：(1)前提：p(qr),sp,q结论：sr证明①s 附加前提引入②sp 前提引入③p ①②假言推理④p(qr)前提引入⑤qr ③④假言推理⑥q 前提引入⑦r ⑤⑥假言推理P中用归谬法证明下面各推理：(1)前提：pq,rq,rs结论：p证明：①p 结论的否定引入②p﹁q 前提引入③﹁q ①②假言推理④￢rq 前提引入⑤￢r ④化简律⑥r￢s 前提引入⑦r ⑥化简律⑧r﹁r ⑤⑦合取由于最后一步r﹁r是矛盾式,所以推理正确.第四章部分课后习题参考答案,(a),(b)条件时命题的真值:x,均有x,

2=(x+ )(x ).其中(a)个体域为自然数集合.(b)个体域为实数集合.解：F(x): 2=(x+ )(x ).G(x):x+5=9.xF(x，在（a）中为假命题，在(b)中为真命题。(2)xG(x，在（a）(b)中均为真命题。在一阶逻辑中将下列命题符号化:没有不能表示成分数的有理数.在北京卖菜的人不全是外地人.解:F(x)x能表示成分数H(x):x是有理数命题符号化为: x(F(x)H(x))F(x)x是北京卖菜的人H(x):x是外地人命题符号化为: x(F(x)H(x))在一阶逻辑将下列命题符号化:火车都比轮船快.(3)不存在比所有火车都快的汽车.解:F(x)x是火车G(x)x是轮船H(x,y)xy快命题符号化为: xy((F(x)G(y))H(x,y))(1)F(x):x是火车;G(x):x是汽车;H(x,y):x比y快命题符号化为: y(G(y)x(F(x)H(x,y)))I如下:DR.D中特定元素=0.特定函数(x,y)=x D.特定谓词(x,y):x=y,(x,y):x<y,x,yD.说明下列公式在I下的含义,并指出各公式的真值:(1)xy(G(x,y)F(x,y))(2)xy(F(f(x,y),a)G(x,y))答:(1)对于任意两个实数如果x<y,那么xy. 真值1.(2)x-y=0,x<y.0.I如下：D=N(N为自然数集合).D=2.D上函数 =x+y,(x,y)=xy.D上谓词(x,y):x=y.说明下列各式在I下的含义，并讨论其真值.xF(g(x,a),x)(2) xy(F(f(x,a),y)→F(f(y,a),x)答:(1)对于任意自然数x,都有2x=x, 真值0.x+2=y,y+2=x.0. 判断下列各式的类型(1)yF(x,y).解:(1)因为p(qp)p(qp)1 为永真式所以 为永真式；(3)取解释I个体域为全体实数F(x,y)：x+y=5所以xyx+y=5，前件真；xyx+y=5，后件假，]此时为假命题IF(x,y)：:x+y=5所以xyx+y=5此公式为非永真式的可满足式。13. 给定下列各公式一个成真的解释，一个成假的解释。(1) (F(x)(2) x(F(x)G(x)H(x))解:(1)个体域本班同学F(x)：x会吃饭,G(x)：x会睡觉.成真解释F(x)：x是泰安人,G(x)：x是济南人.（2）成假解释(2)个体域:泰ft学院的学生F(x)：x出生在ft东,G(x):x出生在北京,H(x):x出生在江苏,成假解释.F(x)：x会吃饭,G(x)：x会睡觉,H(x)：x会呼吸.成真解释.第五章部分课后习题参考答案给定解释Ｉ如下:(a)D={3,4};(b)f(x)为f(3)4,f(4)3(c)F(x,y)为FF(4,4)0, F(3,4)F(4,3)1.试求下列公式在Ｉ下的真值.xyF(x,y)(3)xy(F(x,y)F(f(x),f(y)))解:(1) xyF(x,y)x(F(x,3)F(x,4)) (FF(3,4))(FF(4,4))(00)1(2) xy(F(x,y)F(f(x),f(y)))x((F(x,3)F(f(x),f(F(x,4)F(f(x),f(4))))x((F(x,3)F(f(x),4))(F(x,4)F(f(x),3)))((FF(f(3),4))(FF(f((FF(f(4),4))(F(4,4)F(f(4),3)))((0F(4,4))(FF(4,3)))F(0F(00)(00)112.求下列各式的前束范式。(1)xF(x)yG(x,y)(5)x1

F(x,x1

)(H(x1

)x2

G(x,x1

)) (本题课本上有错误)解:(1) xF(x)yG(x,y)xF(x)yG(t,y)xy(F(x)G(t,y))(5) x1

F(x,x1

)(H(x1

)x2

G(x,x))1 2x1

F(x,x1

)(H(x3

)x2

G(x,x))3 2x1

F(x,x1

)x2

(H(x3

)G(x,x))3 2xx1 2

(F(x,x1

)(H(x3

)G(x,x3 2

)))15.在自然数推理系统F中,构造下面推理的证明:(1)前提: xF(x)y((F(y)G(y))R(y)),xF(x)结论: xR(x)(2)前提: x(F(x)→(G(a)∧R(x))), xF(x)结论:x(F(x)∧R(x))证明(1)xF(x) 前提引入②F(c) ①EIxF(x)y((FyGyRy)) 前提引入④y((FyGy))Ry)) ①③假言推理⑤(F(c)∨G(c))→R(c)) ④UI⑥F(c)∨G(c) ②附加⑦R(c) ⑤⑥假言推理⑧xR(x) ⑦EG(2)xF(x) 前提引入②F(c) ①EIx(F(x)→(G(a)∧R(x))) 前提引入④F(c)→(G(a)∧R(c)) ③UI⑤G(a)∧R(c) ②④假言推理⑥R(c) ⑤化简⑦F(c)∧R(c) ②⑥合取引入⑧x(F(x)∧R(x))第六章部分课后习题参考答案确定下列命题是否为真：（1） 真（2） 假（3）真（4）{} 真（5a,b｝｛a,b,c,｛a,b,c｝ 真（6a,b｝｛a,b,c,｛a,b｝ 真（7a,b｝｛a,b,｛a,｝｝ 真（8a,b｝｛a,b,｛a,｝｝ 假a,b,c各不相同，判断下述等式中哪个等式为真:（1｛a,b，, ｝=｛a,b｝｝ 假（2aa=｛a,b｝（3｛a，｝=｛a,b｝真假（4｛｛，a,b｝=｛,｛｝,a,b｝假8．求下列集合的幂集：（1a,b,c｝ { （21｛2，3｝{ ,, , 1，，}}（3｛｝ { ,｛｝}（4｛｛｝ { ,, , 1，2，}}14．化简下列集合表达式：（1A）B）-（A）（2（AB）-（B）A解:(1)（AB）B）-（AB）=（AB）B）～（AB）=（AB）～（AB）)B=B=（2（AB）-（B）=（AB）～（B）A=（A～（BC）（BC）～（BC）A=（A～（BC）A=（A～（BC）A=A182514人会打篮球，12人会打排球，6人会打篮球和排球，526求不会打球的人数。解:阿A={会打篮球的人}，B={会打排球的人}，C={会打网 球人}|A|=14, |B|=12, |AB|=6,|AC|=5,| ABC|=2,|C|=6,CAB如图所示。25-(5+4+2+3)-5-1=25-14-5-1=5不会打球的人共5人21.设集合A＝{{1，2}，{2，3}，{1，3},{}},计算下列表达式：AA（3）A（4）A解:（1）A={1，2}{2，3}{1，3}}={1，2，3}（2）A={1，2}{2，3}{1，3}{}=（3）A=123=（4）A=A,B,C(1)(A-B)-C=A-BC(2)(A-B)-C=(A-C)-(B-C)证明(1)(A-B)-C=(A～B) ～C=A(～B～C)=A～(BC)=A-BC(2)(A-C)-(B-C)=(A～C) ～(B ～C)=(A～C) (～BC)=(A～C～B) (A～CC)=(A～C～B) A～(BC=ABC 由（1）得证。第七章部分课后习题参考答案7.列出集合A={2,3,4}上的恒等关系IA,全域关系EA,小于或等于关系LA,整除关系DA.解：IA={<2，2>,<3,3>,<4,4>}EA={<2,2>,<2,3>,<2,4>,<3,4>,<4,4>,<3,2>,<3,3>,<4,2>,<4,3>}LA={<2,2>,<2,3>,<2,4>,<3,3>,<3,4>,<4,4>}DA={<2,4>}13.A={<1,2>,<2,4>,<3,3>}B={<1,3>,<2,4>,<4,2>}求AB,AB,domA,domB,dom(AB),ranA,ranB,ran(AB),fld(A-B).解：AB={<1,2>,<2,4>,<3,3>,<1,3>,<4,2>}AB={<2,4>}domA={1,2,3}domB={1,2,4}dom(A∨B)={1,2,3,4}ranA={2,3,4}ranB={2,3,4}ran(AB)={4}fldR=domRranRA-B={<1,2>,<3,3>}，fld(A-B)={1,2,3}14.设R={<0,1><0,2>,<0,3>,<1,2>,<1,3>,<2,3>}求RR, R-1, R{0,1,}, R[{1,2}]解：RR={<0,2>,<0,3>,<1,3>}R-1,={<1,0>,<2,0>,<3,0>,<2,1>,<3,1>,<3,2>}R{0,1}={<0,1>,<0,2>,<0,3>,<1,2>,<1,3>}R[{1,2}]=ran(R{1,2})={2,3}，16A={a,b,c,d}R，1

RA上的关系，其中2R a,a,a,b,b,d 1=Ra,d,b,c,b,d,c,b2R,R RR,R R,R2,R32 2 1 1 21解R1R2={<a,d>,<a,c>,<a,d>}R2R1={<c,d>}R12=R1R1={<a,a>,<a,b>,<a,d>}R22=R2R2={<b,b>,<c,c>,<c,d>}R23=R2R22={<b,c>,<c,b>,<b,d>}A={1，2，3，4}AAR，Au,vR<x,yuyxv.RAA上的等价关系.(2)RAA的划分（1）证明：∵<u,v>R<x,y> u+y=x-y∴<u,v>R<x,y>u-v=x-y<u,v>AA∵u-v=u-v∴<u,v>R<u,v>∴R是自反的任意的<u,v>,<x,y>∈A×A如果<u,v>R<x,y>，那么u-v=x-y∴x-y=u-v ∴<x,y>R<u,v>∴R是对称的任意的<u,v>,<x,y>,<a,b>∈A×A若<u,v>R<x,y>,<x,y>R<a,b>则u-v=x-y,x-y=a-b∴u-v=a-b ∴<u,v>R<a,b>∴R是传递的∴RA×A上的等价关系(2)∏={{<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>}, {<1,4>} }设A={1，2，3，4}，R为AA上的二元关系, 〈a，b〈c，d〉AA,〈a，b〉R〈c，d〉abcdR为等价关系.R导出的划分.(1)证明：<a，b〉AAa+b=a+b∴<a,b>R<a,b>∴R是自反的任意的<a,b>,<c,d>∈A×A设<a,b>R<c,d>a+b=c+d∴c+d=a+b ∴<c,d>R<a,b>∴R是对称的任意的<a,b>,<c,d>,<x,y>∈A×A若<a,b>R<c,d>,<c,d>R<x,y>则a+b=c+d,c+d=x+y∴a+b=x+y ∴<a,b>R<x,y>∴R是传递的∴R是A×A上的等价关系(2) ∏={{<1,1>}, {<1,2>,<2,1>}, {<1,3>,<2,2>,<3,1>},{<2,4>,<4,2>,<3,3>}, {<3,4>,<4,3>}, {<4,4>}}43.对于下列集合与整除关系画出哈斯图:(1){1,2,3,4,6,8,12,24}(2){1,2,3,4,5,6,7,8,9,10,11,12}

{<1,4>,<4,1>,<2,3>,<3,2>},解:8128126238 12104104672395111 1(1) (2)下图是两个偏序集<A,R >的哈斯图.分别写出集合A和偏序关系R 的集合表达式.efbccefbccdbe ga a(b)解:(a)A={a,b,c,d,e,f,g}R ={<a,b>,<a,c>,<a,d>,<a,e>,<a,f>,<a,g>,<b,d>,<b,e>,<c,f>,<c,g>}IAA={a,b,c,d,e,f,g}R ={<a,b>,<a,c>,<a,d>,<a,e>,<a,f>,<d,f>,<e,f>}IA分别画出下列各偏序集<A,R>的哈斯图,并找出A的极大元`极小元`最大元和最小元.(1)A={a,b,c,d,e}R ={<a,d>,<a,c>,<a,b>,<a,e>,<b,e>,<c,e>,<d,e>}(2)A={a,b,c,d,e}, R ={<c,d>}IA.解:ebebcdaea bc(1) (2)项目 (1) (2)极大元: e a,b,d,e极小元: a a,b,c,e最大元: e 无最小元: a 无第八章部分课后习题参考答案1fNN,

1，若x为奇数f(x)=x若x为偶数求f(0),f({0}),f(1),f({1}),f({0,2,4,6,…})，f({4,6,8}), f-1({3,5,7}).解：f(0)=0,f({0})={0},f(1)=1,f({1})={1},f({0,2,4,6,…})=N，f({4,6,8})={2,3,4}, f-1({3,5,7})={6,10,14}.判断下列函数中哪些是满射的哪些是单射的哪些是双射的f:NNf(x)=x2+2 不是满射，不是单射f:NN,f(x)=(x)mod3, x除以3的余数 不是满射，不是单射1，若x为奇数f:NN,f(x)为偶数0，若x为奇数(4)f:N{0,1},f(x)为偶数

不是满射，不是单射是满射，不是单射f:N-{0R,f(x)=lgx 不是满射，是单射f:RR,f(x)=x2-2x-15 不是满射，不是单射5.设X={a,b,c,d},Y={1,2,3},f={<a,1>,<b,2>,<c,3>,}判断以下命题的真假:(1)f是从X到Y的二元关系,但不是从X到Y的函数; 对f是从X到Y的函数,但不是满射,也不是单射的; 错f是从X到Y的满射,但不是单射; 错f是从X到Y的双射. 错第十章部分课后习题参考答案判断下列集合对所给的二元运算是否封闭：Z和普通的减法运算。封闭,不满足交换律和结合律，无零元和单位元非零整数集合 普通的除法运算。不封闭全体nn实矩阵集合（R）和矩阵加法及乘法运算，其中n 2。封闭均满足交换律，结合律，乘法对加法满足分配律；加法单位元是零矩阵，无零元；乘法单位元是单位矩阵，零元是零矩阵；全体nn实可逆矩阵集合关于矩阵加法及乘法运算，其中n 2。不封闭正实数集合和运算，其中运算定义为：不封闭因为1111111Rn 封闭，均满足交换律，结合律，乘法对加法满足分配律加法单位元是0，无零元；乘法无单位元（n1，零元是；n1单位元是1（7）A={a,a,a} n 运算定义如下：1 2 n封闭不满足交换律，满足结合律，（8）S 关于普通的加法和乘法运算。封闭均满足交换律，结合律，乘法对加法满足分配律（9）S={0,1},S是关于普通的加法和乘法运算。加法不封闭，乘法封闭；乘法满足交换律，结合律（10）S ,S加法不封闭，乘法封闭，乘法满足交换律，结合律见上题*为Z上的二元运算xyZ，X*Yminx，yxy之中较小的数.(1)4*6，7*3。4, 3*在Z满足交换律，结合律，和幂等律求*运算的单位元，零元及Z中所有可逆元素的逆元单位元无，零元1, 所有元素无逆元SQQ Q为有理数集，*为S上的二元运算，<a,b>,<x,y> S有<a，b>*<x，y>=<ax，ay+b>*S上是否可交换，可结合是否为幂等的不可交换：<x,y>*<a,b<xa，xb+ya，b>*<x，y>可结合：(<a,b>*<x,y>)*<c,d>=<ax，ay+b>*<c,d>=<axc，axd+(ay+b)><a,b>*(<x,y>*<c,d>)=<a,b>*<xc,xd+y>=<axc，a(xd+y)+b>(<a,b>*<x,y>)*<c,d>=<a,b>*(<x,y>*<c,d>)不是幂等的*运算是否有单位元，零元如果有请指出，并求S中所有可逆元素的逆元设<a,b>是单位元，<x,y> S，<a,b>*<x,y>=<x,y>*<a,b>=<x,y>则<ax,ay+b>=<xa,xb+y>=<x,y>，解的<a,b>=<1,0>，即为单位。设<a,b>是零元，<x,y> S，<a,b>*<x,y>=<x,y>*<a,b>=<a,b>则<ax,ay+b>=<xa,xb+y>=<a,b>，无解。即无零元。<x,y S，设<a,b>是它的逆元<a,b>*<x,y><x,y>*<a,b>=<1,0><ax,ay+b>=<xa,xb+y>=<1,0>a=1/x,b=-y/xx0xy1

1,x 令S={a，b}，S上有四个运算：*， 分别有表确定。(a) (b) (c) (d)4个运算中哪些运算满足交换律，结合律，幂等律a,(b)没有零元a1a,b1b满足交换律,不满足幂等律,不满足结合律a(bb)aab,a(bb)(ab)b没有单位元,没有零元

(ab)baba没有单位元,没有零元见上16V=〈N，++V的子代数，为什么（1）S1=（2）S2=

是不是加法不封闭（3）S31，0，1} 不是，加法不封闭第十一章部分课后习题参考答案8.设S={0，1，2，3}，为模4乘法，即"x,y∈S, x问〈S，〉是否构成群为什么

y=(xy)mod4解：(1) x,y∈S, x y=(xy)mod4S, 是S上的代数运算。(2) x,y,z∈S,设xy=4k+r 0r3(x y) z=((xy)mod4) z=r z=(rz)mod4=(4kz+rz)mod4=((4k+r)z)mod4=(xyz)mod4同理x (3) x∈S,(x

z)=(xyz)mod4y) z=x (y z)，结合律成立1)=(1 x)=x,，所以1是单位元。(4)113102没有逆元S，

〉不构成群9.设Z为整数集合，在Z上定义二元运算。如下：" x,y∈Z,xoy=x+y-2问Z关于o运算能否构成群为什么解：(1) x,y∈Z, xoy=x+y-2Z,o是Z上的代数运算。(2) x,y,z∈Z,(xoy)oz=(x+y-2)oz=(x+y-2)+z-2=x+y+z-4同理(xoy)oz=xo(yoz)，结合律成立。设e是单位元，x∈Z,xoe= e即x+e-2= e+x-2=x, e=2 x∈Z,xyxoyyox=e,x+y-2=y+x-2=2,x1y4x所以〈Z，o〉构成群1 01 0 1 0 1 011.设G=0 1,0

,

,

，证明G关于矩阵乘法构成一个群．

1

0 1

0 1解：(1) x,y∈G, 易知xy∈G,乘法是Z上的代数运算。矩阵乘法满足结合律0 1设1 0 1 每个矩阵的逆元都是自己。所以G关于矩阵乘法构成一个群．14.设G为群，且存在a∈G,使得G={ak∣k∈Z}证明：G是交换群。证明:x,y∈G，设xak, yal，则xyakalaklalkalakyx所以，G是交换群GeG中唯一的幂等元。证明:设e0

G也是幂等元，则e20

e，即e0 0

ee，由消去律知e e0 0G为群，a,b,c∈G,证明∣abc∣=∣bca∣=∣cab∣证明：先证设(abc)ke(bca)ke设(abc)ke,则(abc)(abc)(abc)(abc)e，即 a(bca)(bca)(bca)(bca)a1e左边同乘a1，右边同乘a得(bca)(bca)(bca)(bca)(bac)ka1eae反过来，设(bac)k

e则(abc)k

e.由元素阶的定义知，∣abc∣=∣bca∣，同理∣bca∣=∣cab∣G2阶元。证明：G2G，当aea是一阶元，当aea3阶元,G时有限阶的，所以a是有限阶的，设ak阶的,则a1k阶的，所以321阶元e,GG2阶元GAbel群，证明Gab,a≠b,ab=ba.证明：G3阶元。G1阶元,G={e},GAbel群矛盾；G1e外,其余元a2阶元，则a2ea1aabG,a1ab1b,(ab)1ababa1b1(ba)1ba，GAbel群矛盾；所以，G3阶元，设为a，则aa2，且a2aaa2。令ba2的证。GMn(R)上的加法群，n≥2，判断下述子集是否构成子群。全体对称矩阵 是子群全体对角矩阵 是子群全体行列式大于等于0的矩阵. 不是子群全体上（下）三角矩阵。 是子群G为群，aG中给定元素，aN（a）Ga可交换的元素构成的集合，即N（a）={x∣x∈G∧xa=ax}N（a）G证明：ea=aeeN(a)x,yN(a), 则axxa,ayyaa(xy)(ax)y(xa)yx(ay)x(ya)(xy)a,所以xyN(a)axxa，得x1axx1x1xax1x1aeeax1x1aax1x1N(a)所以N（a）构成G的子群31. G G G G G 设 是群 到 的同态， 是 到 的同态，证明 31. G G G G G 1 1 2 2 2 3 1 2 1 3G G G G G 证明有已知 是 到 的函数， 是 到 的函数，则· G G G G G 1 1 2 2 2 3 1 2 1 3数。a,bG1

, 1

)(ab)2

(ab))1

(a)1

(b))(2

(a)))(1

(b)))1

)(a)(2

)(b)2所以:1·2G1G3的同态。33.证明：G,G=<a>x,yG,xak,yal,那么eabceeabcaaecbbbceccbaexyakalaklalkalakyx,G是阿贝尔群克莱因四元群,G{eabceeabcaaecbbbceccbae是交换群,但不是循环群,因为e是一阶元，a,b,c是二阶元。36.设,5元置换，且 1 2 3 4 5，1 2 3 4 52 1 4 5 3 3 4 5 1 2 (1)计算,,1,1,1；将,1表示成不交的轮换之积。将（2）中的置换表示成对换之积，并说明哪些为奇置换，哪些为偶置换。1 2 3 4 5 1 2 3 4 5 1 2 3 4 5解：(1) 4 5 3 2 1

4 3 1 2 5

1

4 5 1 2 3 1 2 3 4 52 1 5 3 4

1 2 3 4 5 5 4 1 3 (2)1(143)(25)(3) 奇置换，1偶置换奇置换第十四章部分课后习题参考答案5、设无向图G10423，问G少有多少个顶点在最少顶点的情况下，写出度数列、(G)(G。解：由握手定理图G的度数之和为：210203度与4度顶点各2个，这4个顶点的度数之和为14度。其余顶点的度数共有6度。其余顶点的度数均小于3，欲使G的顶点最少，其余顶点的度数应都取2,所以，G至少有7个顶点,出度数列为3,3,4,4,2,2,2,(G)4,(G)2.7D23231211D(D),(D)，(D),(D),(D),(D).解：D的度数列为2，3，2，3，出度列为1，2，1，1，D的入度列为1,1,1,2.(D)3,(D)2,(D)2,(D)1,(D)2,(D)186条边，3512少个顶点解：由握手定理图G的度数之和为：26122x个，则31512x12x24个顶点.14、下面给出的两个正整数数列中哪个是可图化的对可图化的数列，试给出3种非同构的无向图，其中至少有两个时简单图。(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,是偶数，可图化；18344条边的无向简单图G1、G2、G3，证明它们至少有两个是同构的。证明：44382，2，2，2；3，2，2，1；3，3，1，13，3，1，1对应的图不是简单图。所以从同构的观点看，44条边的无向简单图只有两个：所以，G1、G2、G3至少有两个是同构的。20n阶无向简单图GmG的补图G的边数m。mn(nm221、无向图G如下图G的全部点割集与边割集，指出其中的割点和桥；G的点连通度k(G与边连通度(G。a e1e2 db e5 ee3 e4c解：点割集:{a,b},(d)边割集{e2,e3},{e3,e4},{e1,e2},{e1,e4}{e1,e3},{e2,e4},{e5}k(G)=(G)=123G的点连通度k(G、边连通度(G与最小度数(G。k(G)2、(G)3、(G)428n3-mn2n-3=m问这样的无向图有几种非同构的情况3n2m2n3

得n=6,m=9. 31G和它的部图G的边数分别为m和mG的阶数。mm

n(n得n11 18(mm)45、有向图D如图求v2到v51，2，3，4的通路数；求v到v1，2，3，4的回路数；5 5D4的通路数；D4的回路数；D的可达矩阵。v5v1 v4v5v2 v3解：有向图D的邻接矩阵为：0 0 011 0 1A 0 0 01 0

0 1 0 0 0 0 1，A2 0 0 0

0 1 0 2 0 0 2 30 1 0A 2 3 0 0 2 0

2 0 00 2 02 0 00 2 00 1 0 1 0

2

2 0 0

0

0 0 4 44A4

0 0 0 4 0 0 4 0 0 0 0 0 4 AA2A3A4 0 4 0 0 4

2 1 55 2 22 1 55 2 20 4 0 4 0

2

2 5 4 2(1v 到v1，2，3，40,2,0,0；