奥迪汽车制造总厂董事
范文一：离散数学(屈婉玲)答案
第一章部分课后习题参考答案
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 ,,,
,217(判断下面一段论述是否为真:“是无理数。并且，如果3是无理数，则也是无理数。另外6能被2整除，6才能被4整除。”
,答:p: 是无理数 1
q: 3是无理数 0
2 r: 是无理数 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
所以公式类型为永真式 //最后一列全为1
(5)公式类型为可满足式(方法如上例)//最后一列至少有一个1 (6)公式类型为永真式(方法如上例)//
第二章部分课后习题参考答案
3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值.
1
，(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)
2
,，，,,,(pq)(qp)
,，，，,,,(pq)(qp)
,，，，，，，,,,,,,,,, (pq)(qp)(qp)(pq)(pq)
,，，，,,,,, (pq)(pq)(pq)
,m,m,m 023
,?(0,2,3)
主合取范式:
，，, (p?q)?(qp)
,，，,,,(pq)(qp)
,，，，,,,(pq)(qp)
,，，，，,,,,, (p(qp))(q(qp))
,，,, 1(pq)
,,，, (pq) M 1
, ?(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)
3
第三章部分课后习题参考答案
14. 在自然推理系统P中构造下面推理的证明:
,,， (2)前提:pq,(qr),r
结论:，p
,,,, (4)前提:qp,qs,st,tr
,结论:pq
证明:(2)
，,?(qr) 前提引入
，，,?qr ?置换
，,?qr ?蕴含等值式
?r 前提引入
，?q ??拒取式
,?pq 前提引入
?，p ??拒取式
证明(4):
,?tr 前提引入
?t ?化简律
,?qs 前提引入
,?st 前提引入
,?qt ??等价三段论
,,,?(qt)(tq) ? 置换
,?(qt) ?化简
?q ?? 假言推理
,?qp 前提引入
?p ??假言推理
,(11)pq ??合取 15在自然推理系统P中用附加前提法证明下面各推理:
4
,,,(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
错误～未找到引用源。).
5
(2) 存在x,使得x+5=9.
其中(a)个体域为自然数集合.
(b)个体域为实数集合.
解:
F(x): 错误～未找到引用源。2=(x+错误～未找到引用源。)(x错误～未找到
引用源。).
G(x): x+5=9.
(1)在两个个体域中都解释为，在(a)中为假命题，在(b)中为真命题。 ,xF(x)
(2)在两个个体域中都解释为，在(a)(b)中均为真命题。 ，xG(x)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快
,x,y((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.
6
(b) D中特定元素错误～未找到引用源。=0.
(c) 特定函数错误～未找到引用源。(x,y)=x错误～未找到引用源。y,x,y错,D误～未找到引用源。.
(d) 特定谓词错误～未找到引用源。(x,y):x=y,错误～未找到引用源。(x,y):x
说明下列公式在I下的含义,并指出各公式的真值:
(1) ,x,y(G(x,y),，F(x,y))
(2) ,x,y(F(f(x,y),a),G(x,y))
,答:(1) 对于任意两个实数x,y,如果x
(2) 对于任意两个实数x,y,如果x-y=0, 那么x
(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).
p,(q,p),，p,(，q,p),1解:(1)因为 为永真式;
所以 错误～未找到引用源。为永真式;
(3)取解释I个体域为全体实数
F(x,y):x+y=5
所以,前件为任意实数x存在实数y使x+y=5，前件真;
后件为存在实数x对任意实数y都有x+y=5，后件假，]
7
此时为假命题
再取解释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)个体域:本班同学
x会吃饭, G(x):x会睡觉.成真解释 F(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};
f(x)f(3),4,f(4),3(b)错误～未找到引用源。为错误～未找到引用源。
F(x,y)为F(3,3),F(4,4),0,F(3,4),F(4,3),1(c)错误～未找到引用源。.
试求下列公式在，下的真值.
,x，yF(x,y)(1)
,x,y(F(x,y),F(f(x),f(y)))(3)
,x，yF(x,y),,x(F(x,3),F(x,4))解:(1)
(F(3,3),F(3,4)),(F(4,3),F(4,4)) ,
(0,1),(1,0),1 ,
,x,y(F(x,y),F(f(x),f(y)))(2)
8
,,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)))
,((0,F(4,4)),(F(3,4),F(4,3))),((1,F(3,4)),(0,F(3,3)))
,(0,0),(1,1),(1,1),(0,0),112.求下列各式的前束范式。
(1) ,xF(x),,yG(x,y)
，xF(x,x),(H(x),，，xG(x,x)) (本题课本上有错误) (5)1121212
解:(1) ,xF(x),,yG(x,y),,xF(x),,yG(t,y),，x,y(F(x),G(t,y))
(5) ，xF(x,x),(H(x),，，xG(x,x)) 1121212
,，xF(x,x),(H(x),,x，G(x,x)) 1123232
,，xF(x,x),,x(H(x),，G(x,x)) 1142332
,,x,x(F(x,x),(H(x),，G(x,x))) 121433215.在自然数推理系统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 ，
9
(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)) ，
第六章部分课后习题参考答案
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}} ,
10
(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,CA:B ,
如图所示。
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}{}=,,
11
:::::(3)A=123=,,
::A=(4),
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, A,C - B=A:::::C)=(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,全域关系E,小于或等于关系L,整除关系D. AAAA
解:I={<2，2>,<3,3>,<4,4>} A
E={<2,2>,<2,3>,<2,4>,<3,4>,<4,4>,<3,2>,<3,3>,<4,2>,<4,3>} A
L={<2,2>,<2,3>,<2,4>,<3,3>,<3,4>,<4,4>} A
D={<2,4>} A
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}
,fld R=dom Rran R
12
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>}
-1求R,R, R, R{0,1,}, R[{1,2}] ,
解:R,R={<0,2>,<0,3>,<1,3>} -1R,={<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} ,
RR16(设A={a,b,c,d}，为A上的关系，其中 21，
aaabbd,,,,,R,,1=
Radbcbdcb,,,,,,,,,,2
23RRRRRR,,,求。 122112
,解: RR={,,} 12
, RR={ 2,R=RR={,,} 111 2,R=RR={ 32,R=RR={ ，36(设A={1，2，3，4}，在AA上定义二元关系R， ,， ，(1)证明R 是AA上的等价关系. ，(2)确定由R 引起的对AA的划分. (1)证明:? ? ,， ?u-v=u-v ? 13 ?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 ?R是自反的 任意的, 设R ?c+d=a+b ? ?R是对称的 任意的, 若R 则a+b=c+d,c+d=x+y ?a+b=x+y ?R 14 ?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} 解: 24 812 12810649 4653721123 11 (1) (2) 45.下图是两个偏序集的哈斯图.分别写出集合A和偏序关系R的集合表达式. fdegfcdbbc eg aa (a) (b) 解: (a)A={a,b,c,d,e,f,g} ,IR={,,,,,, (b) A={a,b,c,d,e,f,g} ,IR={,,,,, 46.分别画出下列各偏序集的哈斯图,并找出A的极大元`极小元`最大元和 15 最小元. (1)A={a,b,c,d,e} ,R={,,,, ,(2)A={a,b,c,d,e}, R={ 解: e d bdc e ab ca (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，, -1求f (0), f ({0}), f (1), f ({1}), f ({0,2,4,6,?})，f ({4,6,8}), f ({3,5,7}). 解:f (0)=0, f ({0})={0}, f (1)=1, f ({1})={1}, -1 f ({0,2,4,6,?})=N，f ({4,6,8})={2,3,4}, f ({3,5,7})={6,10,14}. 4. 判断下列函数中哪些是满射的?哪些是单射的?哪些是双射的? 2, (1) f:NN, f(x)=x+2 不是满射，不是单射 , (2) f:NN,f(x)=(x)mod 3, x除以3的余数 不是满射，不是单射 1，若为奇数x,, (3) f:NN,f(x)= 不是满射，不是单射 ,0，若为偶数x, 16 0，若为奇数x,, (4) f:N{0,1},f(x)= 是满射，不是单射 ,1，若为偶数x, , (5) f:N-{0}R,f(x)=lgx 不是满射，是单射 2, (6) f:RR,f(x)=x-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) 非零整数集合错误～未找到引用源。普通的除法运算。不封闭 n，n(3) 全体实矩阵集合错误～未找到引用源。(R)和矩阵加法及乘法运算，其 中n错误～未找到引用源。2。 封闭 均满足交换律，结合律，乘法对加法满足分配律; 加法单位元是零矩阵，无零元; 乘法单位元是单位矩阵，零元是零矩阵; n，n(4)全体实可逆矩阵集合关于矩阵加法及乘法运算，其中n错误～未找到引用源。2。不封闭 (5)正实数集合错误～未找到引用源。和错误～未找到引用源。运算，其中错误～未找到引用源。运算定义为: 错误～未找到引用源。 ， 不封闭 因为 1,1,1，1,1,1,,1,R 17 n(6)错误～未找到引用源。关于普通的加法和乘法运算。 封闭，均满足交换律，结合律，乘法对加法满足分配律 加法单位元是0，无零元; 乘法无单位元()，零元是0;单位元是1 n,1n,1 a,a,？,a}(7)A = { 错误～未找到引用源。n错误～未找到引用源。运算定义12n 如下: 错误～未找到引用源。 封闭 不满足交换律，满足结合律， (8)S = 错误～未找到引用源。关于普通的加法和乘法运算。 封闭 均满足交换律，结合律，乘法对加法满足分配律 (9)S = {0,1},S是关于普通的加法和乘法运算。 加法不封闭，乘法封闭;乘法满足交换律，结合律 (10)S = 错误～未找到引用源。 ,S关于普通的加法和乘法运算。 加法不封闭，乘法封闭，乘法满足交换律，结合律 5(对于上题中封闭的二元运算判断是否适合交换律，结合律，分配律。 见上题 ，，,x,y,ZZ7( 设 * 为错误～未找到引用源。上的二元运算， X * Y = min ( x，y ),即x和y之中较小的数. (1)求4 * 6，7 * 3。 4, 3 ，Z(2)* 在上是否适合交换律，结合律，和幂等律, 满足交换律，结合律，和幂等律 ，Z运算的单位元，零元及中所有可逆元素的逆元。 (3)求* 单位元无，零元1, 所有元素无逆元 QS,Q，Q8( 为有理数集，*为S上的二元运算，错误～未找到引用源。, 错误～未找到引用源。S有 18 < a，b="">* (1)*运算在S上是否可交换，可结合,是否为幂等的, ,不可交换: 可结合:(* (* (2)*运算是否有单位元，零元, 如果有请指出，并求S中所有可逆元素的逆元。 设是单位元，错误～未找到引用源。 则= 设是零元，错误～未找到引用源。 则= 错误～未找到引用源。 = a=1/x,b=-y/x 1y,1,,,,xy,,,所以当x0时， xx 10(令S={a，b}，S上有四个运算:*，错误～未找到引用源。分别有表10.8 确定。 (a) (b) (c) (d) (1)这4个运算中哪些运算满足交换律，结合律，幂等律, 19 (a) 交换律，结合律，幂等律都满足， 零元为a,没有单位元; (b)满足交换律和结合律，不满足幂等律，单位元为a,没有零元 ,1,1a,a,b,b (c)满足交换律,不满足幂等律,不满足结合律 a,(b,b),a,a,b,(a,b),b,a,b,a a,(b,b),(a,b),b 没有单位元, 没有零元 (d) 不满足交换律，满足结合律和幂等律 没有单位元, 没有零元 (2)求每个运算的单位元，零元以及每一个可逆元素的逆元。 见上 16(设V=〈 N，+ ，错误～未找到引用源。〉，其中+ ，错误～未找到引用源。分别 代表普通加法与乘法，对下面给定的每个集合确定它是否构成V的子代数，为什么, (1)S=错误～未找到引用源。 是 1 (2)S=错误～未找到引用源。 不是 加法不封闭 2 (3)S = {-1，0，1} 不是，加法不封闭 3 第十一章部分课后习题参考答案 8.设S={0，1，2，3}，为模4乘法，即 "x,y?S, xy=(xy)mod 4 , 问〈S，〉是否构成群,为什么, x,y?S, xy=(xy)mod 4,是S上的代数运算。 解:(1) ,,S (2) x,y,z?S,设xy=4k+r ,0,r,3 (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) x?S, (x1)=(1x)=x,，所以1是单位元。 , 20 ,1,11,1,3,3,(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上的代数运算。 ,,Z x,y,z?Z, (2), (xoy) oz =(x+y-2)oz=(x+y-2)+z-2=x+y+z-4 同理(xoy)oz= xo(yoz)，结合律成立。 eeeee(3)设是单位元，x?Z, xo= ox=x,即x+-2= +x-2=x, e=2 , e(4) x?Z , 设x的逆元是y, xoy= yox=, 即x+y-2=y+x-2=2, , ,1x,y,4,x 所以， 所以〈Z，o〉构成群 ,,1010,10,10,,,,,,,,,,,,,,,,,,,设G=11.，证明G关于矩阵乘法构成一个群( ,,,,,,,,,,010,1010,1,,,,,,,,,,解:(1) x,y?G, 易知xy?G,乘法是Z上的代数运算。 , (2) 矩阵乘法满足结合律 10,,(3)设,,是单位元， ,,01,, (4)每个矩阵的逆元都是自己。 所以G关于矩阵乘法构成一个群( 14.设G为群，且存在a?G,使得 k G={a?k?Z} 证明:G是交换群。 klx,a,y,a证明:x,y?G，设，则 , klk，ll，klkxy,aa,a,,a,aa,yx 21 所以，G是交换群 17.设G为群，证明e为G中唯一的幂等元。 22e,Ge,ee,eee,e证明:设也是幂等元，则，即，由消去律知 000000 18.设G为群，a,b,c?G,证明 ?abc?=?bca?=?cab? kk(abc),e,(bca),e证明:先证设 k(abc),e,设则， (abc)(abc)(abc)？(abc),e ,1a(bca)(bca)(bca)？(bca)a,e即 ,1a左边同乘，右边同乘得 a k,1(bca)(bca)(bca)？(bca),(bac),aea,e kk(bac),e,(abc),e. 反过来，设则 由元素阶的定义知，?abc?=?bca?，同理?bca?=?cab? 19.证明:偶数阶群G必含2阶元。 aaa,e证明:设群G不含2阶元，，当时，是一阶元，当时，至少是3,a,Ga,e ,1aa阶元,因为群G时有限阶的，所以是有限阶的，设是k阶的,则也是k阶的，所以a e高于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群矛盾; 2,1a若G除了1阶元e外,其余元均为2阶元，则， a,ea,a ,1,1,1,1,1,1,a,b,G,a,a,b,b,(ab),ab,所以ab,ab,(ba),ba， 与G为Abel群矛盾; 222aa所以，G含至少含一个3阶元，设为，则，且aa,aa。 a, 2令b,a的证。 22 21.设G是M(R)上的加法群，n?2，判断下述子集是否构成子群。 n (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, e,N(a),, ,x,y,N(a),则ax,xa,ay,ya ,所以xy,N(a) a(xy),(ax)y,(xa)y,x(ay),x(ya),(xy)a ,1,1,1,1,1,1,1,1,1xaxx,xxax,xae,eaxx,N(a)由，得，即，所以 xa,axax,xa 所以N(a)构成G的子群 31.设是群G到G的同态，是G到G的同态，证明是G到G的同态。 ,,,,,1122231213证明:有已知是G到G的函数，是G到G的函数，则?是G到G的函数。 ,,,,1122231213 ,a,b,G,,(,,)(ab),,(,(ab)),,(,(a),(b)) 11221211 ,,(,((a)))(,(,(b))),(,,,)(a)(,,,)(b) 21211212 所以:?是G到G的同态。 ,,1213 33.证明循环群一定是阿贝尔群，说明阿贝尔群是否一定为循环群，并证明你的结论。 klx,a,y,a 证明:设G是循环群,令G=,,x,y,G,令,那么 klk，ll，klkxy,aa,a,a,aa,yx,G是阿贝尔群 G,{e,a,b,c} 克莱因四元群, ,eabc eeabc aaecb bbcea ccbae 是交换群,但不是循环群,因为e是一阶元，a,b,c是二阶元。 36.设是5元置换，且 ,,, 23 1234512345,,,,， ,,,,,,,,,,,,2145334512,,,, ,1,1,1,,,,,,,,,,,,,(1)计算; ,1,1,,,,,,,,(2)将表示成不交的轮换之积。 (3)将(2)中的置换表示成对换之积，并说明哪些为奇置换，哪些为偶置换。 123451234512345,,,,,,,1解:(1) ,,,,,,,,,,,,,,,,,,,,451234532143125,,,,,, 1234512345,,,,,1,1 ,,,,,,,,,,,,,,2153454132,,,, ,1,1,,(14253),,,,(143)(25)(2) ,,,(1425) (3) ,,,(14)(12)(15) 奇置换， ,1,,(14)(12)(15)(13) 偶置换 ,1,,,,(14)(13)(25) 奇置换 第十四章部分课后习题参考答案 5、设无向图G有10条边，3度与4度顶点各2个，其余顶点的度数均小于3，问G至少有多少个顶点,在最少顶点的情况下，写出度数列、,(G)、,(G)。 解:由握手定理图G的度数之和为: 2，10,20 3度与4度顶点各2个，这4个顶点的度数之和为14度。 其余顶点的度数共有6度。 其余顶点的度数均小于3，欲使G的顶点最少，其余顶点的度数应都取2, ,(G),4,,(G),2 所以，G至少有7个顶点, 出度数列为3,3,4,4,2,2,2,. ,(D),,(D)7、设有向图D的度数列为2，3，2，3，出度列为1，2，1，1，求D的入度列，并求， ，，,,,(D),,(D),(D),,(D),. 解:D的度数列为2，3，2，3，出度列为1，2，1，1，D的入度列为1,1,1,2. ，，,,,(D),2,,(D),1,(D),2,,(D),1,(D),3,,(D),2,, 8、设无向图中有6条边，3度与5度顶点各1个，其余顶点都是2度点，问该图有多少个顶点, 解:由握手定理图G的度数之和为: 2，6,12 24 x 设2度点个，则，，该图有4个顶点. x,23，1，5，1，2x,12 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条边的无向简单图G、G、G，证明它们至少有两个是同构的。 123 证明:4阶4条边的无向简单图的顶点的最大度数为3，度数之和为8，因而度数列为2，2，2，2;3，2，2，1;3，3，1，1。但3，3，1，1对应的图不是简单图。所以从同构的观点看，4阶4条边的无向简单图只有两个: 所以，G、G、G至少有两个是同构的。 123 ,G20、已知n阶无向简单图G有m条边，试求G的补图的边数。 m n(n,1),m,,m解: 2 21、无向图G如下图 (1)求G的全部点割集与边割集，指出其中的割点和桥; k(G),(G)(2) 求G的点连通度与边连通度。 ae1e2d ebe5 e4e3c 解:点割集: {a,b},(d) 边割集{e2,e3},{e3,e4},{e1,e2},{e1,e4}{e1,e3},{e2,e4},{e5} 25 ==1 k(G),(G) 23、求G的点连通度、边连通度与最小度数。 k(G),(G),(G) 解:、 、 k(G),2,(G),3,(G),428、设n阶无向简单图为3-正则图，且边数m与n满足2n-3=m问这样的无向图有几种 非同构的情况, 3n,2m,解: 得n=6,m=9. ,2n,3,m, m31、设图G和它的部图G的边数分别为和m，试确定G的阶数。 ,1，1，8(m，m)n(n，1)m，m,解: 得n, 2245、有向图D如图 vv (1)求到长度为1，2，3，4的通路数; 52 vv(2)求到长度为1，2，3，4的回路数; 55 (3)求D中长度为4的通路数; (4)求D中长度小于或等于4的回路数; (5)写出D的可达矩阵。 v4v1 v5 v2v3解:有向图D的邻接矩阵为: 26 000010101020200,,,,,,,,,,,,101000000202020,,,,,, 23,,,,,,， A,,AA,000010101020200,,,,,, 101000000202020,,,,,, ,,,,,,010102020000004,,,,,, 0121500004,,,,,,,,5252240400,,,, 4234,,,, ，，，,,AAAAA2121500004,,,, 4040042522,,,, ,,,,0404025254,,,, vv(1)到长度为1，2，3，4的通路数为0,2,0,0; 52 vv(2)到长度为1，2，3，4的回路数为0,0,4,0; 55 (3)D中长度为4的通路数为32; (4)D中长度小于或等于4的回路数10; 11111,,,,11111,, ,,(4)出D的可达矩阵 P,11111,, 11111,, ,,11111,, 第十六章部分课后习题参考答案 1、画出所有5阶和7阶非同构的无向树. 2、一棵无向树T有5片树叶，3个2度分支点，其余的分支点都是3度顶点，问T有几个顶点? 27 x解:设3度分支点个，则 ，解得 5，1，3，2，3x,2，(5，3，x,1)x,3 T有11个顶点 3、无向树T有8个树叶，2个3度分支点，其余的分支点都是4度顶点，问T有几个4度分支 点,根据T的度数列，请至少画出4棵非同构的无向树。 x解:设4度分支点个，则 ，解得 8，1，2，3，4x,2，(8，2，x,1)x,2 度数列111111113344 n4、棵无向树T有 (i=2，3，?，k错误～未找到引用源。)个i度分支点，其余顶点都是树i 叶，问T应该有几片树叶? x解:设树叶片，则 n，i，x，1,2，(n，x,1)x,(i,2)n，2 ，解得 iii 评论:2，3，4题都是用了两个结论,一是握手定理，二是 m,n,1 至少为几,最多为几, 5、n(n?3)阶无向树T的最大度错误～未找到引用源。 解:2，n-1 6、若n(n?3)阶无向树T的最大度错误～未找到引用源。 =2，问T中最长的路径长度为 几, 解:n-1 7、证明:n(n?2) 阶无向树不是欧拉图. 证明:无向树没有回路，因而不是欧拉图。 8、证明:n(n?2) 阶无向树不是哈密顿图. 证明:无向树没有回路，因而不是哈密顿图。 9、证明:任何无向树T都是二部图. 证明:无向树没有回路，因而不存在技术长度的圈，是二部图。 10、什么样的无向树T既是欧拉图，又是哈密顿图? 解:一阶无向树 14、设e为无向连通图G中的一条边， e在G的任何生成树中，问e应有什么性质? 28 解: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-1)时，结论成立，当k=t时, 无向图 G是t棵树组成的森林,任取两棵树，每棵树,1 k-1). 任取一个顶点，这两个顶点连线。则所得新图有t-1棵树，所以m = n-( 所以原图中m = n-k 得证。 24、在图16.6所示2图中，实边所示的生成子图T是该图的生成树. (1)指出T的弦，及每条弦对应的基本回路和对应T的基本回路系统. (2) 指出T的所有树枝， 及每条树枝对应的基本割集和对应T的基本割集系统. (a) (b) 图16.16 解:(a)T的弦:c,d,g,h 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 29 解: 注:答案不唯一。 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算法求传输它们的前缀码.要求画出最优树，指出每个字母对应的编码.并指出传输n10(n?2)个按上述频率出现的字母，需要多少个二进制数字. 解: 30 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 nn-2传输10(n?2)个按上述频率出现的字母，需要255*10个二进制数字 31 P38 5 2 ()()，,,,pqqr ,,,,()pqqr,，,,,()ppqr,,qr ,,mm ,，,,,,,()()pqrpqr 37 011111 6 2()()pqpr,,，, ,M,,，,,，,,()()pprpqr,，,,()pqr 4 100 7 1()pqr,, ,,,，,,，,,，,,pqrrppqqr()(()()) ,,,，,,,,，,，,,，,,,,，,,,,()()()()()()pqrpqrpqrpqrpqrpqr ,，,，,,，,,,,，,,,,，,,,()()()()()pqrpqrpqrpqrpqr ,,,,,mmmmm 13567 mmm024 MMM,,,MMM 024024 9 ()()pqpr,,，,1 pq，ppq,，,prr ()()pqpr,,，,0 0 0 1 0 0 0 0 0 1 1 0 1 1 0 1 0 1 1 0 1 0 1 1 1 1 1 1 1 0 0 0 1 0 1 1 0 1 0 1 0 1 1 1 0 0 1 0 1 1 1 1 0 1 0 1 77 ,,,,,,,mmmmmmm 1234567 P52-54 11 ，,，,,pqqrrsp,,, s p ，,pq q ，,qr r rs, s 15P 2()(),()pqrsstu,,,,, pu, p pq, ()()pqrs,,, rs, s st, ()stu,, u 16P rs,， pq,，，,rq1 ，p p pq,， ，q ，,rq ，r rs,， r rr,， rr,，,0 17P A11AA A11 A pAqA11rAs A ，s()pqr,，, pqs, r qs, ，s ，q p pq,， ()pqr,，, r P80-81 15N , 3,,xFxGx(()())，，xGx() ，xFx() ，，xGx() ,，xGx() ，Gc() UI ,,xFxGx(()()) FcGc()(), UI Fc() EG ，xFx() N22 , 2 F(x)xG(x)c ,,xFxGx(()())，Gc() ，Fc() ,,xFxGx(()()) FcGc()(), UI ，Gc() ，Fc() N25 , F(x)xG(x)xH(x)xI(x) xc ,,xFxGx(()()),,,xGxHxIx(()()())FcHc()(), Ic() FcHc()(), Fc() Hc() ,,xFxGx(()()) UI FcGc()(), Gc() GcHc()(), ,,,xGxHxIx(()()()) GcHcIc()()(),, UI Ic() P132-135 22A R,1,3,1,4,2,3,2,4,3,4A,1,2,3,4,,,,1R 2R 1 2 1 ? ? ? ? 3 4 2RR RR Rxyyz xzR 26 RAR7.13 A,1,2,3,4,5,6,, 23RR,1 2r(R), s(R), t(R) 1R R,1,5,2,5,3,1,3,3,4,5,, 232 RRR,:,3,1,3,3,3,5RRR,:,3,1,3,3,3,5,,,, n R,3,1,3,3,3,5,n>=2当,, 2 r(R)=RI1,5,2,5,3,1,3,3,4,5,1,1,2,2,4,4,5,5,6,6,,,A ,1 sRR()R1,5,5,1,2,5,5,2,3,1,1,3,3,3,4,5,5,4,,,, 232 tRRR()RR...R1,5,2,5,3,1,3,3,4,5,3,5,,,,, 46AAR,, 1 Radacabaebecede,,,,,,,,,,,,,,I,,,A e b c d a Aea Aea T AR,B,S和AB，48 ,,，abab,,,AB,1122 abTabaRabSb,,,,11221212 T AB， 1 任取，则：ab,AB,，11 RR为偏序关系，具有自反性，？aa11 11SbSb为偏序关系，具有自反性，？ 1111？,aaRbSb 11221212又，abTabaRabSb,,,, 1111？abTab,,T，故满足自反性 2 任取，若且，则有：abababTababTab,,,AB,,,,,，112211222211 aRabSb,（1）1212 aRabSb,（2）2121 ？,,aRaaRaaa，又为偏序关系，具有反对称性，所以R122112 ？,,bSbbSb，又为偏序关系，具有反对称性，所以Sbb122112 ？,abab,,T，故满足反对称性1122 3 任取，，若且，则有：ababababTababTab,,,,AB,,,,,，11223311222233 abTabaRabSb,,,,11221212 abTabaRabSb,,,,22332323 122313？,aRaaRaaRa,R又为偏序关系，具有传递性，所以 122313？,bSbbSb,SbSb又为偏序关系，具有传递性，所以 13131133？,,aRaabTabbSb,,T，故满足传递性。 123TTAB， P179-180 8 S=QQ,QSa,b,x,y，,,,为有理数集，为上的二元运算，有S a,bx,yax,ay+b,, 1,运算在上是否可交换、可结合？是否为幂等的？S 2,运算是否有单位元、零元？如果有，请指出，并求出中所有可逆元素的逆元S 1 xy,a,bxa,xb+y,, ,,,ax,bx+ya,b,xy ？,运算不具有交换律 xy,a,bc,d,,，， ,,ax,bx+yc,d ,acx,adx+bx+y ，，而xy,a,bc,d,, ,xy,*ac,ad+b ,,xac,xad+xb+yacx,adx+bx+y ，，,,,xy,a,bc,d ？,运算有结合律 任取，则有：a,bs, 2a,ba,ba,a,b,,，,adb ？,运算无幂等律 2 令对均成立a,b*,a,ba,bsxy,,, 则有：对均成立ax,ay+ba,ba,bs,,, ,axa,,,,ax10,，，？,,对成立a,b,,，，aybb，,ay0,,,, x10x1,,,,,？,必定有,,y0y0,,,, ？,,运算的右单位元为，，可验证，也为运算的左单位元，1010？,运算的单位元为，10 令，若存在使得对上述等式均成立，a,b*,,,a,bsxyxyxy,,, 则存在零元，否则不存在零元。 由a,b*,,xyxy, ,,ax,ay+b,xy ,a1x0,,,axx,，，,,,,,a1y+b0,,ayby，,，，,,,, ，，由于不可能对均成立，a1y+b0a,bs,,,, 故不可能对均成立，故不存在零元；a,b*,,a,bsxyxy,,, 设元素的逆元为，则令，a,b,a,b*,e10xyxy,, 1,x,,ax1,,,a,,,（当a0）,,ayb0b，,,,y,, ,a, ？,当时，的逆元不存在；a0a,b 1b当aa,b,,,0时，的逆元是aa 11 设，，S12SS?,,...,10，问下面的运算能否与构成代数系统，,, 如果能构成代数系统则说明运算是否满足交换律、结合律，并求运算的单位元和零元。,, 3xyxy,=大于等于和的最小整数 3*xy=max(x,y), x,yS,xySSS,,,,,有，故运算在上满足封闭性，所以运算与非空集合能构成代数系统； 任取有所以运算满足交换律；x,yS,xy=max(x,y)=max(y,x)=y,,,,,x 任取有x,y,zS,xy)z=max(max(x,y),z)=max(x,y,z)=max(x,max(y,z))=x(yz),,,,,,,(所以运算满足结合律；任取，有所以运算的单位元是xSx1=max(x,1)=x=max(1,x)=1x,,,,,1； 任取，有所以运算的零元是xSx10=max(x,10)=10=max(10,x)=10x,,,,,10； 16 设其中表示取和之中较大的数。，V1,2,3,,1,xyV5,6,,6,::,,xy,,,,12 其中表示取和之中较小的数。求出和的所有的子代数。xy,xyVV 12 指出哪些是平凡的子代数，哪些是真子代数。 解：（1）的所有的子代数是：；V1,2,3,,1,1,,1,1,2,,1,1,3,,1::::,,,,,,,,1 V1,2,3,,1,1,,1的平凡的子代数是：；::,,,,1 V1,,1,1,2,,1,1,3,,1的真子代数是：；:::1,,,,,, （2）的所有的子代数是：，；V5,6,,66,,6,,,,,,2 V5,6,,66,,6的平凡的子代数是：，；,,,,,, 2 V6,,6的真子代数是：。,2,, P218-219 111.116 acf b{d,e} d{b,c} e{a,b} 2 1L={12345} 2L={123612} 12 4L 2abcabac,,,,,,()()() abcabac,,,,,,()()()P20811.2 911.11 aa,dadbc ca,fafcdbebecd fa,fafbecd 1011.11 abc ca,fcdbebecd cbdcac,,,,,(), ,,()()cbcdfdd,,,,,,？,,,,,,cbdcbcd()()() ff2L1={a,c,d,e,f}, L2={a,b,c,d,f}L1L2L1L2 P21311.5f cd 离散数学习题答案 习题二及答案：（P38） 5、求下列公式的主析取范式，并求成真赋值： （2）(?p →q ) ∧(q ∧r ) 解：原式?(p ∨q ) ∧q ∧r ?q ∧r ?(?p ∨p ) ∧q ∧r ?(?p ∧q ∧r ) ∨(p ∧q ∧r ) ?m 3∨m 7，此即公式的主析取范式， 所以成真赋值为011，111。 6、求下列公式的主合取范式，并求成假赋值： （2）(p ∧q ) ∨(?p ∨r ) 解：原式?(p ∨?p ∨r ) ∧(?p ∨q ∨r ) 所以成假赋值为100。 7、求下列公式的主析取范式，再用主析取范式求主合取范式： （1）(p ∧q ) ∨r 解：原式? ?(?p ∨q ∨r ) ?M 4，此即公式的主合取范式， p ∧q ∧(?r ∨r ) ∨((?p ∨p ) ∧(?q ∨q ) ∧r ) ?(p ∧q ∧?r ) ∨(p ∧q ∧r ) ∨(?p ∧?q ∧r ) ∨(?p ∧q ∧r ) ∨(p ∧?q ∧r ) ∨(p ∧q ∧r ) ?(?p ∧?q ∧r ) ∨(?p ∧q ∧r ) ∨(p ∧?q ∧r ) ∨(p ∧q ∧?r ) ∨(p ∧q ∧r ) ?m 1∨m 3∨m 5∨m 6∨m 7，此即主析取范式。 主析取范式中没出现的极小项为m 0，m 2，m 4，所以主合取范式中含有三个极大项M 0，M 2，M 4，故原式的主合取范式?M 0 9、用真值表法求下面公式的主析取范式： （1）(p ∨q ) ∨(?p ∧r ) 解：公式的真值表如下： ∧M 2∧M 4。 由真值表可以看出成真赋值的情况有7种，此7种成真赋值所对应的极小项的析取即为主析取范式，故主析取范式 ?m 1∨m 2∨m 3∨m 4∨m 5∨m 6∨m 7 习题三及答案：（P52-54） 11、填充下面推理证明中没有写出的推理规则。 前提：?p ∨q , ?q ∨r , r 结论：s 证明： ① p 前提引入 ② ④ →s , p ?p ∨q 前提引入 ?q ∨r 前提引入 ③ q ①②析取三段论 ⑤ r ③④析取三段论 ⑥ 15、在自然推理系统P 中用附加前提法证明下面推理： （2）前提：(p ∨q ) →(r ∧s ),(s ∨t ) →u 结论： r →s 前提引入 ⑦ s ⑤⑥假言推理 p →u 证明：用附加前提证明法。 ① p 附加前提引入 ② ③ ④ ⑥ ⑦ p ∨q ①附加 (p ∨q ) →(r ∧s ) 前提引入 r ∧s ②③假言推理 ⑤ s ④化简 s ∨t ⑤附加 (s ∨t ) →u 前提引入 ⑧ u ⑥⑦假言推理 故推理正确。 16、在自然推理系统P 中用归谬法证明下面推理： p →?q ，?r ∨q ，r ∧?s 结论：?p （1）前提： 证明：用归谬法 ① p 结论的否定引入 ② ③ ④ ⑤ ⑥ p →?q 前提引入 ?q ①②假言推理 ?r ∨q 前提引入 ?r ③④析取三段论 r ∧?s 前提引入 ⑦ r ⑥化简 ⑧r ∧?r ⑤⑦合取 由于r ∧?r ?0，所以推理正确。 17、在自然推理系统P 中构造下面推理的证明： 只要A 曾到过受害者房间并且11点以前没离开，A 就是谋杀嫌犯。A 曾到过受害者房间。如果A 在11点以前离开，看门人会看见他。看门人没有看见他。所以，A 是谋杀嫌犯。 解：设p ：A 到过受害者房间，q ：A 在11点以前离开，r ：A 是谋杀嫌犯，s ：看门人看见过A 。 则前提：(p ∧?q ) →r ， 结论：r 证明： ① ② ③ ④ ⑤ ⑥ ⑦ 习题五及答案：（P80-81） 15、在自然推理系统N ξ中，构造下面推理的证明： （3）前提：?x (F (x ) ∨G (x )) ，??xG (x ) 结论：?xF (x ) 证明： ① ② ③ ④ p ，q →s ，?s q →s 前提引入 ?s 前提引入 ?q ①②拒取式 p 前提引入 p ∧?q ③④合取引入 (p ∧?q ) →r 前提引入 r ⑤⑥假言推理 ??xG (x ) 前提引入 ?x ?G (x ) ①置换 ?G (c ) ②UI 规则 ?x (F (x ) ∨G (x )) 前提引入 ⑤ ⑥ ⑦ F (c ) ∨G (c ) ④UI 规则 F (c ) ③⑤析取三段论 ?xF (x ) ⑥EG 规则 22、在自然推理系统N ξ中，构造下面推理的证明： （2）凡大学生都是勤奋的。王晓山不勤奋。所以王晓山不是大学生。 解：设F(x)：x 为大学生，G(x)：想是勤奋的，c ：王晓山 则前提：?x (F (x ) →G (x )) ，?G (c ) 结论：?F (c ) 证明： ① ② ③ ④ ?x (F (x ) →G (x )) 前提引入 F (c ) →G (c ) ①UI 规则 ?G (c ) 前提引入 ?F (c ) ②③拒取式 25、在自然推理系统N ξ中，构造下面推理的证明： 每个科学工作者都是刻苦钻研的，每个刻苦钻研而又聪明的人在他的事业中都将获得成功。王大海是科学工作者，并且是聪明的。所以，王大海在他的事业中将获得成功。（个体域为人类集合） 解：设F(x)：x 是科学工作者，G(x)：x 是刻苦钻研的，H(x)：x 是聪明的，I(x)：x 在他的事业中获得成功，c ：王大海 则前提：?x (F (x ) →G (x )) ，?x (G (x ) ∧H (x ) →I (x )) ，F (c ) ∧H (c ) 结论：I (c ) 证明： ① ② ③ ④ ⑤ ⑥ F (c ) ∧H (c ) 前提引入 F (c ) ①化简 H (c ) ①化简 ?x (F (x ) →G (x )) 前提引入 F (c ) →G (c ) ④UI 规则 G (c ) ②⑤假言推理 ⑦ ⑧ ⑨ ⑩ G (c ) ∧H (c ) ③⑥合取引入 ?x (G (x ) ∧H (x ) →I (x )) 前提引入 G (c ) ∧H (c ) →I (c ) ⑧UI 规则 I (c ) ⑦⑨假言推理 习题七及答案：（P132-135） 22、给定 A ={1,2,3,4}，A 上的关系R ={, 4, 2,3, 2, 4, 3, 4}，试 （1）画出R 的关系图； （2）说明R 的性质。 解：（1） （2）R R 是反自反的，不是自反的； R 的关系图中任意两个顶点如果有边的都是单向边，故R 是反对称的，不是对称的； R 的关系图中没有发生顶点x 到顶点y 有边、顶点y 到顶点z 有边，但顶点x 到顶点z 没有边的情况，故R 是 传递的。 26 设 A ={1,2,3,4,5,6}，R 为A 上的关系，R 的关系图如图7.13所示： 2 （1）求R , R 3的集合表达式； ={, 2,5, , , 4,5 （2）求r(R), s(R), t(R)的集合表达式。 解：（1）由R 的关系图可得R 所以R 可得R 2 ， =R ?R ={, 3,3, 3,5，R 3 =R 2?R ={, 3,3, 3,5 n ={, 3,3, 3,5, 当n>=2； ={, 2,5, 3,1, 3,3, 4,5, , 2, 2, 4, 4, , 6,6 （2）r(R)=R I A ， s (R ) =R R -1={, 5,1, 2,5, 5, 2, 3,1, , 3,3, 4,5, 5, 4 t (R ) =R R 2 R 3 ... =R R 2={, 2,5, , , 4,5, 46、分别画出下列各偏序集（1）R ≤ A , R ≤ 的哈斯图，并找出A 的极大元、极小元、最大元和最小元。 ={a , d , a , c , a , b , a , e , b , e , c , e , d , e } I A 解：哈斯图如下： A 的极大元为e 、极小元为a ； A 的最大元为e 、最小元为a 。 48、设 A , R 和为偏序集，在集合A ?B 上定义关系T 如下： ?a 1, b 1, a 2, b 2∈A ?B, a 1, b 1T a 2, b 2?a 1Ra 2∧b 1Sb 2 证明T 为A ?B 上的偏序关系。 证明：（1）自反性： 任取a 1, b 1∈A ?B ，则： R 为偏序关系，具有自反性，∴a 1R a 1 S 为偏序关系，具有自反性，∴b 1Sb 1∴a 1R a 1∧b 1Sb 1 又a 1, b 1T a 2, b 2?a 1Ra 2∧b 1Sb 2，∴a 1, b 1T a 1, b 1，故T 满足自反性 （2）反对称性： 任取a 1, b 1, a 2, b 2∈A ?B ，若a 1, b 1T a 2, b 2且a 2, b 2T a 1, b 1，则有：a 1Ra 2∧b 1Sb 2a 2Ra 1∧b 2Sb 1 （1）（2） ∴a 1Ra 2∧a 2Ra 1，又R 为偏序关系，具有反对称性，所以a 1=a 2∴b 1Sb 2∧b 2Sb 1，又S 为偏序关系，具有反对称性，所以b 1=b 2∴a 1, b 1=a 2, b 2，故T 满足反对称性 （3）传递性： 任取a 1, b 1, a 2, b 2a 3, b 3∈A ?B ，若a 1, b 1T a 2, b 2且a 2, b 2T a 3, b 3，则有：a 1, b 1T a 2, b 2?a 1Ra 2∧b 1Sb 2a 2, b 2T a 3, b 3?a 2Ra 3∧b 2Sb 3 ∴a 1Ra 2∧a 2Ra 3, 又R 为偏序关系，具有传递性，所以a 1Ra 3∴b 1Sb 2∧b 2Sb 3, 又S 为偏序关系，具有传递性，所以b 1Sb 3∴a 1Ra 3∧b 1Sb 3?a 1, b 1T a 3, b 3，故T 满足传递性。 综合（1）（2）（3）知T 满足自反性、反对称性和传递性，故T 为A ?B 上的偏序关系。 习题九及答案：（P179-180） 8、 S=Q?Q,Q 为有理数集，为*S 上的二元运算，?a,b , x,y ∈S 有 a,b *x,y =ax,ay+b （1）*运算在S 上是否可交换、可结合？是否为幂等的？ （2）*运算是否有单位元、零元？如果有，请指出，并求出S 中所有可逆元素的逆元。 解：（1） x , y *a,b =xa,xb+y=ax,bx+y≠a,b *x , y ∴*运算不具有交换律 (x , y *a,b )*c,d =ax,bx+y*c,d =acx,adx+bx+y而x , y *(a,b *c,d =x , y *ac,ad+b =xac,xad+xb+y=acx,adx+bx+y=(x , y *a,b )*c,d ∴*运算有结合律 ) 任取a,b ∈s ，则有：a,b *a,b =a 2, ad +b ≠a,b ∴*运算无幂等律 （2） 令a,b *x , y =a,b 对?a,b ∈s 均成立ax,ay+b=a,b 对?a,b ∈s 均成立??a (x -1)=0?ax =a ∴???对?(a,b )成立ay +b =b ay =0??? ?x -1=0?x =1 ∴必定有??? ?y =0?y =0∴*运算的单位元为0 ∴*运算的右单位元为0，可验证0也为*运算的左单位元， 令a,b *x , y =x , y ，若存在x , y 使得对?a,b ∈s 上述等式均成立，则存在零元，否则不存在零元。由a,b *x , y =x , y ?ax,ay+b=x , y ???ax =x ?(a -1)x =0??? ay +b =y ?(a -1)y+b=0??? 由于(a -1)y+b=0不可能对?a,b ∈s 均成立， 故a,b *x , y =x , y 不可能对?a,b ∈s 均成立，故不存在零元； 设元素a,b 的逆元为x , y ，则令a,b *x , y =e =01? x =??ax =1?a ????（当a ≠0） ay +b =0b ??y =- ?a ? ∴当a =0a,b 的逆元不存在； 当a ≠0a,b 的逆元是 11 1b , -a a 、 设S ={1，2，...,10}，问下面的运算能否与S 构成代数系统S *? 如果能构成代数系统则说明*运算是否满足交换律、结合律，并求*运算的单位元和零元。 （3）x *y =大于等于x 和y 的最小整数； 解：（3）由*运算的定义可知：x *y=max(x,y)， x,y ∈S, 有x *y ∈S ，故*运算在S 上满足封闭性，所以*运算与非空集合S 能构成代数系统； 任取x,y ∈S, 有x *y=max(x,y)=max(y,x)=y*x , 所以*运算满足交换律； 任取x,y,z ∈S, 有(x *y) *z=max(max(x,y),z)=max(x,y,z)=max(x,max(y,z))=x*(y*z), 所以*运算满足结合律； 任取x ∈S ，有x *1=max(x,1)=x=max(1,x)=1*x, 所以*运算的单位元是1； 任取x ∈S ，有x *10=max(x,10)=10=max(10,x)=10*x, 所以*运算的零元是10；16、 设V 1=1, 2,3}, ?,1, 其中x ?y 表示取x 和y 之中较大的数。V 2=5,6}, *,6，其中x *y 表示取x 和y 之中较小的数。求出V 1和V 2的所有的子代数。指出哪些是平凡的子代数，哪些是真子代数。 解：（1）V 11, 2,3}, ?,1, 1}, ?,1, 1, 2}, ?,1, {1,3}, ?,1； V 1{1, 2,3}, ?,1, 1}, ?,1；V 1{1}, ?,1, {1, 2}, ?,1, 1,3}, ?,1； （2）V 25,6}, *,6{6}, *,6； V 2 5,6}, *,66}, *,6；V 26}, *,6。 习题十一及答案：（P218-219） 1、图11.11给出了6个偏序集的哈斯图。判断其中哪些是格。如果不是格，说明理由 解：（a ）、（c ）、（f ）是格；因为任意两个元素构成的集合都有最小上界和最大下界； （b ）不是格，因为{d,e}的最大下界不存在； （d ）不是格，因为{b,c}的最小上界不存在； （e ）不是格，因为{a,b}的最大下界不存在。 2、下列各集合低于整除关系都构成偏序集，判断哪些偏序集是格。 （1）L={1，2，3，4，5}； （2）L={1，2，3，6，12}； 解：画出哈斯图即可判断出：（1）不是格，（2）是格。 4、设L 是格，求以下公式的对偶式： （2）a ∨(b ∧c ) ≤(a ∨b ) ∧(a ∨c ) 解：对偶式为：a ∧(b ∨c ) ≥(a ∧b ) ∨(a ∧c ) ，参见P208页定义11.2。 9、针对图11.11中的每个格，如果格中的元素存在补元，则求出这些补元。 解： （a ）图：a,d 互为补元，其中a 为全下界，d 为全上界，b 和c 都没有补元； （c ）图：a,f 互为补元，其中a 为全下界，f 为全上界，c 和d 的补元都是b 和e ，b 和e 的补元都是c 和d ； （f ）图：a,f 互为补元，其中a 为全下界，f 为全上界，b 和e 互为补元，c 和d 都没有补元。 10、说明图11.11中每个格是否为分配格、有补格和布尔格，并说明理由。 解： （a ）图：是一条链，所以是分配格，b 和c 都没有补元，所以不是有补格，所以不是布尔格； （c ）图：a,f 互为补元，c 和d 的补元都是b 和e ，b 和e 的补元都是c 和d ，所以任何元素皆有补元，是有补格； c ∨(b ∧d ) =c ∨a =c , (c ∨b ) ∧(c ∨d ) =f ∧d =d ∴c ∨(b ∧d ) ≠(c ∨b ) ∧(c ∨d ) ，所以∨对∧运算 不满足分配律，所以不是分配格，所以不是布尔格； （f ）图：经过分析知图（f ）对应的格只有2个五元子格：L1={a,c,d,e,f}, L2={a,b,c,d,f}。画出L1和L2的哈斯图可知L1和L2均不同构于钻石格和五角格，根据分配格的充分必要条件（见P213页的定理11.5）得图（f ）对应的格是分配格；c 和d 都没有补元，所以不是有补格，所以不是布尔格。 1 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∧ 1?0. (3) (?p ∧ ?q ∧ r ) ? (p∧ q ∧﹁ r) ?(1∧ 1∧ 1) ? (0∧ 0∧ 0) ?0 (4)(?r ∧ s )→ (p∧ ?q) ?(0∧ 1)→ (1∧ 0) ?0→ 0?1 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 所以公式类型为永真式 //最后一列全为 1 (5)公式类型为可满足式(方法如上例) //最后一列至少有一个 1 (6)公式类型为永真式(方法如上例) 2 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 ∨ r ?1所以公式类型为永真式 (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) → (?q ∨p) ??(p∨q) ∨(?q ∨p) ?(?p ∧?q) ∨(?q ∨p) ? (?p ∧?q) ∨(?q ∧p) ∨(?q ∧?p) ∨(p∧q) ∨(p∧?q) ? (?p ∧?q) ∨(p∧?q) ∨(p∧q) ?320m m m ∨∨ ?∑ (0,2,3) 主合取范式: (?p → q) → (?q ∨p) ??(p∨q) ∨(?q ∨p) ?(?p ∧?q) ∨(?q ∨p) ?(?p ∨(?q ∨p)) ∧(?q ∨(?q ∨p)) ?1∧(p∨?q) ?(p∨?q) ? M1 ?∏ (1) (2) 主合取范式为: ?(p→ q) ∧q ∧r ??(?p ∨q) ∧q ∧r ?(p∧?q) ∧q ∧r ?0 所以该式为矛盾式 . 主合取范式为∏ (0,1,2,3,4,5,6,7) 矛盾式的主析取范式为 0 (3)主合取范式为: (p∨(q∧r)) → (p∨q ∨r) ??(p∨(q∧r)) → (p∨q ∨r) ?(?p ∧(?q ∨?r)) ∨(p∨q ∨r) ?(?p ∨(p∨q ∨r)) ∧((?q ∨?r)) ∨(p∨q ∨r)) ?1∧1 ?1 所以该式为永真式 . 永真式的主合取范式为 1 主析取范式为∑ (0,1,2,3,4,5,6,7) 第三章部分课后习题参考答案 14. 在自然推理系统 P 中构造下面推理的证明: (2)前提:p →q, ?(q∧r),r 结论:?p (4)前提:q →p,q ?s,s ?t,t ∧r 结论:p ∧q 证明:(2) ① ?(q∧r) 前提引入 ② ?q ∨?r ①置换 ③ q →?r ②蕴含等值式 ④ r 前提引入 ⑤ ?q ③④拒取式 ⑥ p →q 前提引入 ⑦￢ p ⑤⑥拒取式 证明(4) : ① t ∧r 前提引入 ② t ①化简律 ③ q ?s 前提引入 ④ s ?t 前提引入 ⑤ q ?t ③④等价三段论 ⑥(q →t ) ∧(t→q) ⑤ 置换 ⑦(q →t ) ⑥化简 ⑧ q ②⑥ 假言推理 ⑨ q →p 前提引入 ⑩ p ⑧⑨假言推理 (11)p∧q ⑧⑩合取 15在自然推理系统 P 中用附加前提法证明下面各推理: (1)前提:p →(q→r),s →p,q 结论:s →r 证明 ① s 附加前提引入 ② s →p 前提引入 ③ p ①②假言推理 ④ p →(q→r) 前提引入 ⑤ q →r ③④假言推理 ⑥ q 前提引入 ⑦ r ⑤⑥假言推理 16在自然推理系统 P 中用归谬法证明下面各推理: (1)前提:p →?q, ?r ∨q,r ∧?s 结论:?p 证明: ① 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)在两个个体域中都解释为 ) (x xF ?,在(a )中为假命题,在 (b)中为真命题。 (2)在两个个体域中都解释为 ) (x xG ?,在(a ) (b)中均为真命题。 4. 在一阶逻辑中将下列命题符号化 : (1) 没有不能表示成分数的有理数 . (2) 在北京卖菜的人不全是外地人 . 解 : (1)F(x): x能表示成分数 H(x): x是有理数 命题符号化为 : )) ( ) ( (x H x F x ∧ ? ?? (2)F(x): x是北京卖菜的人 H(x): x是外地人 命题符号化为 : )) ( ) ( (x H x F x → ?? 5. 在一阶逻辑将下列命题符号化 : (1) 火车都比轮船快 . (3) 不存在比所有火车都快的汽车 . 解 : (1)F(x): x是火车 ; G(x): x是轮船 ; H(x,y): x比 y 快 命题符号化为 : )) , ( )) ( ) ( ((y x H y G x F y x → ∧ ? ? (2) (1)F(x): x是火车 ; G(x): x是汽车 ; H(x,y): x比 y 快 命题符号化为 : ))) , ( ) ( ( ) ( (y x H x F x y G y → ? ∧ ?? 9. 给定解释 I 如下 : (a) 个体域 D 为实数集合 R. (b) D中特定元素 错误!未找到引用源。 =0. (c) 特定函数 错误!未找到引用源。 (x,y)=x错误!未找到引用源。 y,x,y D ∈错误! 未找到引用源。 . (d) 特 定 谓 词 错 误 ! 未 找 到 引 用 源 。 (x,y):x=y,错 误 ! 未 找 到 引 用 源 。 (x,y):x<> ∈. 说明下列公式在 I 下的含义 , 并指出各公式的真值 : (1))) , ( ) , ( (y x F y x G y x ? → ? ? (2))) , ( ) ), , ( ( (y x G a y x f F y x → ? ? 答 :(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)错误!未找到引用源。 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 ) ( ) (? ∨ ? ∨ ? ? → →p q p p q p 为永真式; 所以 错误!未找到引用源。 为永真式; (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. 给定解释I如下 : (a)个体域 D={3,4}; (b)) (x f 错误!未找到引用源。 为 3) 4(, 4) 3(==f f 错误!未找到引用源。 (c)1) 3, 4() 4, 3(, 0) 4, 4() 3, 3() , (====F F F F y x F 为 错误!未找到引用源。 . 试求下列公式在I下的真值 . (1)) , (y x yF x ?? (3)))) (), (() , ((y f x f F y x F y x →?? 解 :(1) )) 4, () 3, (() , (x F x F x y x yF x ∨???? ? )) 4, 4() 3, 4(()) 4, 3() 3, 3((F F F F ∨∧∨ ?1) 01() 10(?∨∧∨ (2) ))) (), (() , ((y f x f F y x F y x →?? )))) 4(), (() 4, (())) 3(), (() 3, (((f x f F x F f x f F x F x →∧→?? ))) 3), (() 4, (()) 4), (() 3, (((x f F x F x f F x F x →∧→?? ))) 3), 3(() 4, 3(()) 4), 3(() 3, 3(((f F F f F F →∧→? ))) 3), 4(() 4, 4(()) 4), 4(() 3, 4(((f F F f F F →∧→∧ ))) 3, 4() 4, 3(()) 4, 4(0((F F F →∧→?))) 3, 3(0()) 4, 3(1((F F →∧→∧ ) 11() 00(→∧→?) 00() 11(→∧→∧1? 12. 求下列各式的前束范式。 (1)) , () (y x yG x xF ?→? (5))) , () (() , (2121211x x G x x H x x F x ??→→? (本题课本上有错误 ) 解 :(1) ) , () (y x yG x xF ?→?) , () (y t yG x xF ?→??)) , () ((y t G x F y x →??? (5) )) , () (() , (2121211x x G x x H x x F x ??→→? )) , () (() , (2323211x x G x x H x x F x ??→→?? )) , () (() , (2332411x x G x H x x x F x ?→?→?? ))) , () (() , ((2334121x x G x H x x F x x ?→→??? 15. 在自然数推理系统 F 中 , 构造下面推理的证明 : (1) 前提 : )) ()) () ((() (y R y G y F y x xF →∨?→?, ) (x xF ? 结论 : ?xR(x) (2) 前提 : ?x(F(x)→ (G(a)∧ R(x))), 错误!未找到引用源。 xF(x) 结论 :错误!未找到引用源。 x(F(x)∧ R(x)) 证明 (1) ① ) (x xF ? 前提引入 ② F(c) ① EI ③ )) ()) () ((() (y R y G y F y x xF →∨?→? 前提引入 ④ )) ()) () (((y R y G y F 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)) 第六章部分课后习题参考答案 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) (A B ) B ) -(A B ) (2) ((A B C ) -(B C ) ) A 解 : (1)(A B ) B ) -(A B ) =(A B ) B ) ~(A B ) =(A B ) ~(A B ) ) B=? B=? (2) ((A B C ) -(B C ) ) A=((A B C ) ~(B C ) ) A =(A ~(B C ) ) ((B C ) ~(B C ) ) A =(A ~(B C ) ) ? A=(A ~(B C ) ) A=A 18.某班有 25个学生,其中 14人会打篮球, 12人会打排球, 6人会打篮球和排球, 5人会打篮球和网球, 还有 2人会打这三种球。 已知 6个会打网球的人都会打篮球或排球。 求不会打球的人数。 解 : 阿 A={会打篮球的人 }, B={会打排球的人 }, C={会打 网 球 的人 } |A|=14, |B|=12, |A B|=6,|A C|=5,| A B C|=2, |C|=6,C?A B 如图所示。 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=1 2 3 ?=? (4) A=? 27、设 A,B,C 是任意集合,证明 (1)(A-B)-C=A- B?C (2)(A-B)-C=(A-C)-(B-C) 证明 (1) (A-B)-C=(A ~B) ~C= A ( ~B ~C)= A ~(B?C) =A- B?C (2) (A-C)-(B-C)=(A ~C) ~(B ~C)= (A ~C) (~B C) =(A ~C ~B) (A ~C C)= (A ~C ~B) ? = A ~(B?C ) =A- B?C 由(1)得证。 第七章部分课后习题参考答案 7. 列出集合 A={2,3,4}上的恒等关系 I A, 全域关系 E A , 小于或等于关系 L A , 整除关系 D A . 解:I A ={<2, 2="">,<3,3>,<4,4>} E A ={<2,2>,<2,3>,<2,4>,<3,4>,<4,4>,<3,2>,<3,3>,<4,2>,<4,3>} L A ={<2,2>,<2,3>,<2,4>,<3,3>,<3,4>,<4,4>} D A ={<2,4>} 13. 设 A={<1,2>,<2,4>,<3,3>} B={<1,3>,<2,4>,<4,2>} 求 A ?B,A ?B, domA, domB, dom(A?B), ranA, ranB, ran(A?B ), fld(A-B). 解:A ?B={<1,2>,<2,4>,<3,3>,<1,3>,<4,2>} A?B={<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(A?B)={4} fld R=dom R?ran R 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>} 求 R R, R -1, R ↑{0,1,}, R[{1,2}] 解:R R={<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}, 1R , 2R 为 A 上的关系,其中 1R ={}, , , , , a a a b b d {2, , , , , , , R a d b c b d c b = 求 23 122112, , , R R R R R R 。 解 : R1 R 2={,,} R2 R 1={ R 12=R1 R 1={,,} R 22=R2 R 2={ 36.设 A={1, 2, 3, 4},在 A ?A 上定义二元关系 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 为 A ?A 上的二元关系 , ?〈 a , b 〉 , 〈 c , d 〉 ∈A ?A , 〈 a , b 〉 R 〈 c , d 〉 ?a + b = c + d (1)证明 R 为等价关系 . (2)求 R 导出的划分 . (1)证明:? a+b=a+b ∴ R ∴ R 是自反的 任意的 , 设 R ∴ c+d=a+b ∴ ∴ R 是对称的 任意的 , 若 R 则 a+b=c+d,c+d=x+y ∴ a+b=x+y ∴ R ∴ 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} 解 : 2 3 468 1 11 (1) (2) 45. 下图是两个偏序集 的哈斯图 . 分别写出集合 A 和偏序关系 R 的集合表达式 . d g a b f g (a) (b) 解 : (a)A={a,b,c,d,e,f,g} R ={,,,,,, (b) A={a,b,c,d,e,f,g} R ={,,,,, 46. 分别画出下列各偏序集 的哈斯图 , 并找出 A 的极大元 `极小元 `最大元和 最小元 . (1)A={a,b,c,d,e} R ={,,,, a b c d e (1) (2) 项目 (1) (2) 极大元 : e a,b,d,e 极小元 : a a,b,c,e 最大元 : e 无 最小元 : a 无 第八章部分课后习题参考答案 1.设 f :N→N, 且 f (x)=12x 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}. 4. 判断下列函数中哪些是满射的 ? 哪些是单射的 ? 哪些是双射的 ? (1) f:N→N, f(x)=x2+2 不是满射,不是单射 (2) f:N→N,f(x)=(x)mod 3, x 除以 3的余数 不是满射,不是单射 (3) f:N→N,f(x)=10x x ???,若 为奇数 ,若 为偶数 不是满射,不是单射 (4) f:N→{0,1},f(x)=01x x ???,若 为奇数 ,若 为偶数 是满射,不是单射 (5) f:N-{0}→R,f(x)=lgx 不是满射,是单射 (6) f:R→R,f(x)=x2-2x-15 不是满射,不是单射 5. 设 X={a,b,c,d},Y={1,2,3},f={, 第十章部分课后习题参考答案 4. 判断下列集合对所给的二元运算是否封闭: (1) 整数集合 Z 和普通的减法运算。 封闭 , 不满足交换律和结合律,无零元和单位元 (2) 非零整数集合 错误!未找到引用源。 普通的除法运算。 不封闭 (3) 全体 n n ?实矩阵集合 错误!未找到引用源。 (R )和矩阵加法及乘法运算,其中 n 错误!未找到引用源。 2。 封闭 均满足交换律,结合律,乘法对加法满足分配律; 加法 单位元是零矩阵,无零元; 乘法 单位元是单位矩阵,零元是零矩阵; (4) 全体 n n ?实可逆矩阵集合关于矩阵加法及乘法运算, 其中 n 错误! 未找到引用源。 2。 不封闭 (5)正实数集合 错误!未找到引用源。 和 错误!未找到引用源。 运算,其中 错误!未 找到引用源。 运算定义为: 错误!未找到引用源。 不封闭 因为 +?-=--?=R 1111111 (6) n 错误!未找到引用源。 关于普通的加法和乘法运算。 封闭,均满足交换律,结合律,乘法对加法满足分配律 加法 单位元是 0,无零元; 乘法 无单位元(1>n ) ,零元是 0; 1=n 单位元是 1 (7) A = {}, , , 21n a a a 错误!未找到引用源。 n 错误!未找到引用源。 运算定义如下: 错误!未找到引用源。 封闭 不满足交换律,满足结合律, (8) S = 错误!未找到引用源。 关于普通的加法和乘法运算。 封闭 均满足交换律,结合律,乘法对加法满足分配律 (9) S = {0,1},S是关于普通的加法和乘法运算。 加法不封闭,乘法封闭;乘法满足交换律,结合律 (10) S = 错误!未找到引用源。 ,S 关于普通的加法和乘法运算。 加法不封闭,乘法封闭,乘法满足交换律,结合律 5.对于上题中封闭的二元运算判断是否适合交换律,结合律,分配律。 见上题 7. 设 * 为 +Z 错误!未找到引用源。 上的二元运算 +∈?Z y x , , X * Y = min ( x, y ),即 x 和 y 之中较小的数 . (1)求 4 * 6, 7 * 3。 4, 3 (2)* 在 + Z 上是否适合交换律,结合律,和幂等律? 满足交换律,结合律,和幂等律 (3)求 *运算的单位元,零元及 +Z 中所有可逆元素的逆元。 单位元无,零元 1, 所有元素无逆元 8. Q Q S ?= Q 为有理数集, *为 S 上的二元运算, 错误! 未找到引用源。 , < a,="" b="">* (1) *运算在 S 上是否可交换,可结合?是否为幂等的? 不可交换: 可结合:(* *( (* 不是幂等的 (2) *运算是否有单位元,零元? 如果有请指出,并求 S 中所有可逆元素的逆元。 设 是单位元, 错误!未找到引用源。 则 = 设 是零元, 错误!未找到引用源。 则 = 错误!未找到引用源。 = a=1/x,b=-y/x 所以当 x ≠0时, x y x y x - = > <> 1 , 1 10.令 S={a, b}, S 上有四个运算:*, 错误!未找到引用源。 分别有表 10.8确定。 (a) (b) (c) (d) (1)这 4个运算中哪些运算满足交换律,结合律,幂等律? (a) 交换律,结合律,幂等律都满足, 零元为 a, 没有单位元; (b)满足交换律和结合律,不满足幂等律,单位元为 a, 没有零元 b b a a = =- -1 1, (c)满足交换律 , 不满足幂等律 , 不满足结合律 a b a b b a b a a b b a ==== ) (, ) ( b b a b b a ) () (≠ 没有单位元 , 没有零元 (d) 不满足交换律,满足结合律和幂等律 没有单位元 , 没有零元 (2)求每个运算的单位元,零元以及每一个可逆元素的逆元。 见上 16.设 V=〈 N, + , 错误!未找到引用源。 〉 ,其中 + , 错误!未找到引用源。 分别代 表普通加法与乘法,对下面给定的每个集合确定它是否构成 V 的子代数,为什么? (1) S 1=错误!未找到引用源。 是 (2) S 2=错误!未找到引用源。 不是 加法不封闭 (3) S 3 = {-1, 0, 1} 不是,加法不封闭 第十一章部分课后习题参考答案 8. 设 S={0, 1, 2, 3}, 为模 4乘法,即 y=(xy)mod 4 问〈 S , 〉是否构成群?为什么? 解:(1) ?x,y ∈ S, x y=(xy)mod 4S ∈, 是 S 上的代数运算。 (2) ?x,y,z ∈ S, 设 xy=4k+r 30≤≤r (x y) z =((xy)mod 4) z=r z=(rz)mod 4 =(4kz+rz)mod 4=((4k+r)z)mod 4 =(xyz)mod 4 同理 x (y z) =(xyz)mod 4 所以, (xy) z = x(y z) ,结合律成立。 (3) ?x ∈ S, (x 1)=(1 x)=x,,所以 1是单位元。 (4), 33, 1111==-- 0和 2没有逆元 所以, 〈 S , 〉不构成群 9. 设 Z 为整数集合,在 Z 上定义二元运算。如下: 解:(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 = e ox=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, 所以, x y x -==-41 所以〈 Z , o 〉构成群 11. 设 G=? ?? ??????? ??--???? ??-???? ??-???? ??1001, 1001, 1001, 1001,证明 G 关于矩阵乘法构成一个群. 解:(1) ?x,y ∈ G, 易知 xy ∈ G, 乘法是 Z 上的代数运算。 (2) 矩阵乘法满足结合律 (3)设 ???? ??1001是单位元, (4)每个矩阵的逆元都是自己。 所以 G 关于矩阵乘法构成一个群. 14. 设 G 为群,且存在 a∈G,使得 G={ak ∣k∈Z} 证明 :G 是交换群。 证明 :?x,y ∈ G ,设 l k a y a x ==, ,则 yx a a a a a a xy k l k l l k l k ======++ 所以, G 是交换群 17. 设 G 为群,证明 e 为 G 中唯一的幂等元。 证明 :设 G e ∈0也是幂等元,则 020e e =,即 e e e 02 0=,由消去律知 e e =0 18. 设 G 为群,a,b,c∈G,证明 ∣abc∣=∣bca∣=∣cab∣ 证明:先证设 e bca e abc k k =?=) () ( 设 , ) (e abc k =则 e abc abc abc abc =) () )()(( , 即 e a b c a b c a b c a b c a a =-1) () )()(( 左边同乘 1-a ,右边同乘 a 得 e ea a bac bca bca bca bca k ===-1) () () )()(( 反过来, 设 , ) (e bac k =则 . ) (e abc k = 由元素阶的定义知,∣abc∣=∣bca∣,同理∣bca∣=∣cab∣ 19. 证明:偶数阶群 G 必含 2阶元。 证明:设群 G 不含 2阶元, G a ∈?,当 e a =时, a 是一阶元,当 e a ≠时, a 至少是 3阶元 , 因为群 G 时有限阶的,所以 a 是有限阶的,设 a 是 k 阶的 , 则 1-a 也是 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阶元,则 e a =2, a a =-1 ba ba b a ab ab ab b b a a G b a ======∈?------111111) (, ) (, , , , 所以 , 与 G 为 Abel 群矛盾; 所以, G 含至少含一个 3阶元,设为 a ,则 ≠a 2a ,且 22aa a a =。 令 2a b =的证。 21. 设 G 是 M n (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,φ≠∈) (a N e ya ay xa ax a N y x ==∈?, ), (, 则 a xy ya x ay x y xa y ax xy a ) () () () () () (=====, 所以 ) (a N xy ∈ 由 xa ax =,得 111111, ------==eax ae x xax x axx x ,即 11--=ax a x ,所以 ) (1a N x ∈- 所以 N (a )构成 G 的子群 31. 设 ?1是群 G 1到 G 2的同态, ?2是 G 2到 G 3的同态,证明 ?1? 2是 G 1到 G 3的同态。 证明:有已知 ?1是 G 1到 G 2的函数, ?2是 G 2到 G 3的函数,则 ?1·?2是 G 1到 G 3的函数。 , , 1G b a ∈?)) () (()) (() )((1121221b a ab ab ???????== ) )()()(())) (()))((((21211212b a b a ???????? == 所以 :?1·?2是 G 1到 G 3的同态。 33. 证明循环群一定是阿贝尔群,说明阿贝尔群是否一定为循环群,并证明你的结论。 证明:设 G 是循环群 , 令 G=,G y x ∈?, , 令 l k a y a x ==, , 那么 yx a a a a a a xy k l k l l k l k =====++,G 是阿贝尔群 克莱因四元群 , }, , , {c b a e G = e a b c c a e c b b b c e a a c b a e e c b a e 是交换群 , 但不是循环群 , 因为 e 是一阶元, a,b,c 是二阶元。 36. 设 τσ, 是 5元置换,且 ???? ??=3541254321σ, ??? ? ??=2154354321τ (1)计算 τσσσττσστ111, , , , ---; (2)将 τσσττσ11, , --表示成不交的轮换之积。 (3)将(2)中的置换表示成对换之积,并说明哪些为奇置换,哪些为偶置换。 解:(1) ???? ??=1235454321τσ ???? ??=5213454321στ ??? ? ??=-32154543211τ ???? ??=-43512543211σ ??? ? ??=-23145543211 τσσ (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 至 少有多少个顶点?在最少顶点的情况下,写出度数列、 ) () (G G δ、 ?。 解:由握手定理图 G 的度数之和为:20102=? 3度与 4度顶点各 2个,这 4个顶点的度数之和为 14度。 其余顶点的度数共有 6度。 其余顶点的度数均小于 3,欲使 G 的顶点最少,其余顶点的度数应都取 2, 所以, G 至少有 7个顶点 , 出度数列为 3,3,4,4,2,2,2, 2) (, 4) (==?G G δ. 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. 2) (, 3) (==?D D δ, 1) (, 2) (==?++D D δ, 1) (, 2) (==?--D D δ 8、设无向图中有 6条边, 3度与 5度顶点各 1个,其余顶点都是 2度点,问该图有多少 个顶点? 解:由握手定理图 G 的度数之和为:1262=? 设 2度点 x 个,则 1221513=+?+?x , 2=x ,该图有 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条边的无向简单图 G 1、 G 2、 G 3,证明它们至少有两个是同构的。 证明:4阶 4条边的无向简单图的顶点的最大度数为 3, 度数之和为 8, 因而度数列 为 2, 2, 2, 2; 3, 2, 2, 1; 3, 3, 1, 1。但 3, 3, 1, 1对应的图不是简单图。所以 从同构的观点看, 4阶 4条边的无向简单图只有两个: 所以, G 1、 G 2、 G 3至少有两个是同构的。 20、已知 n 阶无向简单图 G 有 m 条边,试求 G 的补图 G 的边数 m '。 解:m n n m --= '2 ) 1( 21、无向图 G 如下图 (1)求 G 的全部点割集与边割集,指出其中的割点和桥; (2) 求 G 的点连通度 ) (G k 与边连通度 ) (G λ。 c 解:点割集 : {a,b},(d) 边割集 {e2,e3},{e3,e4},{e1,e2},{e1,e4}{e1,e3},{e2,e4},{e5} ) (G k =) (G λ=1 23、求 G 的点连通度 ) (G k 、边连通度 ) (G λ与最小度数 ) (G δ。 解:2) (=G k 、 3) (=G λ 、 4) (=G δ 28、设 n 阶无向简单图为 3-正则图,且边数 m 与 n 满足 2n-3=m问这样的无向图有几种 非同构的情况? 解:? ??=-=m n m n 3223 得 n=6,m=9. 31、设图 G 和它的部图 G 的边数分别为 m 和 m ,试确定 G 的阶数。 解:2) 1(+= +n n m m 得 2 ) (81m m n +++-= 45、有向图 D 如图 (1)求 2v 到 5v 长度为 1, 2, 3, 4的通路数; (2)求 5v 到 5v 长度为 1, 2, 3, 4的回路数; (3)求 D 中长度为 4的通路数; (4)求 D 中长度小于或等于 4的回路数; (5)写出 D 的可达矩阵。 v3v4 解:有向图 D 的邻接矩阵为: ???????? ??=0101000 10110000 001011000 0A , ???????? ? ?=002022000 00101020000010102A ??? ??? ? ? ??=400000202 00020 2020200020 23A ???????? ? ?=040400040440000 00404400004A ??? ??? ? ? ??=+++452522252 45121 2225255121 0432A A A A (1)2v 到 5v 长度为 1, 2, 3, 4的通路数为 0,2,0,0; (2)5v 到 5v 长度为 1, 2, 3, 4的回路数为 0,0,4,0; (3)D中长度为 4的通路数为 32; (4)D中长度小于或等于 4的回路数 10; (4)出 D 的可达矩阵 ??? ??? ? ? ? ?=111111111111111 11111 11111 P 第十六章部分课后习题参考答案 1、画出所有 5阶和 7阶非同构的无向树 . 2、 一棵无向树 T 有 5片树叶, 3个 2度分支点, 其余的分支点都是 3度顶点, 问 T 有几个顶点 ? 解:设 3度分支点 x 个,则 ) 135(232315-++?=+?+?x x ,解得 3=x T 有 11个顶点 3、无向树 T 有 8个树叶, 2个 3度分支点,其余的分支点都是 4度顶点,问 T 有几个 4度分支 点?根据 T 的度数列,请至少画出 4棵非同构的无向树。 解:设 4度分支点 x 个,则 ) 128(243218-++?=+?+?x x ,解得 2=x 度数列 111111113344 4、棵无向树 T 有 i n (i=2, 3,?, k 错误!未找到引用源。 ) 个 i 度分支点, 其余顶点都是树叶, 问 T 应该有几片树叶 ? 解:设树叶 x 片,则 ) 1(21-+?=?+?x n x i n i i ,解得 2) 2(+-=i n i x 评论:2, 3, 4题都是用了两个结论 , 一是握手定理,二是 1-=n m 5、n(n≥ 3) 阶无向树 T 的最大度 错误!未找到引用源。 至少为几?最多为几? 解:2, n-1 6、若 n(n≥ 3) 阶无向树 T 的最大度 错误!未找到引用源。 =2,问 T 中最长的路径长度为几? 解:n-1 7、证明:n(n≥ 2) 阶无向树不是欧拉图 . 证明:无向树没有回路,因而不是欧拉图。 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 的基本割集系统 . (a) (b) 图 16.16 解:(a)T的弦:c,d,g,h 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个二进制数字 31 第七章部分课后习题参考答案 7. 列出集合 A={2,3,4}上的恒等关系 I A, 全域关系 E A , 小于或等于关系 L A , 整除关系 D A . 解:I A ={<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>} L A ={<2,2>,<2,3>,<2,4>,<3,3>,<3,4>,<4,4>} D A ={<2,4>} 13. 设 A={<1,2>,<2,4>,<3,3>} B={<1,3>,<2,4>,<4,2>} 求 A ?B,A ?B, domA, domB, dom(A?B), ranA, ranB, ran(A?B ), fld(A-B). 解:A ?B={<1,2>,<2,4>,<3,3>,<1,3>,<4,2>} A?B={<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(A?B)={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>} 求 R R, R -1, R ↑{0,1,}, R[{1,2}] 解:R R={<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}, 1R , 2R 为 A 上的关系,其中 1 R = { }, , , , , a a a b b d {2, , , , , , , R a d b c b d c b = 求 23 122112, , , R R R R R R 。 解 : R1 R 2={,,} R2 R 1={ R 12=R1 R 1={,,} R 22=R2 R 2={ 36.设 A={1, 2, 3, 4},在 A ?A 上定义二元关系 R , ? ∴ ?范文二：离散数学习题答案（耿素云/屈婉玲）
范文三：离散数学习题答案(耿素云屈婉玲)
范文四：武汉工程大学离散数学(屈婉玲)答案
范文五：屈婉玲高教版离散数学部分答案2