离散数学试题及答案

1、离散数学试题及答案一、填空题1 设集合 A,B,其中 A = 1,2,3, B= 1,2,则 A - B =；(A)- (B) =2 .设有限集合 A, |A| = n,则 | (A>A)| =.3 .设集合A = a, b, B = 1,2,则从A到B的所有映射是 其中双射的是.4 .已知命题公式 G= (P Q)AR,则G的主析取范式是 .5 .设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为 一分枝点数为.6 设 A、B 为两个集合，A= 1,2,4, B = 3,4,则从 A B =A；B = 二B 洪 .7 .设R是集合A上的等价关系，则R所具有的关系的三个特性是 ,

2、 , .8 .设命题公式G= (P (Q R),则使公式G为真的解释有 ,.9 .设集合 A=1,2,3,4, A上的关系 R = (1,4),(2,3),(3,2), R = (2,1),(3,2),(4,3),则Ri?R2 = _,R,Ri2 =10 .设有P6集 A, B,冏二 m, |B| = n,则| | (A B)| =.11 设 A,B,R是三个集合，其中 R是实数集，A = x | -1 <x< 1, x R, B = x | gx < 2, x R,则 A-B=, B-A =, An b = ,.13 .设集合A=2, 3, 4, 5, 6, R是A上的整除

3、，则R以集合形式(列举法)记为Word资料14 .设一阶逻辑公式G = xP(x) xQ(x),则G的前束范式是15 .设G是具有8个顶点的树，则G中增加条边才能把G变成完全图。16 .设谓词的定义域为a, b,将表达式xR(x)- xS(x)中量词消除，写成与之对应的命题公式是17 .设集合 A=1,2, 3, 4, A 上的二元关系 R= (1,1),(1,2),(2,3), S= (1,3),(2,3),(3,2)。则RS=R2 =、选择题设集合A=2,a,3,4, B = a,3,4,1, E为全集，则下列命题正确的是()o(A)2 A (B)a A (C)a B E (D)a,1,3

4、,4 B.设集合 A=1,2,3,A 上的关系 R= (1,1),(2,2),(2,3),(3,2),(3,3),则 R 不具备().(A)自反性(B)传递性(C)对称性(D)反对称性设半序集(A,0)关系0的哈斯图如下所示，若(A)下界(B)上界(C)最小上界4下列语句中，()是命题。(D)以上答案A的子集(A)请把门关上(B)地球外的星球上也有人(C)x + 5 > 6(D)下午有会吗?5设I是如下一个解释：D=a,b,P(a,a) P(a,b) P(b,a) P(b,b)则在解释I下取真值为1的公式是().(A) x yP(x,y) (B) x yP(x,y) (C) xP(x,x

5、) (D) x yP(x,y).().6 .若供选择答案中的数值表示一个简单图中各个顶点的度，能画出图的是(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).7 .设G、H是一阶逻辑公式，P是一个谓词，G= xP(x), H= xP(x)，则一阶逻辑公式 G H是().(A)包真的(B)包假的(C)可满足的(D)前束范式.8 设命题公式 G= (P Q), H=P (QP),则G与H的关系是()。(A)G H(B)H G (C)G=H(D)以上都不是.9 设A, B为集合，当("9AB=B.(A)A=B (B)

6、AB (C)BA(D)A=B=.10 设集合 A = 1,2,3,4, A 上的关系 R= (1,1),(2,3),(2,4),(3,4),则 R 具有()。(A)自反性(B)传递性(C)对称性(D)以上答案都不对11下列关于集合的表示中正确的为()。(A)a a,b,c(B)a a,b,c (C)a,b,c(D)a,b a,b,c12命题xG(x)取真值1的充分必要条件是().(A)对任意x, G(x)都取真值1.(B用一个x。，使G(x9取真值1.(C)有某些x,使G(xo)取真值1.(D)以上答案都不对.13.设G是连通平面图，有 5个顶点，6个面，则G的边数是().(A) 9 条 (B

7、) 5 条 (C) 6 条 (D) 11 条.14 .设G是5个顶点的完全图，则从 G中删去()条边可以得到树(A)6(B)5 (C)1015 .设图G的相邻矩阵为(D)4.0 111110 10 0110 1110 10 110 110则G的顶点数与边数分别为).(A)4, 5(B)5, 6(C)4, 10(D)5, 8.三、计算证明题设集合A = 1,2, 3, 4, 6, 8, 9, 12 , R为整除关系。(1)画出半序集(A,R)的哈斯图；(2)写出A的子集B = 3,6,9,12的上界，下界，最小上界，最大下界；(3)写出A的最大元，最小元，极大元，极小元。2 .设集合 A = 1

8、,2, 3, 4, A 上的关系 R= (x,y) | x, y A 且 x y,求(1)画出R的关系图；(2)写出R的关系矩阵.3 .设R是实数集合，是R上的三个映射，(x) = x+3, (x) = 2x, (x) = x/4,试求复合映射？，？，？，？，？ ？.4 .设I是如下一个解释：D = 2, 3,a b f (2) f (3)P(2, 2) P(2, 3) P(3, 2)P(3, 3)32320011试求(1) P(a, f (a)AP(b, f (b);(2) x y P (y, x).5 .设集合A = 1,2, 4, 6, 8,12, R为A上整除关系。(1)画出半序集(A

9、,R)的哈斯图；(2)写出A的最大元，最小元，极大元，极小元；(3)写出A的子集B = 4, 6, 8, 12的上界，下界，最小上界，最大下界 .6 .设命题公式 G =(P-Q)V(QA( P-R),求G的主析取范式。7 . (9分)设一阶逻辑公式：G = ( xP(x) V yQ(y)H xR(x),把G化成前束范式.9 .设 R 是集合 A = a, b, c, d. R 是 A 上的二元关系，R = (a,b), (b,a), (b,c), (c,d),(1)求出 r(R), s(R), t(R);(2)画出r(R), s(R), t(R/勺关系图.11.通过求主析取范式判断下列命题公

10、式是否等价：(1) G = (PAQ)V( PAQAR)(2) H = (P V (Q A R)A (Q V ( PAR)13.设 R和 S是集合 A=a, b, c, d上的关系,其中 R= (a, a),(a, c),(b, c),(c, d),S= (a, b),(b, c),(b, d),(d, d).(1)试写出R和S的关系矩阵；(2)计算 R?S, RU S, R 1, S 1?R 1.四、证明题1 .利用形式演绎法证明：P一 Q, R-S, PV R蕴?B QVSo2 .设A,B为任意集合，证明：(A-B)-C = A-(B U C).3 .(本题10分)利用形式演绎法证明： A

11、VB,C一 B, C-D蕴涵A-D。4 .(本题10分)A, B为两个任意集合，求证：A (An B) = (AU B)B .、填空题1. 3; 3,1,3,2,3,1,2,3.n22. 2 .3. 1= (a,1), (b,1),2= (a,2), (b,2), 3= (a,1), (b,2), 4= (a,2), (b,1); 3, 4.4. (PA QA R).5. 12, 3.6. 4, 1,2, 3, 4, 1,2.7.自反性；对称性；传递性8.9.(1,0, 0),(1,0,1), (1,1, 0).(1,3),(2,2),(3,1); (2,4),(3,3),(4,2); (2,

12、2),(3,3)._m n10. 211. x | -1 <x < 0, x R; x | 1 < x < 2, x R； x | 0<x< 1, x R.12. 12; 6.13. (2, 2),(2, 4),(2, 6),(3, 3),(3, 6),(4, 4),(5, 5),(6, 6).14. x( P(x)V Q(x).15. 21.16. (R(a)A R(b)一(S(a)V S(b).17. (1,3),(2, 2); (1, 1),(1,2),(1,3).、选择题1. C.2.D.3.B. 4.B.5. D.6.C.7.C.8. A.9.D.

13、10.B. 11.B.13.A.14.A.15. D三、计算证明题1.(2) B无上界，也无最小上界。下界1,3;最大下界是3.A无最大元，最小元是 1,极大元8,12, 90+;极小元是1.2.R = (1,1),(2,1),(2,2),(3,1),(3,2),(3,3),(4,1),(4,2),(4,3),(4,4).10 0 02) ) Mr3) (1) ?=110 011101111(x)= (x)+3 = 2x+3 = 2x+3.(2) ? = ( (x)= (x)+3 = (x+3)+3 =x+6,(3) ? = ( (x)= (x)+3 = x/4+3,(4) ?= ( (x)=

14、 (x)/4=2x/4 = x/2,(5) ? ?= %？)= ?+3=2x/4+3 =x/2+3.4. (1) P(a, f (a) A P(b, f (b) = P(3, f (3) A P(2, f (2)=P(3, 2) A P(2, 3)=1 A 0 =0.(2) x y P (y, x) = x (P (2, x)VP (3, x)二(P (2, 2) VP (3, 2) A (P (2, 3) VP (3, 3)=(0 V 1)A (0 V 1)=1 A 1 =1.5. (1)(2)无最大元，最小元 1,极大元8, 12;极小元是1.(3) B无上界，无最小上界。下界 1,2;最

15、大下界2.6. G =(P-Q)V(QA( P-R)=(PV Q)V(QA(PVR)=(PA Q)V(QA(PVR)=(PA Q) V (QA P)V (QA R)=(PAQ AR)V(PAQ AR)V(PAQ A R) V (PA Q AR)V(PAQAR)V( PA QA R)=(PAQ AR)V(PAQ AR)V(PAQ A R) V (PA Q AR)V(PAQAR)=m 3Vm4Vm5Vm6Vm7 =(3, 4, 5, 6, 7).7. G = ( xP(x) V yQ(y)一 xRx)=(xP(x)V yQ(y)V xR(x)=(xP(x)AyQ(y)V xR(x)=(x P(x)

16、A y Q(y)V zR(z)=x y z( P(x)A Q(y)VR(z)9. (1) r(R) = RU Ia= (a,b), (b,a), (b,c), (c,d), (a,a), (b,b), (c,c), (d,d),s(R)= RU R 1= (a,b), (b,a), (b,c), (c,b) (c,d), (d,c),t(R)= RU R2UR3U R4= (a,a), (a,b), (a,c), (a,d), (b,a), (b,b), (b,c), (b,d), (c,d);关系图:r(R)s(R)11. G = (PA Q) V( PA Q AR)= (PAQA R)V

17、(PAQAR)V( PA Q A R)=m6Vm7 V m3=(3, 6, 7)H = (P V(QAR)A (Q V ( PAR)= (PA Q)V(QAR)V( PA QAR)= (PAQA R)V (PAQAR)V( PA Q A R)V (PAQA R)V(PA QA R)= (PA QA R)V ( PAQAR)V(PA Q AR)=m6Vm3 V m7(3, 6, 7)G,H的主析取范式相同，所以G = H.1 0 10 0 113.(1)Mr0 0 00 0 0001000Ms00100001000101(2)R?S= (a, b),(c, d),RU S= (a, a),(a,

18、 b),(a, c),(b, c),(b, d),(c, d),(d, d),R1 = (a, a),(c, a),(c, b),(d, c),S 1?RT = (b,a),(d,c).四证明题1 .证明：P-Q,R-S,PVR蕴涵 QVS(1) PV RP(2) R- PQ(1)(3) P- QPR- QQ(2)(3)(5) Q-RQ(4)(6) R- SPQ-SQ(5)(6)(8) Q V SQ(7)2 .证明：(A-B)-C = (A n B) n C=a n (b n C)=A n (B U C)=A-(B U C)3 .证明： AV B, C一 B, C-D蕴涵 A-D(1)AD(附

19、加)(2) A V BP BQ(1)(2)(4) C- B P(5) B-CQ(4)(6) CQ(3)(5)(8) DQ(6)(9) A - DD(1)(8)所以 AVB, C- B, C-D蕴涵A-D.4.证明：A(APB)=a n (A n B)=An (A UB)=(An -A) u (An -B)=U(AnB)= (AnB)=A B而(AU B)-B=(A U B)n -B=(A nB)U(BnB)=(An -B) u=A - B所以：A (APB) = (A UB)- B.离散数学试题(A卷及答案)一、(10分)某项工作需要派 A、B、C和D 4个人中的2个人去完成，按下面 3个 条

20、件，有几种派法？如何派？(1)若A去，则C和D中要去1个人；(2)B和C不能都去；(3)若C去，则D留下。解 设A: A去工作；B: B去工作；C: C去工作；D: D去工作。则根据题意应有：A C D, (BA C), C D必须同时成立。因此(A C D)A (BA C)A(CD)(AV(CA D)V( CAD)A( BV C)A( CV D)(AV(CAD)V(CAD)A( BAC)V( BAD)VCV( CAD)(AA BAC)V(AA BA D)V(AA C)V (A ACAD)V(CA DA BA C)V(CA DA BA D)V(CA DA C)V(CA D A CA D)V(

21、CADA BA C) V ( CA DA BA D)V ( CA DA C)V ( CA DACA D)FVFV( AA C)VFVFV(CADA B)VFVFV( CADA B) V FV(CAD)VF(AA C) V( BA CA D)V( CADA B)V( CAD)(AA C) V( BA CA D)V( CAD) T故有三种派法：BAD, A AC, AAD。二、(15分)在谓词逻辑中构造下面推理的证明：某学术会议的每个成员都是专家并且是工人，有些成员是青年人，所以，有些成员是青年专家。解：论域：所有人的集合。S(x)： x是专家；W(x)： x是工人；Y(x)： x是青年人；则推理

22、化形式为：x (s(x)A w(x),xY(x)F x (s(x)A y (x)下面给出证明：(1) x Y(x)P(2)Y(c)T(1), ES(3) x(s(x)Aw(x)P5>1><4<5即5( C)A W( c)S( C)(6)S( C)AY(C) x(S(x)A Y(x)T(3), UST(4), IT(2)(5), IT(6) , EG三、(10分)设A、B和C是三个集合，则A B证明：A B x(xCA-xC B)A x(xC BA x A)x(xCAAx B)Ax(x BVx A)四、<2<2(B A)。x(x AVx B)A x(xC BA

23、 x A)x(xC AA x B)Vx(xCAVx B)(x(x C A A x B) Ax(xCAVxB)(x(x AAx B)Ax(xCBfxCA)(B A)。(15 分)设 A=1, 2, 34>, <3, 4>, <4, 4>,4, 5, R是A上的二元关系，且<5, 2>,求 g s(R)和 t(R)0r(R)=RU Ia=<2, 1>, <2, 5> , <2, 4> , <3, 4> ,-1s(R)=RU R =<22>, <4_2R =<2R3 = <2_4R

24、 =<2<41>4><2<55>5><24><34><44>3>2>,1> ，2>,<2<2<24>5>4><3<2<3t(R)=Ri=<2, 1>, <2 i 11> , <5 , 4> , <5 , 5> o五、(10分)R是非空集合证明对任意的x、yCA,4>4>4><4<3<44>4>4><5<4<51>

25、;4>1>,5> , <2 , 4> , <3 , 4> ,<5<5<55>2>5>A上的二元关系，若 R是对称的，则R= <2 ,<5,<5<5<5<52>1> ，<2,2>,<1 ，<12>,4>4>2>, <2,2>,r(R)和t(R)是对称的。若 xr(R)y, M 由 r(R)= RU Ia 得，xRy或 xky。因 R 与 Ia对称,所以有yRx或yLx,于是yr(R)x。所以r(R)是对称的。下证

26、对任意正整数n,Rn对称。2因R对称，则有xRyz(xRzA zRy) z(zRxA yRz) yR2x,所以 R?对称。若 Rn 对称,则 xRn 1yz(xRnzA zRy)z亿RnxAyRz) yRn1x,所以Rn1对称。因此，对任意正整数n, Rn对称。对任意的x、yCA,若xt(R)y,则存在m使彳马xRmy,于是有yRmx,即有yt(R)x。因此，t(R) 是对称的。六、(10分)若f： A-B是双射，则 厂：B一A是双射。证明 因为f: A- B是双射，则l1是B到A的函数。下证 11是双射。对任意xC A,必存在y B使f(x)= y,从而f1(y)=x,所以f1是满射。

27、87; . 、 如,.1.- 1一 .、.、, , » . _,_, . /对任意的 y、y2 B,若 f(y1)=f (y2)=x,则 f(x)= y1，f(x)=y2。因为 f： A-B 是函数，则v1 = W所以f1是单射。综上可得，二B一A是双射。七、(10分)设<$, *>是一个半群，如果 S是有限集，则必存在 aCS,使得a*a=a。证明 因为<S, *>是一个半群，对任意的 bCS,由*的封闭性可知，b2=b*bCS, b3= b2*bes,，bne S,。因为S是有限集，所以必存在j>i,使得bi = bj。令p = j i,则bj=bp

28、*bj。所以对q>i,有 bq= bp*bq0因为p1,所以总可找到k>1,使得kpi。对于bkp CS,有bkp= bp*bkp= bp*(bp*bkp) = = bkp*bkp。令 a= bkp,则 a e S 且 a*a = a。八、(20分)(1)若G是连通的平面图，且 G的每个面的次数至少为l(l>3),则G的边数m与结点数n有如下关系：m< -n (n -2)。r证明 设G有r个面，则2m=d(fi)lr。由欧拉公式得，nm+r= 2。于是，mi 1< (n-2)0l 2(2)设平面图 G=<V, E, F>是自对偶图，则|曰=2(|V|1

29、)。证明 设G*=<V*, E*>是连通平面图 G= <V, E, F>的对偶图，则 G* G,于是旧= |V*| = |V|,将其代入欧拉公式 |V|E|+|F|=2 得，|E|=2(|V|1)。离散数学试题(B卷及答案)一、(10 分)证明(PV Q)A(P R)A(Q S)卜 SV R证明 因为SV R R S,所以，即要证(PV Q)A(P R)A (Q S)卜R S.R附加前提PRP PT(1)(2), I(4)PV QPQT(3)(4), I(6)QSP(7)S(8) R S(9)SV RT(5)(6), ICPT(8), E二、(15分)根据推理理论证明：

30、每个考生或者勤奋或者聪明，所有勤奋的人都将有所作为， 但并非所有考生都将有所作为，所以，一定有些考生是聪明的。设Re)： e是考生，Q(e)： e将有所作为，A(e)： e是勤奋的，B(e)： e是聪明的，个体域：人 的集合，则命题可符号化为：x(P(x) (A(x)V B(x), x(A(x) Q(x), x(P(x) Q(x)l x(P(x)AB(x)o(1) x(P(x) Q(x)P(2) x( P(x)VQ(x)T(1), E(3) x(P(x)A Q(x)T(2), E(4)P(a)A Q(a)T(3), ES(5)P(a)T(4), I(6) Q(a)T(4), I(7) x(P(

31、x) (A(x)VB(x)P(8)P(a) (A(a)V B(a)T(7), US(9)A(a) V B(a)T(8)(5), I(10) x(A(x) Q(x)P(11)A(a) Q(a)T(10), US(12) A(a)T(11)(6), I(13)B(a)T(12)(9), I(14)P(a)A B(a)T(5)(13), I(15) x(P(x)A B(x)T(14), EG三、(10分)某班有25名学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球， 5人会打篮球和网球，还有 2人会打这三种球。而6个会打网球的人都会打另外一种球，求不会 打这三种球的人数。解 设A、B、C

32、分别表示会打排球、网球和篮球的学生集合。则：|A|=12, |B| = 6, |C|=14, |AAC| = 6, |BAC| = 5, |AABAC|=2, |(AUC)AB| = 6o因为 |(AUC)nB| = (AAB)U(BnC)| = |(An B)| + |(BnC)|-|AABnC| = |(AnB)| + 5-2 = 6,所以|(AnB)| = 3。于是 |AUBUC|=12+6+14 6 5 3 + 2 = 20, |A b C|=25 20=5。故，不会 打这三种球的共5人。3四、(10分)设Ai、A2和A3是全集U的子集，则形如 A (A为A或A )的集合称为由Ai、

33、i 1A2和A3产生的小项。试证由 Al、A2和A3所产生的所有非空小项的集合构成全集 U的一个划分。证明 小项共8个，设有r个非空小项s、&、sr(r<8)o对任意的a U,则a A或a W ,两者必有一个成立，取 A为包含元素a的人或可,则a 3 Ai ,即有a r s,于是U r So又显然有r S U,所以U= ' S。 i 1i 1i 1i 1i 1任取两个非空小项 &和Sq,若SpW$,则必存在某个 A和可分别出现在Sp和Sq中，于是SpASq = o综上可知，S1, S2,，Sr是U的一个划分。五、(15分)设R是A上的二元关系，则：R是传递的 R*

34、R Ro证明若R是传递的，则<x,y>GRRz(xRzzSy)xRcAcSy,由R是传递的得xRy即有<x, y> G R,所以 R*R Ro反之，若R*R R,则对彳i意的x、v、zGA,如果xRz且zRy,则vx, y> R*R,于是有vx, y> w R,即有xRy,所以R是传递的。六、(15分)若G为连通平面图，则nm+r=2,其中，n、m、r分别为G的结点数、边 数和面数。证明对G的边数m作归纳法。当m=0时，由于G是连通图，所以G为平凡图，此时n = 1, r= 1,结论自然成立。假设对边数小于m的连通平面图结论成立。下面考虑连通平面图G的边数为m的情况。设e是G的一条边，从G中删去e后得到的图记为G,并设其结点数、边数和面数分别为 n、m和r。对e分为下列情况来讨论：若e为割边，则G有两个连通分支G1和G2。G的结点数、边数和面数分别为 m、mi和。显 然 n1 + n2 = n=n, m + m2= m=m1,门+r + 1 = r+1。由归纳假设有 m m + c = 2, n2 m2+2=2, 从而(n+作)一(m+m2)+(c + r2)=4, n (m 1)+(r+1)=4, 即 n m + r = 2。若e不为割边，则n =n, m = m1, r =r1,由归纳假设有 n -m +r