《离散数学》题库大全及答案

1课程内容涉及1．集合论部分：集合及其运算、支配集、覆盖集、独立集与匹配、带权图及其应用3．代数结构部分：代数系统的基本概念、半群与独异点、群、环与域、格与布尔代数4．组合数学部分：组合存在性定理、基本的计数公式、组合计数方法、组合计数定理离散数学被分成三门课程进行教学，即集合论与图论、代数结构与组合数学、数理逻辑。教学方式以课堂讲授为主,课后有书面作业、通过学校网络教学平台发布课件并进行师生交编辑本段相关文献耿素云.离散数学习题集--数理逻辑与集合论分册.北大出版社，离散数学习题辅导软件命题逻辑教学软件为离散数学领域的经典教材,全世界几乎所有知名的院校都曾经使用本书作为教材.以我个人观点看来,这本书可以称之为离散数学百科.书中不但介绍了离散数学的理论和方法,还有丰富的历史资料和相关学习网站资源.更为令人激动的便是这本书少有的将离散数学理论与应用结合得如此的好.你可以看到离散数学理论在逻辑电路,程序设计,商业和互联网等诸多领域的应用实例.本书的英文版(第六版)当中更增添了相当多的数学和计算机科学家的传记,是计算机科学历史不可多得的参考资料.作为教材这本书配有相当数量的练习.每一章后面还有一组课题,把学生已经学到的计算和离散数学的内容结合在一起进行训练.这本书也是我个人在学习离散数学时读的唯一的英文教材,实为一本值得推荐的好书。2《离散数学》题库答案3、设有下列公式，请问哪几个是永真蕴涵式?()答23456）6、命题“存在一些人是大学生”的否定是(是要死的”的否定是()。38、设个体域为整数集，则下列公式的意义是()。在哪个个体域中为真?()12、永真式的否定是()419、设P={x|(x+1)2<4且xeR},Q={x|5<x2+16且xeR},则下列命题哪个正确()20、下列各集合中，哪几个分别相等()。22、判断下列命题哪个为真?()527、A,B,C是三个集合，则下列哪几个推理正确：-1。6-1。-1。<A,*>中，单位元是()，零元是()。7<A,*>中，单位元是()，零元是()；39、设〈G,*〉是一个群，则43、群<G,*>的等幂元是()，有()个。44、素数阶群一定是()群,它的生成元是()。46、<H,,*>是<G,,*>的子群的充分必要条件是()。答：<H,,*>是群或a，bG，a*bH，a-1H或a,bG，a*b-1H47、群＜A,*＞的等幂元有()个，是()，零元有()个。849、在自然数集N上，下列哪种运算是可结合的？()52、下列哪个偏序集构成有界格()54、设G是一个哈密尔顿图，则G一定是()。956、一个图的哈密尔顿路是一条通过图中()的路。59、n阶无向完全图K的边数是()n263、下面给出的集合中，哪一个不是前缀码()。64、n个结点的有向完全图边数是()，每个结点的度数是()。65、一个无向图有生成树的充分必要条件是()。74、任一有向图中，度数为奇数的结点有(）（）（）（9、P→Q（P视R）喻Q（P喻Q）喻RB提(8)RSCP18）（3）R（12）QS（12）W（710）（13）X（811）（14）W^X（1213）（5）U（34）（5）R（24）（7）Q→S（56）（8）S（27）（9）Q→SCP28）（10）P→(Q→S)CP19）（5）P（34）提提16、PQ，QR，RSP（3）Q（12）17、用真值表法证明PQ(PQ)(QP)PPQPQFFTTFTFFTFFFTTTT（6）B（35）PP喻QQ四、设A,B,C是三个集合，证明：12、(A-B)(A-C)=ABCx(A-B)-C，有xA-B且xC，即xA，xB且xC。从而xA，xB-C，故xA-(B-C)。从而(A-B)-CA-(B-C)15、P(A)P(B)P(AB)（P(S)表示S的幂集）SP(A)P(B)，有SP(A)或SP(B)，所以SA或SB。16、P(A)P(B)=P(AB)（P(S)表示S的幂集）SP(A)P(B)，有SP(A)且SP(B)，所以SA且SB。从而SP(A)且SP(B)，故SP(A)P(B)。即P(AB)P(A)P(B)。(1)xy（xy=1）;(2)xy(xy=1);(4)xy（xy=0）;(6)xy（xy=x）;(7)xyz(x-y=z)（1）A={0,1,2}，B={0,2,4}，R={<x,（2）A={1,2,3,4,5}，B={1,2}，R={<x,y>|2x+y4且xA且yB};（3）A={1,2,3}，B={-3,-2,-1,0,1}，R={<x,y>||x|=|y|且xA且yB};4、对任意集合A,B，证明：若AA=BB，则B=B。222={<a,c,a,c>,<a,c,b,c>,<b,c,a,c>,<b,c,b,c>};,<A,a>,<A,b>}。（3）若AeB，且BeC，则AeC；（4）若AB，且BC，则AC；但AC。BC，但AC。(4)成立。因为AB,且BC，所以AC。AAxAIR，<x,x>R。即xRx，故R是自反的。Ax，yA，若<x,y>R，即<y,x>R-1。：R=R-1，<y,x>R。即yRx，故（1）<x，z>R。(ST)，则由合成关系的定义知yB，使得<x，y>R且R|R|A<10,3>,<10,5>,<5,10>,<4,6>,<6,4>,<4,8>,<8,4>,AR诱导的划分为{{1,5},{2,4},{3,6}}。aaebcdf5,a9},{a2,a6,a10},{a3,a7,a11}。3526子群外，还有{e,a4},{e,a2,a4,a6}。-13352)=b·a4。454vb，ceSkl=ak+lvxeG，因为a是〈G，*〉的生成元，所以存在整数k，使得x=ak。2。a,bSa·b）2=(a·b)·(a·b)=((a·b)·a)·ba,bS，因为（a·b）2=a2·b2，所（1）aA,记b=a*a。因为*是可结合的，故有b*a=(a*a)*a=a*(a*a)=a*b。（2）a,bA,因为由（1a*(a*b*a)=(a*a)*(b*a)=a*(b*a),（3）a,b,cA,（a*b*c）*（a*c）=a*b*c）*a）*c=(a*(b*c)*a)*c且(a*c)*(a*b*c)=a*(c*(a*b*c))=a*(c*(a*b)*c))。故（a*b*c）*（a*c）=(a*(b*c)*a)*c=a*c且(a*c)*(a*b*c)=a*(c*(a*b)*c))=a*c，即（a*b*c）*（a*c）=(a*c)*(a*b*c)。-1)-1=(f(b)-1=(f(b·a))-1=((b·a)-1)--1-1=a-1-142、若群<G,＊>的子群<H,＊>满足|G|＝2|H|，则<H,＊>一定是群<G,＊>-1-1对aG，hC(G)，记b=a·h·a-1。下证bC(G)。因为hC(G)，所以-1-1=h·(a·a-1)=hC(G)。-1•>是<S,•>e•e=e，eT，即T是S的非空子集。va,beT,<S，.>是可交换独异点,：(a.b).(a.b)=((a.b).a).b=(a.(b.a)).b=（a.(a.b)）.b=((a.a).b).b=(a.a).(b.b)=a.b,即a.beT。由于p和m都是正整数，所以p=m。即｜ak|=──。vaeG，由封闭性及|G|=n可知a,a2,…,an,an+1中必有相同的元素，不妨设为m)；r=ak-mq=ak.a-mq=b.(am)-q。meH,且H<G，所以areH。d1nnm则1（4）若h为单一同态，则vaeG1，|h(a)|=|a|。(1)因为h(e).h(e)=h(e.e)=h(e)=e.h(e),所以h(e)=e。(2)va∈G，h(a).h(a-1)=h(a.a-1)=h(e)=e,h(a-1).h(a)=h(a-1.a)=h(e)=e,故h(a-1)=h(a)-1。(3)vc,d∈h(H),二a,b∈H，使得c=h(a),d=h(b)。故c.d=h(a).h(b)设|G|=n，vaeG，则|a|=m。令H={e,a,a2,…,am-1}。a.b=c。同理可得a.c=c.a=b,c.b=b.c=a,b.a=c。是k。-1故a,beG，从而a*beG。有设S关于*的单位元为(a,b)。根据*和单位元的定义，对(x,y)eS,有即ax=x,ay+b=y,xb+y=y对x,yeQ都成立。解得a=1,b=0。即ac=1,ad+b=0,cb+d=0。解得c=-,d=-（4）a∈G，h∈G，a•h•a-1H。1H•aH。(3)(4)类似于（2）(3)的证明。-1•a)=(a•h•a-1)•a。由于a•h•a-1∈H，所以b∈H•a。即a•HH•a。-1)即H•aa•H。63、在半群<G,*>中，若对a,bG，方程a*x=b和y*a=b都有惟一Rb*e=(y*a)*e=y*(a*e)=y*a=b。Le*b=e*(a*x)=(e*a)*x=a*x=b。从而在半群<G,*>中,关于运算*存在单位元，记为e。:d=e。:-1=b-1-1-1eH,b-1eK，即ceKH。从而HK坚KH。vceKH，则存在aeH,beK,使得c=b·a。因为c=（a-1·b-1）-1。-1-1=(a-1=b-1-1对vaeHK，有heH，keK，使得a=h·k。因为a=h·k=(h·k·h-1)·h，且K=(c*b)2*a*bn2=(c*b)2*(a*b)*bn3=(c*b)2*(c*b*a)*bn3=(c*b)3*a*bn3=…=(c*b)n*a,…=b*(a*c)m,69、设(L,≤)是格，若a,b,ceL，a≤b≤c，则70、在布尔代数中，证明恒等式a①(a,*且仅当a=a=…=a。72、在布尔代数中，证明恒等式(a*c)①(a,*b)①(b*c)=(a*c)①(a,*b)((a*c)①(a,*b))*(b*c)=((a*c)*(b*c))①((a,*b)*(b*c))=(a*b*c)①(a,*b*c)=(a①a,)*b*c=1*b*c=b*c,故b*c<(a*c)①(a,*b)，从而(a*c)①(a,*b)①(b*c)=(a*c)①(a,*b)。73、在布尔代数中，证明恒等式(a*b)①(a,*c)①(b,*c)=(a*b)①ca*c<b*d(a*c)*(b*d)=((a*c)*b)*d=(b*(a*c))*d=((b*a)*c)*d=a*(c*d)=a*c，所以a*c<b*d。n10..5.2.1.45.9..9.35..35.(a①b,)*(b①c,)*(c①a,)=(a,①b)*(b,①c)*(c,①a)=(a*b*c)①(a*b*a,)①(a*c,*a,)①(a*c,*c)①(b,*b*c)①(b,*c,*c)①(b,*c,*a,)①(b,*b*a,)=(a*b*c)①(b,*c,*a,)，=(a,*b,*c,)①(a,*b,*a)①(a,*c*c,)①(a,*c*a)①(b*b,*c,)①(b*b,*a)①(b*c*c,)①(<I[a,b]，≤>是<L，≤>的子格。dcba.db.a..c81、格<L,,>是模格a,b,cL，有83、证明：在有补分配格中，每个元素的补元一定惟一。84、设<L,,>是格，则L是分配格当且仅当a,b,cL，有(ab)ca(bc)设L是分配格。对a,b,cL，有85、设<S,,⊙,′,0,1>是一布尔代数，则<S,＋>是一个交换群，其中+，：设T=<V,E>是任一棵树，则|V|=n，且|E|=n-1。veV由欧拉握手定理可得Σdeg(v)=2|E|=2n-2。veVveV解kkkk设|V|=n，则|E|=n-1。由欧拉握手定理可得Σdeg(v)=2|E|=2n-2。veVΣdeg(v)>2n>2n-2。veV由欧拉握手定理可得Σdeg(v)=2|E|=2n-2。veVΣdeg(v)>2(n-1)+1>2n-2,veV则m<k(n-2)／(k-2)。由已知对任一feF,deg(f)>k。feFk所以m<k(n-2)／(k-2)。由公式Σdeg(f)=2|E|可得fF2记|V|=n,|E|=m,|F|=k。由欧拉握手定理得Σdeg(v)=2|E|得5n<2m。所以对每个面f,deg(f)3。fF-6。:feF3:|E|<3|V|－6。feF,d(f)=3。所以对任一feF，deg(f)之3。再由公式Σdeg(f)=2|E|，Σdeg(f)=24。feFfeF101、设G=<V,E>是n个顶点的无向图(n>2)，若对任意u,veV，有而G中的任一顶点至多只和G中的顶点邻接。任取ueV(G),veV(G),这20人围成一圆桌入席。有没有可能使任意相邻而坐的两个人都是朋1A3=||，A4=||1..v4.v2.v.v31.....bd.e.f在这个无向图中d(a)=3,d(b)=6,d(c)=4,d(d)=3,d(e)=0,d(f)=0。befefa•bd•e•f106、求下列无向图的子图、生成子图、由边集诱导的子图和由顶点cbdaabdbbc由边集{(a,b),(a,c),(a,d),(b,ddafbf●••d•a471c•b••f•3164324v5Sl(v2)l(v3)l(v4)l(v5)l(v6)tl(t){v1}34v23v34v56v47v69ddaebc则0|0|00000002004|||||||||0430001ΣiiΣdeg(v)=2|E|vEV可得2|E|=k+4+3+12=k+19。再由于它是一棵树，故1