离散数学复习题高起本docx.docx
《离散数学复习题高起本docx.docx》由会员分享，可在线阅读，更多相关《离散数学复习题高起本docx.docx（16页珍藏版）》请在冰点文库上搜索。
离散数学复习题高起本docx
《离散数学》复习题
一、填空题
1、P：
你努力，Q：
你失败。
“除非你努力，否则你将失败”的翻译为
“虽然你努力了，但还是失败了”的翻译为。
2、论域D={1,2},指定谓词P
p
（1,1）
P
（1,2）
P
（2,1）
P（2,2）
T
T
F
F
贝!
J公式Vx3vP（v,x）真值为。
2、设S={a”a2,…，aJ,B,是S的子集，则由班所表达的子集是。
设入={2,3,4,5,6}上的二元关系R={（列举法）。
R的关系矩阵o
5、设A={1,2,3},则A上既不是对称的又不是反对称的关系R=；A上
既是对称的又是反对称的关系日=。
6、设代数系统〈A,*>,其中A={a,b,c},则幺元是；是否有矗等性是否有对称性。
7、4阶群必是群或群。
8、下面偏序格是分配格的是。
10、公式（Pv（^Pa2））a（（^Pv2）a^7?
的根树表示为
11、设f,g是自然数集N上的函数/U）=x+1,g（x）=2x,
则f。
g（W=。
12、设A二{a,b,c},A上二元关系R={〈a,a>,,,}
则s（R）=o
13、A={1,2,3,4,5,6},A上二元关系T={\x^y是素数},则用列举法
T=；
T的关系图为
T具有性质。
14、集合A={{①,2},{2}）的矗集2a=0
15、P,Q真值为0；R,S真值为lo则倾（P△（RvS））f（（PvQ"（R人S））的真值为。
16、"T（PaQWRIR的主合取范式为。
17、设P（x）：
x是素数，E（x）:
x是偶数，0（x）：
x是奇数N（x,y）:
x可以整数y。
则谓词沛Va-（P（x）t3y（O（y）aN（y,x）））的自然语言是
18、谓词wffSVy（王（P（x,z）aP（y,z））TBuQ（x,y,u））的前束范式为
二、选择题
1、在下述公式中是重言式为（）
A.（P八Q）t（PvQ）；B.
C.「（PtQ）aQ；d-Pt（PvQ）。
2、命题公式（「pfQUQvP）中极小项的个数为（），成真赋值的个数为
（）。
A.0；B.1；C.2；D.3o
3、设S={A.3；B.6；C.7；D.8o
3、设S={1,2,3}，定义SxS上的等价关系
R=（«a,b>,\个划分共有（）个分块。
A.4；
B.5；C.6；
D.9o
5、设、={1,2,3}，S上关系R的关系图为
B.反自反性、反对称性;
D.自反性。
）是域。
B.S={x\x=2n,a,beZ}
则R具有（）性质。
A.自反性、对称性、传递性；
C.反自反性、反对称性、传递性;
6、设+,o为普通加法和乘法，则（
A・S=（x|x=a+b4?
>,a,beQ]
C.S={x|x=2*+1,ngZ）
D.S=（x|xeZAX>0）=N。
7、下面偏序集（）能构成格。
[B）
[C]
[D]
10、设R是实数集合，“X”为普通乘法，则代数系统〈R,X>是（）。
A.群；B.独异点；C.半群；D.不确定。
11、下述命题公式中，是重言式的为（）。
A、（pu）T（pvq）；b、（psq）s（（p，q））八（q，p））；
c、TpT0）U；d、
12、"TP人qlr的主析取范式中含极小项的个数为（）。
A、2；B、3；C、5；D、0；E、8。
13、给定推理
1X/x（尸⑴tG（x））p
2尸（y）rG（y）低①
33xF（x）p
4F（V）ES③
5G（V）T②④I
6VxG（x）UG⑤
Vx（F（x）TG（x））=>VxG（x）
推理过程中错在（）。
A、①-〉②；B、②-〉③；C、③-〉④；D、④-〉⑤；E、⑤-〉⑥
14、设Si={l,2,…,8,9},S2={2,4,6,8},S3={1,3,5,7,9},S4={3,4,5},
S5=｛3,5｝,在条件X.Si且XA、X=S,或Ss；B、X=S<或&；
C、X=S”S2或&；D、X与Si，…,S,中任何集合都不等。
15、设R和s是p上的关系，p是所有人的集合，R=｛lx,ycPAx是y的父亲｝,
S=｛|x,yeP心是y的母亲｝则。
人表示关系（）。
A、｛<%,y>|%,jePa的丈夫｝;
B、｛<%,y>|%,jePa的孙子或孙女J；
c、lx,ycPax是y的祖父或祖母。
16、下面函数（）是单射而非满射。
A、f：
RtR,f（-v）—+2x—1.
B、fZtR,/（x）-lnx.
C、f：
RtZ,/（%）=[%],[%]表示不大五的最大整数；
D、f：
RtR,/（a-）=2a-+1o
其中R为实数集，七为整数集，R\Z+分别表示正实数与正整数集。
17、设S={L2,3},R为S上的关系，其关系图为
©@
则R具有（）的性质。
B、自反、对称、传递；B、什么性质也没有；
C、反自反、反对称、传递；D、自反、对称、反对称、传递。
18、设S={A、{{1,2}}；B、{1,2）；C、{1}；D、{2}o
19、设A={1,2,3},则A上有（）个二元关系。
A、23；B、3，；C、2’；D、23'o
20、全体小项合取式为（）o
A、可满足式；B、矛盾式；C、永真式；D、A,B,C都有可能。
三、证明题
1、设R是A上一个二元关系，
51={|（a,beA）/\（对于某一■个?
eA,有e我且e我）}试证明右R是A上一个等价关系，则S也是A上的一个等价关系。
2、用逻辑推理证明：
所有的舞蹈者都很有风度，王华是个学生且是个舞蹈者。
因此有些学生很有风度。
3、若f:
A^B是从A到B的函数，定义一个函数g-B^2A对任意beB有g（b）={x|（a-gA）a（y（A-）=/?
）},证明：
右f是A到B的*两射，则g是从B到2入的单射。
4、若无向图G中只有两个奇数度结点，则这两个结点一定连通。
5、设G是有n个结点的无向简单图，其边数秫=J_（〃_i）（〃_2）+2，则G是Hamilton图
6、AvB^CaD,DvE^F=>At/7
7、Vx（P（x）vQ（x））=VxP（x）vHx0x）
四、计算题
1、设〈Z6,+6>是一个群，这里+6是模6加法,Z6={[0],[1],[2],[3],[4],[5]},试求出的所有子群及其相应左陪集。
2、权数1,4,9,16,25,36,49,64,81,100构造一棵最优二叉树。
3、集合X={<1,2>,<3,4>,<5,6>,••-},R=（«xbyi>,1）证明R是X上的等价关系。
2）求出X关于R的商集。
五、简答题
设集合A={a,b,c,d}上关系R={〈a,b>,,,}要求1、写出R的关系矩阵和关系图。
2、用矩阵运算求出R的传递闭包。
六、理论题
1、设f和g是函数，证明fcg也是函数。
2、设函数g：
S—Tf：
T_S,证明f'.T^S有一左逆函数当且仅当f是入射函数。
参考答案
一、填空题
「P".P^Q
1、，
2、T
3、B31—^00011111={。
4，。
5，。
6，。
7，。
8}
4、R={<2,2>,<2,3>,<2,4>,<2,5>,<2,6>,<3,2>,<3,3>,<3,4>,<3,5>,<3,6>,<4,5>,<4,6>,<
<1
1
1
1
1
1
1
1
1
0
0
0
1
1
1
1
1
1
1
5,2>,<5,3>,<5,4>,<5,5>,<5,6>}；
3
0
0
0
0,
5、R={<1,2>,<1,3>,<2,1>}；R={<1,1>,<2,2>,<3,3>}
6、a；否；有
7、Klein四元群；循环群
8、B
10、
11、2（x+l）；
12、（,,,,,}_
13、（<2,1>,<3,1>,<5,1>,<4,2>,<6,2>,<6,3>}.
14、
反对称性、反自反性;
{①,{{①,2}},{{2}},{{①,2},{2}}}；
15、1；
16、（Pv「QvR）QvR）/\（PvQvR）；
17、任意x,如果x是素数则存在一个y,y是奇数且y整除x；
18、VxVyVz九（一lP（x,z）v~^P（y,z）vQ（x,y,〃））。
二、选择题
题
i
1
2
3
4
5
6
7
8
9
10
答
案
B、D
D；D
D
B
D
A
B
B
B
B、C
题目
11
12
13
14
15
16
17
18
19
20
答案
C
C
C
C
A
B
D
A
D
C
三、证明题
1、
（1）S自反的
VtzeA,由r自反，:
.（aR）八（eR）,:
.（2）S对称的
\/a,beA
eSna,c〉eR）c,b〉eR）•••$定义
=4>（e7?
）a（e7?
）•••/?
对称
^eS•••/?
传递
（3）S传递的
X/a,b,ceA
&S/\&S
=>（eR）a（eR）a（e>eR）a（eR）
=^>（eR）/\（eR）•••/?
传递
=>由
（1）、
（2）、（3）得；S是等价关系。
2、证明：
设P（x）：
x是个舞蹈者；Q（x）:
x很有风度；S（x）：
x是个学生；a：
王华
上述句子符号化为:
前提：
FP（X）T0X））、
S（a）/\P（a）结论：
女（S（x）/\0x））
①S（a）aP（a）
P
②Va-（P（a-）t2（a））
P
③P（a）T0。
）
US②
④P（。
）
T①I
⑤。
（。
）・
T③④I
⑥S（a）
T①I
⑦S（a）/\Q（a）
T⑤⑥I
⑧3x（S（x）aQ（x）
EG⑦
3、证明：
尹/?
2）、•/'满射•■-3<2],«2eA
WX%）=々，f（a2）=如，且/（«i）*/（。
2），由'2?
^函数，...。
1*a2
又g（A）={%I（%eA）a（/（%）=bj},g（t>2）={%|（%eA）a（/（%）=如）}•'•Geg—）,但eg（4）但%£幺（如）,％任8（bi）•'•g（A）尹g（A）
由》i，Z>2任意性知，g为单射。
4、证明：
设G中两奇数度结点分别为u和v,若u,v不连通，则G至少有两个连通分支Gi、G2,使得u和v分别属于&和G2,于是&和Gz中各含有1个奇数度结点，这与图论基本定理矛盾，因而U,V一定连通。
5、证明：
证G中任何两结点之和不小于no
反证法：
若存在两结点u,v不相邻且+令的={”,v},则G*是具
1
m>-（/7-1）（h-2）+2-（77-1）
1
m>—（n-2）（n-3）+1
2,这与GlG-Vi为n-2个结点为简单图的题设矛盾，因而G中任何
两个相邻的结点度数和不少于n。
所以G为Hamilton图.
1A
2A'vB
P（附加前提）
T①I
④
△£）
T②③I
⑤。
T④I
⑥DvE
T⑤I
⑦DvEF
P
⑧F
T⑥⑦I
⑨A^F
CP
p
③AvBTC/\D
7、
VxP（x）v3xQ（x）=—i（Vx）P（x）T3xQ（x）
本题可证Vx（P（x）v2（x））n^（VxP（x）TBxQ（x）
①^（Va-P（a-））
P（附加前提）
T①E
③->P（a）
ES②
④Vx（P（x）v2（x））
P
⑤P（a）vQ（a）
US④
⑥。
（。
）
T③⑤I
⑦女Q3）
EG⑥
⑧-.（VxP（x）T3xQ（x）
CP
四、计算题
1、解：
子群有<（[0]）,+6>;<（[0],[3]},+6>;<（[0],[2],[4]},+6>;<{z6）,+6>
{[0]}的左陪集：
{[0]},（[1]}；{⑵},{⑶}；{[4]},（[5]）
{[0],⑶}的左陪集：
{[0],⑶};{[1],[4]}；（[2],[5]）
{[0],⑵，[4]}的左陪集：
{[0],⑵，[4]}；{[1],[3],[5]}
Z&的左陪集：
Z6o
2、
五、
1、
r0
1
0
0、
1
0
1
0
0
0
0
1
<0
0
0
0>
Mr
关系图
R2
2、
R3
<1
0
1
0、
0
1
0
1
0
0
0
0
<0
0
0
<0
1
0
n
1
0
1
0
0
0
0
0
E
0
0
g
q
0
1
0、
0
1
0
1
0
0
0
0
——
<0
0
0
0,
R2
=MroMr
M中=MkoMr
Mr，=M史°Mr
Mr，=Mr,
Mr6=Mr4,
Me=Mr+M『+Mr3+Mr4=
1
1
1
1
1
1
1
1
0
0
0
1
0
0
0
0
t（R）={,,,,,,,,d>}o
K、
cg={vx,y>|xgdomf/\xgdomg/\y-/（x）/\y=g（x）}
1、
（1）=（|xedomfr\domg/\y=/（x）=g（x）}
令力=/■cg
domfog=domh={x\x&domfodomg/（%）=g（x）}
（2）//={|xedomfrxdomg/\y=h{x）=f（x）=g（x）}
对x任domh若有凹,无使得
J1=成x）=f（x）=g（x）,j2=h（x）=f（x）=g（x）
由于f（或g）是函数有Vi=y2即Vxedom侑唯r使得y="（x）.•.了eg也是函数。
2、证明：
"n”苟有一左近，则对V/eTgof（t）=t
故8。
_/是入射，所以f是入射。
是入射，扫TTS定义如下：
V5e/（T）,if入射，B\teT,^f（t）=s
此时令g（s）=t,若s£f（T）令g（s）=ceT
则对VseS,g（s）只有一个值7或c且若=s
则g项。
）=g（s）=7,故g野的左逆元
即必射，必能构造函巍，使g为/左逆函数
升级会员 