离散数学复习题及答案.docx
《离散数学复习题及答案.docx》由会员分享，可在线阅读，更多相关《离散数学复习题及答案.docx（16页珍藏版）》请在冰点文库上搜索。
离散数学复习题及答案
1.写出命题公式﹁（P→（P∨Q））的真值表。
答案：
2.证明
答案：
3.证明以下蕴涵关系成立：
答案：
4.写出下列式子的主析取范式：
答案：
5.构造下列推理的论证：
p∨q,p→?
r,s→t,?
s→r,?
t?
q
答案：
①s→t前提
②t前提
③s①②拒取式I12
④s→r前提
⑤r③④假言推理I11
⑥p→r前提
⑦p⑤⑥拒取式I12
⑧p∨q前提
⑨q⑦⑧析取三段论I10
6.用反证法证明：
p→（?
（r∧s）→?
q）,p,?
s?
?
q
7.请将下列命题符号化：
所有鱼都生活在水中。
答案：
令 F（x）：
x是鱼W（x）：
x生活在水中
8.请将下列命题符号化：
存在着不是有理数的实数。
答案：
令Q（x）：
x是有理数R（x）：
x是实数
9.请将下列命题符号化：
尽管有人聪明，但并非一切人都聪明。
答案：
令M（x）：
x是人C（x）：
x是聪明的
则上述命题符号化为
10.请将下列命题符号化：
对于所有的正实数x,y，都有x+y≥x。
答案：
令P（x）:
x是正实数S（x,y）:
x+y≥x
11.请将下列命题符号化：
每个人都要参加一些课外活动。
答案：
令P（x）:
x是人Q（y）:
y是课外活动S（x,y）:
x参加y
12.请将下列命题符号化：
某些人对某些药物过敏。
答案：
令P（x）:
x是人Q（y）:
y是药S（x,y）:
x对y过敏
13.求
的对偶式:
答案：
14.求下列谓词公式的前束范式：
答案：
15.证明：
答案：
16.用反证法证明：
?
?
x（P（x）∧Q（x））,?
xP（x）?
?
?
xQ（x）
答案：
17.证明：
前提：
?
x（C（x）?
W（x）∧R（x））,?
x（C（x）∧Q（x））.
结论：
?
x（Q（x）∧R（x））.
答案：
⏹
（1）?
x（C（x）∧Q（x））前提引入
⏹
（2）C（a）∧Q（a）
（1）ES
⏹（3）C（a）
（2）化简规则
⏹（4）?
x（C（x）?
W（x）∧R（x））前提引入
⏹（5）C（a）?
W（a）∧R（a）（4）US
⏹（6）W（a）∧R（a）（3）（5）假言推理
⏹（7）R（a）（6）化简规则
⏹（8）Q（a）
（2）化简规则
⏹（9）R（a）∧Q（a）（7）（8）合取引入规则
⏹（10）?
x（Q（x）∧R（x））（9）EG
18.判断：
下列命题是否正确？
答案：
⏹
（1）√
⏹
（2）×
⏹（3）√
⏹（4）√
⏹（5）√
⏹（6）√
⏹（7）√
⏹（8）×
19.列出下列集合的元素
⏹
（1）{x|x∈N∧?
t（t∈{2,3}∧x=2t）}
⏹
（2）{x|x∈N∧?
t?
s（t∈{0,1}∧s∈{3,4}∧t⏹（3）{x|x∈N∧?
t（t整除2?
x≠t）}
答案：
⏹
（1）{4,6}
⏹
（2）{1,2,3}
⏹（3）{3,4,5…}
20.
S={0,1,2,3,4,5,6,7,8,9}，A={2,4,5,6,8}
B={1,4,5,9}，C={x|x∈Z+,2≤x≤5}
答案：
21.一个学校有507，292，312和344个学生分别选择了A,B,C,D四门课程。
有14人选了A和B，213人选了A和D，211人选了B和C，43人选了C和D。
没有学生同时选择A和C，也没有学生同时选择B和D。
问共有多少学生在这四门课程中选了课？
答案：
解：
画文氏图
280+87+38+88+14+211+213+43
=974
22.分别求下列集合的幂集
（1）?
（2）{?
}（3）{1,{?
1}}
答案：
⏹解:
（1）ρ（?
）={?
}空集?
的幂集的基数为1
⏹
（2）ρ（{?
}）={?
{?
}}幂集的基数为2
⏹（3）ρ（{1,{?
1}}）={?
{1},{{?
1}},{1,{?
1}}}
23.
A={0,1},B={1,2},C={3,4,5},求A×B,B×A,A×B×C,A2,C2.
答案：
⏹A×B={（0,1）,（0,2）,（1,1）,（1,2）}
⏹B×A={（1,0）,（2,0）,（1,1）,（2,1）}
⏹A×B×C={（0,1,3）,（0,1,4）,（0,1,5）,（0,2,3）,（0,2,4）,（0,2,5）,（1,1,3）,（1,1,4）,（1,1,5）,（1,2,3）,（1,2,4）,（1,2,5）}
⏹A2={（0,0）,（0,1）,（1,0）,（1,1）}
⏹C2={（3,3）,（3,4）,（3,5）,（4,3）,（4,4）,（4,5）,（5,3）,（5,4）,（5,5）}
24.
⏹1.设A={{1,2,3},{4,5},{6,7,8}},下列选项正确的是（C）
⏹A.1∈AB.{1,2,3}AC.{{4,5}}AD.?
∈A
⏹2.设A={x|x3–x=0},B={x|x2–4<0,x∈z},C={x|y=2x-1},D={x|x+y=5,xy=6}则有（A）
⏹A.A=BB.A=CC.C=DD.C=A
25.求关系的定义域和值域：
⏹设A={2，4，6，8}，R是A上的小于关系，即当a,b∈A且a答案：
R={（2，4）,（2，6）,（2，8）,（4，6）,（4，8）,（6，8）}.
R的定义域D（R）={2，4，6}，
R的值域C（R）={4，6，8}。
26.设A={a,b,c,d},求A上的恒等关系。
答案：
IA={（a,a）,（b,b）,（c,c）,（d,d）}。
27.设A={1,2,3,4,5},R是A上的小于等于关系,即当a≤b时,（a,b）∈R。
求R的关系矩阵和关系图。
答案：
解:
易知A上的小于等于关系为
R={（1,1）,（1,2）,（1,3）,（1,4）,（1,5）,（2,2）,（2,3）,（2,4）,（2,5）,（3,3）,（3,4）,（3,5）,
（4,4）,（4,5）,（5,5）}
其关系矩阵为
28.X={a,b,c}，Y={1,2}，
关系R={（a,1）,（b,2）,（c,1）}S={（a,1）,（b,1）,（c,1）}
求R∪S、R∩S和R的补
答案：
29.设A={1，2，3}，B={a,b,c,d},C={x,y,z}，R是A到B的二元关系，R={（1,a）,（1,b）,（2,b）,（3,c）}，S是B到C的二元关系，S={（a,x）,（b,x）,（b,y）,（b,z）}。
求复合关系RοS的关系矩阵.
答案：
30.
答案：
31.设A={a,b,c}，R是A上的二元关系，R={（a,a）,（b,b）,（a,b）,（a,c）,（c,a）}，问：
R是自反的吗？
是反自反的吗？
是对称的吗？
是反对称的吗？
是可传递的吗？
答案：
⏹
由于c∈A，而（c,c），所以R不是自反的。
×
⏹由于（a,a）∈R，（b,b）∈R，所以R不是反自反的。
×
⏹
由于（a,b）∈R，而（b,a），所以R不是对称的。
×
⏹由于（a,c）∈R，且（c,a）∈R，所以R不是反对称的。
×
⏹
由于（c,a）∈R，且（a,c）∈R，但（c,c），所以R不是可传递的。
×
32.
⏹设A={1,2,3}，分析A上的下述5个关系具有哪些性质：
⏹L={<1,1>,<1,2>,<2,1>,<2,2>,<3,3>}
⏹N={<1,3>,<2,3>}
⏹S={<1,2>,<2,1>,<1,3>}
⏹G={<1,1>,<1,2>,<2,3>}
答案：
33.设A={a,b,c,d}，A上的关系，R={（a,b）,（b,a）,（b,c）,（c,d）}
求r（R）、s（R）、t（R）
答案：
34.A={a,b,c},R={（a,b）,（b,c）,（c,a）}，求r（R）,S（R）和t（R）
答案：
35.A={1,2,3,4}，R={（1,1）,（1,2）,（1,4）,（2,1）,（2,2）,（3,3）,（4,1）,（4,4）},判断R是否是等价的。
答案：
36.判断下列关系是否为等价关系？
（1）A={a,b,c,d}，R={（a,a）,（b,a）,（b,b）,（c,c）,（d,d）,（d,c）}
（2）A={1,2,3,4}，
R={（1,1）,（1,2）,（1,3）,（2,1）,（2,2）,（3,1）,（2,3）,（3,3）,（4,4）,（3,2）}
答案：
（1）×
（2）√
37.A={1,2,3,4}在幂集ρ（A）上定义的二元关系如下：
R={（S,T）|S,T∈ρ（A），|S|=|T|}，写出商集ρ（A）/R。
答案：
解：
首先求ρ（A）。
ρ（A）={?
{1},{2},{3},{4},{1,2},{1,3},{1,4},{2,3},{2,4},{3,4},{1,2,3},{1,2,4},{1,3,4},{2,3,4},
{1,2,3,4}}共16个元素！
38.设集合X={2166，243，375，648，455}
X中的关系R为：
R={（x,y）|x,y∈X，并且x和y中有相同数字}
问：
R是不是相容关系？
答案：
39.A={1，2，3，4，5，6，8，10，12，16，24}，R是A上的整除关系，请画出Ｒ的哈斯图。
答案：
40.已知偏序集的哈斯图如图所示,试求出集合A和关系R的表达式.?
求A的极小元、最小元、极大元、最大元.设B＝{b,c,d},求B的下界、上界、最大下界、最小上界.
答案：
极小元：
a,b,c,g；
极大元：
a,f,h；
没有最小元与最大元.
B的下界和最大下界都
不存在,上界有d和f,
最小上界为d.
41.以下关系矩阵所代表的关系是什么关系？
答案：
相容关系
42.设集合A={1，2，3，4，5，6，8，10，12，16，24}，R是A上的整除关系，请问关系R是否是偏序关系？
是否是全序关系？
画出Ｒ的哈斯图，并根据图求集合A的极大极小元、最大最小元，
设B={2，3，4}，求集合B的上界、最小上界、下界、最大下界。
答案：
是偏序关系，不是全序关系。
A的极大元：
24,16,10
A的极小元：
1
A的最大元：
没有
A的最小元：
1
B的上界：
12,24
B的最小上界：
12
B的下界：
1
B的最大下界：
1
43.找出如下哈斯图中的子集{a,b,c}、{j,h}和{a,c,d,f}的上界和下界。
答案：
⏹{a,b,c}上界：
e,f,j,h下界：
a
⏹{j,h}上界：
无下界：
f,d,e,b,c,a
⏹{a,c,d,f}上界：
f,j,h下界：
a
44.判断下列关系是否是映射？
是否是单射？
是否是满射？
答案：
映射（非单射、非满射）、映射（满射）
映射（单射）、不是映射
45.X={x1,x2,x3},Y={y1,y2},Z={z1,z2}
f:
X→Y，g:
Y→Z，求h=g?
f
答案：
46.
下列哪些关系可以构成函数（映射）？
a.f={（x,y）|x,y∈N,x+y<10}
b.f={（x,y）|x,y∈R,x2=y}
答案：
能
不能
47.
判断下列函数是单射、满射或双射？
a.f:
N→N,f（x）=x+2;
b.f:
N→N,f（x）=x（mod2）;
c.f:
N→ρ（N）,f（x）={x};
答案：
单射
什么都不是
单射
48.
f?
1°f=？
，f°f?
1=？
答案：
f?
1°f=IA，f°f?
1=IB
49.
构造下列函数的反函数：
1.f（x）=sinx
2.f（x）=x2,x∈（-∞，0）
3.A={1,2,3},B={a,b,c},f:
A→B,f={（1,a）,（2,c）,（3,b）}
答案：
f-1（x）=arcsinx
f-1（x）=-x1/2
f-1={（a,1）,（c,2）,（b,3）}
50.
答案：
51.
已知x={a,b,c},Y={1,2,3,4}f:
X→Y如图所示,试构造函数g:
Y→X,使得g·f=Ix
答案：
g={（1,a）,（2,c）,（3,b）,（4,a）}
52.
请给出图中各点的度数，以及图的最大度数和最小度数。
答案：
d（v1）=4,d（v2）=4,d（v3）=2,d（v4）=1,d（v5）=3
D（G）=4,d（G）=1
53.请给出图中各点的出度和入，以及图的最大出度和最小入度。
答案：
d+（a）=4,d-（a）=1,d（a）=5,
d+（b）=0,d-（b）=3,d（b）=3,
?
+（D）=4,?
+（D）=0,?
?
（D）=3,
?
?
（D）=1,?
（D）=5,?
（D）=3.
54.（3,3,3,4）,（2,3,4,6,8）能成为图的度数序列吗?
答案：
不可能.它们都有奇数个奇数.
55.已知图G有10条边,4个3度顶点,其余顶点的度数均小于等于2,问G至少有多少个顶点?
答案：
设G有n个顶点.由握手定理,
4?
3+2?
（n-4）?
2?
10
解得n?
8
56.下面无向图中有几个顶点？
（1）16条边，每个顶点都是2度顶点
（2）21条边，3个4度顶点，其余的都是3度顶点
（3）35条边，每个顶点的度数至少为3的图最多有几个顶点？
答案：
57.确定下列各图的出度、入度和度数
答案：
58.判断下列图是否同构
答案：
是
是
不是
是
59.下图中，
1.写出{a,d,e}的导出子图
2.画出它的一个生成子图
3.边集{e4,e7,e6}的导出子图
答案：
60.试画出以下两个图的并图、交图和环和。
答案：
61.判断下列各图是否是连通图：
答案：
是、不是
62.指出下列有向图的连通性
答案：
强连通图 单向连通图 弱连通图
强连通图 单向连通图 弱连通图
63.求下列图的强连通分支
答案：
64.
（1）{e5}、{e2、e3}、{e6}、{e4}是否是下图的边割集？
（2）{v5}、{v2、v4}、{v3}、{v1、v2}、{v2、v3}是否是下图的点割集？
答案：
（1）是、是、是、否
（2）是、是、是、否、否
65.求出下图的全部割点和桥
答案：
66.下列图是否是树？
如果是，找出树的分枝结点和树叶。
答案：
不是、是
分枝结点：
e,f
树叶：
a,b,c,d,g,h
67.设一棵树T有2个度数为2的结点，1个度数为3的结点，3个度数为4的结点，求T有几片树叶。
答案：
68.已知无向树T有5片树叶,2度与3度顶点各1个,其余顶点的度数均为4.求T的阶数n。
答案：
69.求下列树的树根、树叶、树高、内点、分枝点、各个结点的层数
答案：
a是树根.
b,e,f,h,i是树叶.
c,d,g是内点.
a,c,d,g是分枝点.
a为0层;1层有b,c;2层有d,e,f;
3层有g,h;4层有i.
树高为4.
70.求下列树的树高、内点数、分枝点树、几叉树？
答案：
4、5、6、4
71.下列树是不是完全二叉树？
是不是满二叉树？
答案：
4叉树、完全3叉树
72.求下列二叉树的前序、中序、后序遍历
答案：
前序：
a→b→d→e→h→c→f→g→i→j
中序：
d→b→h→e→a→f→c→i→g→j
后序：
d→h→e→b→f→i→j→g→c→a
73.求下列二叉树的前序、中序、后序遍历
答案：
74.构造下列数的排序二叉树：
15,3,1,6,18,7,10,20
答案：
75.求树叶权为4，2，3，5，1的最优树。
答案：
最优树的权重W（T）为：
1×3+2×3+3×2+4×2+5×2=33
76.求带权图的最小生成树。
答案：
这棵最小生成树的权为:
1+1+2+2+3+4=13.
77.求下图的邻接矩阵
答案：
78.写出下列表达式的“波兰表示式”
（（a–4b）c–（7d+b））/（c+5a）
答案：
先表示成二叉树的形式
再对二叉树进行前序遍历即的波兰式为：
/–×–a×4bc+×7db+c×5a
升级会员 