2023年12月27日发(作者：怎么做数学试卷的妙招视频)
离散数学答案 屈婉玲版第二版 高等教育出版社课后答案
第一章部分课后习题参考答案
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→01
17．判断下面一段论述是否为真：“是无理数。并且，如果3是无理数，则2也是无理数。另外6能被2整除，6才能被4整除。”
答：p:
是无理数 1
q: 3是无理数 0
r:
2是无理数 1
s: 6能被2整除 1
t: 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）
p q p→q
q
p
q→p (p→q)→(q→p)
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）公式类型为永真式（方法如上例）
第二章部分课后习题参考答案
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)
P q r p∨q p∧r （p∨q）→(p∧r)
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→(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)
m0m2m3
∑(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))
11
1
所以该式为永真式.
永真式的主合取范式为 1
主析取范式为∑(0,1,2,3,4,5,6,7)
第三章部分课后习题参考答案
14. 在自然推理系统P中构造下面推理的证明：
(2)前提：pq,(qr),r
结论：p
(4)前提：qp,qs,st,tr
结论：pq
证明：（2）
①(qr) 前提引入
②q③qr ①置换
r ②蕴含等值式
④r 前提引入
⑤q ③④拒取式
⑥pq 前提引入
⑦￢p（3） ⑤⑥拒取式
证明（4）：
①tr 前提引入
②t ①化简律
③qs 前提引入
④st 前提引入
⑤qt ③④等价三段论
⑥（qt）(tq) ⑤ 置换
⑦（qt） ⑥化简
⑧q ②⑥ 假言推理
⑨qp 前提引入
⑩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 结论的否定引入
②p﹁q 前提引入
③﹁q ①②假言推理
④￢rq 前提引入
⑤￢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)在两个个体域中都解释为xF(x)，在（a）中为假命题，在(b)中为真命题。
(2)在两个个体域中都解释为xG(x)，在（a）(b)中均为真命题。
4. 在一阶逻辑中将下列命题符号化:
(1) 没有不能表示成分数的有理数.
(2) 在北京卖菜的人不全是外地人.
解:
(1)F(x): x能表示成分数
H(x): x是有理数
命题符号化为:
x(F(x)H(x))
(2)F(x): x是北京卖菜的人
H(x): x是外地人
命题符号化为:
x(F(x)H(x))
5. 在一阶逻辑将下列命题符号化:
(1) 火车都比轮船快.
(3) 不存在比所有火车都快的汽车.
解:
(1)F(x): x是火车; G(x): x是轮船; H(x,y): x比y快
命题符号化为:
xy((F(x)G(y))H(x,y))
(2) (1)F(x): x是火车; G(x): x是汽车; H(x,y): x比y快
命题符号化为:
y(G(y)x(F(x)H(x,y)))
9.给定解释I如下:
(a) 个体域D为实数集合R.
(b) D中特定元素=0.
(c) 特定函数(x,y)=xy,x,yD.
(d) 特定谓词(x,y):x=y,(x,y):x 说明下列公式在I下的含义,并指出各公式的真值: (1) xy(G(x,y)F(x,y)) (2) xy(F(f(x,y),a)G(x,y)) 答:(1) 对于任意两个实数x,y,如果x (2) 对于任意两个实数x,y,如果x-y=0, 那么x 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)因为 p(qp)p(qp)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)f(x)为f(3)4,f(4)3 (c)F(x,y)为F(3,3)F(4,4)0,F(3,4)F(4,3)1. 试求下列公式在Ｉ下的真值. (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)) (F(3,3)F(3,4))(F(4,3)F(4,4)) (01)(10)1 (2) xy(F(x,y)F(f(x),f(y))) x((F(x,3)F(f(x),f(3)))(F(x,4)F(f(x),f(4)))) x((F(x,3)F(f(x),4))(F(x,4)F(f(x),3))) ((F(3,3)F(f(3),4))(F(3,4)F(f(3),3))) ((F(4,3)F(f(4),4))(F(4,4)F(f(4),3))) ((0F(4,4))(F(3,4)F(4,3)))((1F(3,4))(0F(3,3))) (00)(11)(11)(00)1 12.求下列各式的前束范式。 (1)xF(x)yG(x,y) (5)x1F(x1,x2)(H(x1)x2G(x1,x2)) (本题课本上有错误) 解:(1) xF(x)yG(x,y)xF(x)yG(t,y)xy(F(x)G(t,y)) (5) x1F(x1,x2)(H(x1)x2G(x1,x2)) x1F(x1,x2)(H(x3)x2G(x3,x2)) x1F(x1,x4)x2(H(x3)G(x3,x2)) x1x2(F(x1,x4)(H(x3)G(x3,x2))) 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) ①EI ③xF(x)y((F(y)G(y))R(y)) 前提引入 ④y((F(y)G(y))R(y)) ①③假言推理 ⑤(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)) ③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}} } 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=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.设集合A＝{{1，2}，{2，3}，{1，3},{}},计算下列表达式： （1）A （2）A （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=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}上的恒等关系I A,全域关系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}，R1，R2为A上的关系，其中 R1=a,a,a,b,b,d R2a,d,b,c,b,d,c,b23求R1R2,R2R1,R1,R2。 解: R1R2={ R2R1={ R12=R1R1={ R22=R2R2={ R23=R2R22={ 36．设A={1，2，3，4}，在AA上定义二元关系R， (1)证明R 是AA上的等价关系. (2)确定由R 引起的对AA的划分. （1）证明：∵ u+y=x-y ∴ ∵u-v=u-v ∴ ∴R是自反的 任意的 如果 ∴x-y=u-v ∴ ∴R是对称的 任意的 若 则u-v=x-y,x-y=a-b ∴u-v=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=a+b ∴ ∴R是自反的 任意的 设 ∴c+d=a+b ∴ ∴R是对称的 任意的 若 则a+b=c+d,c+d=x+y ∴a+b=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} 解: 248842511 107 42 (1) (2) 45.下图是两个偏序集 debafc gbcfdeag (a) (b) 解: (a)A={a,b,c,d,e,f,g} R={ (b) A={a,b,c,d,e,f,g} R={ 46.分别画出下列各偏序集 (1)A={a,b,c,d,e} R={ (2)A={a,b,c,d,e}, R={ 解: edbcadea bc (1) (2) 项目 (1) (2) 极大元: e a,b,d,e 极小元: a a,b,c,e 最大元: e 无 最小元: a 无 第八章部分课后习题参考答案 1．设f :NN,且 1，若x为奇数 f (x)=x 若x为偶数2，求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的余数 不是满射，不是单射 1，若x为奇数 (3) f:NN,f(x)= 不是满射，不是单射 0，若x为偶数 0，若x为奇数 (4) f:N{0,1},f(x)= 是满射，不是单射 1，若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={ (1)f是从X到Y的二元关系,但不是从X到Y的函数; 对 (2)f是从X到Y的函数,但不是满射,也不是单射的; 错 (3)f是从X到Y的满射,但不是单射; 错 (4)f是从X到Y的双射. 错 第十章部分课后习题参考答案 4．判断下列集合对所给的二元运算是否封闭： （1） 整数集合Z和普通的减法运算。 封闭,不满足交换律和结合律，无零元和单位元 （2） 非零整数集合普通的除法运算。不封闭 （R）和矩阵加法及乘法运算，其中n2。 （3） 全体nn实矩阵集合封闭 均满足交换律，结合律，乘法对加法满足分配律； 加法单位元是零矩阵，无零元； 乘法单位元是单位矩阵，零元是零矩阵； （4）全体nn实可逆矩阵集合关于矩阵加法及乘法运算，其中n2。不封闭 （5）正实数集合和运算，其中运算定义为： 不封闭 因为 1111111R （6）n关于普通的加法和乘法运算。 封闭，均满足交换律，结合律，乘法对加法满足分配律 加法单位元是0，无零元； 乘法无单位元（n1），零元是0；n1单位元是1 （7）A = {a1,a2,,an} n运算定义如下： 封闭 不满足交换律，满足结合律， （8）S = 关于普通的加法和乘法运算。 封闭 均满足交换律，结合律，乘法对加法满足分配律 （9）S = {0,1},S是关于普通的加法和乘法运算。 加法不封闭，乘法封闭；乘法满足交换律，结合律 （10）S = ,S关于普通的加法和乘法运算。 加法不封闭，乘法封闭，乘法满足交换律，结合律 5．对于上题中封闭的二元运算判断是否适合交换律，结合律，分配律。 见上题 7．设 * 为Z上的二元运算x,yZ， X * Y = min ( x，y ),即x和y之中较小的数. (1)求4 * 6，7 * 3。 4, 3 (2)* 在Z上是否适合交换律，结合律，和幂等律？ 满足交换律，结合律，和幂等律 (3)求*运算的单位元，零元及Z中所有可逆元素的逆元。 单位元无，零元1, 所有元素无逆元 8．SQQ Q为有理数集，*为S上的二元运算， < a，b >* （1）*运算在S上是否可交换，可结合？是否为幂等的？ 不可交换： 可结合：( ( 不是幂等的 （2）*运算是否有单位元，零元？ 如果有请指出，并求S中所有可逆元素的逆元。 设 则 设 则 a=1/x,b=-y/x 所以当x0时，x,y11y, xx 10．令S={a，b}，S上有四个运算：*， 分别有表10.8确定。 (a) (b) (c) (d) (1)这4个运算中哪些运算满足交换律，结合律，幂等律？ (a) 交换律，结合律，幂等律都满足， 零元为a,没有单位元； (b)满足交换律和结合律，不满足幂等律，单位元为a,没有零元 a1a,b1b (c)满足交换律,不满足幂等律,不满足结合律 a(bb)aab, a(bb)(ab)b 没有单位元, 没有零元 (d) 不满足交换律，满足结合律和幂等律 没有单位元, 没有零元 (2)求每个运算的单位元，零元以及每一个可逆元素的逆元。 见上 (ab)baba 16．设V=〈 N，+ ，〉，其中+ ，分别代表普通加法与乘法，对下面给定的每个集合确定它是否构成V的子代数，为什么？ （1）S1=（2）S2= 是 不是 加法不封闭 （3）S3 = {-1，0，1} 不是，加法不封闭 第十一章部分课后习题参考答案 8.设S={0，1，2，3}，为模4乘法，即 y=(xy)mod 4 \"x,y∈S, x 问〈S，〉是否构成群？为什么？ y=(xy)mod 4S,是S上的代数运算。 解：(1) x,y∈S, x(2) x,y,z∈S,设xy=4k+r 0r3 (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 y)z = x1)=(1(yz)，结合律成立。 所以，(x(3) x∈S, (xx)=x,，所以1是单位元。 (4)111,313, 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是单位元，x∈Z, xoe= eox=x,即x+e-2= e+x-2=x, e=2 (4) x∈Z , 设x的逆元是y, xoy= yox=e, 即x+y-2=y+x-2=2, 所以，x1y4x 所以〈Z，o〉构成群 〉不构成群 101011.设G=01,01,101001,01，证明G关于矩阵乘法构成一个群． 解：(1) x,y∈G, 易知xy∈G,乘法是Z上的代数运算。 (2) 矩阵乘法满足结合律 10(3)设01是单位元， (4)每个矩阵的逆元都是自己。 所以G关于矩阵乘法构成一个群． 14.设G为群，且存在a∈G,使得 G={ak∣k∈Z} 证明：G是交换群。 证明:x,y∈G，设xak,yal，则 xyakalaklalkalakyx 所以，G是交换群 17.设G为群，证明e为G中唯一的幂等元。 22e0，即e0e0e，由消去律知e0e 证明:设e0G也是幂等元，则e0 18.设G为群，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)e,则(abc)e. kk由元素阶的定义知，∣abc∣=∣bca∣，同理∣bca∣=∣cab∣ 19.证明：偶数阶群G必含2阶元。 证明：设群G不含2阶元，aG，当ae时，a是一阶元，当ae时，a至少是3阶元,因为群G时有限阶的，所以a是有限阶的，设a是k阶的,则a1也是k阶的，所以高于3阶的元成对出现的，G不含2阶元，G含唯一的1阶元e,这与群G是偶数阶的矛盾。所以，偶数阶群G必含2阶元 20.设G为非Abel群，证明G中存在非单位元a和b,a≠b,且ab=ba. 证明：先证明G含至少含3阶元。 若G只含1阶元,则G={e},G为Abel群矛盾； 若G除了1阶元e外,其余元a均为2阶元，则a2e，a1a a,bG,a1a,b1b,(ab)1ab,所以aba1b1(ba)1ba， 与G为Abel群矛盾； 所以，G含至少含一个3阶元，设为a，则aa2，且a2aaa2。 令ba2的证。 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,eN(a) x,yN(a),则axxa,ayya a(xy)(ax)y(xa)yx(ay)x(ya)(xy)a,所以xyN(a) 由axxa，得x1axx1x1xax1,x1aeeax1，即x1aax1，所以x1N(a) 所以N（a）构成G的子群 31.设1是群G1到G2的同态，2是G2到G3的同态，证明12是G1到G3的同态。 证明：有已知1是G1到G2的函数，2是G2到G3的函数，则1·2是G1到G3的函数。 a,bG1,(12)(ab)2(1(ab))2(1(a)1(b)) (2(1(a)))(2(1(b)))(12)(a)(12)(b) 所以:1·2是G1到G3的同态。 33.证明循环群一定是阿贝尔群，说明阿贝尔群是否一定为循环群，并证明你的结论。 证明：设G是循环群,令G=,x,yG,令xak,yal,那么 xyakalaklalkalakyx,G是阿贝尔群 克莱因四元群,G{e,a,b,c} eeabeabecccaabbccb eacbae是交换群,但不是循环群,因为e是一阶元，a,b,c是二阶元。 36.设,是5元置换，且 21453，34512 (1)计算,,1,1,1； (2)将,1,1表成不交的轮换之积。 (3)将（2）中的置换表示成对换之积，并说明哪些为奇置换，哪些为偶置换。 12345123451234512345112345解：(1) 4532143125 45123 1 12153454132 1234512345(2) (1425) 1(14253) 1(143)(25) (3) (14)(12)(15) 奇置换， 1(14)(12)(15)(13) 偶置换 1(14)(13)(25) 奇置换 第十四章部分课后习题参考答案 5、设无向图G有10条边，3度与4度顶点各2个，其余顶点的度数均小于3，问G至(G)。 少有多少个顶点？在最少顶点的情况下，写出度数列、(G)、 解：由握手定理图G的度数之和为：21020 3度与4度顶点各2个，这4个顶点的度数之和为14度。 其余顶点的度数共有6度。 其余顶点的度数均小于3，欲使G的顶点最少，其余顶点的度数应都取2, 所以，G至少有7个顶点, 出度数列为3,3,4,4,2,2,2,(G)4,(G)2. 7、设有向图D的度数列为2，3，2，3，出度列为1，2，1，1，求D的入度列，并求(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)1 8、设无向图中有6条边，3度与5度顶点各1个，其余顶点都是2度点，问该图有多少个顶点？ 解：由握手定理图G的度数之和为：2612 设2度点x个，则31512x12，x2，该图有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的补图G的边数m。 解：mn(n1)m 221、无向图G如下图 (1)求G的全部点割集与边割集，指出其中的割点和桥； (2) 求G的点连通度k(G)与边连通度(G)。 ae2be3解：点割集: {a,b},(d) e1de5ee4c 边割集{e2,e3},{e3,e4},{e1,e2},{e1,e4}{e1,e3},{e2,e4},{e5} k(G)=(G)=1 23、求G的点连通度k(G)、边连通度(G)与最小度数(G)。 解：k(G)2、(G)3 、(G)4 28、设n阶无向简单图为3-正则图，且边数m与n满足2n-3=m问这样的无向图有几种非同构的情况？ 3n2m解： 得n=6,m=9. 2n3m 31、设图G和它的部图G的边数分别为m和m，试确定G的阶数。 解：mm118(mm)n(n1) 得n 2245、有向图D如图 (1)求v2到v5长度为1，2，3，4的通路数； (2)求v5到v5长度为1，2，3，4的回路数； (3)求D中长度为4的通路数； (4)求D中长度小于或等于4的回路数； (5)写出D的可达矩阵。 v1v4v5v2v3 解：有向图D的邻接矩阵为： 0000101010202010100020202A0000000110A320010100，A201002201010000202200020000000004012154040052522A400004 AA2A3A422154040014522 04040225254(1)v2到v5长度为1，2，3，4的通路数为0,2,0,0； (2)v5到v5长度为1，2，3，4的回路数为0,0,4,0； (3)D中长度为4的通路数为32； (4)D中长度小于或等于4的回路数10； 1111111111(4)出D的可达矩阵P1111111111 11111第十六章部分课后习题参考答案 、画出所有5阶和7阶非同构的无向树. 00004 1 2、一棵无向树T有5片树叶，3个2度分支点，其余的分支点都是3度顶点，问T有几个顶点? 解：设3度分支点x个，则 51323x2(53x1)，解得x3 T有11个顶点 3、无向树T有8个树叶，2个3度分支点，其余的分支点都是4度顶点，问T有几个4度分支点？根据T的度数列，请至少画出4棵非同构的无向树。 解：设4度分支点x个，则 81234x2(82x1)，解得x2 度数列4 4、棵无向树T有ni (i=2，3，…，k)个i度分支点，其余顶点都是树叶，问T应该有几片树叶? 解：设树叶x片，则 niix12(nix1)，解得x(i2)ni2 评论：2，3，4题都是用了两个结论,一是握手定理，二是mn1 5、n(n≥3)阶无向树T的最大度解：2，n-1 6、若n(n≥3)阶无向树T的最大度解：n-1 7、证明：n(n≥2) 阶无向树不是欧拉图. =2，问T中最长的路径长度为几？ 至少为几？最多为几？ 证明：无向树没有回路，因而不是欧拉图。 8、证明：n(n≥2) 阶无向树不是哈密顿图. 证明：无向树没有回路，因而不是哈密顿图。 9、证明：任何无向树T都是二部图. 证明：无向树没有回路，因而不存在技术长度的圈，是二部图。 10、什么样的无向树T既是欧拉图，又是哈密顿图? 解：一阶无向树 14、设e为无向连通图G中的一条边， e在G的任何生成树中，问e应有什么性质? 解：e是桥 15、设e为无向连通图G中的一条边， e不在G的任何生成树中， 问e应有什么性质? 解：e是环 23、已知n阶m条的无向图 G是k(k≥2)棵树组成的森林，证明：m = n-k.； 证明：数学归纳法。k=1时, m = n-1，结论成立； 设k=t-1(t-11)时，结论成立，当k=t时, 无向图 G是t棵树组成的森林,任取两棵树，每棵树任取一个顶点，这两个顶点连线。则所得新图有t-1棵树，所以m = n-（k-1）. 所以原图中m = n-k 得证。 24、在图16.6所示2图中，实边所示的生成子图T是该图的生成树. (1)指出T的弦，及每条弦对应的基本回路和对应T的基本回路系统. (2) 指出T的所有树枝， 及每条树枝对应的基本割集和对应T的基本割集系统. 图16.16 解：(a)T的弦：c,d,g,h (a) (b) T的基本回路系统: S={{a,c,b},{a,b,f,d},{e,a,b,h},{e,a,b,f,g}} T的所有树枝: e,a,b,f T的基本割集系统: S={{e,g,h},{a,c,d,g,h},{b,c,d,g,h},{f,d,g}} (b)有关问题仿照给出 25、求图16.17所示带权图中的最小生成树. (a) (b) 图16.17 解： 注：答案不唯一。 37、画一棵权为3，4，5，6，7，8，9的最优2叉树，并计算出它的权. 38.下面给出的各符号串集合哪些是前缀码? A1={0，10，110，1111} 是前缀码 A2={1，01，001，000} 是前缀码 A3={1，11，101，001，0011} 不是前缀码 A4={b，c，aa，ac，aba，abb，abc} 是前缀码 A5={ b，c，a，aa，ac，abc，abb，aba} 不是前缀码 41.设7个字母在通信中出现的频率如下: a: 35% b: 20% c: 15% d: 10% e: 10% f: 5% g: 5% 用Huffman算法求传输它们的前缀码.要求画出最优树，指出每个字母对应的编码.并指出传输10n(n≥2)个按上述频率出现的字母，需要多少个二进制数字. 解： a:01 b:10 c:000 d:110 e:001 f:1111 g:1110 W(T)=5*4+5*4+10*3+10*3+15*3+20*2+35*2=255 传输10n(n≥2)个按上述频率出现的字母，需要255*10n-2个二进制数字.
更多推荐
集合,下列,证明,满足
发布评论