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

离散数学复习资料 一、单项选择题（每小题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 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)，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，则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）消去量词后的等值式为 (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将语句“他去旅游，仅当他有时间”翻译成命题公式解：设 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分，本题共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上的自反关系，判断结论：“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是连通的，同时结点度数都是偶数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）（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+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的邻接矩阵；（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）补图 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、求出如图一所示赋权图中的最小生成树（要求写出求解步骤），并求此最小生成树的权解 用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）自由变元为中的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）（pqr）（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，