离散数学模拟题一套及答案

1、离散数学考试(试题及答案)一、(10分)某项工作需要派A、B、C和D4个人中的2个人去完成，按下面3个条件，有几种派法？如何派？若A去，则C和D中要去1个人；(2)B和C不能都去；(3)若C去，则D留下。解设A:A去工彳B:B去工作；C:C去工作；D:D去工作。则根据题意应有：ACD,(BAC),CD必须同时成立。因此(ACD)A(BAC)A(CD)(AV(CAD)V(CAD)A(BVC)A(CVD)(AV(CAD)V(CAD)A(BAC)V(BAD)VCV(CAD)(AABAC)V(AABAD)V(AAC)V(AACAD)V(CADABAC)V(CADABAD)V(CADAC)V(CADAC

2、AD)V(CADABAC)V(CADABAD)V(CADAC)V(CADACAD)FVFV(AAC)VFVFV(CADAB)VFVFV(CADAB)VFV(CAD)VF(AAC)V(BACAD)V(CADAB)V(CAD)(AAC)V(BACAD)V(CAD)T故有三种派法：BAD,AAC,AAD。二、(15分)在谓词逻辑中构造下面推理的证明：某学术会议的每个成员都是专家并且是工人，有些成员是青年人，所以，有些成员是青年专家。解：论域：所有人的集合。S(x):x是专家；W(x):x是工人；Y(x):x是青年人；则推理化形式为：x(S(x)AW(x),xY(x)卜x(S(x)AY(x)下面给出证

3、明：(1)xY(x)P(2)Y(c)T(1),ESx(S(x)AW(x)PS(c)AW(c)T(3),US(5)S(c)T(4),I(6)S(c)AY(c)T(2)(5),I(7)x(S(x)AY(x)T(6),EG三、(10分)设A、B和C是三个集合，则AB(BA)。证明：ABx(xCA-xCB)/x(xCBAxA)x(xAVxCB)Ax(xCBAxA)x(xCAAxB)Ax(xBVxCA)x(xCAAxB)Vx(xCAVxB)(x(xCAAxB)Ax(xCAVxB)(x(xAAxB)Ax(xCBfxCA)(BA)。四、(15分)设A=1,2,3,4,5,R是A上的二元关系，且R=<2

4、,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,求r(R)、s(R)和t(R)。解r(R)=RUIa=<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,1>,<2,2>,<3,3><44><55>s(R)=RUR1=<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2&g

5、t;,<1,2>,<4,2>,<4,3>R2=<2,2>,<2,4>,<3,4>,<4,4>,<5,1>,<5,5>,<5,4>R3=<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<5,4>R4=<2,2>,<2,4>,<3,4>,<4,4>,<5,1>,<5,5>,<5,4>=R2t

6、(R)=R=<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<2,2>,<5,1>,<5,4>,<5,i15>。五、(10分)R是非空集合A上的二元关系，若R是对称的，则r(R)和t(R)是对称的。证明对任意的x、yCA,若xr(R)y,则由(R)=RUIa得，xRy或xlAy。因R与Ia对称，所以有yRx或ylAx,于是yr(R)x。所以r(R)是对称的。下证对任意正整数n,Rn对称。因R对称，则有xR2yz(xRzAzRy)z(zRxAyRz)yR

7、2x,所以R对称。若Rn对称，贝UxRn1yz(xRnzAzRy)z(zRnxAyRz)yRn1x,所以Rn1对称。因此，对任意正整数n,Rn对称。对任意的x、yCA,若xt(R)y,则存在m使得xR，于是有yR”，即有yt(R)x。因此，t(R)是对称的。六、(10分)若f:AfB是双射，则L:BfA是双射。证明因为f:A-B是双射，则r1是B到A的函数。下证r1是双射。对任意xCA,必存在yCB使f(x)=y,从而f1(y)=x,所以r1是满射。对任意的y、y2B,若fT(y1)y2)=x,则f(x)=y1,f(x)=y2。因为f：A-B是函数，则号=乎。所以r1是单射。综上可得，二B-A

8、是双射。七、(10分)设<$,*>是一个半群，如果S是有限集，则必存在aCS,使得a*a=a。证明因为<S,*>是一个半群，对任意的bCS,由*的封闭性可知，b2=b*bCS,b3=b2*bCS,，bnes,。因为S是有限集，所以必存在j>i,使得bi=bjo令p=j-i,则bj=bp*bj。所以对q>i,有bq=bp*bq。因为p>1,所以总可找到21,使得kp>io对于bkpeS,有bkp=bp*bkp=bp*(bp*bkp)=bkp*bkp。令a=bkp,则aCS且a*a=a。八、(20分)(1)若G是连通的平面图，且G的每个面的次数至少为

9、l(l>3),则G的边数m与结点数n有如下关系：mW._L(n2)。1 2rl证明设G有r个面，则2m=d(%)>lr。由欧拉公式得，nm+r=2。于是，m<(niil22)。(2)设平面图G=<V,E,F>是自对偶图，则|E|=2(|V|1)。证明设G*=<V*,E*>是连通平面图G=<V,E,F>的对偶图，则G*G,于是|F|=|V*|=|V|,将其代入欧拉公式|V|E|+|F|=2得，|E|=2(|V|1)。离散数学考试试题(B卷及答案)一、(10分)证明(PVQ)A(PR)A(QS)SVR证明因为SVRRS,所以，即要证(PVQ)A

10、(PR)A(QS)|-RS。(1) R附加前提(2)PRP(3) PT(1)(2),I(4)PVQP(5)QT(3)(4),I(6)QSPST(5)(6),I(8) RSCP(9)SVRT(8),E二、(15分)根据推理理论证明：每个考生或者勤奋或者聪明，所有勤奋的人都将有所作为，但并非所有考生都将有所作为，所以，一定有些考生是聪明的。设P(e)：e是考生，Q(e)：e将有所作为，A(e)：e是勤奋的，B(e)：e是聪明的，个体域：人的集合,则命题可符号化为：x(P(x)(A(x)VB(x),x(A(x)Q(x),x(P(x)Q(x)Lx(P(x)AB(x)。(1) x(P(x) Q(x)(2

11、) x( P(x)VQ(x) x(P(x)A Q(x)P(a)A Q(a)(5)P(a)(6) Q(a) x(P(x) (A(x)VB(x)(8)P(a) (A(a)VB(a)(9)A(a)V B(a)(10) x(A(x) Q(x)(11)A(a) Q(a)(12) A(a)(13)B(a)(14)P(a)A B(a)(15) x(P(x)A B(x)三、(10分)某班有25名学生，其中14PT(1), ET(2), ET(3), EST(4), IT(4), IPT(7), UST(8)(5), IPT(10), UST(11)(6), IT(12)(9), IT(5)(13), IT(1

12、4), EG富球，12人会打排球，6人会打篮球和排球,5人会打篮球和网球，还有2人会打这三种球。而6个会打网球的人都会打另外一种球，求不会打这三种球的人数。解设A、B、C分别表示会打排球、网球和篮球的学生集合。则：|A|=12,|B|=6,|C|=14,|AnC|=6,|BAC|=5,|AnBnC|=2,|（AUC）AB|=6。因为|（auc）nB|=（AAB）u（Bnc）|=|（anb）|+|（bnc）|-|AnbnC|=|（Anb）|+52=6,所以|（AnB）|=3。于是AUBUC|=12+6+14653+2=20,|ABC|=2520=5。故，不会打这三种球的共5人。四、（10分）设A

13、i、A2和A3是全集U的子集，则形如3Ai（Ai为Ai或豆）的集合称为由Ai、A2和i1A3产生的小项。试证由Ai、A2和A3所产生的所有非空小项的集合构成全集U的一个划分。证明小项共8个，设有r个非空小项si、s2、sr（rW8）。对任意的aCU,则aCAi或aeA,两者必有一个成立，取Ai为包含元素a的Ai或H,则aCAi,i1rrrr即有aCs,于是u.1sio又显然有siU,所以U=.s。任取两个非空小项Sp和Sq,若SpWSq,则必存在某个Ai和A分别出现在Sp和Sq中，于是SpASq=。综上可知，S1,S2,，Sr是U的一个划分。五、（15分）设R是A上的二元关系，则：R是传递的R

14、*RRo证明（5）若R是传递的，则<x,y>CR*Rz（xRzAzS»xRcAcSy,由R是传递的得xRy,即有<x,y>£R,所以R*RRo反之，若R*RR,则对任意的x、v、zCA,如果xRz且zRy,贝U<x,y>CR*R,于是有<x,y>CR,即有xRy,所以R是传递的。六、（15分）若G为连通平面图，则nm+r=2,其中，n、m、r分别为G的结点数、边数和面数。证明对G的边数m作归纳法。当m=0时，由于G是连通图，所以G为平凡图，此时n=1,r=1,结论自然成立。假设对边数小于m的连通平面图结论成立。下面考虑连通平面

15、图G的边数为m的情况。设e是G的一条边，从G中删去e后得到的图记为G,并设其结点数、边数和面数分别为n、m和r。对e分为下列情况来讨论：若e为割边，则G有两个连通分支G1和G2。Gi的结点数、边数和面数分别为ni、mi和r%显然n1+n2=n=n,m1+m2=m=m1,口+2=r+1=r+1。由归纳假设有mm1+门=2,n2m2+r2=2,从而（n1+n2）（m1+m2）+（门+2）=4,n（m1）+（r+1）=4,即nm+r=2。若e不为割边，则n=n,m=m1,r=r1,由归纳假设有nm+r=2,从而n-（m1）+r1=2,即nm+r=2。由数学归纳法知，结论成立。七、（10分）设函数g：

16、A-B,f：B-C,则：（1）fg是A到C的函数；（2）对任意的xCA,有fg（x）=f（g（x）o证明（1）对任意的xCA,因为g：A-B是函数，则存在yCB使<x,y>Cg。对于yCB,因f:BfC是函数，则存在zCC使<y,z>Cf。根据复合关系的定义，由<x,y>Cg和<y,z>CR|Hx,z>Cg*f,即<x,z>Cfg。所以Dfg=A。对任意的xCA,若存在y1、y2CC,使得<x,yi>、<x,y2>Cfg=g*f,则存在ti使得<x,ti>Cg且<ti,yi>Cf,

17、存在t2使得<x,t2>Cg且<2,y2>Cf。因为g：AfB是函数，则ti=t2。又因f:B-C是函数，则yi=y2o所以A中的每个元素对应C中惟一的元素。综上可知，fg是A到C的函数。(2)对任意的xCA,由g：A-B是函数，有<x,g(x)>Cg且g(x)CB,又由f：B-C是函数，得<g(x),f(g(x)>Cf,于是<x,f(g(x)>Cg*f=fg。又因fg是A至iJC的函数，则可写为fg(x)=f(g(x)。八、(15分)设<H,*>是<G,*>的子群，定义R=<a,b>|a、bCG且a1*bH,则R是G中的一个等价关系，且aR=aH。证明对于任意aCG,必有a1CG使得a1*a=eH,所以<a,a>CR。若<a,b>CR,则a1*