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

1 离散数学答案屈婉玲版第二版 高等教育出版社课后答案第一章部分课后习题参考答案16 设 p、q 的真值为 0；r、s 的真值为 1，求下列各命题公式的真值。（1）p(qr)0(01) 0 （2） （p? r）( qs) （0? 1）(1 1) 010. （3） （pqr ）? (pqr) （111） ? (0 00)0 (4) （r s）(p q) （01）(10) 001 17判断下面一段论述是否为真： “是无理数。并且，如果3 是无理数，则2也是无理数。另外 6 能被 2 整除， 6 才能被 4 整除。 ”答：p: 是无理数1 q: 3 是无理数0 r: 2是无理数1 s:6 能被 2 整除1 t: 6 能被 4 整除0 命题符号化为：p(qr)(ts)的真值为 1，所以这一段的论述为真 。19用真值表判断下列公式的类型：（4）(pq) (qp) （5）(pr) (pq) （6）(pq) (qr) (pr) 答：（4）p q pq q p qp (pq)(qp) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式（5）公式类型为可满足式（方法如上例）（6）公式类型为永真式（方法如上例）第二章部分课后习题参考答案名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 30 页 - - - - - - - - - 2 3. 用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值 . (1) (pqq) (2)(p(pq)(pr) (3)(pq)(pr) 答：(2)（p(pq)）(pr)(p(pq)(pr)ppqr1所以公式类型为永真式(3) Pq r pq pr （pq）(pr) 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 所以公式类型为可满足式4. 用等值演算法证明下面等值式：(2)(p q)(p r)(p (qr) (4)(p q)(pq)(pq) (pq)证明（ 2）(pq)(p r) (pq) (pr) p(q r) p(qr) （4）(pq)(pq)(p (pq) (q(pq) (pp) (pq)(qp) (qq) 1(pq) (pq)1 (pq)(pq) 5. 求下列公式的主析取范式与主合取范式，并求成真赋值(1)(pq)(qp) (2)(pq)qr (3)(p (q r) (p qr)名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 30 页 - - - - - - - - - 3 解：（1）主析取范式(pq)(qp) (pq)(qp) (pq)(qp) (pq)(qp)(qp)(pq)(pq) (pq)(pq)(pq) 320mmm(0,2,3) 主合取范式： (pq) (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) 11 1 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 30 页 - - - - - - - - - 4 所以该式为永真式 . 永真式的主合取范式为 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 前提引入q 拒取式pq 前提引入p（3）拒取式证明（ 4） ：tr 前提引入t 化简律qs 前提引入st 前提引入qt 等价三段论（qt ）(tq) 置换（qt ）化简q 假言推理qp 前提引入名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 30 页 - - - - - - - - - 5 p 假言推理(11)pq 合取15 在自然推理系统 P中用附加前提法证明下面各推理：(1) 前提： p(qr),sp,q 结论： sr 证明s 附加前提引入sp 前提引入p 假言推理p(qr) 前提引入qr 假言推理q 前提引入r 假言推理16 在自然推理系统 P中用归谬法证明下面各推理：(1) 前提： pq,rq,rs 结论：p 证明：p 结论的否定引入pq 前提引入q 假言推理rq 前提引入r 化简律rs 前提引入r 化简律rr 合取由于最后一步 rr 是矛盾式 , 所以推理正确 . 第四章部分课后习题参考答案3. 在一阶逻辑中将下面将下面命题符号化, 并分别讨论个体域限制为(a),(b)条件时命名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 30 页 - - - - - - - - - 6 题的真值 : (1) 对于任意 x, 均有2=(x+)(x). (2) 存在 x, 使得 x+5=9. 其中(a) 个体域为自然数集合 . (b)个体域为实数集合 . 解：F(x): 2=(x+)(x). G(x): x+5=9. (1) 在两个个体域中都解释为)(xxF，在（ a）中为假命题，在 (b) 中为真命题。(2) 在两个个体域中都解释为)(xxG，在（ a）(b) 中均为真命题。4. 在一阶逻辑中将下列命题符号化: (1) 没有不能表示成分数的有理数. (2) 在北京卖菜的人不全是外地人. 解: (1)F(x): x能表示成分数 H(x): x是有理数命题符号化为 : )()(xHxFx(2)F(x): x是北京卖菜的人 H(x): x是外地人命题符号化为 : )()(xHxFx5. 在一阶逻辑将下列命题符号化: (1) 火车都比轮船快 . (3) 不存在比所有火车都快的汽车. 解: (1)F(x): x是火车 ; G(x): x是轮船 ; H(x,y): x比 y 快命题符号化为 : ),()()(yxHyGxFyx(2) (1)F(x): x是火车 ; G(x): x是汽车 ; H(x,y): x比 y 快命题符号化为 : ),()()(yxHxFxyGy9. 给定解释 I 如下: 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 30 页 - - - - - - - - - 7 (a) 个体域 D为实数集合 R. (b) D中特定元素=0. (c) 特定函数 (x,y)=xy,x,yD . (d) 特定谓词(x,y):x=y,(x,y):xy,x,yD . 说明下列公式在 I 下的含义 , 并指出各公式的真值 : (1),(),(yxFyxGyx(2),(),(yxGayxfFyx答:(1) 对于任意两个实数x,y, 如果 xy, 那么 xy. 真值 1. (2) 对于任意两个实数x,y, 如果 x-y=0, 那么 xy. 真值 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)x y(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) 因为1)()(pqppqp为永真式；所以为永真式；(3) 取解释 I 个体域为全体实数F(x,y) ：x+y=5 所以, 前件为任意实数x 存在实数 y 使 x+y=5，前件真；后件为存在实数x 对任意实数 y 都有 x+y=5，后件假， 此时为假命题名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 30 页 - - - - - - - - - 8 再取解释 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)(xf为3)4(,4)3(ff(c)1)3,4()4,3(,0)4,4()3, 3(),(FFFFyxF为. 试求下列公式在下的真值. (1),(yxyFx(3)(),(),(yfxfFyxFyx解:(1)4,()3 ,(),(xFxFxyxyFx)4,4()3,4()4,3()3,3(FFFF1)01()10(2)(),(),(yfxfFyxFyx)4(),()4,()3(),()3 ,(fxfFxFfxfFxFx)3),()4,()4),()3 ,(xfFxFxfFxFx名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 30 页 - - - - - - - - - 9 )3),3()4,3()4),3()3, 3(fFFfFF)3),4()4,4()4),4()3,4(fFFfFF)3,4()4,3()4 ,4(0(FFF)3 , 3(0()4,3(1(FF)11 ()00()00()11 (112. 求下列各式的前束范式。(1),()(yxyGxxF(5),()(),(2121211xxGxxHxxFx (本题课本上有错误 ) 解:(1),()(yxyGxxF),()(ytyGxxF),()(ytGxFyx (5),()(),(2121211xxGxxHxxFx),()(),(2323211xxGxxHxxFx),()(),(2332411xxGxHxxxFx),()(),(2334121xxGxHxxFxx15. 在自然数推理系统F 中, 构造下面推理的证明 : (1)前提: )()()()(yRyGyFyxxF,)(xxF结论: xR(x) (2)前提: x(F(x) (G(a) R(x), xF(x) 结论: x(F(x) R(x) 证明(1) )(xxF前提引入F(c) EI )()()()(yRyGyFyxxF前提引入)()()(yRyGyFy假言推理(F(c) G(c) R(c) UI F(c) G(c) 附加R(c) 假言推理xR(x) EG (2) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 30 页 - - - - - - - - - 10 xF(x) 前提引入F(c) EI x(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) 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 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 30 页 - - - - - - - - - 11 14化简下列集合表达式：（1） （AB）B ）- （AB）（2） （ （AB C）- （BC） ）A 解: (1) （AB）B ）- （AB）=（AB）B ）（AB）=（AB）（AB）)B=B=（2） （ （AB C）- （BC） ）A=（ （AB C）（BC） ）A =（A（BC ） ）（ （BC ）（BC） ）A =（A（BC ） ）A=（A（BC ） ）A=A 18某班有 25 个学生，其中 14 人会打篮球， 12 人会打排球， 6 人会打篮球和排球， 5人会打篮球和网球， 还有 2 人会打这三种球。已知 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. 设集合 A1 ，2，2 ，3，1，3, 计算下列表达式：（1）A （2）A （3）A （4）A 解: （1）A=1，22，31，3=1 ，2，3,（2）A=1，22，31，3=（3）A=123=（4）A=27、设 A,B,C 是任意集合，证明名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 30 页 - - - - - - - - - 12 (1)(A-B)-C=A- BC (2)(A-B)-C=(A-C)-(B-C) 证明(1) (A-B)-C=(AB) C= A( BC)= A(BC) =A- BC (2) (A-C)-(B-C)=(AC) (B C)= (AC) (BC) =(ACB) (ACC)= (ACB) = A(BC) =A- BC 由（1）得证。第七章部分课后习题参考答案7.列出集合 A=2,3,4 上的恒等关系 I A,全域关系 EA,小于或等于关系LA,整除关系 DA. 解：IA =, EA=, LA=, DA= 13.设 A=, B=, 求 AB,AB, domA, domB, dom(AB), ranA, ranB, ran(AB ), fld(A-B).解：AB=, AB= 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=,，fld(A-B)=1,2,3 14.设 R=, 求 R R, R-1, R0,1, R1,2解：R R=, 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 30 页 - - - - - - - - - 13 R-1,=, R0,1=, R1,2=ran(R|1,2)=2,3 16设 A=a,b,c,d ，1R，2R为 A 上的关系，其中1R=,a aa bb d2,Ra db cb dc b求23122112,RRRR RR。解: R1R2=, R2R1= R12=R1R1=, R22=R2R2=, R23=R2R22=,36设 A=1，2，3，4 ，在 A A上定义二元关系 R ，,A A ， u,v R u + y = x + v. (1) 证明 R 是 A A上的等价关系 . (2) 确定由 R 引起的对 A A的划分 . （1）证明： R u+y=x-y Ru-v=x-y A A u-v=u-v R R是自反的任意的 , AA 如果R ，那么 u-v=x-y x-y=u-v R R是对称的任意的 ,AA 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 30 页 - - - - - - - - - 14 若R,R 则 u-v=x-y,x-y=a-b u-v=a-b R R是传递的R是 AA上的等价关系(2) =, , , , , , 41. 设 A=1 ，2，3，4，R 为 AA 上的二元关系 , a，b ， c，dAA , a，bRc，da + b = c + d (1) 证明 R为等价关系 . (2) 求 R 导出的划分 . (1) 证明：a，bAA a+b=a+b R R是自反的任意的 , AA 设R，则 a+b=c+d c+d=a+b R R是对称的任意的 ,AA 若R,R 则 a+b=c+d,c+d=x+y a+b=x+y R R是传递的R是 AA上的等价关系(2) =, , , , , , 43. 对于下列集合与整除关系画出哈斯图: 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 30 页 - - - - - - - - - 15 (1) 1,2,3,4,6,8,12,24 (2) 1,2,3,4,5,6,7,8,9,10,11,12 解: 1234681224123456789101112 (1) (2) 45. 下图是两个偏序集 的哈斯图 . 分别写出集合 A和偏序关系 R的集合表达式 . abcdefgabcdefg (a) (b) 解: (a)A=a,b,c,d,e,f,g R=,AI (b) A=a,b,c,d,e,f,g R=,AI46. 分别画出下列各偏序集 的哈斯图 , 并找出 A 的极大元 极小元 最大元和最小元 . (1)A=a,b,c,d,e R =,IA. (2)A=a,b,c,d,e, R=IA. 解:名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 30 页 - - - - - - - - - 16 abcdeabcde(1) (2) 项目 (1) (2) 极大元 : e a,b,d,e 极小元 : a a,b,c,e 最大元 : e 无最小元 : a 无第八章部分课后习题参考答案1设 f :NN,且f (x)=12xxx，若 为奇数若 为偶数，求 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:NN,f(x)=(x)mod 3,x 除以 3 的余数不是满射，不是单射(3) f:NN,f(x)=10 xx，若 为奇数，若 为偶数不是满射，不是单射(4) f:N0,1,f(x)=01xx，若 为奇数，若 为偶数是满射，不是单射(5) f:N-0R,f(x)=lgx 不是满射，是单射(6) f:RR,f(x)=x2-2x-15 不是满射，不是单射名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 30 页 - - - - - - - - - 17 5. 设 X=a,b,c,d,Y=1,2,3,f=,判断以下命题的真假 : (1)f 是从 X 到 Y 的二元关系 ,但不是从 X 到 Y 的函数 ; 对(2)f 是从 X 到 Y 的函数 ,但不是满射 ,也不是单射的 ; 错(3)f 是从 X 到 Y 的满射 ,但不是单射 ; 错(4)f 是从 X 到 Y 的双射 . 错第十章部分课后习题参考答案4判断下列集合对所给的二元运算是否封闭：（1） 整数集合 Z 和普通的减法运算。封闭,不满足交换律和结合律，无零元和单位元（2） 非零整数集合普通的除法运算。 不封闭（3） 全体nn实矩阵集合（R）和矩阵加法及乘法运算，其中n 2。封闭 均满足交换律，结合律，乘法对加法满足分配律；加法单位元是零矩阵，无零元；乘法单位元是单位矩阵，零元是零矩阵；（4）全体nn实可逆矩阵集合关于矩阵加法及乘法运算，其中n 2。不封闭（5）正实数集合和运算，其中运算定义为：不封闭因为R1111111（6）n关于普通的加法和乘法运算。封闭，均满足交换律，结合律，乘法对加法满足分配律加法单位元是 0，无零元；乘法无单位元（1n） ，零元是 0；1n单位元是 1（7）A = ,21naaan运算定义如下：封闭 不满足交换律，满足结合律，（8）S = 关于普通的加法和乘法运算。封闭均满足交换律，结合律，乘法对加法满足分配律（9）S = 0,1,S 是关于普通的加法和乘法运算。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 30 页 - - - - - - - - - 18 加法不封闭，乘法封闭；乘法满足交换律，结合律（10）S = ,S关于普通的加法和乘法运算。加法不封闭，乘法封闭，乘法满足交换律，结合律5对于上题中封闭的二元运算判断是否适合交换律，结合律，分配律。见上题7设 * 为 Z 上的二元运算Zyx,，X * Y = min ( x，y ), 即 x 和 y 之中较小的数 .(1) 求 4 * 6 ，7 * 3 。4, 3(2)* 在Z上是否适合交换律，结合律，和幂等律？满足交换律，结合律，和幂等律(3) 求*运算的单位元，零元及Z 中所有可逆元素的逆元。单位元无，零元 1, 所有元素无逆元8QQSQ为有理数集， *为 S上的二元运算，,S有* = （1）*运算在 S上是否可交换，可结合？是否为幂等的？不可交换： *= * 可结合： (*)*=*= *(*)=*=(*)*=*(*) 不是幂等的（2）*运算是否有单位元，零元？如果有请指出，并求S中所有可逆元素的逆元。设是单位元，S ，*= *= 则=，解的 =，即为单位。设是零元，S ，*= *= 则=，无解。即无零元。S，设是它的逆元 *= *= = a=1/x,b=-y/x 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 30 页 - - - - - - - - - 19 所以当 x0 时，xyxyx,1,110令 S=a，b ，S上有四个运算： *，分别有表 10.8 确定。(a) (b) (c) (d) (1) 这 4 个运算中哪些运算满足交换律，结合律，幂等律？(a) 交换律，结合律，幂等律都满足，零元为 a,没有单位元；(b)满足交换律和结合律，不满足幂等律，单位元为a,没有零元bbaa11,(c)满足交换律 ,不满足幂等律 ,不满足结合律ababbabaabba)(,)(bbabba)()(没有单位元 , 没有零元(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)mod 4 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 30 页 - - - - - - - - - 20 问S，是否构成群？为什么？解：(1) x,y S, xy=(xy)mod 4S,是 S上的代数运算。(2) x,y,z S,设 xy=4k+r 30r (xy)z =(xy)mod 4)z=rz=(rz)mod 4 =(4kz+rz)mod 4=(4k+r)z)mod 4 =(xyz)mod 4 同理 x(yz) =(xyz)mod 4 所以， (xy)z = x(yz) ，结合律成立。(3) xS, (x1)=(1x)=x, ，所以 1 是单位元。(4), 33,1111 0 和 2 没有逆元所以， 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)，结合律成立。(3) 设e是单位元，xZ, xoe= eox=x, 即 x+e-2= e+x-2=x, e=2 (4) xZ , 设 x 的逆元是 y, xoy= yox=e, 即 x+y-2=y+x-2=2, 所以，xyx41所以Z，o构成群11. 设 G=1001,1001,1001,1001，证明 G关于矩阵乘法构成一个群解：(1) x,y G, 易知 xyG,乘法是 Z 上的代数运算。(2) 矩阵乘法满足结合律(3) 设1001是单位元，名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 30 页 - - - - - - - - - 21 (4) 每个矩阵的逆元都是自己。所以 G关于矩阵乘法构成一个群14. 设 G为群，且存在 aG,使得 G=akkZ证明：G是交换群。证明:x,y G ，设lkayax,，则yxaaaaaaxyklkllklk所以， G是交换群17. 设 G为群，证明 e 为 G中唯一的幂等元。证明: 设Ge0也是幂等元，则020ee，即eee020，由消去律知ee018. 设 G为群，a,b,c G,证明abc=bca=cab证明： 先证设ebcaeabckk)()(设,)(eabck则eabcabcabcabc)()()(，即eab c ab c ab c ab c aa1)()()(左边同乘1a，右边同乘a得eeaabacbcabcabcabcak1)()()()(反过来，设,)(eback则.)(eabck由元素阶的定义知， abc=bca，同理 bca=cab19. 证明：偶数阶群 G必含 2 阶元。证明： 设群 G不含 2 阶元，Ga，当ea时，a是一阶元，当ea时，a至少是 3阶元, 因为群 G时有限阶的，所以a是有限阶的，设a是 k 阶的, 则1a也是 k 阶的，所以高于 3 阶的元成对出现的， G不含 2 阶元， G含唯一的 1 阶元e, 这与群 G是偶数阶的矛盾。所以，偶数阶群G必含 2 阶元名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 21 页，共 30 页 - - - - - - - - - 22 20. 设 G为非 Abel 群，证明 G中存在非单位元 a 和 b,ab, 且 ab=ba. 证明： 先证明 G含至少含 3 阶元。若 G只含 1 阶元, 则 G=e,G 为 Abel 群矛盾；若 G除了 1 阶元 e 外, 其余元a均为 2 阶元，则ea2，aa1bababaabababbbaaGba111111)(,)( ,所以，与 G为 Abel 群矛盾；所以，G含至少含一个 3 阶元，设为a，则 a2a，且22aaaa。令2ab的证。21. 设 G是 Mn(R) 上的加法群， n2，判断下述子集是否构成子群。（1）全体对称矩阵是子群（2）全体对角矩阵是子群（3）全体行列式大于等于0 的矩阵 . 不是子群（4）全体上（下）三角矩阵。是子群22. 设 G为群，a 是 G中给定元素， a 的正规化子 N （a）表示 G中与 a 可交换的元素构成的集合，即 N（a）=xxG xa=ax 证明 N（a）构成 G的子群。证明： ea=ae,)(aNeyaayxaaxaNyx,),(,则axyyaxayxyxayaxxya)()()()()()(, 所以)(aNxy由xaax，得111111,eaxaexxaxxaxxx，即11axax，所以)(1aNx所以 N （a）构成 G的子群31. 设1是群 G1到 G2的同态，2是 G2到 G3的同态，证明12是 G1到 G3的同态。证明： 有已知1是 G1到 G2的函数，2是 G2到 G3的函数，则12是 G1到 G3的函数。,1Gba)()()()(1121221baabab)()()()()(21211212baba所以:12是 G1到 G3的同态。33. 证明循环群一定是阿贝尔群，说明阿贝尔群是否一定为循环群，并证明你的结论。证明： 设 G是循环群 , 令 G=,Gyx, 令lkayax, 那么名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 22 页，共 30 页 - - - - - - - - - 23 yxaaaaaaxyklkllklk,G 是阿贝尔群克莱因四元群 ,cbaeGeabccaecbbbceaacbaeecbae是交换群 , 但不是循环群 , 因为 e是一阶元， a,b,c是二阶元。36. 设, 是 5 元置换，且3541254321，2154354321(1) 计算111,；(2) 将11,表成不交的轮换之积。(3) 将（2）中的置换表示成对换之积，并说明哪些为奇置换，哪些为偶置换。解：(1) 12354543215213454321321545432114351254321123145543211(2) )1425()14253(1)25)(143(1(3) )15)(12)(14(奇置换，)13)(15)(12)(14(1偶置换)25)(13)(14(1奇置换第十四章部分课后习题参考答案5、设无向图 G有 10 条边， 3 度与 4 度顶点各 2 个，其余顶点的度数均小于3，问 G至少有多少个顶点？在最少顶点的情况下，写出度数列、)()(GG 、。解：由握手定理图 G的度数之和为：201023 度与 4 度顶点各 2 个，这 4 个顶点的度数之和为14 度。其余顶点的度数共有6 度。其余顶点的度数均小于3，欲使 G的顶点最少，其余顶点的度数应都取2, 所以， G至少有 7 个顶点 , 出度数列为 3,3,4,4,2,2,2,2)(,4)(GG. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 23 页，共 30 页 - - - - - - - - - 24 7、 设有向图 D的度数列为 2， 3， 2， 3， 出度列为 1， 2， 1， 1， 求 D的入度列，并求)(),(DD，)(),(DD,)(),(DD. 解：D的度数列为 2，3，2，3，出度列为 1，2，1，1，D的入度列为 1,1,1,2. 2)(,3)(DD,1)(, 2)(DD,1)(,2)(DD8、设无向图中有 6 条边，3 度与 5 度顶点各 1 个，其余顶点都是 2 度点，问该图有多少个顶点？解：由握手定理图 G的度数之和为：1262设 2 度点x个，则1221513x，2x，该图有 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) 22+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 的补图G的边数 m 。解：mnnm2)1(21、无向图 G 如下图名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 24 页，共 30 页 - - - - - - - - - 25 (1)求 G 的全部点割集与边割集，指出其中的割点和桥；(2) 求 G 的点连通度)(Gk与边连通度)(G。abcdee1e2e3e4e5解：点割集 : a,b,(d) 边割集 e2,e3,e3,e4,e1,e2,e1,e4e1,e3,e2,e4,e5 )(Gk=)(G=1 23、求 G 的点连通度)(Gk、边连通度)(G与最小度数)(G。解：2)(Gk、3)(G、4)(G28、设 n 阶无向简单图为 3-正则图，且边数