离散数学本科

1、离散数学复习资料 2014年12月一、单项选择题（每小题3分，本题共15分）1若集合A=1，2，B=1，2，1，2，则下列表述正确的是( A ) A AÌB，且AÎB BBÌA，且AÎB CAÌB，且AÏB DAËB，且AÎB 2设有向图（a）、（b）、（c）与（d）如图一所示，则下列结论成立的是 ( D ) 图一 A（a）是强连通的 B（b）是强连通的C（c）是强连通的 D（d）是强连通的3设图G的邻接矩阵为则G的边数为( B )A6 B5 C4 D34无向简单图G是棵树，当且仅当( A )AG连通且边数比结点数

2、少1 BG连通且结点数比边数少1CG的边数比结点数少1 DG中没有回路5下列公式 ( C )为重言式AØPÙØQ«PÚQ B(Q®(PÚQ) «(ØQÙ(PÚQ)C(P®(ØQ®P)«(ØP®(P®Q) D(ØPÚ(PÙQ) «Q6设A=a, b，B=1, 2，R1，R2，R3是A到B的二元关系，且R1=<a，2>, <b，2>，R2=<a，1&g

3、t;, <a，2>, <b，1>，R3=<a，1>, <b，2>，则（ B ）不是从A到B的函数AR1和R2 BR2 CR3 DR1和R37设A=1, 2, 3, 4, 5, 6, 7, 8，R是A上的整除关系，B=2, 4, 6，则集合B的最大元、最小元、上界、下界依次为 ( B ) A8、2、8、2 B无、2、无、2 C6、2、6、2 D8、1、6、18若集合A的元素个数为10，则其幂集的元素个数为（ A ） A1024 B10 C100 D19设完全图K有n个结点(n2)，m条边，当（ C ）时，K中存在欧拉回路Am为奇数 Bn为偶数 Cn

4、为奇数 Dm为偶数10已知图G的邻接矩阵为 ，则G有（ D ） A5点，8边 B6点，7边 C6点，8边 D5点，7边11.无向完全图K3的不同构的生成子图的个数为（ C ）(A) 6 (B) 5 (C) 4 (D) 312 n阶无向完全图Kn中的边数为（ A ）(A) (B) (C) n (D)n(n+1) 13.在图G<V,E>中，结点总度数与边数的关系是( C )A deg(vi)=2½E½ (B) deg(vi)=½E½ C D二、填空题（每小题3分，本题共15分）1命题公式的真值是 1 2若A=1,2，R=<x, y>|

5、xÎA, yÎA, x+y<4，则R的自反闭包为 <1,1>,<2,2>,<1,2>,<2,1> 3已知一棵无向树T中有8个结点，4度，3度，2度的分支点各一个，T的树叶数为 5 4("x)(P(x)Q(x)R(x，y)中的自由变元为 R(x，y )中的y 5设集合Aa，b，那么集合A的幂集是 Æ,a,b,a,b 6如果R1和R2是A上的自反关系，则R1R2，R1R2，R1-R2中自反关系有 2 个 7设图G是有6个结点的连通图，结点的总度数为18，则可从G中删去 4 条边后使之变成树8无向图G存在欧

6、拉回路，当且仅当G所有结点的度数全为偶数且 连通 9设连通平面图G的结点数为5，边数为6，则面数为 3 10设个体域Da, b，则谓词公式("x)A(x)（$x）B（x）消去量词后的等值式为 (A (a)A (b)(B（a）B（b）) 三、逻辑公式翻译（每小题6分，本题共12分） 1将语句“雪是黑色的”翻译成命题公式设P：雪是黑色的， （2分）则命题公式为：P2将语句“他不去学校”翻译成命题公式解：设P：他去学校， 则命题公式为： Ø P 3将语句“小王是个学生，小李是个职员，而小张是个军人”翻译成命题公式设P：小王是个学生，Q：小李是个职员，R：小张是个军人 （2分）则命

7、题公式为：PQR4将语句“如果所有人今天都去参加活动，则明天的会议取消”翻译成命题公式解：设P：所有人今天都去参加活动，Q：明天的会议取消， 则命题公式为： P® Q5将语句“他去旅游，仅当他有时间”翻译成命题公式解：设 P：他去旅游，Q：他有时间， 则命题公式为： P ®Q6将语句“41次列车下午五点开或者六点开”翻译成命题公式解：设P：41次列车下午五点开，Q：41次列车下午六点开， （2分）命题公式为：（PØQ）（ØPQ） 7将语句“小张学习努力，小王取得好成绩”翻译成命题设P：小张学习努力，Q：小王取得好成绩， （2分）则命题公式为：PÙ

8、;Q8将语句“有人去上课” 翻译成谓词公式 解：设P(x)：x是人，Q(x)：x去上课， （1分）($x)(P(x) ÙQ(x) 9将语句“所有的人都学习努力”翻译成命题公式 解：设P(x)：x是人，Q(x)：x学习努力， "x）(P(x)®Q(x) 四、判断说明题（每小题7分，本题共14分）判断下列各题正误，并说明理由 1设集合A=1, 2, 3, 4，B=2, 4, 6, 8，判断下列关系f是否构成函数f：，并说明理由(1) f=<1, 4>, <2, 2,>, <4, 6>, <1, 8>； (2)f=<

9、1, 6>, <3, 4>, <2, 2>；(3) f=<1, 8>, <2, 6>, <3, 4>, <4, 2,> 答：（1）不构成函数 因为，但没有定义，所以不构成函数 （2）不构成函数 因为，但没有定义，所以不构成函数 （3）满足。 因为任意，都有且结果唯一。2若集合A = 1，2，3上的二元关系R=<1, 1>，<2, 2>，<1, 2>，则(1) R是自反的关系； (2) R是对称的关系答：（1）错误 因为，所以R不是自反的 （2）错误 因为，但是，所以R不是对称的 3

10、如果R1和R2是A上的自反关系，判断结论：“R-11、R1R2、R1R2是自反的” 是否成立？并说明理由 答：成立 因为任意，有所以， R-11、R1R2、R1R2是自反的ooooabcd图一ooogefho4若偏序集<A，R>的哈斯图如图一所示，则集合A的最大元为a，最小元不存在 答：错误，集合A没有最大元，也没有最小元 其中a是极大元5若偏序集<A，R>的哈斯图如图一所示，则集合A的最大元为a，最小元不存在 解：正确对于集合A的任意元素x，均有<x, a>ÎR（或xRa），所以a是集合A中的最大元按照最小元的定义，在集合A中不存在最小元 6如果

11、图G是无向图，且其结点度数均为偶数，则图G存在一条欧拉回路答：错误 如果图G是无向图，且图G是连通的，同时结点度数都是偶数7设G是一个连通平面图，且有6个结点11条边，则G有7个面答案：正确 定理，连通平面图G的结点数为v，边数是e，面数为r，则欧拉公式v-e+r=2成立 所以r=2-v+e=2-6+11=7 则G存在一条欧拉回路8设G是一个有6个结点14条边的连通图，则G为平面图解：错误，不满足“设G是一个有v个结点e条边的连通简单平面图，若v3，则e3v-6” 9命题公式ØPÙ(P®ØQ)ÚP为永真式 解：正确 因为，由真值表PQØ

12、;PØQP®ØQØP(PØQ)P001111011011100111110001可知，该命题公式为永真式 五计算题（每小题12分，本题共36分）1设集合A=a, b, c，B=a, c，试计算（1）（AB）； （2）（B - A）； （3）（AB）×B解（1）（AB）=c； （2）（B - A）=a； （3）（AB）×B=<c，a>, < c，c > 2设A=0，1，2，3，4，5，6，R=<x，y>|xÎA，yÎA且x+y<1，S=<x，y>|x&#

13、206;A，yÎA且x+y£3，试求R，S，R·S，R-1，S-1，r(R)解：R=<0,0> S=<0,0>,<0,1>,<0,2>,<0,3>,<1,0>,<1,1>,<1,2>,<2,0>,<2,1>,<3,0> R·S=<0,0>,<0,1>,<0,2>,<0,3> R-1=<0,0> S-1= S ）r(R)=IA 3图G=<V, E>，其中V

14、= a, b, c, d, e，E= (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (c, d), (d, e) ，对应边的权值依次为2、1、2、3、6、1、4及5，试（1）画出G的图形； （2）写出G的邻接矩阵；（3）求出G权最小的生成树及其权值解：（1）G的图形表示为： （3分）（2）邻接矩阵： （6分）（3）粗线表示最小的生成树， 权为7： 4设图G=<V，E>，V= v1，v2，v3，v4，v5，E= (v1, v2)，(v1, v3)，(v2, v3)，(v2, v4)，(v3, v4)，(v3, v5)，(v4, v5)

15、 ，试(1) 画出G的图形表示；(2) 求出每个结点的度数； (3) 画出图G的补图的图形v1v2v3v4v5ooooo解：（1）关系图 （2）deg(v1)=2 deg(v2)=3 deg(v3)=4deg(v4)=3 v1v2v3v4v5ooooodeg(v5)=2 （3）补图 5设集合A=1，2，3，4，R=<x, y>|x, yÎA；|x-y|=1或x-y=0，试（1）写出R的有序对表示； （2）画出R的关系图；（3）说明R满足自反性，不满足传递性解:（1）R=<1,1>,<2,2>,<3,3>,<4,4>,<

16、1,2>,<2,1>,<2,3>,<3,2>,<3,4>,<4,3> （3分）°°°°1234（2）关系图为 （3）因为<1,1>,<2,2>,<3,3>,<4,4>均属于R，即A的每个元素构成的有序对均在R中，故R在A上是自反的。 因有<2,3>与<3,4>属于R，但<2,4>不属于R，所以R在A上不是传递的。6设集合A=1, 2, 3，R=<1，1>, <2，1>,<3，1

17、>，S=<1，2>, <2，2>试计算（1）R·S； （2）R -1； （3）r（R）解： （1）R·S =<1，2>, <2，2>,<3，2>； （4分）（2）R -1=<1，1>, <1，2>, <1，3> ； （8分）（3）r（R）=<1，1>, <2，2> , <3，3>, <2，1>,<3，1> 7、求出如图一所示赋权图中的最小生成树（要求写出求解步骤），并求此最小生成树的权解 用Kruskal算法求产生

18、的最小生成树步骤为： 选 选 选 选 选 选 （6分）最小生成树如图四所示： （9分） 图四 最小生成树的权为：w(T)=22+1+4+9+3+18=57 （12分）8试画一棵带权为2, 3, 3, 4, 5,的最优二叉树,并计算该最优二叉树的权ooooooooo23345510717解： 最优二叉树如图二所示 （10分） 图二 权为2´3+3´3+3´2+4´2+5´2=39 9设谓词公式，试（1）写出量词的辖域； （2）指出该公式的自由变元和约束变元（1）$x量词的辖域为， （2分）"z量词的辖域为, （4分） "y量词

19、的辖域为 （6分）（2）自由变元为中的y，以及中的z （9分）约束变元为中的x与中的z，以及中的y 10设谓词公式，试（1）写出量词的辖域； （2）指出该公式的自由变元和约束变元（1）$x量词的辖域为， （3分）"z量词的辖域为, （6分） （2）自由变元为公式中的y与中的x， （9分）约束变元为的x与z 11求命题公式(PÚQ)®(RÚQ) 的主析取范式、主合取范式解：PQRPÚQRÚQ(PÚQ)®(RÚQ)极小项极大项0000111100110011010101010011111101110111 1

20、 1 1 1 0 1 1 1ØPÙØQÙØRØPÙØQÙRØPÙQÙØRØPÙQÙRPÙØQÙRPÙQÙØRPÙQÙRØPÚQÚR 主析取范式（极小项析取）： （ØPÙØQÙØR）Ú（ØPÙØQÙR）Ú（ØPÙQÙØR）