(电大复习)本科离散数学共享资料

1 离散数学复习资料 2014 年 6 月 一、单项选择题（每小题 3 分，本题共 15 分） 1若集合 A=1， 2， B=1， 2， 1， 2，则下列表述正确的是 ( A ) A AB，且 AB B BA，且 AB C AB，且 AB D AB，且 AB 2设有向图（ a）、（ b）、（ c）与（ d）如 图一所示 ， 则下列结论成立的是 ( D ) 图一 A （ a） 是强连通的 B（ b） 是强连通的 C（ c） 是强连通的 D（ d） 是强连通的 3设图 G 的邻 接 矩阵为 0101010010000011100100110则 G 的边数为 ( B ) A 6 B 5 C 4 D 3 4无向简单图 G 是棵树，当且仅当 ( A ) A G 连通且边数比 结点 数少 1 B G 连通且 结点 数 比 边数少 1 C G 的边数比 结点 数少 1 D G 中没 有回路 5下列公式 ( C )为重言式 A PQPQ B (Q(PQ) (Q(PQ) C (P(QP)(P(PQ) D (P(PQ) Q 6设 A=a, b， B=1, 2， R1， R2， R3是 A 到 B 的二元关系，且 R1=, ，R2=, , ， R3=, ，则（ B ）不是从 A 到 B 的函数 A R1 和 R2 B R2 C R3 D R1 和 R3 7设 A=1, 2, 3, 4, 5, 6, 7, 8， R 是 A 上的整除关系， B=2, 4, 6，则集合 B 的最大元、最小元、上界、下界依次为 ( B ) A 8、 2、 8、 2 B无、 2、无、 2 C 6、 2、 6、 2 D 8、 1、 6、 1 8若集合 A 的元素个数为 10，则其幂集的元素个数为（ A ） A 1024 B 10 C 100 D 1 9设完全图 Kn有 n 个结点 (n 2)， m 条边，当（ C ）时， Kn中存在欧拉回路 A m 为奇数 B n 为偶数 2 C n 为奇数 D m 为偶数 10已知图 G 的邻接矩阵为 ， 则 G 有（ D ） A 5 点， 8 边 B 6 点， 7 边 C 6 点， 8 边 D 5 点， 7 边 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)=2E (B) deg(vi)=E C VvEv 2)deg( DVvEv )deg( 二、填空题（每小题 3 分，本题共 15 分） 1命题公式 )( PQP 的真值是 1 2 若 A=1,2， R=|xA, yA, x+y, 3已知一棵无向树 T 中有 8 个 结点 ， 4 度， 3 度 ， 2 度的分支点各一个， T 的树叶数为 5 4 (x)(P(x) Q(x) R(x， y)中的 自由 变元 为 R(x， y )中的 y 5设集合 A a， b， 那么集合 A 的幂集是 ,a,b,a,b 6如果 R1和 R2是 A上的自反关系，则 R1 R2， R1 R2， R1-R2中自反关系有 2 个 7设图 G 是有 6 个结点的连通图，结点的总度数为 18，则可从 G 中删去 4 条边后使之变成树 8无向图 G 存 在欧拉回路，当且仅当 G 所有结点的度数全为偶数且 连通 9 设连通平面图 G 的结点数为 5，边数为 6，则面数为 3 10设个体域 D a, b，则谓词公式 (x)A(x)（ x） B（ x） 消去量词后的等值式为 (A (a) A (b) (B（ a） B（ b） ) 三、逻辑公式翻译 （ 每小题 6 分， 本题共 12 分） 1将 语句“雪是黑色的 ”翻译成命题公式 设 P：雪是黑色的， （ 2 分） 3 则命题公式为： P 2 将 语句“ 他不去学校 ”翻译成命题公式 解：设 P：他去学校， 则命题公式为： P 3 将 语句 “小王是个学生，小李是个职员，而小张是个军人 ”翻译成命题公式 设 P：小王是个学生， Q：小李是个职员， R：小张是个军人 （ 2 分） 则命题公式为： P Q R 4 将 语句“如果所有人今天都去参加活动，则明天的会议取消 ”翻译成命题公式 解：设 P：所有人今天都去参加活动， Q：明天的会议取消， 则命题公式为： P Q 5 将 语句“ 他去旅游，仅当他有时间 ”翻译成命题公式 解：设 P：他去旅游， Q：他有时间， 则命题公式为： P Q 6 将 语句“ 41 次列车下午五点开或者六点开 ”翻译成命题公式 解： 设 P： 41 次列车下午五点开， Q： 41 次列车下午六点开， （ 2 分） 命题公式为：（ P Q） （ P Q） 7 将 语句“小张学习努力，小王取得好成绩 ”翻译成命题 设 P：小张学习努力， Q：小王取得好成绩， （ 2 分） 则命题公式为： PQ 8 将 语句“有人去上课 ” 翻译成谓词公式 解： 设 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： BA ，并说明理由 (1) f=, , , ； (2)f=, , ； (3) f=, , , 答 ：（ 1）不构成函数 因为 3 A ，但 3f 没有定义，所以不构成函数 （ 2）不构成函数 因为 4 A ，但 4f 没有定义，所以不构成函数 （ 3）满足。 因为任意 xA ，都有 f x B 且结果唯一。 2 若 集合 A = 1， 2， 3上的 二元关系 R=， ， ，则 4 (1) R 是自反的关系； (2) R 是对称的关系 答 ：（ 1）错误 因为 3 3 R， ，所以 R 不是自 反的 （ 2） 错误 因为 1 2 R， ，但是 2 1 R， ，所以 R 不是对称的 3如果 R1和 R2是 A 上的自反关系，判断结论：“ R- 11、 R1 R2、 R1R2 是自反的” 是否成立？并说明理由 答 ：成立 因为任意 aA ，有12, , ,a a R a a R所以 1,a a R ，12,a a R R U，12,a a R R IR-11、 R1 R2、 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 有 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 条边的连通简单平面图，若 v 3，则 e 3v-6” 9命题公式 P(PQ)P 为永真式 解 ： 正确 因为，由真值表 P Q P Q PQ P (P Q) P 0 0 1 1 1 1 a b c d 图一 g e f h 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）（ AB）； （ 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+y|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 的邻接矩阵 ； （ 3） 求出 G 权最小的生成树 及其权值 解： （ 1） G 的图形表示为： （ 3 分） （ 2）邻接矩阵： 0111110110110011100110110（ 6 分） （ 3）粗线 表示最小的生成树， 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=1， 2， 3， 4， R=|x, yA； |xy|=1 或 xy=0， 试 （ 1）写出 R 的有序对表示； （ 2）画出 R 的关系图； （ 3）说明 R 满足自反性，不满足传递性 解 :（ 1） R=, （ 3 分） （ 2）关系图为 （ 3）因为 ,均属于 R，即 A 的每个元素构成的有序对均在 R 中，故 R 在 A 上是自反的。 因有 与 属于 R，但 不属于 R，所以 R 在 A 上不是传递的。 1 2 3 4 v1 v2 v3 v4 v5 v1 v2 v3 v4 v5 7 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、 求出如 图一 所示赋权图中的最小生成树（要求写出求解步骤），并求此最小生成树的权 解 用 Kruskal 算法求产生的最小生成树 步骤为： 1),(71 vvw选711 vve 3),(43 vvw选432 vve 4),(72 vvw选723 vve 9),(73 vvw选734 vve 18),(54 vvw选545 vve 22),(61 vvw选616 vve （ 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 8 权为 23+33+32+42+52=39 9设谓词公式 ),(),(),( zyyCzyxzByxAx ，试 （ 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 中的 y 10设谓词公式 ),()(),()( zyxQzyxPx ，试 （ 1）写出量词的辖域； （ 2）指出该公式的自 由变元和约束变元 （ 1） x 量词的辖域为 ),( yxP ， （ 3 分） z 量词的辖域为 ),( zyxQ , （ 6 分） （ 2）自由变元为公式中的 y 与 ),( zyxQ 中的 x， （ 9 分） 约束变元为 ),( yxP 的 x 与 ),( zyxQ z 11求命题公式 (PQ)(RQ) 的主析取范式、主合取范式 解： P Q R PQ RQ (PQ)(RQ) 极小项 极大项 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 PQR PQR PQR PQR PQR PQR PQR 主析取范式（极小项析取）：