《电大离散数学本科期末复习题》由会员分享，可在线阅读，更多相关《电大离散数学本科期末复习题（58页珍藏版）》请在金锄头文库上搜索。
1、资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。离散数学( 本) 一、 单项选择题1设P: a是偶数, Q: b是偶数。R: a + b是偶数, 则命题”若a是偶数, b是偶数, 则a + b 也是偶数”符号化为( D P QR) 。2表示式x( P( x, y) Q( z) ) y( Q( x, y) zQ( z) ) 中x的辖域是( P( x, y) Q( z) ) 。3设则命题为假的是( ) 。4设G是有n个结点的无向完全图, 则G的边数( 1/2 n( n-1) ) 。5设G是连通平面图, 有v个结点, e条边, r个面, 则r=( e-v+2) 。6若集合A=1, 2,
2、 1, 2, 则下列表述正确的是( 1A )7已知一棵无向树T中有8个顶点, 4度、 3度、 2度的分支点各一个, T的树叶数为( 5 )8设无向图G的邻接矩阵为则G的边数为( 7 )9设集合A=a, 则A的幂集为(, a )10下列公式中 (AB (AB) )为永真式11若G是一个汉密尔顿图, 则G一定是( 连通图 )12集合A=1, 2, 3, 4上的关系R=|x=y且x, yA, 则R的性质为( 传递的 ) 13设集合A=1, 2, 3, 4, 5, 偏序关系是A上的整除关系, 则偏序集上的元素5是集合A的( 极大元 ) 14图G如图一所示, 以下说法正确的是 ( (a, d) ,(b,
3、 d)是边割集 ) 图一15设A( x) : x是人, B( x) : x是工人, 则命题”有人是工人”可符号化为( (x)(A(x)B(x) ) 16若集合A=1, 2, B=1, 2, 1, 2, 则下列表述正确的是(AB, 且AB )17设有向图( a) 、 ( b) 、 ( c) 与( d) 如图一所示, 则下列结论成立的是 ( ( d) 是强连通的 )18设图G的邻接矩阵为则G的边数为( 5 )19无向简单图G是棵树, 当且仅当(G连通且边数比结点数少1 )20下列公式 (P(QP)(P(PQ) )为重言式21若集合A a, a, 1, 2, 则下列表述正确的是(aA)22设图G,
4、vV, 则下列结论成立的是 ( ) 23命题公式( PQ) R的析取范式是 ( PQ) R )24下列等价公式成立的为(P(QP) P(PQ) )25设A=a, b, B=1, 2, R1, R2, R3是A到B的二元关系, 且R1=, , R2=, , , R3=, , 则( R2 ) 不是从A到B的函数26设A=1, 2, 3, 4, 5, 6, 7, 8, R是A上的整除关系, B=2, 4, 6, 则集合B的最大元、 最小元、 上界、 下界依次为 (无、 2、 无、 2)27若集合A的元素个数为10, 则其幂集的元素个数为( 1024) 28如图一所示, 以下说法正确的是 (e是割点)
5、图一29设完全图K有n个结点(n2), m条边, 当( n为奇数) 时, K中存在欧拉回路 30已知图G的邻接矩阵为 , 则G有( 5点, 7边 ) 二、 填空题( 每小题3分, 共15分) 1设A, B为任意命题公式, C为重言式, 若A CBC, 那么AB是 重言 式( 重言式、 矛盾式或可满足式) 。2命题公式( PQ) P的主合取范式为 。3设集合A=, a, 则P( A) = 。4设图G =V, E, G =V, E, 若 V=V,E E ,则G是G的生成子图。5在平面G =V, E中, 则= 2|E| , 其中( i=1, 2, , r) 是G的面。6命题公式的真值是 假( 或F,
6、 或0) 7若无向树T有5个结点, 则T的边数为 4 8设正则m叉树的树叶数为t, 分支数为i, 则(m-1)i= t-1 9设集合A=1, 2上的关系R, 则在R中仅需加一个元素 , 就可使新得到的关系为对称的10(x)(A(x)B(x, z)C(y)中的自由变元有 z, y 11若集合A=1, 3, 5, 7, B=2, 4, 6, 8, 则AB= 空集( 或) 12设集合A=1, 2, 3上的函数分别为: f=, g=, 则复合函数gf = , , , 13设G是一个图, 结点集合为V, 边集合为E, 则G的结点度数之和为 2|E|( 或”边数的两倍”) 14无向连通图G的结点数为v,
7、边数为e, 则G当v与e满足 e=v-1 关系时是树 15设个体域D1, 2, 3, P(x)为”x小于2”, 则谓词公式(x)P(x) 的真值为 假( 或F, 或0) 16命题公式的真值是 T ( 或1) 17若图G=中具有一条汉密尔顿回路, 则对于结点集V的每个非空子集S, 在G中删除S中的所有结点得到的连通分支数为W, 则S中结点数|S|与W满足的关系式为 W|S| 18给定一个序列集合000, 001, 01, 10, 0, 若去掉其中的元素 0 , 则该序列集合构成前缀码19已知一棵无向树T中有8个结点, 4度, 3度, 2度的分支点各一个, T的树叶数为 5 20(x)(P(x)Q
8、(x)R(x, y)中的自由变元为 R(x, y )中的y 21设集合A=0, 1, 2, 3, B=2, 3, 4, 5, R是A到B的二元关系, 则R的有序对集合为 , , , 22设G是连通平面图, v, e, r分别表示G的结点数, 边数和面数, 则v, e和r满足的关系式 v-e+r=2 23设G是有6个结点, 8条边的连通图, 则从G中删去 3 条边, 能够确定图G的一棵生成树24无向图G存在欧拉回路, 当且仅当G连通且 所有结点的度数全为偶数 25设个体域D1,2, 则谓词公式消去量词后的等值式为 A(1)A(2) 26设集合Aa, b, 那么集合A的幂集是 ,a,b,a,b 2
9、7如果R1和R2是A上的自反关系, 则R1R2, R1R2, R1-R2中自反关系有 2 个 28设图G是有6个结点的连通图, 结点的总度数为18, 则可从G中删去 4 条边后使之变成树29设连通平面图G的结点数为5, 边数为6, 则面数为 3 30设个体域Da, b, 则谓词公式(x)A(x)( $x) B( x) 消去量词后的等值式为 (A (a)A (b)(B( a) B( b) ) 31. 设集合A=0, 1 , 2 , B=l , 2 , 3 , 剖, R 是A到B 的二元关系, R= |xA且yB且x, yAB 则R的有序对集合为_,_32. 设G是连通平面图, v, e , r
10、分别表示G的结点数, 边数和面数, 则 v, e 和r 满足的关系式_v-e+r=2_33.G=是有20个结点, 25 条边的连通图,则从G中删去_6_条边, 能够确定图G的一棵生成树.34. 无向图G存在欧拉回路, 当且仅当G所有结点的度数全为偶数且_ 连通_35. 设个体域D= 1, 2 , 则谓词公式 xA(x)消去量词后的等值式为_A(1)A(2)_三、 化简解答题11设集合A=1, 2, 3, 4, A上的二元关系R, R=1, 1, 1, 4, 2, 2, 2, 3, 3, 2, 3, 3, 4, 1, 4, 4, 说明R是A上的等价关系。解 从R的表示式知, 即R具有自反性; 三
11、、 逻辑公式翻译1将语句”今天上课”翻译成命题公式设P: 今天上课, 则命题公式为: P 2将语句”她去操场锻炼, 仅当她有时间”翻译成命题公式设 P: 她去操场锻炼, Q: 她有时间, 则命题公式为: P Q3将语句”她是学生”翻译成命题公式设P: 她是学生, 则命题公式为: P 4将语句”如果明天不下雨, 我们就去郊游”翻译成命题公式设P: 明天下雨, Q: 我们就去郊游, 则命题公式为: P Q 5将语句”她不去学校”翻译成命题公式设P: 她去学校, P 6将语句”她去旅游, 仅当她有时间”翻译成命题公式设 P: 她去旅游, Q: 她有时间, P Q 7将语句”所有的人都学习努力”翻译成
12、命题公式设P(x): x是人, Q(x): x学习努力, ( x) (P(x)Q(x)8将语句”如果你去了, 那么她就不去”翻译成命题公式设P: 你去, Q: 她去, PQ 9将语句”小王去旅游, 小李也去旅游”翻译成命题公式设P: 小王去旅游, Q: 小李去旅游, PQ 10将语句”所有人都去工作”翻译成谓词公式设P(x): x是人, Q(x): x去工作, (x)(P(x)Q(x) 11将语句”如果所有人今天都去参加活动, 则明天的会议取消”翻译成命题公式 设P: 所有人今天都去参加活动, Q: 明天的会议取消, P Q 12将语句”今天没有人来” 翻译成命题公式设 P: 今天有人来, P13将语句”有人去上课” 翻译成谓词公式设P(x): x是人, Q(x): x去上课, ($x)(P(x) Q(x)1 1. 将语句如果小李学习努力, 那么她就会取得好成绩. 翻译成命题公式. 设P: 小李学习努力, Q:小李会取得好成绩, PQ12. 将语句小张学习努力,小王取得好成绩. 翻译成命题公式.设P: 小张学习努力, Q:小王取得好成绩, PQ四、 判断说明题1设集合A=1, 2, B=3, 4, 从A到B的关系为f=1
