离散数学试题及答案

1、离散数学考试试题(A卷及答案)一、(10分)某项工作需要派A、B、C和D4个人中的2个人去完成，按下面3个条件，有几种派法？如何派？若A去，则C和D中要去1个人；B和C不能都去；若C去，则D留下。解设A：A去工作；B：B去工作；C：C去工作；D：D去工作。则根据题意应有：AtCD,(BAC)，C,d必须同时成立。因此(ACD)A,(BAC)A(C,D)OGAV(CA,D)V(,CAD)A(,BV,C)A(,CV,D)o(W(CA,D)V(,CAD)A(,BA,C)V(,BA,D)V,CV(,CA,D)o(-AA,BA,C)V(-AA,BA,D)V(-AA,C)V(-AA,CA,D)V(CA,D

2、A,BA,C)V(CA,DA,BA,D)V(CA,DA,C)V(CA,DA,CA,D)V(,CADA,BA,C)V(,CADA,BA,D)V(,CADA,C)V(,CADA,CA,D)oFVFVGAA,C)VFVFV(CA,DA,B)VFVFV(,CADA,B)VFV(,CAD)VFo(-AA,C)V(,BACA,D)V(,CADA,B)V(,CAD)o(-AA,C)V(,BACA,D)V(,CAD)OT故有三种派法：BAD，AAC，AAD。二、(15分)在谓词逻辑中构造下面推理的证明：某学术会议的每个成员都是专家并且是工人，有些成员是青年人，所以，有些成员是青年专家。解：论域：所有人的集合。

3、S(x)：x是专家；W(x)：x是工人；Y(x)：x是青年人；则推理化形式为：x(S(x)AW(x)，xY(x)卜x(S(x)AY(x下面给出证明：(1)xY(x)P(2)Y(c)T(1)，ES(3)x(S(x)AW(x)P(4)S(c)AW(c)T(3)，US(5)S(c)T(4)，I(6)S(c)AY(c)T(2)(5)，I(7)xS(x)AY(x)T(6)，EG三、(10分)设A、B和C是三个集合，则AuBn,(Bu4)。证明：AuBox(x丘AxWB)Ax(xWBAx笑A)ox(x笑AVxWB)Ax(xWBAx笑A)3x(xAAxB)AVx(xBVxWA)一3x(xAAxB)ViVx(

4、xAVx笑B)i(,x(xWAAxgB)AVx(xWAVx笑B)o(,x(xWAAxB)AVx(xWB_xWA)(BcA)。四、(15分)设A=1,2,3,4,5,R是A上的二元关系，且R=2,1，2,5，2,4，3,4，,求r(R)、s(R)和t(R)。解r(R)=RUT=2,1，,1,1，,3,A3,4,4,5,5s(R)=RUR-i=,4,3R2=2,2,2,4,3,4,4,4,5,i,5,5,5,4R3=2,i,2,5,2,4,3,4,4,4,5254R4=2,2,2,4,3,4,4,4,5,i,5554=R2t(R)=Ri=2,i,2,5,2,4,3,4,4,4,5,2,2,2,5,

5、i,5,4,i,使得bi=bj。令p=j-i,则bj=bp*bj。所以对q三i,有bq=bp*bq。因为pi,所以总可找到k2i,使得kp三i。对于bkpWS,有bkp=bp*bkp=bp*(bp*bkp)=bkp*bkp。令a=bkp,贝9aS且a*a=a。八、(20分)(1)若G是连通的平面图，且G的每个面的次数至少为1(123)，则G的边数m与结点数n有如下关系：mW(n2)。l2证明设G有r个面，贝92m=工d(f)三lr。由欧拉公式得，nm+r=2。于是，mW(nil2i,12)。(2)设平面图G=是连通平面图G=V,E，F的对偶图，则G*仝G,于是|F|=|V*|=|V|,将其代入

6、欧拉公式Iv|e|+|f|=2得，|E|=2(|v|i)。离散数学考试试题(B卷及答案)一、(10分)证明(PVQ)A(PR)A(QS)4SVR证明因为SVRo,RS,所以，即要证(PVQ)A(PR)A(QS)4,RS。(1)，R附加前提(2)PRP(3)，PT(1)(2)，I(4)PVQP(5)QT(3)(4)，I(6)QSP(7)ST(5)(6)，I(8),RSCP(9)SVRT(8)，E二、(15分)根据推理理论证明：每个考生或者勤奋或者聪明，所有勤奋的人都将有所作为，但并非所有考生都将有所作为，所以，一定有些考生是聪明的。设P(e)：e是考生，Q(e)：e将有所作为，A(e)：e是勤奋

7、的，B(e)：e是聪明的，个体域：人的集合则命题可符号化为：Vx(P(x)(A(x)VB(x),Vx(A(x)Q(x),Vx(P(x)Q(x)卜x(P(x)AB(x)o(1),Vx(P(x)Q(x)P(2),Vx(,P(x)VQ(x)T(1)，Ex(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)Vx(P(x)(A(x)VB(x)P(8)P(a)(A(a)VB(a)T(7)，US(9)A(a)VB(a)T(8)(5)，I(10)Vx(A(x)Q(x)P(11)A(a)Q(a)T(10)，US(12T(a)T(1

8、1)(6)，I(13)B(a)T(12)(9)，I(14)P(a)AB(a)T(5)(13)，I(15)x(P(x)AB(x)T(14)，EG三、(10分)某班有25名学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。而6个会打网球的人都会打另外一种球，求不会打这三种球的人数。解设A、B、C分别表示会打排球、网球和篮球的学生集合。则：IAI=12,IBI=6,ICI=14,IAnCI=6,IBnCI=5,IAnBnCI=2,l（AUC）HBI=6。因为I（Auc）nBI=（AnB）u（Bnc）I=I（AnB）I+I（Bnc）IiAnBnci

9、=I（AnB）I+52=6,所以I（AnB）I=3o于是IAUBUCI=12+6+14653+2=20,IaBCI=2520=5。故，不会打这三种球的共5人。四、（10分）设AA2和A3是全集U的子集，则形如什A,（A,为A,或）的集合称为由AA2和TOC o 1-5 h zi1iA3产生的小项。试证由AA2和A3所产生的所有非空小项的集合构成全集U的一个划分。证明小项共8个，设有r个非空小项ss2、sr（rW8）。对任意的aWU,则aA.或aA，两者必有一个成立，取A.，为包含元素a的A.或,则aW介A/,iiiiii1i即有aWOs，于是U,Os。又显然有$,所以U=Us,。i1i1i1i

10、1任取两个非空小项s和s,若sMs,则必存在某个A,和A分别出现在s和s中，于是sns=0opqpqpqpq综上可知，s1，s2，sr是U的一个划分。五、（15分）设R是A上的二元关系，贝9：R是传递的R*R,R。证明若R是传递的，则vx,yWR*Rmz（xRzAzSy）xRcAcSy,由R是传递的得xRy,即有WR，所以R*R,R。反之，若R*R,R，则对任意的x、y、zWA,如果xRz且zRy,则WR*R，于是有vx,yWR,即有xRy,所以R是传递的。六、（15分）若G为连通平面图，则nm+r=2,其中，n、m、r分别为G的结点数、边数和面数。证明对G的边数m作归纳法。当m=0时，由于G

11、是连通图，所以G为平凡图，此时n=1,r=1,结论自然成立。假设对边数小于m的连通平面图结论成立。下面考虑连通平面图G的边数为m的情况。设e是G的一条边，从G中删去e后得到的图记为G,并设其结点数、边数和面数分别为n、m，和ro对e分为下列情况来讨论：若e为割边，则G有两个连通分支G1和G2oG,的结点数、边数和面数分别为叫、m,和厂广显然n1+n2=n=n,m1+m2=m=m1,r1+r2=r+1=r+1。由归纳假设有n1m1+r1=2,n2m2+r2=2,从而(幻+勺)一从而(幻+勺)一(m1+m2)+(r1+r2)=4.n(m1)+(r+1)=4,即nm+r=2。若e不为割边，则n=n,

12、m=m1,r=r1,由归纳假设有nm+r=2,从而n(m1)+r1=2,即nm+r=2。由数学归纳法知,结论成立。七、（10分）设函数g：AfB,fBC，贝y：（1）f，g是A到C的函数；(2)对任意的xA,有fg(x)=fg(x)。证明(1)对任意的xA,因为g：AfB是函数，则存在yB使Wg。对于yB,因f：BC是函数，贝9存在zC使Ef。根据复合关系的定义，由vx,yg和vy,zEf得g*f,即Wfog。所以Dfg=A。对任意的xA,若存在yy2C，使得efg=g*f,则存在“使得vx,t/Wg且wf,存在t2使得vx,t产g且vt2,y2wf。因为g：AB是函数，则t1=t2o又因fB

13、C是函数，则y1=y2。所以A中的每个元素对应C中惟一的元素。综上可知，fg是A到C的函数。(2)对任意的xWA,由g：AB是函数，有vx,g(x)Wg且g(x)WB,又由f：BC是函数，得vg(x),f(g(x)Wf,于是vx,fg(x)Wgf=fg。又因fg是A到C的函数，则可写为fg(x)=f(g(x)o八、(15分)设vH,*是vG,*的子群，定义R=va,bla、bWG且a-i*bH,则R是G中的一个等价关系，且aR=aH。证明对于任意aWG,必有a-iWG使得a-i*a=eH,所以va,aWR。若va,bWR,则a-i*bWH。因为H是G的子群，故(a-i*b)-i=b-i*aWH

14、。所以vb,aWR。若va,bWR,vb,cWR,则a-i*bWH,bT*cWH。因为H是G的子群，所以(a-i*b)*(b-i*c)=at*cWH,故va,cWR。综上可得，R是G中的一个等价关系。对于任意的bWaR,有va,bWR,a-1*bWH,则存在hWH使得a-i*b=h,b=a*h,于是bWaH,aRaH。对任意的bWaH,存在hWH使得b=a*h,a-i*b=hWH,va,bWR,故aHaR。所以，aR=aH。发到哪？给个邮箱啊一、填空20%(每小题2分)1设(N：自然数集，E-+正偶数)则A,B,C表示三个集合，文图中阴影部分的集合表达式为设P,Q的真值为0,R,S的真值为1,

15、贝V的真值=。公式的主合取范式为O若解释I的论域D仅包含一个元素，则在I下真值为O设A=1，2，3，4，A上关系图为则R2=7设A=a,b,c,d，其上偏序关系R的哈斯图为则R=8图的补图为。9设A=a,b,c,d,A上二元运算如下：*abcdabcdabcdTOC o 1-5 h zbcdacdab,它们的逆,它们的逆那么代数系统vA,*的幺元是，有逆元的元素为元分别为。10下图所示的偏序集中,是格的为二、选择20%（每小题2分）1、下列是真命题的有（）A；B；C；D。2、下列集合中相等的有（）A4,3；B,3,4；C4,3,3；D3,43、设A=1,2,3,则A上的二元关系有（）个。A23

16、；B32；C；D。4、设R,S是集合A上的关系，则下列说法正确的是（）若R,S是自反的，则是自反的；若R,S是反自反的，则是反自反的；若R,S是对称的，则是对称的；若R,S是传递的，则是传递的。5、设A=1,2,3,4,P（A）（A的幂集）上规定二元系如下则P（A）/R=（）AA；BP（A）；C1，1，2，1，2，3，1，2，3，4；D，2，2，3，2，3，4，ATOC o 1-5 h z6、设A=,1,1,3,1,2,3则A上包含关系“”的哈斯图为（）7、下列函数是双射的为（）Af:IE,f（x）=2x；Bf:NNN,f（n）=；Cf:RI,f（x）=x；Df:IN,f（x）=|x|。（注：

17、I-整数集，E-偶数集，N-自然数集，R-实数集）&图中从v1到v3长度为3的通路有（）条。A0；B1；C2；D3。9、下图中既不是Eular图，也不是Hamilton图的图是（）10、在一棵树中有7片树叶,3个3度结点,其余都是4度结点则该树有（）个4度结点。A1；B2；C3；D4。三、证明26%1、R是集合X上的一个自反关系，求证：R是对称和传递的，当且仅当和在R中有v.b,c在R中。（8分）2、f和g都是群到vG2,*的同态映射，证明是的一个子群。其中C=（8分）3、G=vV,E（|V|=v,|E|=e）是每一个面至少由k（k3）条边围成的连通平面图，则,由此证明彼得森图（Peterso

18、n）图是非平面图。（11分）四、逻辑推演16%用CP规则证明下题（每小题8分）1、2、五、计算18%1、设集合A=a,b,c,d上的关系R=va,b,vb,a,vb,c,vc,d用矩阵运算求出R的传递闭包t（R）。（9分）2、如下图所示的赋权图表示某七个城市及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。（9分）试卷一答案：一、填空20%（每小题2分）1、0，1，2，3，4，6；2、；3、1；4、；5、1；6、v1,1,v1,3,v2,2,v2,47、va.b,va,c,va,d,vb,d,vc,dIA；8、9、a；a,b,c,d；a,d,c,d；10、c;二、选择20%（每小题2分）题目12345678910答案CDB、CCADCADBA三、证明26%1、证：JJ若由R对称性知，由R传递性得JJ若，有任意，因若所以R是对称的若，则即R是传递的。2、证，有，又是的子群。3、证：设G有r个面，则，即。而故即得。（8分）彼得森图为，这样不