离散数学期末练习试题[带答案]

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

2、 q rD. pqr3.令p:今天下雪了，q:路滑，则命题“虽然今天下雪了，但是路不滑”可符号 化为()。A p -qB. p qC. p qD. p - q4 .设P(x): x是鸟，Q(x): x会飞，命题“有的鸟不会飞”可符号化为().A x)(P(x)T Q(x)B.”x)(P(x) A Q(x)C.(三x)(P(x)T Q(x)D.(三x)(P(x) A Q(x)5 .设P(x): x是整数，f(x):x的绝对值，L(x,y)： x大于等于y ；命题”所有整 数的绝对值大于等于0”可符号化为()。A. -x(P(x) L(f(x),0)B. -x(P(x) L(f(x),0)C. -

3、xP(x) L(f(x),0)D. -xP(x) L(f(x),0)6.设F(x) : x是人，G(x): x犯错误，命题“没有不犯错误的人”符号化为( )。A. -x(F(x) G(x)B. x(F(x) - 一G(x)C. x(F(x) G(x)D. x(F(x) -G(x)7 .下列命题公式不是永真式的是()。A. (p q) pB. p (q p)C. -p (q p)D. (p q) p8 .设R(x): x为有理数；Q(x) :x为实数。命题“任何有理数都是实数”的符号化为()A. ( x)(R(x) Q(x)B. (-x)(R(x) Q(x)C. (-x)(R(x) Q(x)D.

4、 x(R(x) Q(x)9.设个体域D =a,b,与公式VxA(x)等价的命题公式是()A. A(a) A(b)B, A(a) A(b)C. A(a) A(b)D. A(b)A(a)10 .下列等价式不正确的是()。A. x(P(x)Q(x)=-xP(x)-xQ(x)B. -x(P(x)Q(x)=-xP(x)-xQ(x)C. x(P(x)Q(x)=xP(x)xQ(x)D. -x(P(x)Q)：=-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=0,a,

5、 a,0,则下列陈述正确的是()。A. a XB.a, _ XC. a,. XD. X13 .有向图D是连通图，当且仅当()0A.图D中至少有一条通路B.图D中有通过每个顶点至少一次的通路C.图D的连通分支数为一D.图D中有通过每个顶点至少一次的 回路14 .设A=a,b,c,则下列是集合A的划分的是()B. a, b,cD. a,b, c)。B. -xF(x) -yG(y)D. -x y(P(x)，Q(x, y)A.b,c, cC.a,b, a,c15 .下列谓词公式中是前束范式的是(A. -xF(x) -( x)G(x)C. x(P(x)- -yQ(x,y)16.设 M =x| f(x)

6、=0, N =x | fz(x) =0,则方程 f1(x) fz(x) =0 的解为(A. MHNB. MU NC . MNC. M-N17.设G kA,” 是群，则下列陈述不正确的是()。A. (a)“ =aB. anam=an mC. (ab) 4 = a b4D. (a 4ba)n = a 4bna18.在整数集合Z上，下列定义的运算满足结合律的是（）。A. a b = b 1B. a b = a -1C. a b=ab-1D a b=a b 119.设简单图G所有结点的度数之和为50,则G的边数为（）0（）A. 50B. 25C. 10D. 520 .设简单无向图G是一个有5个顶点的4

7、正则图，则6有（）条边。A. 4B. 5C 10D. 2021 .设集合 A=1,2,3,4 , A上的等价关系 R=,4,4AUIa,则对应于R的划分是（）。A 1,2,3,4B. 1,3,2,4C. 1,3,2,4D. 1,2,3,422 .设集合 A=1,2,3,4 , A 上的等价关系 R =,UIa,则对应于R的划分是（）。A. 1,2,3,4B. 1,3,2,4C. 1,3,2,4D. 1,2,3,423 .设Gx A,* a是群，则下列陈述不正确的是（）。1 1111A. （a ） =aB. （ab） = a bCnmn“m1nn.a a =aD. （a ba） = a b a2

8、4 . A=1,2,L ,10,下列定义的运算关于集合 A是不封闭的是（）。A. x* y =maxx, y,即 x,y 的较大数B. x* y =min x, y,即 x, y 的较小数C. x* y =gcdx, y,即x, y的最大公约数D. x* y = lcmx, y,即x, y的最小公倍数25 .设 X =1,2,3, Y=a,b,c,d, f =,c2,b a, 3,c ,则 f 是（）。A.从X到Y的双射B.从X到Y的满射，但不是单射C从X到Y的单射，但不是满射D.从X到Y的二元关系，但不是从X到Y的映射26 .设简单无向图G是一个有6个顶点的5正则图，则6有（） 条边。A.

9、5B. 6C 15D. 30- b27 .图G如下图所示，以下说法正确的是（）。/A. a是割点C b,d是点割集28 .格L是分配格的充要条件是A.链C.五角格B.b,c是点割集D c是割点L不含与下面哪一个选项同构的子格(B.钻石格D.五角格与钻石格29 .下列图是欧拉图的是(D30 .给定一个有n个结点的无向树，下列陈述不正确的是()。A.所有结点的度数学2B.无回路但若增加一条新边就会变成回路C.连通且e = v-1 ,其中e是边数，v是结点数D.无回路的连通图31.设A有5个元素，则其募集P(A)的元素总个数为()。A 32B.25C. 50D.532 .若供选择答案中的数值表示一个

10、简单图中各个顶点的度，能画出图的是 ( )。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. a b = a b 2abB. a*b=a+bC. a*b=a + b+abD. a b = a。b35 .无向图G是欧拉图，当且仅当()。A. G的所有结点的度数全为偶数B. G中所有结点的度数全为奇数C. G连通且所有结点度数全为奇数D G连通且所有结点度数全为偶数3

11、6 .下列不丁车是树的是（）A.无回路的连通图DB.有n个结点，n-1条边的连通图C.每对结点之间都有通路的图D.连通但删去一条边则不连通的图37.设简单图G所有结点的度数之和为48,则G的边数为（）A. 48B. 24C. 16D. 1238.下面既是哈密顿图又是欧拉图的图形是（ B ）。39 .下列必为欧拉图的是（A.有回路的连通图C.有1个奇数度结点的连通图40 .二部图右3是（）。A.欧拉图C.平面图B.不可以一笔画的图D.无奇数度结点的连通图B.哈密顿图D.完全图41.下列所示的哈斯图所对应的偏序集中能构成格的是（ C ）专业整理条边42.设简单无向图G是一个有6个顶点的3正则图，则

12、6有（）A. 3C. 943 .下列式子为矛盾式的是(A. p (p q) c p -p44 .设集合A=a,b,c , A上的关系A.自反的C.传递的8. 6D. 18oB. p -pD.一(p q)u -p -qR =,a,o, ,则 R是(B.对称的D.反对称的A自反C.传递46 .下列公式是前束范式的是(A. (-x)(-y)(-F(z,x) G(y)C. ( x)F(x,y) (-y)G(y)47 .设R为实数集,函数f : RtA.单射而非满射45.设R,R2是集合A=a,b,c,d上的两个关系，其中Ri =, , R2 =a,a a, b,b a, cc,b a, b,c a,则

13、 R2 是 R1 的 ()闭包。B.对称D.自反、对称且传递闭包)。B. (-( x)F(x) (-y)G(y) H (z)D . x)(F(x,y)T (Vy)G(x, y)R , f (x) =-x2 + 2x + 5 ,则 是()B.满射而非单射C.双射D.既不是单射，也不是满射48 .下列各图中既是欧拉图，又是汉密尔顿图的是( C )49 .下列四个格，是分配格的是(C )D50.设集合 A=a,b, c上的关系如下，具有传递性的是(A. R=,B. R=,C. R=,D. R=参考答案：(若有问题，可以到1#40减打电话问) 一、选择题AAAAB DACAA CCDBD BCDBC

14、ABBDC CBDDAACCDD BBBDB CCCBB ADCCD二、填空题1 .命题公式F p t q)的成真指派为10 ,成假指派为 00, 01, 11 02 .命题公式(pq)T p的成真指派为00 10 11 ,成假指派为01 。3 .命题公式pt (p Aq)的成真指派为00 01 11 ,成假指派为 10_。4 .公式(Vx)(寸y)(P(y)T Q(x,z)/(R)R(x, y)约束变元为 x,y ,自由变元 为 x,z o5 .公式 X7x(P(x) yR(y)T Q(x,z)约束变元为 _xy_,自由变元为 _x,z _。6 .设 A=a,b,a,b , B =a,b,则

15、 B A = 2, A B = a,b。7 .设A =1,2,3 , A上的关系R=c1,2,则对称闭包s(R) = ,、传递闭包 t(R) = ,。8 .设*是集合S上的二元运算，若运算*满足 结合律一并且存在单位元 则称为独异点。9 . 设庆=2,32闷 , B =a,b,c,则 A A = 0 , A- B = a,b,c。10 .一棵无向树的顶点数n与边数m的关系是 m=n-1。6阶无向连通 图至多有 6 棵不同构的生成树。11 .设 f(x) =x1 , g(x) =x2 ,则复合函数(f 0g)(x)=(x1)2, (g。f )(x) = x2 -1 012 . 是一个群，其中 Z

16、n =0,1,2,|,n-1 , x(B y =(x + y)mod n ,则当 n =6 时，在Z6,5a中，2的阶为 3, 3的阶为_2。13 .设是格，其中A=1, 3,4, 6, 8, 12, 24, 0为整除关系，则1的补 元是 24, 3的补元是8 。14 .设 A=, , , B= , ，那么 dom(AU B =1,3,4,5 ran (AH B) = 3,5。15 . &A=l,2,3,4,A的二元关系 R=, S=, ,贝 1 RO S = , (rC S)二= ,。16 .设=, ftS=,是集合 A=1,2,3,4,5上的两个关系，M RQS = , S-0R- = ,

17、。17 . 设人=2, 4, 6, Ah的二元运算*定义为：a*b=maXa, b,则在独异点 中，单位元是2 ,零元是 6 。18 .一棵无向树的顶点数n与边数m关系是m=n-1。设G是具有8个顶点的树， 则G中增加 21条边才能把G变成完全图。19 .设复合函数g”是从A到C的函数，如果g：f是满射，那么 g_必是满 射，如果gof是单射，那么 f 必是单射。20 .设是格，其中A=1,3, 5, 9,45, 0为整除关系，则1的补元是45 , 3的补元是_ 5 _ 。21 .给出A=l , 2上的一个等价关系., ,并给出其对应的划分 _1,2。22 .设人=伯由5,A上的二元关系R =

18、, , ,则R的自反 闭包r(R) = RUIA ,传递闭包t(R)= R23 .命题公式(pq)- p的成真赋值为 01 10 11,成假赋值为 00 024 .公式(p Aq) v( p Aq)的成真赋值是00,11。成假赋值 01 1025 .公式(p八q) v( p Aq)的成真赋值是01 11。成假赋值00 1026 .公式(p q)八(p q)的成假赋值是 01 10。成假赋值00 1127 .设个体域是实数集，命题Vx(x-3 x)的真值为1;命题三x(x 10, 00、01、11 00 10 11、01_29. ,30. 0,3, 6, 0,3,631. 0 ,4 32. n(

19、n-1)/2, n-1 +1 = 0)的真值为0 Q28 .设 f ： FHR,f(x)=x+3,g : FHR,g(x)=2x+1,则复合函数(fjg)(x)= 2x+4 , (g 0 f )(x) = 2x+7 o29 .给定集合 A=1,2,3,4,5,在集合 A上定义两种关系：R=, S=,则 R()S= ,。30 .设 A=0, 1, 2, 3, 6 , R =x, y X x, yE AAx#y ax 三 y(mod3)贝 domR=0 ,3,6, ranR= 0 , 3,6,3231 .设 Z64 a为模 6 加群，其中 Z6 =0,1,2,3, 4,5,则 2 =0, 4 =

20、4。32 . 一个结点为n的无向完全图，其边的数目为n(n-1)/2,顶点的度为n-1 。33 .已知n阶无向简单图G有m条边，则G的补图G中有m-n(n-1)/2 条边。word格式文档3. 00 01 11, 10 _4. _x ,y , x, z_5. _x ,y , x, z6. 巴，a,b7. , , ,8. 结合律,单位元9. 丝,，a,b , c10. n-1, 6 2211. (x -1) , x -1 , 12.1322 13. 24 , 814. 1,3,4,5, 315. ,16. , , , 17. 2 , 618. m= n-1, 2119. _g_,_20. 45

21、, _5_21. _：二1,1 ,：二2,2 , 1,222. Rljl a, R_23. 01 10 11, 0024. 00 , 11 ,01 , 1025. 01 , 11 ,00 , 1026. 01 10, 00 1127. 堂28. 2x+ 4, 2x+ 7三、计算题(仅给出部分题目的解题思路，未给出答案自己完成)1 .已知命题公式(Ft q)T (p Ar)(1)构造真值表(2)求出公式的主析取范式 解题思路：(1)真值表p q rF(Ft q)p Ar(Ft q)T (pAr)0 0 010010 0 110010 1 011000 1 111001 0 001001 0 10

22、1111 1 001001 1 101112 2) (-p q) (p r)=(P q r) (p q r) (p _q r) (p q r) =m0 m1 m5 m72 .已知命题公式(pq)T(pr)(1)构造真值表；(2)用等值演算法求公式的主析取范式 解：(1)真值表p q rp vqp vr( p r)(pq)T(pr)0 0 000110 0 101010 1 010110 1 111001 0 011001 0 111001 1 011001 1 11100(2)主析取范式 (p q) . -(p r)上(p q) -(p r)二(一p q) (p r)=(p -q) (r r)

23、 (p (q q) -r)二(一p q r) (p q r) (p q - r) (-p q - r)：-mo mi m23 .求公式(pt (r m p) r、(qT p)的主合取范式及主析取范式。4 .构造命题公式丁 pA r) V (pt q)的真值表。5 . 一棵(无向)树有2结点的度为2, 1个结点的度为3, 3个结点的度为4,其 余都是叶结点，问该树有几个叶结点？解：在一个有限图中，各结点的度数总和是边数的2倍；而树中的边数为结点数减1。根据这两点，可知树中各结点的度数总和 =2* (树中点数-1),设树叶有x 个，于是，2*2+3+3*4+x=2* (2+1+3+x-l)得 x=

24、9o6 .一棵无向树T有5片树叶，3个2度分支点，其余的分支点都是3度顶点，问 T有几个顶点？提示：类似上题求解。7 .设 f : Rt R, f (x) =x2 2 , g : Rt R,g(x) =x+4, h : Rt R, h(x) = x3 -1 , 其中R表示实数集。(1)求函数 f Og , g。f ；(2) f,g,h哪些函数有反函数？如果有，求出这些反函数。解：(1) g0 f(x)= f(g(x) = f(x+4)=(x+4)22 = x2+8x + 14f g(x)(f (x) =g(x2 -2) =x2 2(2) g 和 h有反函数，g：RT R,g(x)=x-4;hd

25、： R； R,hd(x) =3T18.设 A= a, b, c , R! Ah 的二元关系，且 R= , ,求 r(R)、s(R) 和 t(R)。解：r(R)=R U I A=,s(R)=RU R-1=,专业整理t(R)= R UR2UR3=, , , 9.设A =1,2,3,4,6,9,24,54 , w为整除关系。(1)(2)(3)解：(1)画出偏序集A, 的哈斯图;求A中的极大元； 求子集B= 3, 6, 9 哈斯图的上确界与下确界。(2) A中的极大元为24 , 54;极小元为1;最大元：无；最小元：1(3)求子集B=3, 6, 9 的上确界为54,下确界为3。10.设有向图D如图所示

26、，用邻接矩阵完成以下计算。(1)必到V4长度小于或等于4的通路数；(2)必到自身长度小于或等于4的回路数；(3)求出D的可达矩阵，并说明D的连通性。3 1有向图的邻接矩阵为1 20 0A =0 09 0A3,0A310A40 0一1,04101(1)必到V4长度小于或等于4的通路数为4、:端=0 1 3 4 = 8 i=1(2) vi到自身长度小于或等于4的回路数为4a1(1) =1 1 1 1 =411111_D是单向连通的。(3) P(D)=一100g11001111由可达矩阵可知11 .设A =0,1,2,给出募集合P(A)对称差运算的运算表。12 .设Z6 =0,1, 2,3, 4,5

27、,给出模6加运算的运算的运算表参看教材P167例9.4与9.514 .设人=1 , 2, 3, 4, 5, RgAh的二元关系，且 R= , , , , , ,求 r(R)、s(R)和t(R)。解：r(R)=R U I as(R)=RUR-1t(R)= , , , , (2,2,15 .下图为一连通赋权图，计算该图的最小生成树和权值。四、简答题1.设集合 A =1,2,3,4,5,6上的关系 R= (1,1, , , , , , , , , , 6,3), (1)画出R的关系图，并写出R的关系矩阵;(2) R是否为等价关系？若是，写出R的所有等价类。(2) R的关系矩阵10 10 00 10

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

29、二元关系，R=|x,y 8A Ax+y=10说明R具有哪些性质。解：R=, , , , , , , 易知R既不是自反也不是反自反的R是对称的R不是反对称的R不是传递的。找出它的互补结点子集。它是否为哈密顿图?4 .判断下图是否为二部图？若是 若是，找出一条哈密顿回路。5 .判断下图G是否是二部图？若是，找出它的互补结点子集。它是否为哈密顿图？若是，找出一条哈密顿回路6 .设A= 1,3,5,9,45 , M为A上的整除关系。(1) mA,E是否为偏序集，若是，画出其哈斯图;(2) cA,E是否为格？说明理由；解：(1) 是偏序集。哈斯图为：45(2) -G(x) F(x)tG(x)(8)G(x

30、)Yx(F(x),H(x),三xH(x)前提引入(D -前提引入(3) 3(2) (4)析取三段论 (4分)前提引入(6)-(5) (7)假言推理(9) 3-G(x)(8)三十(3 分)2 .设A是非空集合，F是所有从A到A的双射函数的集合，。是函数的复合运证明：二证明：由于集合A是非空的，1A WF,因此F非空。 ,(1) f,gWF,因为f和g都是A到A的双射函数，故f0g也是A到A的双射函数，从而集合F关于运算 是封闭的。(2) f,g,hWF ,由函数复合运算的结合律有(f Og)0h = f gOh),故运算口 是可结合的。(3) A上的恒等函数IA也是A到A的双射函数即1AWF,且

31、fWF有I A Of = f CI A,故Ia是FA中的幺元。(4) f WF ,因为f是双射函数，故其逆函数是存在的，也是A到A的双射函 数，且有f Qf - L。f =底，因止匕f、是f的逆元由此上知F,。下是群3 .设代数系统V KZ6,出a, Z6 =0,123,4,5,学为模6加法。证明：Z6关于中 运算构成群。证明：集合Z6显然非空。(1) Va,bZ6, ab=Z6从而集合Z6关于运算是封闭的。,(2) Va,b,c WZ6,有(a(Bb)c =a(B(bc),故运算是可结合的。(3) VaZ6, a0 = a,故 0 是 中的幺元。(4) VaWZ6,因为a6(6a)=0,因止匕6a是a的逆元由此上知Z6,$ A是群4 .设七集合，P(A)是A的幕集合，田是对称差运算， 证明构成群。 提示：参考2、3证明题完成。5 .设A = x, yax, y为正整数,在A上定义二元关系R如下：x, yR 当且仅当x y=uV。证明：R是一个等价关系。证明：任取:二x, y .:：x, y 大三 A = x - y = x - y u ： x, y R : x, y所以R自反的