离散数学屈婉玲版课后习题.doc

完整word版)离散数学屈婉玲版课后习题
第一章部分课后习题参考答案

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是无理数，则也是无理数。另外6能被2整除，6才能被4整除。”
答p: 是无理数 1
q: 3是无理数 0
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
所以公式类型为永真式
（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)

∑(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) 前提引入
②qr ①置换
③qr ②蕴含等值式
④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)在两个个体域中都解释为，在（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):xa） 个体域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.确定下列命题是否为真：
（1） 真
（2） 假
（3） 真
（4） 真
（5）｛a,b｝｛a,b,c,｛a,b,c｝｝ 真
（6）｛a,b｝｛a,b,c,｛ab｝｝ 真
（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},{ac},{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}，，为A上的关系，其中
=

求。
解: R1R2={,,}
R2R1={}
R12=R1R1={,,}
R22=R2R2={,,}

R23=R2R22={,,}
36．设A={1，2，3，4}，在AA上定义二元关系R，
,AA ，〈u,v> R u + y = x + v.
(1) 证明R 是AA上的等价关系.
(2)确定由R 引起的对AA的划分.
（1）证明：∵R u+y=x-y
∴Ru-v=x-y
AA
∵u-v=u-v
∴R
∴R是自反的
任意的,∈A×A
如果R ，那么u-v=x-y
∴x-y=u-v ∴y>R
∴R是对称的
任意的,,∈A×A
若R,R
则u-v=x-y,x-y=a-b
∴u-v=a-b ∴R
∴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)证明：R
∴R是自反的
任意的,∈A×A
设R，则a+b=c+d
∴c+d=a+b ∴R
∴R是对称的
任意的,,∈A×A
若R,R
则a+b=c+d,c+d=x+y
∴a+b=x+y ∴Ry>
∴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) (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={,,,,,,}IA.
(2)A={a,b,c,d,e}, R={}IA.
解:

(1) (2)
项目 (1) (2)
极大元: e a,b,d,e
极小元: a a,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:NN,f(x)=(x)mod 3,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={,,,}判断以下命题的真假:
(1)f是从X到Y的二元关系,但不是从X到Y的函数; 对
(2)f是从X到Y的函数,但不是满射,也不是单射的; 错
(3)f是从X到Y的满射,但不是单射; 错
(4)f是从X到Y的双射. 错
第十四章部分课后习题参考答案
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}
==1
23、求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度分支点个，则
，解得
度数列111111113344

4、棵无向树T有 (i=2，3，…，k)个i度分支点，其余顶点都是树叶，问T应该有几片树叶?
解：设树叶片，则
，解得
评论：2，3，4题都是用了两个结论,一是握手定理，二是
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-1)时，结论成立，当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个二进制数字.

39