《离散数学复习题》由会员分享,可在线阅读,更多相关《离散数学复习题(11页珍藏版)》请在金锄头文库上搜索。
1、. .离散数学复习题一、单项选择题1.以下命题公式为重言式的是【 A 】。Ap (pq)B(pp)qCqqDpq2以下语句中不是命题的是【 A 】。A这个语句是假的。B1+1=1.0C飞碟来自地球外的星球。D凡石头都可练成金。3设A=,1,1,3,1,2,3,那么A上包含关系“的哈斯图为【 C 】4在公式中变元y是【 B 】。A自由变元B约束变元C既是自由变元,又是约束变元D既不是自由变元,又不是约束变元5设A=1,2,3,A上二元关系S=,那么S是【 D 】。A自反关系B反自反关系C对称关系D传递关系6图 中 从v1到v3长度为3 的通路有【 D 】条。 A0; B1; C2; D3。7在以
2、下代数系统中,不是环的只有【 C 】。AZ,+,*),其中Z为整数集,+,*分别为整数加法和乘法。B(Q,+,*),其中Q为有理数集,+,*分别为有理数加法和乘法。C,其中R为实数集,+为实数加法,a*b=a+2b。D,其中Mn(R)为实数集nn阶矩阵结合,+,*是矩阵加法和乘法。8以下整数集对于整除关系都构成偏序集,而能构成格的是【 B 】。Al,2,3,4,5B1,2,3,6,12C2,3,7Dl,2,3,79结点数为奇数且所有结点的度数也为奇数的连通图必定是【 D 】。A欧拉图B汉密尔顿图C非平面图D不存在的10无向图G是欧拉图当且仅当G是连通的且【 C 】。AG中各顶点的度数均相等BG
3、中各顶点的度数之和为偶数CG中各顶点的度数均为偶数DG中各顶点的度数均为奇数11.设S=0,1,*为普通乘法,那么是【 B 】。 A.半群,但不是独异点; B.只是独异点,但不是群; C.群 ; D.环,但不是群;12设A,+,是代数系统,其中+,是普通的加法和乘法运算,能使A,+,成为环的集合A是【 A 】。A所有偶数组成的集合; B所有奇数组成的集合; C所有正整数组成的集合; D所有非负整数组成的集合。13设A=1,2,3,那么A上的二元关系有【 C 】个。 A 23 ;B 32 ;C ; D 。14在【A】下有。A; B、C、; D、15以下结果正确的选项是【 B 】。A; B;C;
4、D。 16设p:我很累,q:我去学习,命题:“除非我很累,否那么我就去学习的符号化正确的选项是【 B 】。ApqBpqCpqDpq 17以下函数是双射的为【 A 】Af : IE , f (x)=2x ; Bf : NNN, f (n)= ;Cf : RI , f (x)=x ;Df :IN, f (x) = | x |。注:I整数集,E偶数集, N自然数集,R实数集18有向图中D= ,那么长度为2的通路有【 D 】条。A0; B1; C2; D3 。19在一棵树中有7片树叶,3个度为3的结点,其余都是度为4的结点,那么该树有【 A 】个度为4的结点。A1; B2; C3; D4 。20以下图
5、中既不是Eular图,也不是Hamilton图的图是【 B 】二、填空题请在每题的空格中填上正确答案。错填、不填均无分。1.命题逻辑与谓词逻辑的区别是。2.谓词逻辑中,命题被分解为_, _两局部。3.集合的常用表示方法有_, _, _和图示法四种。4.具有_, _和_ 三种性质的二元关系叫等价关系。5.n阶有向完全图的边数为_, n阶无向完全图的边数为_。6.如果一个图的每条边都是_称为有向图,每条边都是称为无向图。7.假设图中存在_的通路, 该图称为半欧拉图。8.有向图树T中,_称为根,_称为树叶。9.设R是A上的二元关系,当有a,bR和b,cR时,必有 ,那么称R为可传递的二元关系。abc
6、a b cb b cc c b10.设代数系统,其中A=a,b,c,那么幺元是 ;是否有幂等性 ;是否有对称性。 11.能够判断_称为命题。 12.不包含任何联结词的命题叫做_命题, 至少包含一个联结词的命题叫做_命题。 13.二元关系的表示方法有_, _, _ 三种。 14.1A,B,C表示三个集合,文图中阴影局部的集合表达式为 A B C 。2设P,Q 的真值为0,R,S的真值为1,那么的真值= 。3公式的主合取X式为。 15.,*表示求两数的最小公倍数的运算Z表示整数集合,对于*运算的幺元是 ,零元是 。 16.将有向图D各边的方向去掉得无向图G, 称G为D的_。 17.假设图中存在_回
7、路, 该图称为欧拉图。 18.拉格朗日定理说明假设是群的子群,那么可建立G中的等价关系R= 。假设|G|=n, |H|=m 那么m和n关系为 。19根据入射函数,满射函数,双射函数的定义填空。设N是自然数集合,Z是整数集合,R是实数集合,那么f1NN, f1n= n2是函数;f2NN, f2n= n + 10是函数;f3ZZ, f3z= z + 10是函数;f4RR, f4r= r +5.6是函数;f5Z0,1,当z为偶数时,f5(z)=1;当z为奇数时,f5(z)=0。是函数。填空题参考答案:1.在命题逻辑中,原子命题是进展演算的根本单位,不再研究命题的内部构造。而谓词逻辑的任务就是对原子命
8、题作进一步的分析,研究其内部的逻辑构造。2.个体词和谓词两局部。 3.列举法、表达法、特定字母集和图表法。4自反性、对称性和传递性 5. n2和n(n-1)/26有向边和无向边7一条通过图中各边一次且仅一次的通路。8入度为零的顶点称为根,出度为零的顶点称为叶子。9a,cR 10.a、 否、 有 11能够判断内容真假的语句称为命题。12原子和复合。 13表格法、矩阵法和图表法。 14.(1);(2)1;(3) 15不存在、e 16.底图 17一条通过图中各边一次且仅一次的回路。 18、 19入射、入射、双射、双射、满射。三、判断说明题判断以下各题正误,正确的在题后括号内打“,错误的打“,并说明其
9、正确或错误的理由。一 判断以下语句那些是命题1我是工程师。 【 】2计算机有空吗? 【 】36是奇数。 【 】4太美妙了! 【 】5.雪是白的。 【 】6.我是大学生 【 】7.雪是黑的。 【 】8.外星人是存在的。 【 】9.请翻开门! 【 】10.这束花多么好看啊! 【 】二以下函数中15小题,哪些是单射函数,满射函数,双射函数。其中N是自然数集合,I是整数集合,R是实数集合。集合A =a, b, c,集合B =1, 2, 3, 以下AB的二元关系中,R1R5哪些可以构成函数。1f:NN, fn= 2n【单射 】2f:AB,A=0,1,2,B=0,1,2,3,4,f(a)=a2 【单射 】
10、3f:II, fi= i + 10【双射】4f: II, f(i)=|i|【既不是单射,也不是满射】 5.f: I0,1,当I为偶数时,f(i)=0;当I为奇数时,f(i)=1。 【满射】 6.R1= a, 1,b, 2,c, 3 【 】 7.R2= a, 3,c, 2,c, 1 【 】 8.R3= a, 2,b, 1,b, 2,c, 3 【 】 9.R4= b, 1,c, 3 【 】 10.R5= a, 1,b, 1,c, 3 【 】 四、表述题:将以下命题符号化(一) 命题逻辑符号化1.我美丽而又快乐。2.如果老X和老李都不去,他就去。3.电灯不亮,当且仅当灯泡或开关发生故障。 4.王强工作努力且身体好。 5.我