电大离散数学(本科)期末考试复习资料

《电大离散数学(本科)期末考试复习资料》由会员分享，可在线阅读，更多相关《电大离散数学(本科)期末考试复习资料（9页珍藏版）》请在装配图网上搜索。

1、离散数学复习资料 一、单项选择题（每小题3分，本题共15分）1若集合A=1，2，B=1，2，1，2，则下列表述正确的是( A ) A AB，且AB BBA，且AB CAB，且AB DAB，且AB 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连通且边数比结点数少1 BG连通且结点数比边数少1CG的边数比结点数少1 DG中没有回路5下列公式 ( C )为重言式APQPQ

2、B(Q(PQ) (Q(PQ)C(P(QP)(P(PQ) D(P(PQ) Q6设A=a, b，B=1, 2，R1，R2，R3是A到B的二元关系，且R1=, ，R2=, , ，R3=, ，则（ 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)

3、，m条边，当（ C ）时，K中存在欧拉回路Am为奇数 Bn为偶数 Cn为奇数 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中，结点总度数与边数的关系是( C )A deg(vi)=2E (B) deg(vi)=E C D二、填空题（每小题3分，本题共15分）1命题公式的真值是 1 2若A=1,2，R=|xA, yA, x+y4

4、，则R的自反闭包为 , 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存在欧拉回路，当且仅当G所有结点的度数全为偶数且 连通 9设连通平面图G的结点数为5，边数为6，则面数为 3 10设个体域Da, b，则谓词公式(x)A(x)（$x）B（x）消去

5、量词后的等值式为 (A (a)A (b)(B（a）B（b）) 三、逻辑公式翻译（每小题6分，本题共12分） 1将语句“雪是黑色的”翻译成命题公式设P：雪是黑色的， （2分）则命题公式为：P2将语句“他不去学校”翻译成命题公式解：设P：他去学校， 则命题公式为： P 3将语句“小王是个学生，小李是个职员，而小张是个军人”翻译成命题公式设P：小王是个学生，Q：小李是个职员，R：小张是个军人 （2分）则命题公式为：PQR4将语句“如果所有人今天都去参加活动，则明天的会议取消”翻译成命题公式解：设P：所有人今天都去参加活动，Q：明天的会议取消， 则命题公式为： P Q5将语句“他去旅游，仅当他有时间”

6、翻译成命题公式解：设 P：他去旅游，Q：他有时间， 则命题公式为： P Q6将语句“41次列车下午五点开或者六点开”翻译成命题公式解：设P：41次列车下午五点开，Q：41次列车下午六点开， （2分）命题公式为：（PQ）（PQ） 7将语句“小张学习努力，小王取得好成绩”翻译成命题设P：小张学习努力，Q：小王取得好成绩， （2分）则命题公式为：PQ8将语句“有人去上课” 翻译成谓词公式 解：设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、题（每小题7分，本题共14分）判断下列各题正误，并说明理由 1设集合A=1, 2, 3, 4，B=2, 4, 6, 8，判断下列关系f是否构成函数f：，并说明理由(1) f=, , , ； (2)f=, , ；(3) f=, , , 答：（1）不构成函数 因为，但没有定义，所以不构成函数 （2）不构成函数 因为，但没有定义，所以不构成函数 （3）满足。 因为任意，都有且结果唯一。2若集合A = 1，2，3上的二元关系R=，则(1) R是自反的关系； (2) R是对称的关系答：（1）错误 因为，所以R不是自反的 （2）错误 因为，但是，所以R不是对称的 3如果R1和R2是A上的自反关系，判断结论

8、：“R-11、R1R2、R1R2是自反的” 是否成立？并说明理由 答：成立 因为任意，有所以， R-11、R1R2、R1R2是自反的ooooabcd图一ooogefho4若偏序集的哈斯图如图一所示，则集合A的最大元为a，最小元不存在 答：错误，集合A没有最大元，也没有最小元 其中a是极大元5若偏序集的哈斯图如图一所示，则集合A的最大元为a，最小元不存在 解：正确对于集合A的任意元素x，均有R（或xRa），所以a是集合A中的最大元按照最小元的定义，在集合A中不存在最小元 6如果图G是无向图，且其结点度数均为偶数，则图G存在一条欧拉回路答：错误 如果图G是无向图，且图G是连通的，同时结点度数都是偶

9、数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(PQ)P为永真式 解：正确 因为，由真值表PQPQPQP(PQ)P001111011011100111110001可知，该命题公式为永真式 五计算题（每小题12分，本题共36分）1设集合A=a, b, c，B=a, c，试计算（1）（A

10、B）； （2）（B - A）； （3）（AB）B解（1）（AB）=c； （2）（B - A）=a； （3）（AB）B=, 2设A=0，1，2，3，4，5，6，R=|xA，yA且x+y1，S=|xA，yA且x+y3，试求R，S，RS，R-1，S-1，r(R)解：R= S=, RS=, R-1= S-1= S ）r(R)=IA 3图G=，其中V= 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的邻接

11、矩阵；（3）求出G权最小的生成树及其权值解：（1）G的图形表示为： （3分）（2）邻接矩阵： （6分）（3）粗线表示最小的生成树， 权为7： 4设图G=，V= v1，v2，v3，v4，v5，E= (v1, v2)，(v1, v3)，(v2, v3)，(v2, v4)，(v3, v4)，(v3, v5)，(v4, v5) ，试(1) 画出G的图形表示；(2) 求出每个结点的度数； (3) 画出图G的补图的图形v1v2v3v4v5ooooo解：（1）关系图 （2）deg(v1)=2 deg(v2)=3 deg(v3)=4deg(v4)=3 v1v2v3v4v5ooooodeg(v5)=2 （3）补

12、图 5设集合A=1，2，3，4，R=|x, yA；|x-y|=1或x-y=0，试（1）写出R的有序对表示； （2）画出R的关系图；（3）说明R满足自反性，不满足传递性解:（1）R=, （3分）1234（2）关系图为 （3）因为,均属于R，即A的每个元素构成的有序对均在R中，故R在A上是自反的。 因有与属于R，但不属于R，所以R在A上不是传递的。6设集合A=1, 2, 3，R=, ,，S=, 试计算（1）RS； （2）R -1； （3）r（R）解： （1）RS =, ,； （4分）（2）R -1=, , ； （8分）（3）r（R）=, , , , 7、求出如图一所示赋权图中的最小生成树（要求写出

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

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

15、QR）（PQR）（PQR）（PQR ）（PQR） 主合取范式（极大项合取）：PQR12求（PQ）（RQ）的析取范式，合取范式解：（PQ）（RQ） （PQ）（RQ） （4分） (PQ)（RQ） (PRQ)(QRQ)(PRQ) 析取、合取范式 六、证明题（本题共8分）1试证明集合等式A (BC)=(AB) (AC)证明：设S=A(BC)，T=(AB)(AC)， 若xS，则xA且xBC，即 xA且xB 或 xA且xC， 也即xAB 或 xAC ，即 xT，所以ST 反之，若xT，则xAB 或 xAC， 即xA且xB 或 xA且xC 也即xA且xBC，即xS，所以TS 因此T=S 2试证明（$x）（P（x）R（x） （$x）P（x）（$x）R（x）证明： （1）（$x）（P（x）R（x） P （2）P（a）R（a） ES(1) （3）P（a） T(2)I （4）（$x）P（x） EG(3) （5）R（a） T(2)I （6）（$x）R（x） EG(5) （7）（$x）P（x）（$x）R（x） T(5)(6)I 9