离散数学(本科)(

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

2、少1C G 的边数比结点数少 1D G 中没有回路5下列公式(C)为重言式A PQPQB(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=< a，2>, <b，2> ，R2=< a， 1>, <a， 2>, <b， 1> ， R3=< a， 1>, <b， 2> ，则（B）不是从 A 到 B 的函数AR1和 R2B R2C R3DR1和 R37设 A=1, 2, 3, 4, 5, 6, 7,

3、8 ， R 是 A 上的整除关系， B=2, 4, 6 ，则集合 B 的最大元、最小元、上界、下界依次为( B)A8、2、8、2B 无、 2、无、 2C6、 2、 6、2D8、 1、6、18若集合 A 的元素个数为10，则其幂集的元素个数为（A）A 1024B 10C100D 19设完全图 K n 有 n 个结点 (n2)， m 条边，当（C）时， K n 中存在欧拉回路A m 为奇数B n 为偶数C n 为奇数D m 为偶数10已知图G 的邻接矩阵为，则G有（ D）A5点，8边B6点，7边C6点，8边D5点，7边11.无向完全图K3 的不同构的生成子图的个数为（C）(A) 6(B) 5(C)

4、 4(D) 312 n 阶无向完全图 Kn 中的边数为（A ）n(n1)n(n1)(C) n(D) n(n+1)(A)(B)2213.在图 G <V ,E>中，结点总度数与边数的关系是(C)Adeg(vi)=2E(B) deg( vi )=ECdeg(v)2 EDdeg(v)Ev Vv V二、填空题（每小题3 分，本题共 15 分）1命题公式 P(QP) 的真值是12 若 A=1,2 ， R=< x, y>|xA, yA, x+y<4 ，则 R 的自反闭包为<1,1>,<2,2>,<1,2>,<2,1>3已知一棵无向

5、树 T 中有 8 个结点， 4 度， 3 度， 2 度的分支点各一个，T 的树叶数为54 ( x)( P( x)Q(x) R(x， y)中的自由变元为R(x，y )中的 y5设集合 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，则面数为310设个体域D a, b ，则谓词公

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

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

8、式解：设 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： A B ，并说明理由(1) f=<1, 4>, <2, 2,>, <4, 6>, <1, 8> ；(2)f=<1, 6>, <3, 4>, <2, 2> ；(3) f=<1, 8>, <2, 6>, <3, 4>,

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

10、R、 R 是自反的”是1121 R2否成立？并说明理由答：成立因为任意 aA ，有 a, aR1 , a, aR2所以 a, a R 1， a, aR1R2 ， a, aR1R2R11、 R1 R2、R1R2 是自反的-a4若偏序集 <A，R>的哈斯图如图一所示，bcg则集合 A 的最大元为 a，最小元不存在答：错误，集合A 没有最大元，也没有最小元其中 a 是极大元dhef图一5若偏序集 <A， R>的哈斯图如图一所示，则集合A 的最大元为a，最小元不存在解：正确对于集合 A 的任意元素x，均有 <x, a>R（或 xRa），所以 a 是集合 A 中的最大

11、元按照最小元的定义，在集合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

12、 (PQ)P 为永真式解：正确因为，由真值表PQPQPQP (P Q)P001111011011100111110001可知，该命题公式为永真式五计算题 （每小题 12 分，本题共36 分）1设集合A=a, b, c， B= a, c，试计算（ 1）（ AB）；（ 2）（ BA）；解（ 1）（ AB）= c ；（ 3）（ AB） ×B（ 2）（ B A） = a ；（ 3）（AB） ×B= < c， a>, < c，c >2设 A=0 ， 1， 2， 3，4，5，6， R=< x， y>|xA，y A 且 x+y<1 ， S=<

13、; x， y>|xA， 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>RS=<0,0>,<0,1>,<0,2>,<0,3>R-1=<0,0>-1）S = Sr(R)=I A3图 G=<V , E>，其中 V= a,

14、 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）邻接矩阵：011011001110011（6分）0110111110（ 3）粗线表示最小的生成树，权为 7：4设图 G=<V， E >， V= v1， v2， v3， v4， v5 ， E= ( v1 , v2

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

16、性，不满足传递性解 :（ 1）R=<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<2,1>,<2,3>,<3,2>,<3,4>,<4,3>（3 分）（ 2）关系图为2134（ 3）因为 <1,1>,<2,2>,<3,3>,<4,4> 均属于 R，即 A 的每个元素构成的有序对均在R 中，故 R 在 A 上是自反的。因有 <2,3> 与 <3,4>属于 R，但 <2,4> 不属于

17、R，所以 R 在 A 上不是传递的。6设集合A=1, 2, 3 ， R=<1 ， 1>, <2， 1>,<3 ， 1> ， S=<1 ， 2>, <2 ， 2>试计算（1） R S；（2）R 1；（ 3） r（ R）解： （ 1）RS =<1 ，2>, <2 ， 2>,<3 ， 2> ；（4 分）（2） R1=<1 ， 1>, <1， 2>, <1， 3> ；（8 分）（ 3） r （R） =<1 ， 1>, <2， 2> , <3，

18、 3>, <2， 1>,<3 ， 1>7、求出如图一所示赋权图中的最小生成树（要求写出求解步骤），并求此最小生成树的权解 用 Kruskal 算法求产生的最小生成树步骤为：w(v1 , v7 )1选 e1v1v7w(v3 , v4 ) 3选 e2v3v4w(v2 , v7 ) 4选 e3v2v7w(v3 , v7 ) 9选 e4v3v7w(v4 , v5 ) 18选 e5v4 v5w(v1 , v6 ) 22选 e6v1v6最小生成树如图四所示：图四最小生成树的权为：w(T)=22+1+4+9+3+18=57 8试画一棵带权为 2, 3, 3, 4, 5,的最优二

19、叉树 , 并计算该最优二叉树的权解：最优二叉树 如图二所示171075534（6 分）（ 9 分）（ 12 分）（10分）图二权为23+33+32+42+52=399设谓词公式x( A( x, y)zB( x, y, z)yC( y, z) ，试（ 1）写出量词的辖域；（ 2）指出该公式的自由变元和约束变元（ 1）x 量词的辖域为 ( A( x, y)zB( x, y, z) ，（2 分）z 量词的辖域为 B( x, y, z) ,（4 分）y 量词的辖域为 C ( y, z) （6 分）（ 2）自由变元为 (A(x, y)zB( x, y, z) 中的 y，以及 C ( y, z) 中的 z（9 分）约束变元为 ( A(x, y)zB( x, y, z) 中的 x 与 B( x, y, z) 中的 z，以及 C ( y, z) 中的 y10设谓词公式 ( x)P( x, y)(z)Q ( x, y, z) ，试（ 1）写出量词的辖域；（ 2）指出该公式的自由变元和约束变元（ 1）x 量词的辖域为 P( x, y) ，（3分）z 量词的辖域为 Q ( x, y, z) ,（6 分）（2）自由变元为公式中的y 与 Q( x, y, z) 中的 x，（9 分）约束变元为P( x, y) 的 x 与 Q( x, y, z) z11求命题公式(PQ)(RQ)