离散数学答案屈婉玲版第二版高等教育出版社课后答案

离散数学答案屈婉玲版第二版高等教育出版社课后答案第一章部分课后习题参考答案16设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。（1）p∨(q∧r)0∨(0∧1)0（2）（p?r）∧(﹁q∨s)（0?1）∧(1∨1)0∧10.（3）（p∧q∧r）?(p∧q∧﹁r)（1∧1∧1）?(0∧0∧0)0(4)（r∧s）→(p∧q)（0∧1）→(1∧0)0→0117．判断下面一段论述是否为真：“是无理数。并且，如果3是无理数，则也是无理数。另外6能被2整除，6才能被4整除。”答：p:是无理数1q:3是无理数0r:是无理数1s:6能被2整除1t:6能被4整除0命题符号化为：p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。19．用真值表判断下列公式的类型：（4）(p→q)→(q→p)（5）(p∧r)(p∧q)（6）((p→q)∧(q→r))→(p→r)答：（4）pqp→qqpq→p(p→q)→(q→p)0001111001101111111001101011所以公式类型为永真式（5）公式类型为可满足式（方法如上例）（6）公式类型为永真式（方法如上例）第二章部分课后习题参考答案3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值.(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)000101010100111111000001011001110000100110111011所以公式类型为可满足式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)∑(0,2,3)主合取范式：(p→q)→(qp)(pq)(qp)(pq)(qp)(p(qp))(q(qp))1(pq)(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结论：pq证明：（2）①(qr)前提引入②qr①置换③qr②蕴含等值式④r⑤前提引入qq③④拒取式⑥p前提引入⑦￢p（3）证明（4）：①t⑤⑥拒取式r前提引入②t①化简律③q④s⑤qstt前提引入前提引入③④等价三段论⑥（qt）(tq)⑤置换⑦（qt）⑥化简⑧q⑨q②⑥假言推理⑧⑨假言推理pq前提引入⑩p(11)p⑧⑩合取15在自然推理系统P中用附加前提法证明下面各推理：(1)前提：p(qr),sp,q结论：sr证明①s附加前提引入②sp前提引入③p④p①②假言推理(qr)前提引入⑤qr③④假言推理⑥q⑦r前提引入⑤⑥假言推理16在自然推理系统P中用归谬法证明下面各推理：(1)前提：pq,rq,rsp结论：证明：①p②p结论的否定引入﹁q前提引入③﹁q④￢r①②假言推理q前提引入前提引入⑤￢r⑥r④化简律￢s⑦r⑧r⑥化简律﹁r⑤⑦合取由于最后一步r﹁r是矛盾式,所以推理正确.第四章部分课后习题参考答案3.在一阶逻辑中将下面将下面命题符号化,并分别讨论个体域限制为(a),(b)条件时命题的真值:(1)对于任意x,均有2=(x+)(x).(2)存在x,使得x+5=9.其中(a)个体域为自然数集合.(b)个体域为实数集合.解：F(x):2=(x+)(x).G(x):x+5=9.(1)在两个个体域中都解释为，在（a）中为假命题，在(b)中为真命题。(2)在两个个体域中都解释为，在（a）(b)中均为真命题。4.在一阶逻辑中(1)没有不能表示成分数的有理数.(2)在北京卖菜的人不全是外地人.解:将下列命题符号化:(1)F(x):x能表示成分数H(x):x是有理数命题符号化为:(2)F(x):x是北京卖菜的人H(x):x是外地人命题符号化为:5.在一阶逻辑将下列命题符号化:(1)火车都比轮船快.(3)不存在比所有火车都快的汽车.解:(1)F(x):x是火车;G(x):x是轮船;H(x,y):x比y快命题符号化为:(2)(1)F(x):x是火车;G(x):x是汽车;H(x,y):x比y快命题符号化为:9.给定解释I如下:(a)个体域D为实数集合R.(b)D中特定元素=0.(c)特定函数(x,y)=xy,x,y.(d)特定谓词(x,y):x=y,(x,y):x<y,x,y.说明下列公式在I下的含义,并指出各公式的真值:(1)(2)答:(1)对于任意两个实数x,y,如果x<y,那么xy.真值1.(2)对于任意两个实数x,y,如果x-y=0,那么x<y.真值0.10.给定解释I如下：（a）个体域D=N(N为自然数集合).（b）D中特定元素=2.（c）D上函数=x+y,(x,y)=xy.（d）D上谓词(x,y):x=y.说明下列各式在I下的含义，并讨论其真值.(1)xF(g(x,a),x)(2)xy(F(f(x,a),y)→F(f(y,a),x)答:(1)对于任意自然数x,都有2x=x,真值0.(2)对于任意两个自然数x,y,使得如果x+2=y,那么y+2=x.真值0.11.判断下列各式的类型:(1)(3)yF(x,y).解:(1)因为为永真式；所以为永真式；(3)取解释I个体域为全体实数F(x,y)：x+y=5所以,前件为任意实数x存在实数y使x+y=5，前件真；后件为存在实数x对任意实数y都有x+y=5，后件假，]此时为假命题再取解释I个体域为自然数N，F(x,y)：:x+y=5所以,前件为任意自然数x存在自然数y使x+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)个体域:泰山学院的学生F(x)：x出生在山东,G(x):x出生在北京,H(x):x出生在江苏,成假解释.F(x)：x会吃饭,G(x)：x会睡觉,H(x)：x会呼吸.成真解释.第五章部分课后习题参考答案5.给定解释Ｉ如下:(a)个体域D={3,4};(b)为(c).试求下列公式在Ｉ下的真值.(1)(3)解:(1)(2)12.求下列各式的前束范式。(1)(5)(本题课本上有错误)解:(1)(5)15.在自然数推理系统F中,构造下面推理的证明:(1)前提:,结论:xR(x)(2)前提:x(F(x)→(G(a)∧R(x))),xF(x)结论:x(F(x)∧R(x))证明(1)①前提引入②F(c)①EI③前提引入④①③假言推理⑤(F(c)∨G(c))→R(c))④UI②附加⑥F(c)∨G(c)⑦R(c)⑧⑤⑥假言推理xR(x)⑦EG(2)①xF(x)前提引入②F(c)①EI③x(F(x)→(G(a)∧R(x)))前提引入④F(c)→(G(a)∧R(c))⑤G(a)∧R(c)⑥R(c)③UI②④假言推理⑤化简⑦F(c)∧R(c)⑧②⑥合取引入x(F(x)∧R(x))⑦EG第六章部分课后习题参考答案5.确定下列命题是否为真：（1）真（2）假（3）真（4）真（5）｛a,b｝｛a,b,c,｛a,b,c｝｝真（6）｛a,b｝｛a,b,c,｛a,b｝｝真（7）｛a,b｝｛a,b,｛｛a,b｝｝｝真（8）｛a,b｝｛a,b,｛｛a,b｝｝｝假6．设a,b,c各不相同，判断下述等式中哪个等式为真:（1）｛｛a,b｝，c,｝=｛｛a,b｝,c｝假（2）｛a,b,a｝=｛a,b｝真（3）｛｛a｝，{b}｝=｛｛a,b｝｝假（4）｛，｛｝，a,b｝=｛｛,｛｝｝,a,b｝假8．求下列集合的幂集：（1）｛a,b,c｝P(A)={,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}（2）｛1，｛2，3｝｝P(A)={,{1},{{2,3}},{1，{2，3}}}（3）｛｝,｛｝}P(A)={（4）｛，｛｝｝P(A)={,{1},{{2,3}},{1，{2，3}}}14．化简下列集合表达式：（1）（AB）B）-（AB）（2）（（ABC）-（BC））A解:(1)（AB）B）-（AB）=（AB）B）～（AB）=（AB）～（AB）)B=B=（2）（（ABC）-（BC））A=（（ABC）～（BC））A=（A～（BC））（（BC）～（BC））A=（A～（BC））A=（A～（BC））A=A18．某班有25个学生，其中14人会打篮球，5人会打篮球和网球，还有2人会打这三种球。已知6个会打网球的人都的人数。12人会打排球，6人会打篮球和排球，会打篮球或排球。求不会打球解:阿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},{}},计算下列表达式：（1）AAAA（2）（3）（4）解:（1）A={1，2}{2，3}{1，3}{}={1，2，3,}（2）A={1，2}{2，3}{1，3}{}=（3）A=123=（4）A=27、设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)=A-BC由（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}A-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}16．设A={a,b,c,d}，，为A上的关系，其中=求。解: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>}36．设A={1，2，3，4}，在AA上定义二元关系R，<u,v>,<x,y>AA，〈u,v>R<x,y>u+y=x+v.(1)证明R是AA上的等价关系.(2)确定由R引起的对AA的划分.（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是传递的∴R是A×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>}}41.设A={1，2，3，4}，R为AA上的二元关系,〈a，b〉，〈c，d〉AA,〈a，b〉R〈c，d〉a+b=c+d(1)证明R为等价关系.(2)求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>},{<1,4>,<4,1>,<2,3>,<3,2>},{<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)(2)45.下图是两个偏序集<A,R>的哈斯图.分别写出集合A和偏序关系R的集合表达式.(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>}(b)A={a,b,c,d,e,f,g}R={<a,b>,<a,c>,<a,d>,<a,e>,<a,f>,<d,f>,<e,f>}46.分别画出下列各偏序集<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>}IA.(2)A={a,b,c,d,e},R={<c,d>}IA.解:(1)(2)项目极大元:(1)e(2)a,b,d,e极小元:aa,b,c,e最大元:e无无最小元:a第八章部分课后习题参考答案1．设f:NN,且f(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}.4.判断下列函数中哪些是满射的?哪些是单射的?哪些是双射的?(1)f:NN,f(x)=x2+2(2)f:N不是满射，不是单射N,f(x)=(x)mod3,x除以3的余数不是满射，不是单射(3)f:NN,f(x)=不是满射，不是单射(4)f:N{0,1},f(x)=是满射，不是单射(5)f:N-{0}R,f(x)=lgx不是满射，是单射(6)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的函数;对(2)f是从X到Y的函数,但不是满射,也不是单射的;错(3)f是从X到Y的满射,但不是单射;错(4)f是从X到Y的双射.错第十章部分课后习题参考答案4．判断下列集合对所给的二元运算是否封闭：（1）整数集合Z和普通的减法运算。封闭,不满足交换律和结合律，无零元和单位元（2）非零整数集合普通的除法运算。不封闭（3）全体实矩阵集合（R）和矩阵加法及乘法运算，其中n2。封闭均满足交换律，结合律，乘法对加法满足分配律；加法单位元是零矩阵，无零元；乘法单位元是单位矩阵，零元是零矩阵；（4）全体实可逆矩阵集合关于矩阵加法及乘法运算，其中n2。不封闭（5）正实数集合和运算，其中运算定义为：不封闭因为（6）关于普通的加法和乘法运算。封闭，均满足交换律，结合律，乘法对加法满足分配律加法单位元是0，无零元；乘法无单位元（），零元是0；单位元是1（7）A={n运算定义如下：封闭不满足交换律，满足结合律，（8）S=关于普通的加法和乘法运算。封闭均满足交换律，结合律，乘法对加法满足分配律（9）S={0,1},S是关于普通的加法和乘法运算。加法不封闭，乘法封闭；乘法满足交换律，结合律（10）S=,S关于普通的加法和乘法运算。加法不封闭，乘法封闭，乘法满足交换律，结合律5．对于上题中封闭的二元运算判断是否适合交换律，结合律，分配律。见上题7．设*为上的二元运算，X*Y=min(x，y),即x和y之中较小的数.(1)求4*6，7*3。4,3(2)*在上是否适合交换律，结合律，和幂等律？满足交换律，结合律，和幂等律(3)求*运算的单位元，零元及中所有可逆元素的逆元。单位元无，零元1,所有元素无逆元8．为有理数集，*为S上的二元运算，<a,b>,<x,y>S有<a，b>*<x，y>=<ax，ay+b>（1）*运算在S上是否可交换，可结合？是否为幂等的？不可交换：<x,y>*<a,b>=<xa，xb+y><a，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>)不是幂等的（2）*运算是否有单位元，零元？如果有请指出，并求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/x所以当x0时，10．令S={a，b}，S上有四个运算：*，分别有表10.8确定。(a)(b)(c)(d)(1)这4个运算中哪些运算满足交换律，结合律，幂等律？(a)交换律，结合律，幂等律都满足，零元为a,没有单位元；(b)满足交换律和结合律，不满足幂等律，单位元为a,没有零元(c)满足交换律,不满足幂等律,不满足结合律没有单位元,没有零元(d)不满足交换律，满足结合律和幂等律没有单位元,没有零元(2)求每个运算的单位元，零元以及每一个可逆元素的逆元。见上16．设V=〈N，+，〉，其中+，分别代表普通加法与乘法，对下面给定的每个集合确定它是否构成V的子代数，为什么？（1）S1=是（2）S2=不是加法不封闭（3）S3={-1，0，1}不是，加法不封闭第十一章部分课后习题参考答案8.设S={0，1，2，3}，为模4乘法，即"x,y∈S,xy=(xy)mod4问〈S，〉是否构成群？为什么？解：(1)x,y∈S,xy=(xy)mod4,是S上的代数运算。(2)x,y,z∈S,设xy=4k+r(xy)z=((xy)mod4)z=rz=(rz)mod4=(4kz+rz)mod4=((4k+r)z)mod4=(xyz)mod4同理x(yz)=(xyz)mod4所以，(xy)z=x(yz)，结合律成立。(3)x∈S,(x1)=(1x)=x,，所以1是单位元。(4)0和2没有逆元所以，〈S，〉不构成群9.设Z为整数集合，在Z上定义二元运算。如下："x,y∈Z,xoy=x+y-2问Z关于o运算能否构成群？为什么？解：(1)x,y∈Z,xoy=x+y-2,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)，结合律成立。(3)设是单位元，x∈Z,xo=ox=x,即x+-2=+x-2=x,e=2(4)x∈Z,设x的逆元是y,xoy=yox=,即x+y-2=y+x-2=2,所以，所以〈Z，o〉构成群11.设G=，证明G关于矩阵乘法构成一个群．解：(1)x,y∈G,易知xy∈G,乘法是Z上的代数运算。(2)矩阵乘法满足结合律(3)设是单位元，(4)每个矩阵的逆元都是自己。所以G关于矩阵乘法构成一个群．14.设G为群，且存在a∈G,使得G={ak∣k∈Z}证明：G是交换群。证明:x,y∈G，设，则所以，G是交换群17.设G为群，证明e为G中唯一的幂等元。证明:设也是幂等元，则，即，由消去律知18.设G为群，a,b,c∈G,证明∣abc∣=∣bca∣=∣cab∣证明：先证设设则，即左边同乘，右边同乘得反过来，设则由元素阶的定义知，∣abc∣=∣bca∣，同理∣bca∣=∣cab∣19.证明：偶数阶群G必含2阶元。证明：设群G不含2阶元，，当时，是一阶元，当时，至少是3阶元,因为群G时有限阶的，所以是有限阶的，设是k阶的,则也是k阶的，所以高于3阶的元成对出现的，G不含2阶元，G含唯一的1阶元,这与群G是偶数阶的矛盾。所以，偶数阶群G必含2阶元20.设G为非Abel群，证明G中存在非单位元a和b,a≠b,且ab=ba.证明：先证明G含至少含3阶元。若G只含1阶元,则G={e},G为Abel群矛盾；若G除了1阶元e外,其余元均为2阶元，则，，与G为Abel群矛盾；所以，G含至少含一个3阶元，设为，则，且。令的证。21.设G是Mn(R)上的加法群，n≥2，判断下述子集是否构成子群。（1）全体对称矩阵是子群是子群（2）全体对角矩阵（3）全体行列式大于等于0的矩阵.不是子群（4）全体上（下）三角矩阵。是子群22.设G为群，a是G中给定元素，a的正规化子N（a）表示G中与a可交换的元素构成的集合，即N（a）={x∣x∈G∧xa=ax}证明N（a）构成G的子群。证明：ea=ae,,所以由，得，即，所以所以N（a）构成G的子群31.设1是群G1到G2的同态，2是G2到G3的同态，证明12是G1到G3的同态。证明：有已知1是G1到G2的函数，2是G2到G3的函数，则1·2是G1到G3的函数。所以:1·2是G1到G3的同态。33.证明循环群一定是阿贝尔群，说明阿贝尔群是否一定为循环群，并证明你的结论。证明：设G是循环群,令G=<a>,,令,那么,G是阿贝尔群克莱因四元群,是交换群,但不是循环群,因为e是一阶元，a,b,c是二阶元。36.设是5元置换，且，(1)计算；(2)将表成不交的轮换之积。(3)将（2）中的置换表示成对换之积，并说明哪些为奇置换，哪些为偶置换。解：(1)(2)(3)奇置换，偶置换奇置换第十四章部分课后习题参考答案5、设无向图G有10条边，3度与4度顶点各2个，其余顶点的度数均小于3，问G至少有多少个顶点？在最少顶点的情况下，写出度数列、。解：由握手定理图G的度数之和为：3度与4度顶点各2个，这4个顶点的度数之和为14度。其余顶点的度数共有6度。其余顶点的度数均小于3，欲使G的顶点最少，其余顶点的度数应都取2,所以，G至少有7个顶点,出度数列为3,3,4,4,2,2,2,.7、设有向图D的度数列为2，3，2，3，出度列为1，2，1，1，求D的入度列，并求，,.解：D的度数列为2，3，2，3，出度列为1，2，1，1，D的入度列为1,1,1,2.,,8、设无向图中有6条边，3度与5度顶点各1个，其余顶点都是2度点，问该图有多少个顶点？解：由握手定理图G的度数之和为：设2度点个，则，，该图有4个顶点.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,是偶数，可图化；18、设有3个4阶4条边的无向简单图G1、G2、G3，证明它们至少有两个是同构的。证明：4阶4条边的无向简单图的顶点的最大度数为3，度数之和为8，因而度数列为2，2，2，2；3，2，2，1；3，3，1，1。但3，3，1，1对应的图不是简单图。所以从同构的观点看，4阶4条边的无向简单图只有两个：所以，G1、G2、G3至少有两个是同构的。20、已知n阶无向简单图G有m条边，试求G的补图的边数。解：21、无向图G如下图(1)求G的全部点割集与边割集，指出其中的割点和桥；(2)求G的点连通度与边连通度。解：点割集:{a,b},(d)边割集{e2,e3},{e3,e4},{e1,e2},{e1,e4}{e1,e3},{e2,e4},{e5}==123、求G的点连通度、边连通度与最小度数。解：、、28、设n阶无向简单图为3-正则图，且边数m与n满足2n-3=m问这样的无向图有几种非同构的情况？解：得n=6,m=9.31、设图G和它的部图的边数分别为和，试确定G的阶数。解：得45、有向图D如图(1)求到长度为1，2，3，4的通路数；(2)求到长度为1，2，3，4的回路数；(3)求D中长度为4的通路数；(4)求D中长度小于或等于4的回路数；(5)写出D的可达矩阵。解：有向图D的邻接矩阵为：，(1)到长度为1，2，3，4的通路数为0,2,0,0；(2)到长度为1，2，3，4的回路数为0,0,4,0；(3)D中长度为4的通路数为32；(4)D中长度小于或等于4的回路数10；(4)出D的可达矩阵第十六章部分课后习题参考答案1、画出所有5阶和7阶非同构的无向树.2、一棵无向树T有5片树叶，3个2度分支点，其余的分支点都是3度顶点，问T有几个顶点?解：设3度分支点个，则，解得T有11个顶点3、无向树T有8个树叶，2个3度分支点，其余的分支点都是4度顶点，问T有几个4度分支点？根据T的度数列，请至少画出4棵非同构的无向树。解：设4度分支点个，则，解得度数列1111111133444、棵无向树T有(i=