离散数学期末练习题-(带答案)

1、离散数学复习注意事项：1、第一遍复习一定要认真按考试大纲要求将本学期所学习内容系统复习一遍。2、第二遍复习按照考试大纲的要求对第一遍复习进行总结。把大纲中指定的例题及书后习题认真做一做。检验一下主要内容的掌握情况。3、第三遍复习把随后发去的练习题认真做一做，检验一下第一遍与第二遍复习 情况，要认真理解，注意做题思路与方法。离散数学综合练习题、选择题1 .下列句子中，()是命题。A. 2是常数。B.这朵花多好看呀!C.请把门关上！D.下午有会吗？2 .令p:今天下雪了，q:路滑，r:他迟到了则命题下雪路滑，他迟到了可符号化为(A. p q rC. p q r3 .令p:今天下雪了,B.D.q：路

2、滑，则命题 虽然今天下雪了，但是路不滑”可符号化为(A. pC. P4 .设P(x): x是鸟,A.( x)(P(x)C.( x)(P(x)5 .设P(x):x是整数,Q(x):x会飞，命题Q(x)Q(x)f (x): x的绝对值,的绝对值大于等于0”可符号化为(A.C.x(P(x) L(f(x),0) xP(x) L(f(x),0)6 .设F(x):x是人，G(x):x犯错误，命题A.C.x(F(x) G(x)x(F(x) G(x)7 .下列命题公式不是永真式的是(A. (pq)pc. p (qp)b. p qd. p q宥的鸟不会飞”可符号化为(B.D.(x)(P(x) A Q(x) (x

3、)(P(x) AQ(x)L(x, y)。y ;命题所有整数B. x(P(x) L(f(x),0)D. xP(x) L( f (x),0)没有不犯错误的人”符号化为(B.D.)。B.D.P(Px(F(x)x(F(x)G(x)G(x)(q p)q) p8.设R(x):x为有理数；Q(x):x为实数。命题 任何有理数都是实数”的符号化为 ()1 . ( x)(R(x) Q(x)8 . ( x)(R(x) Q(x)C . ( x)(R(x)Q(x)D. x(R(x) Q(x)9 .设个体域D a,b,与公式xA(x)等价的命题公式是(A. A(a) A(b)C. A(a) A(b)10 .下列等价式不

4、正确的是(B. A(a)A(b)D. A(b)A(a)A-x(P(x)Q(x)B. x(P(x)Q(x)C. x(P(x)Q(x)D. x(P(x)Q)xP(x) xQ(x)xP(x) xQ(x)xP(x) xQ(x)xP(x) Q11 .设个体域D a,b,与公式xA(x)等价的命题公式是(A.A(a)A(b)B.A(a)A(b)C.A(a)A(b)D.A(b)A(a)12 .设X= ,a,a, ,则下列陈述正确的是()。A. a XB.a, XC. a, XD. X13 .有向图D是连通图,当且仅当()。A.图D中至少有一条通路B.图D中有通过每个顶点至少一次的通路C.图D的连通分支数为一

5、D.图D中有通过每个顶点至少一次的 回路14 .设A=a,b,c,则下列是集合A的划分的是()A.b,c, cC. a,b, a,c15.下列谓词公式中是前束范式的是(A.xF(x)( x)G(x)C.x(P(x) yQ(x,y)16.设 Mx|f(x) 0, N x| f2(x)B. a, b,cD. a,b, c)°B. xF(x) yG(y)D. x y(P(x) Q(x,y)0,则方程"x) f2(x) 0的解为()A. MANB. M U NC. M NC. M-N17 .设GA, 是群，则下列陈述不正确的是()。A. (a 1) 1 aB. anam an mC

6、. (ab) 1 a 1b 1D. (a 1ba)n a 1bna18 .在整数集合Z上，下列定义的运算满足结合律的是(26 / 20A. a b b 1B.C. a b ab 1D.19.设简单图G所有结点的度数之和为50,则G的边数为（）A. 50B. 25C. 10D. 520.设简单无向图G是一个有5个顶点的4正则图，则6有（）条边。A. 4B. 5C. 10D. 20R 1,1 , 3,2 , 2,3【 )。B. 1,3,2,4D. 1,2,3,4R 1,3 , 3,1 , 2,4【 )。B. 1,3,2,4D. 1,2,3,421.设集合A 1,2,3,4 , A上的等价关系4,4

7、 UIa,则对应于R的划分是A. 1,2,3,4C. 1,3,2,422.设集合A 1,2,3,4 , A上的等价关系4,2 UIa,则对应于R的划分是A. 1,2,3,4C. 1,3,2,423.设GA, 是群，则下列陈述不正确的是（A.C.11(a ) an m n ma a a24.A1,2,L ,10,B.D.卜列定义的运算关于集合111(ab) a b(a 1ba)n a 1bnaA是不封闭的是(A.B.C.D.25.设 X(A.maxx, y,即x, y的较大数 min x, y,即x, y的较小数 gcd x, y,即x, y的最大公约数 lcm x, y,即x, y的最小公倍数

8、1,2,3, Y a,b,c,d, f 1,a , )o2,b , 3,c ,则B.C.D.从X到Y的双射从X到Y的满射，但不是单射从X到Y的单射，但不是满射从X到Y的二元关系，但不是从26.设简单无向图G是一个有6个顶点的X到Y的映射5正则图，则6有（A. 5B. 6C. 15D. 3027.图G如下图所示，以下说法正确的是A. a是割点C. b,d是点割集(B.D.）ob,c是点割集c是割点28.格L是分配格的充要条件是L不含与下面哪一个选项同构的子格(A.链B.钻石格oC.五角格D.五角格与钻石格)。30 .给定一个有n个结点的无向树，下列陈述不正确的是(A.所有结点的度数2B.无回路但

9、若增加一条新边就会变成回路C.连通且e v 1,其中e是边数，v是结点数D.无回路的连通图31 .设A有5个元素，则其募集P(A)的元素总个数为()B.25D. 5A. 32C. 5032 .若供选择答案中的数值表示一个简单图中各个顶点的度，能画出图的是 ( )。A. (1,2,2,3,4,5)B. (1,2,3,4,5,5)C. (1,1,1,2,3)D. (2,3,3,4,5,6)33 .设A a,a, a,a则其募集P(A)的元素总个数为()。A. 3B. 4C.8D.1634 .在实数集合R上，下列定义的运算中不可结合的是()A. abab2abB. ababC. abababD. a

10、bab35 .无向图G是欧拉图，当且仅当()。A. G的所有结点的度数全为偶数B. G中所有结点的度数全为奇数C. G连通且所有结点度数全为奇数D. G连通且所有结点度数全为偶数36 .下列不二足是树的是()A.无回路的连通图DB.有n个结点，n-1条边的连通图C.每对结点之间都有通路的图D.连通但删去一条边则不连通的图37.设简单图G所有结点的度数之和为（）A. 48C. 1648,则G的边数为B. 24D. 1238 .下面既是哈密顿图又是欧拉图的图形是（ B ）。B.不可以一笔画的图D.无奇数度结点的连通图B.哈密顿图D.完全图39 .下列必为欧拉图的是（）A.有回路的连通图C.有1个奇

11、数度结点的连通图40 .二部图七,3是（）。A.欧拉图C.平面图42.设简单无向图G是一个有6个顶点的3正则图，则6有（)）条边A. 3B. 6C. 9D. 1843 .下列式子为矛盾式的是(A- p (p q)B- p pC.- p pD- (p q) p q44 .设集合 A a, b,c, A 上的关系 R a,a , a, c , c, a ,则 R 是()A.自反的B.对称的C.传递的D.反对称的45 .设R,R2是集合A a,b,c,d上的两个关系，其中Ri a,a , b,b , b,c , d,d , R2 a,a , b,b , c,b , b,c , d,d ，则 R2 是

12、 Ri的 ()闭包。A.自反C.传递46 .下列公式是前束范式的是(A ( x)( y)( F(z,x) G(y)C(x)F(x, y) ( y)G(y)47 .设R为实数集，函数f : RA.单射而非满射C.双射48 .下列各图中既是欧拉图，又是汉密尔顿图的是(旦.对称D.自反、对称且传递闭包)。B. ( ( x)F(x) ( y)G(y) H (z)D(x)(F(x,y)( y)G(x, y)R, f(x)x2 2x 5 ,则 f 是()B.满射而非单射D.既不是单射，也不是满射C )。49 .下列四个格，是分配格的是(C )具有传递性的是(B. R=<a,c>,<c,a

13、>D.R=<a,a>50 .设集合A=a,b, c上的关系如下, A. R=<a,c>,<c,a>,<a,b>,<b,a> C. R=<a,b>,<c,c>,<b,a>,<b,c>参考答案：（若有问题，可以到1#40减打电话问） 一、选择题AAAABDACAAACCDDBBBDBCCDBD BCDBC ABBDC CBDDACCCBB ADCCD二、填空题1 .命题公式(pq)的成真指派为10 ,成假指派为_00, 01, 11 _02 .命题公式(p q)p的成真指派为00 10

14、 11,成假指派为01 03 .命题公式p (p q)的成真指派为00 01 11 ,成假指派为10 。4 .公式(x)( y)(P(y)Q(x,z) ( y)R(x, y)约束变元为x,y ,自由变元为 x,z。5 .公式x(P(x) yR(y) Q(x,z)约束变元为x,y ,自由变元为x,z 。6 .设 Aa,b,a,b , Ba,b,则 B A A B a,b。7 .设A 1,2,3 , A上的关系R 1,2 , 2,1 ,则对称闭包s(R) <1,2>,<2,1>,传递闭包 t(R) <1,2>,<2,1>,<1,1>,&l

15、t;2,2>。8 .设*是集合S上的二元运算，若运算*满足一结合律一并且存在单位元一则 称S,*为独异点。9 . 设A a,b,a,b , B a,b,c,则 A A A B a,b,c。10 .一棵无向树的顶点数n与边数m的关系是m=n-1。6阶无向连通图至多有 6 棵不同构的生成树。11 .设 f(x) x 1 , g(x) x2 ,则复合函数(f og)(x) =(x 1)2, (gof)(x) = x2 1。12 . Zn,是一个群，其中 Zn 0,1,2,L ,n 1 , x y (x y)modn,则当 n=6时，在 Z6,中，2的阶为 3, 3的阶为 2。13 .设<

16、人，&九格，其中A=1,3,4, 6, 8, 12, 24,斗整除关系，则1的补元 是_ 24 一，3的补元是 8 。14 .设 A= <1, 3>, <3, 5>, <4, 4>, B= <1,3>,<4,5>,<5,5>，刃B么 dom(AU B) =1,3,4,5 ran(AI B) = 3,5 c15 .设人=1,2,3,4, A上的二元关系 R=<1,2>,<2,3>,<3,2> , S=<l,3>,<2,3> , <4, 3>,WJ

17、 RoS <1,3>,<3,3>, (RoS) 1<3,1>,<3,3>016 .设 R=<1,2>,<3,4>,<3,5>和 S=<2,1>,<3,3>,<5,5>是集合 A=1,2,3,4,5上的 两个关系，则 RoS= <1,1>,<3,5> 、 S 1oR 1= <1,1>,<5,3>。17 .设人=2, 4, 6 , A上的二元运算*定义为：a*b=maxa,b,则在独异点<A,*>中，单位元是 2 ,零元

18、是 6 。18 . 一棵无向树的顶点数n与边数m关系是m= n-1 。设G是具有8个顶点的 树，则G中增加 21 条边才能把G变成完全图。19 .设复合函数g f是从A到C的函数，如果g f是满射，那么 g 必是满 射，如果g f是单射，那么 f 必是单射。20 .设<人，&九格，其中A=1, 3, 5, 9,45,秋整除关系，则1的补元是 45,3的补元是 5 。21 .给出A=l , 2上的一个等价关系<1,1>,<2,2>,并给出其对应的划分1,2。22 .设 A a,b,c,d, A上的二元关系 R a,b , a,d , b,b ，则 R 的自反

19、 闭包r(R) RU Ia ,传递闭包t(R) _R_23 .命题公式(p q) p的成真赋俏为01 10 11 、成假赋值为 Q0 o24 .公式(p q) ( p q)的成真赋值是00,11。成假赋值01 1025 .公式(p q) (p q)的成真赋俏是 01 11 。成假赋俏00 1026 .公式(pq) ( p q)的成假赋值是 01 10 。成假赋值00 1127 .设个体域是实数集，命题x(x 3 x)的真俏为 1:命题x(x2 1 0)的真值为0028 .设 f ： R- R,f(x)=x+3,g : R- R,g(x)=2x+1，则复合函数(fog)(x)= 2x+4,(g

20、of )(x) = 2x+7 o29 .给定集合A=1,2,3,4,5,在集合A上定义两种关系：R=<1,2>,<3,4>,<2,2>, S=<4,2>,<2,5>,<3,1>,<1,3>,则 RoS= <1,5>,<3,2>,<2,5>。30 .设人=0, 1, 2, 3, 6, R x,y |x, y A x y x y(mod3)则 domR= 0、 3、6、 ranR=0、 3,6,31 .设 Z6, 为模 6 加群，其中 Z6 0,1,2,3, 4,5,则 2-3=

21、_Q_, 4-2=4。32 . 一个结点为n的无向完全图，其边的数目为 n(n-1)/2 ,顶点的度为 n-1 。33 .已知n阶无向简单图G有m条边，则G的补图G中有m-n(n-1)/2条边。1. _10_, 00. 01. 112. 00 10 11, 01_3. _00 01 11, 104. _x_ , xz_5. _x_ , xz_6. a,b1,7. 1,2 , 2,1 , 1,2 , 2,1 , 1,1 , 2,2 8. 结合律,单位元9. _ a,b , c10. n-1, 62211. (x 1) ,x 1 ,12. 3, A13. 24 , 814. 134,5、_315.

22、 <1,3>,<3,3>,<3,1>,<3,3>16. 1,1 , 3,5 , 1,1 , 5,3 17. 2 , 618. m= n-1, 2119. /20. 45 , 521. _ 1,1 , 2,2 , 1,222. RU IA, R23. 01 10 11、0024. 00, 11 ,01, 1025. 01、11 ,00、1026. 01 10 , 00 1127. 。,_0_28. 2x+ 4,2x+ 729. <1,5>,<3,2>,<2,5>30. 0. 3. 6,0. 3. 631. _0_

23、,432. n(n-1)/2, n133. m- n(n-1)/2三、计算题（仅给出部分题目的解题思路，未给出答案自己完成）1 .已知命题公式（p q） （p r）(1)构造真值表(2)求出公式的主析取范式解题思路：(1)真值表p q rp(p q)p r(p q) (p r)000100100110010101100011110010001001010111110010011101112 2) ( p q) (p r)(p q r) (p q r) (p q r) (p q r)m° mi m)5 m72 .已知命题公式(p q) (p r)(1)构造真值表；(2)用等值演算法求公

24、式的主析取范式 解：(1)真值表p q rp qp r(p r)(p q)(p r)00000110010101010101101111001001100101110011011001111100(2)主析取范式(p q) (p r)(p q) (p r)(p q) ( p r)(pq)( rr)( p ( q q)r)(pqr)( p q r) ( pqr) ( p q r)m0 mi m23 .求公式(p (r p) (q p)的主合取范式及主析取范式。4 .构造命题公式(p A r) V (p q)的真值表。5 . 一棵(无向)树有2结点的度为2, 1个结点的度为3, 3个结点的度为4,

25、其 余都是叶结点，问该树有几个叶结点？解：在一个有限图中，各结点的度数总和是边数的2倍；而树中的边数为结点数减1。根据这两点，可知树中各结点的度数总和=2* (树中点数-1),设树叶有x个，于是，2*2+3+3*4+x=2* (2+1+3+x-l)得 x=9。6 .一棵无向树T有5片树叶，3个2度分支点，其余的分支点都是3度顶点，问 T有几个顶点？提示：类似上题求解。237.设 f:RR, f(x) x2 2, g:R R,g(x) x 4,h:R R,h(x) x3 1,其中R表示实数集。(1)求函数 f og , g of ；(2) f,g,h哪些函数有反函数？如果有，求出这些反函数。解：

26、(1) gof(x) f(g(x) f (x 4) (x 4)2 2 x2 8x 142_2_f og(x) g( f (x) g(x 2) x 29.设A 1,2,3,4,6,9,24,54, 为整除关系。(1)画出偏序集A, 的哈斯图；(2)求A中的极大元；(3)求子集B= 3, 6, 9的上确界与下确界解：(1)哈斯图(2) A中的极大元为24, 54;极小元为1;最大元：无；最小元：1(3)求子集B= 3, 6, 9的上确界为54,下确界为3。10.设有向图D如图所示，用邻接矩阵完成以下计算。(1)必到V4长度小于或等于4的通路数；(2)必到自身长度小于或等于4的回路数；(3)求出D的

27、可达矩阵，并说明D的连通性。有向图的邻接矩阵为12 1012 3 10 0 10，A0 0 0 10 0 0 10 0 100 0 1012 4 312 6 4A30 0 100 0 0 1A40 0 0 10 0 100 0 10(1) V1到V4长度小于或等于4的通路数为a(4)(2) vi到自身长度小于或等于4的回路数为4(i) ai11141111(3) P(D)0 1110 0 110 0 11由可达矩阵可知D是单向连通的11 .设A 0,1,2,给出募集合P(A)对称差运算的运算表。12 .设Z6 0,1, 2,3, 4,5,给出模6加运算的运算的运算表参看教材P167例9.4与9

28、.514 .设人=1 , 2, 3, 4, 5, R是A上的二元关系，且 R=<2, 1>, <2, 5>, <2, 4>, <3, 4>, <4, 4>, <5, 2>,求r(R)、s(R)和t(R)。解：r(R)=R U Ias(R)=RUR-1t(R)= <2, 1>, <2, 5>, <2, 4>, <3, 4>, <4, 4>, <5, 2>, (2,2>,<5,5> 15.下图为一连通赋权图，计算该图的最小生成树和权值。四

29、、简答题(1) 集合 A 1,2,3,4,5,6上的关系 R= (1,1>,< 1,3>,< 1,6>,< 2,2>,< 2,5 > ,< 3,1 > ,< 3,3> ,< 3,6 > ,< 4,4 > ,< 5,2 > ,< 5,5> ,< 6,1 > ,< 6,3), < 6,6 > (1)画出R的关系图，并写出R的关系矩阵；(2) R是否为等价关系？若是，写出R的所有等价类。解：(1) R的关系图为10 10 00 10 0 1(2)

30、 R的关系矩阵10 10 00 0 0 1 00 10 0 1由关系图可以看出R是等价关系。等价类为:1 3 6 1,3,6,22,5,44或写为：A/R=1,3,6,2,5,42.设 R 1,3 ,(1,4 , 2,2 , 3,1 , 3,3), 4,1 是 A=1,2,3,4上的二元关 系。(1)画出R的关系图；(2)写出R的关系矩阵；(3)讨论R的性质。解：(1) R的关系图0 0 11(2) R的关系矩阵0 10 010 0 010 0 0(3) R非自反、非反自传、对称、非反对称、非传递的(4) R不是函数，不满足函数单值性的要求。3.设 A=1,2,3,4,5,6,7,8,9,10

31、 , R 是 A 上的二元关系,R=|x,y A Ax+y=10说明R具有哪些性质。解：R=<1,9>,<2,8> ,<3,7> ,<4,6> ,<5,5> ,<9,1>,<8,2> ,<7,3> ,<6,4> R是对称的R不是反对称的R不是传递的。4 .判断下图是否为二部图？若是， 若是，找出一条哈密顿回路。5 .判断下图G是否是二部图？若是找出它的互补结点子集。它是否为哈密顿图?acj> e,找出它的互补结点子集。它是否为哈密顿易知R既不是自反也不是反自反的图？若是，找出一条哈

32、密顿回路。6.设A= 1,3,5,9,45,为A上的整除关系。(1) A,是否为偏序集，若是，画出其哈斯图；(2) A,是否为格？说明理由；解：(1) A,是偏序集。哈斯图为：459tA315(2) A,是格。因为偏序集中的任意两个元素i四、证明题1.用一阶逻辑的推理理论证明：前提：x(F(x)G(x), x(F(x) H(x),结论： x G(x)证明：(1) x(F(x) H (x)前提引入V 怔S V2b_vDv3匀后上、卜确界。x H(x)2) F (x) H (x)3) x H (x)4) H (x)5) F(x)6) x(F(x) G(x)7) F(x) G(x)8) G(x)9)

33、 G(x)1)前提引入3)(2) (4)析取三段论 (4分)前提引入6)5) ( 7)假言推理(8) ( 3 分)2 .设A是非空集合，F是所有从A到A的双射函数的集合,o是函数的复合运算证明： F ,o 是群。证明：由于集合A 是非空的，I A F ， 因此 F 非空 。,(1) f,g F ,因为f和g都是A到A的双射函数，故f og也是A至A的双射函数，从而集合F 关于运算 是封闭的。(2) f,g,h F ,由函数复合运算的结合律有(f og)oh f o(goh) ，故运算 o 是可结合的。(3) A上的恒等函数I a也是A到A的双射函数即Ia F,且f F有lAOf f oI a故

34、Ia是 F,o中的幺元。(4) f F ,因为 f 是双射函数， 故其逆函数是存在的， 也是 A 到 A 的双射函数，且有fof1 f 1 of I a,因此f1是f的逆元由此上知 F ,o 是群3 .设代数系统V Z6, Z6 0,1,2,3,4,5,为模6加法。证明：Z6关于运算构成群。证明：集合Z6 显然非空。(1) a,b Z6,a b Z6 从而集合Z6关于运算是封闭的。,(2) a, b, c Z6 ,有 (a b) c a (b c) ， 故运算是可结合的。(3) a Z6, a 0 a,故0是Z6, 中的幺元。(4) a Z6,因为a (6 a) 0,因此6 a是a的逆元由此上

35、知Z6 ,是群4 .设A是集合，P(A)是A的募集合，是对称差运算，证明P(A),构成群提示：参考2、 3证明题完成。5 .设A x, y | x, y为正整数，在A上定义二元关系R如下：x, y R u,v 当且仅当 x y u v 。证明： R 是一个等价关系。证明：任取 x,yx, y A x y x y x, y R x, y所以 R 自反的。任取 x,y , u,vx, yR u,v x yu v u v x y u,v R x, y所以 R 是对称的。任取x,y , u,v , s,tx, y R u,v u,v R s,t x y u v u v s tx y s t x, y

36、R s,t所以 R 是传递的。因此， R 是等价关系。6.设 R 是 A 上的关系，如果R 满足以下两条件：（ 1）对于任意的 a R， 都有 aRa，（ 2）若aRb, aRc, 则有 bRc，证明： R 是等价关系证明： 任取 a, b,c R（ 1）由已知条件（ 1）得a,a R,所以R是自反的。 ,（ 2）由已知条件（1） 、 （ 2）得a,b R a, a R b,a R所以 R 是对称的。（ 3）由已知条件（1） 、 （ 2）得a,b R b,c R b,a R c,b Rb,c R b,a R c,a R所以 R 是传递的。五、应用题（仅给出第 7 题的参考答案,未给出参考答案的

37、自己完成）1 . 构造下列推理的证明。如果今天是星期一，则要进行英语或离散数学考试。 如果英语老师有会，则不考 英语。今天是星期一，英语老师有会，所以进行离散数学考试。2 .构造下列推理的证明。小王是理科学生，则他的数学成绩很好。如果小王不是文科学生，则他一定 是理科学生。小王的数学成绩不好，所以小王是文科学生。3 .如果甲是冠军，则乙或丙将得亚军；如果乙得亚军，则甲不能得冠军；如果丁得亚军，丙不能得亚军；事实是甲已得冠军。因此丁不能得亚军。参照作业：P54 17,184 .用一阶逻辑推理证明每个喜欢步行的人都不喜欢骑自行车，每个人或喜欢骑自行车或者喜欢乘汽车。有的人不喜欢乘汽车，所以，有的人不喜