




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
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*
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 中国松香精项目投资计划书
- 佳木斯市人民医院甲状腺癌根治术主刀医师资质评审考核
- 鄂尔多斯市中医院护士长职业发展规划考核
- 北京市人民医院结石成因分析考核
- 长治市人民医院护理管理与卫生经济学交叉知识试题
- 鄂尔多斯市中医院骨折术后康复方案制定考核
- 黑河市人民医院胃肠镜报告书写考核
- 2025年中国顺酐项目创业计划书
- 中国粉针剂项目投资计划书
- 小学生英文绘本阅读教案
- 水电工安全知识培训课件
- 2025 SMETA员工公平职业发展管理程序-SEDEX验厂专用文件(可编辑)
- 卫生法律法规试题题库(附答案)
- A1技术环境下教学数据分析方案
- 压缩机基础知识培训课件
- 危险作业安全知识培训
- OJT基础知识培训课件
- 2025年质量管理体系内审员培训考试卷及答案
- 产褥期间质性乳腺炎的护理查房
- 危险品航空运输知识考核试题及答案
- 油田专家管理办法
评论
0/150
提交评论