2022年2022年离散数学( .pdf

《2022年2022年离散数学( .pdf》由会员分享，可在线阅读，更多相关《2022年2022年离散数学( .pdf（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、 连通且结点数比边数少1 CG 的边数比结点数少1 DG 中没有回路5下列公式( C )为重言式APQP QB(Q(P Q) (Q (P Q) C (P(QP)(P(PQ) D(P (P Q) Q 6设 A=a, b，B=1, 2，R1，R2，R3是 A 到 B 的二元关系，且R1=, ，R2=, , ，R3=, ，则（B ）不是从A 到 B 的函数AR1和 R2BR2CR3D R1和 R37设 A=1, 2, 3, 4, 5, 6, 7, 8 ，R 是 A 上的整除关系，B=2, 4, 6，则集合 B 的最大元、最小元、上界、下界依次为( B )A8、2、8、2 B无、 2、无、 2C6、2

3、、6、2 D8、 1、6、1 8若集合A 的元素个数为10，则其幂集的元素个数为（A ） A1024 B10 C100 D1 9设完全图Kn有 n 个结点 (n2)，m 条边，当（C ）时， Kn中存在欧拉回路Am 为奇数Bn 为偶数名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 9 页 - - - - - - - - - 2 Cn 为奇数Dm 为偶数10已知图 G 的邻接矩阵为，则 G 有（ D ） A5 点， 8 边B6 点， 7 边C6 点， 8 边D5 点， 7

4、边11.无向完全图K3的不同构的生成子图的个数为（C ）(A) 6 (B) 5 (C) 4 (D) 3 12 n 阶无向完全图Kn中的边数为（A ）(A) 2)1(nn(B) 2)1(nn(C) n(D) n(n+1) 13.在图 G中，结点总度数与边数的关系是( C ) A deg(vi)=2 E(B) deg(vi)=EC VvEv2)deg(DVvEv)deg(二、填空题（每小题3 分，本题共15 分）1命题公式)(PQP的真值是1 2若 A=1,2 ，R=|xA, y A, x+y4，则 R 的自反闭包为, 3已知一棵无向树T 中有 8 个结点， 4度， 3 度， 2 度的分支点各一个

5、，T 的树叶数为5 4(x)(P(x)Q(x)R(x，y)中的自由变元为R(x，y )中的 y5设集合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）消去量词后的等值式为(A (a)A (b)(B（a）B（b）)三、逻辑

6、公式翻译（每小题6 分，本题共12 分）1将语句“雪是黑色的”翻译成命题公式设 P：雪是黑色的，（2 分）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 9 页 - - - - - - - - - 3 则命题公式为：P2将语句“他不去学校”翻译成命题公式解：设 P：他去学校，则命题公式为：P3将语句 “ 小王是个学生，小李是个职员，而小张是个军人” 翻译成命题公式设 P：小王是个学生，Q：小李是个职员，R：小张是个军人（2 分）则命题公式为：PQR4将语句“如果所有人今天

7、都去参加活动，则明天的会议取消”翻译成命题公式解：设 P：所有人今天都去参加活动，Q：明天的会议取消，则命题公式为：PQ5将语句“他去旅游，仅当他有时间”翻译成命题公式解：设P：他去旅游， Q：他有时间，则命题公式为：PQ6将语句“ 41 次列车下午五点开或者六点开”翻译成命题公式解：设 P：41 次列车下午五点开，Q：41 次列车下午六点开，（2 分）命题公式为：（PQ）（PQ）7将语句“小张学习努力，小王取得好成绩”翻译成命题设 P：小张学习努力，Q：小王取得好成绩，（2 分）则命题公式为：P Q8将语句“有人去上课” 翻译成谓词公式解：设 P(x)：x 是人， Q(x)：x 去上课，（1

8、 分）( 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：BA，并说明理由(1) f=, , , ；(2)f=, , ；(3) f=, , , 答： （1）不构成函数因为3A，但3f没有定义，所以不构成函数（2）不构成函数因为4A，但4f没有定义，所以不构成函数（3）满足。因为任意xA，都有fxB且结果唯一。2若集合A =

9、1，2，3上的二元关系R= ， ，则名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 9 页 - - - - - - - - - 4 (1) R 是自反的关系；(2) R 是对称的关系答： （1）错误因为3 3R，所以 R 不是自反的（2）错误因为1 2R，但是2 1R，所以 R 不是对称的3如果 R1和 R2是 A 上的自反关系，判断结论：“ R-11、 R1R2、R1R2是自反的”是否成立？并说明理由答：成立因为任意aA，有12,a aRa aR所以1, a aR，12

10、,a aRR，12,a aRRR-11、R1R2、R1R2是自反的4若偏序集 的哈斯图如图一所示，则集合 A 的最大元为a，最小元不存在答：错误，集合A 没有最大元，也没有最小元其中 a是极大元5若偏序集 的哈斯图如图一所示，则集合A 的最大元为a，最小元不存在解：正确对于集合 A 的任意元素x，均有 R（或 xRa） ，所以 a 是集合 A 中的最大元按照最小元的定义，在集合A 中不存在最小元6如果图G 是无向图，且其结点度数均为偶数，则图G 存在一条欧拉回路 答：错误如果图 G 是无向图，且图G 是连通的，同时结点度数都是偶数7设 G 是一个连通平面图，且有6 个结点 11条边，则G 有

11、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 为永真式解：正确因为，由真值表P Q P QPQP(PQ)P0 0 1 1 1 1 a b c d 图一g e f h 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精

12、心整理 - - - - - - - 第 4 页，共 9 页 - - - - - - - - - 5 0 1 1 0 1 1 1 0 0 1 1 1 1 1 0 0 0 1 可知，该命题公式为永真式五计算题（每小题 12 分，本题共36 分）1设集合 A=a, b, c，B= a, c，试计算（1）（ A B）；（2）（ B A）；（3）（ AB）B解（ 1）（ A B）= c；（2）（ B A）= a ；（3） （A B） B= , 2设 A=0，1，2，3，4，5，6， R=|xA，y A 且 x+y1，S=|xA，y A且 x+y 3，试求 R，S， R S，R-1，S-1， r(R)解：

13、 R= S=, R S=, R-1= S-1= S）r(R)=IA3图 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 的邻接矩阵；（3）求出 G 权最小的生成树及其权值解：（ 1）G 的图形表示为：（3 分）（2）邻接矩阵：0111110110110011100110110（6 分）（3）粗线表示最小的生成树，名师资料总结 - - -精品资料欢迎下载 - - - -

14、 - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 9 页 - - - - - - - - - 6 权为 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 的补图的图形解： （1）关系图（2）deg(v1)=2 deg(v2)=3 deg(v3)=4 deg(v4)=3 deg(v5)=2 （3）补图5设集合A=

15、1，2，3，4，R=|x, y A；|x y|=1 或 x y=0，试（1）写出 R 的有序对表示；（2）画出 R 的关系图；（3）说明 R 满足自反性，不满足传递性解:（1）R=, （3 分）（2）关系图为（3）因为 , 均属于 R，即 A的每个元素构成的有序对均在R 中，故 R 在 A 上是自反的。因有 与属于 R，但 不属于 R，所以 R 在 A 上不是传递的。12 3 4 v1 v2 v3 v4 v5 v1 v2 v3 v4 v5 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - -

16、第 6 页，共 9 页 - - - - - - - - - 7 6设集合A=1, 2, 3，R=, ,，S=, 试计算（1） R S；（2）R 1；（3）r（R）解： （ 1）R S =, ,；（4 分）（2）R 1=, , ；（8 分）（3）r（R）=, , , , 7、求出如图一所示赋权图中的最小生成树（要求写出求解步骤），并求此最小生成树的权解 用 Kruskal 算法求产生的最小生成树步骤为：1),(71vvw选711vve3),(43vvw选432vve4),(72vvw选723vve9),(73vvw选734vve18),(54vvw选545vve22),(61vvw选616vve

17、（6 分）最小生成树如图四所示：（9 分）图四最小生成树的权为：w(T)=22+1+4+9+3+18=57 （12 分）8试画一棵带权为2, 3, 3, 4, 5,的最优二叉树 , 并计算该最优二叉树的权解：最优二叉树 如图二所示（ 10 分）图二2 3 3 4 5 5 10 7 17 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 9 页 - - - - - - - - - 8 权为 2 3+3 3+3 2+4 2+5 2=39 9设谓词公式),(),(),(zyyCz

18、yxzByxAx，试（1）写出量词的辖域；（2）指出该公式的自由变元和约束变元（1） x 量词的辖域为),(),(zyxzByxA，（ 2 分）z 量词的辖域为),(zyxB, （4 分）y 量词的辖域为),(zyC（6 分）（2）自由变元为),(),(zyxzByxA中的 y，以及),(zyC中的 z（9 分）约束变元为),(),(zyxzByxA中的 x 与( , )B x y z中的 z，以及( , )C y z中的 y10设谓词公式),()(),()(zyxQzyxPx，试（1）写出量词的辖域；（2）指出该公式的自由变元和约束变元（1） x 量词的辖域为),(yxP，（3 分）z 量词

19、的辖域为),(zyxQ, （6 分）（ 2）自由变元为公式中的y 与),(zyxQ中的 x，（9 分）约束变元为),(yxP的 x 与),(zyxQz11求命题公式 (P Q)(R Q) 的主析取范式、主合取范式解：P Q R P QR Q(PQ)(R Q) 极小项极大项0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 PQR PQ R P QR P Q R PQ R P QR P Q R P Q R 主析取范式（极小项析取）：（PQR）（PQ R）（P

20、 QR）（P Q R）（PQ R）（P QR ）（P Q R）主合取范式（极大项合取）：P Q R 12求（ PQ）（ RQ）的析取范式，合取范式解： （PQ）（ RQ）（PQ）（ RQ）（4 分）(PQ)（ RQ）(P RQ)(QRQ) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 9 页 - - - - - - - - - 9 (PRQ) 析取、合取范式六、证明题（本题共 8 分）1试证明集合等式A (BC)=(AB) (AC)证明：设 S=A (BC)，T=(A

21、B)(AC)， 若 xS，则 xA 且 xBC，即xA且 xB 或 xA 且 xC，也即 xAB 或 xAC ，即xT，所以 ST反之，若 xT，则 xAB 或 xAC，即 xA 且 xB 或 xA 且 xC也即 xA 且 xBC，即 xS ，所以 TS 因此 T=S2试证明（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 页，共 9 页 - - - - - - - - -