离散数学期末试题

百度文库-让每个人平等地提升自我百度文库-让每个人平等地提升自我离散数学考试试题(A卷及答案)一、(10分)求(PQ)(P八(QVR))的主析取范式解：(PQ)(PA(QVR)) ((PVQ))V(PAQAR))(PVQ)V(PAQAR))/ (PVQVP)A(PVQVQ)A(PVQVR)(PVQ)A(PVQVR) \(PVQV(RAR))A(PVQVR)\/ (PVQVR)A(PVQVR)A(PVQVR)M0AMi \m2Vm3Vm4Vm5Vm6Vm7二、(10分)在某次研讨会的休息时间， 3名与会者根据王教授的口音分别作出下述判断：,\甲说：王教授不是苏州人，是上海人。乙说：王教授不是上海人，是苏州人。丙说：王教授既不是上海人，也不是杭州人。王教授听后说：你们3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。试判断王教授是哪里人？解设设P:王教授是苏州人；Q:王教授是上海人；R:王教授是杭州人。则根据题意应有：甲：PAQ'乙：QAP丙:\QAR王教授只可能是其中一个城市的人或者 3个城市都不是。所以，丙至少说对了一半。因此，可得甲或乙必有一人全错了。又因为，若甲全错了，则有QAP,因此，乙全对。同理，乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为：TOC\o"1-5"\h\z((PAQ)A((QAR)V(QAR)))V((QAP)A(QAR)) /(PAQAQAR)V(PAQAQAR)V(QAPAQAR) /(PAQAR)V(PAQAR)PAQAR\ /T因此，王教授是上海人。三、(10分)证明tsr(R)是包含R的且具有自反性、对称性和传递性的最小关系。证明设R是非空集合A上的二元关系，则tsr(R)是包含R的且具有自反性、对称性和传递性的关系。若R’是包含R的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知 r(R)R'o则

sr(R)s(R)=R,进而有tsr(R)t(R)=R。综上可知，tsr(R)是包含R的且具有自反性、对称性和传递性的最小关系。四、(15分)集合A={a,b,c,de}上的二元关系R为R={<a,a>,<a,b>,<a,c>,<a,d>,四、(15分)集合A={a,b,c,de}上的二元关系R为R={<a,a>,<a,b>,<a,c>,<a,d>,<a,e>,<b,b>,<b,c>,<be>,<c,c>,<c,<ce>,<d,d>,<d,e>,<e,e>},(1)写出R(1)写出R的关系矩阵。(2)判断R是不是偏序关系，解(1)R的关系矩阵为：为什么?计算对应的关系矩阵为:M(R)(2)由关系矩阵可知，对角线上所有元素全为1,故R是自反的；rij计算对应的关系矩阵为:M(R)(2)由关系矩阵可知，对角线上所有元素全为1,故R是自反的；rij+rji<1,故R是反对称的；可由以上矩阵可知R是传递的。02M(R由以上矩阵可知R是传递的。02M(R2) 001M(R)1五、(10分)设五、(10分)设A、B、C和D为任意集合，证明(A—B)XC=(AXC)—(BXC)。(X(X(x(X<X<X€AA€AAXB)Ay€CyeCAXB)(X(X(x(X<X<X€AA€AAXB)Ay€CyeCAXB)V(Xy€C)a(xbvyy€C)A(X€BA€AAy€CAyc)C)yCC),y>e(AXC)A<X,y>(BXC),y>€(AXC)-(BXC)所以，(A—B)XC=(AXC—BXC)。证明：因为<x,y>C(A—B)XCxC(A—B)AyCCfhg=Ib,gfh=Ic,贝Uf、六、(10分)设f:AB,g:BC,h:%CA,证明：如果hgf=Ia,g、h均为双射，并求出fhg=Ib,gfh=Ic,贝Uf、解因Ia恒等函数，由hgf=lA可得f是单射，h是满射；因Ib恒等函数，由fhg=lB可得g是单射，f是满射；因IC恒等函数，由gfh=Ic可彳#h是单射，g是满射。从而f、g、h均为双射。由hgf=E,得f=hg；由fhg=IB,得g=fh；由gfh=k,得h=gf。七、(15分)设<G,*>是一代数系统，运算*满足交换律和结合律，且a*x=a*yx=y,证明：若G有限，则G是一群。 / \证明因G有限，不妨设G={a1,a2，…，an}。由a*x=a*yx=y得，若xwy,则a*xwa*y。于是可证，对任意的aCG,有aG=Go又因为运算*满足交换律，所以aG=G=Ga。令eCG使得a*e=a。对任意的bCG,令c*a=b,则b*e=(c*a)*e=c*(a*e)=c*a=b,再由运算*满足交换律得e*b=b,所以e是关于运算*的幺元。对任意aCG,由aG=G可知，存在bCG使得%a*b=e,再由运算*满足交换律得b*a=e,所以b是a的逆元。由a的任意性知，G中每个元素都存在逆元。故G是一群。八、(20分)(1)证明在n个结点的连通图G中，至少有n-1条边。证明不妨设G是无向连通图(若G为有向图，可略去边的方向讨论对应的无向图)、。设G中结点为V1、V2、…、环。由连通性，必存在与V1相邻的结点，不妨设它为V2(否则可重新编号)，连接V］和V2,得边6| ,还是由连通性，在 V3、V4、…、Vn中必存在与W或V2相邻的结点，不妨设为V3,将其连接得边比,续行此法，Vn必与V、V2、…、Vn1中的某个结点相邻，得新边91,由此可见G中至少有n—1条边。 \(2)给定简单无向图G=<V,E>,且|V|=m,|E|=n。试证：若n>41+2,则G是哈密尔顿图。证明若nAa1+2,则2nAm2-3m+6 (1)。2右存在两个不相邻结点u、v使彳导d(u)+d(V)vm,则有2n=d(w)vm+(m—2)(m—3)+m=m—wV3m+6,与(1)矛盾。所以，对于G中任意两个不相邻结点u、v都有d(u)+d(v)>m。由定理可知，G是哈密尔顿图。离散数考试试题（B卷及答案）、（10、（10分）使用将命题公式化为主范式的方法，证明(PQ)\(PAQ)(QP)A(PVQ)。证明：因为(PQ)(PAQ) (PVQ)V(PAQ)证明：因为(PQ)(PAQ) (PVQ)V(PAQ)(Q(PAQ)V(PAQ)P)A(PVQ)(QVP)A(PVQ)(PA(PAQ)VP(PA(PA(PAQ)V(PA(QVQ))Q)V(PAQ)V(PAQ)Q)V(PAQ)Q)V(QAQ)V(PAP)V(PAQ)(Q(PAQ)V(PAQ)P)A(PVQ)(QVP)A(PVQ)(PA(PAQ)VP(PA(PA(PAQ)V(PA(QVQ))Q)V(PAQ)V(PAQ)Q)V(PAQ)Q)V(QAQ)V(PAP)V(PAQ)所以,(PQ)(PAQ)(QP)A(PVQ)o所以,二、（10分）证明下述推理： 如果A努力工作，那么B或C感到愉快；如果B愉快，那么A不努如果D愉快那么C不愉快。所以，如果A努力工作，则D不愉快。力工作;解BVC,BA设A:A努力工作;B、C、DC1AD分别表示B、C、D愉快；则推理化形式为:附加前提(2)ABVCBVCT(1)(2)如果D愉快那么C不愉快。所以，如果A努力工作，则D不愉快。力工作;解BVC,BA设A:A努力工作;B、C、DC1AD分别表示B、C、D愉快；则推理化形式为:附加前提(2)ABVCBVCT(1)(2)(5)(6)BT(1)(5)T(4),ET(3)(6)(8)(9)T(7)(8)(10)ACP、（10分）证明xy(P(x)Q(y))(xP(x)yQ(y))。xy(P(x)Q(y))xy(P(x)VQ(y))P(x)VyQ(y))xy(P(x)Q(y))xy(P(x)VQ(y))P(x)VyQ(y))x(P(x)VyQ(y)xP(x)VyQ(y)

(xP(x)四、(10分)设A={1,{1}},yQ(y))B={0,{0}},求P(A)、P(B)—{0}、P(B)B。解P(A)={{1},{{1}},{,1},{J{1}},{1，{1}},{,1,{1}}}P(B)—{0}={，{0}{{0}}，{0{0}}—{0}={d{0},{{0}}{0{0}}P(B)B={，五、(15分)设{0}，{{0}}X={1<3,2>,<4,3>,<4,1>,<4(1)画出R的关系图。(2)写出R的关系矩阵。(xP(x)四、(10分)设A={1,{1}},yQ(y))B={0,{0}},求P(A)、P(B)—{0}、P(B)B。解P(A)={{1},{{1}},{,1},{J{1}},{1，{1}},{,1,{1}}}P(B)—{0}={，{0}{{0}}，{0{0}}—{0}={d{0},{{0}}{0{0}}P(B)B={，五、(15分)设{0}，{{0}}X={1<3,2>,<4,3>,<4,1>,<4(1)画出R的关系图。(2)写出R的关系矩阵。(3)说明R是否是自反、，{0,{0}} {0,{0}}={3,4},R是X上的二元关系,2>,<1,2>}反自反、对称、传递的。R的关系图如图所示:(2)R的关系矩阵为:0,{{0}}R={<1{01>,{0}}<3,1>,<1,3>,<3,3>,M(R)⑶对于R的关系矩阵,由于对角线上不全为R不是自反的；由于又扪t线上存在非 0元，R不是反自反的；由于矩阵不对称,R不是对称的;经过计算可得M(R2)0M(R),所以0R是传递的。六、(15分)设函数f:RXRRXR,f定义为：f(<x,y>)=<x+y,x—y>。(2)证明f是满射。(3)求逆函数f1o1 X(4)求复合函数ff和ff。Xi—y1>,证明(1)对任意的x,y,Xi,y1CR,若f(<x,y>)=f(<X1,y>),贝U<x+y,x-y>=<X1+y1x+y=x1+y1,x-y=x1-y1,从而x=x1,y=y1,故fXi—y1>,uwuw uw,uw(2)对任，国的<u,w>CRXR,令x= ,y= ,则f(<x,y>)=< + u—w>=<u,w>,所以f是满射。2，…1, 、uwuwTOC\o"1-5"\h\zf(<u,w>)=< , >。,八「1 I,一 、、 「1, , 、、xyxyxy(xy)ff(<x,y>)=f(f(<x,y>))=f(<x+y,x-y>)=< , ->=<x,y>Z\ 2 2ff(<x,y>)=f(f(<x,y>))=f(<x+y,x-y>)=<x+y+x-y,x+y—(x—y)>=<2x,2y>。七、(15分)给定群<G,*>,若对G中任意元a和b,有a3*b3=(a*b)3,a4*b4=(a*b)4,a5*b5=(a*b)5,试证<G,*>是Abel群。 \证明对G中任意元a和bo因为a3*b3=(a*b)3,所以a1*a3*b3*b1=a1*(a*b)3*b1,即得a2*b2=(b*a)2。同理，由a4*b4=(a*b)4可得，a3*b3=(b*a)3。由a5*b5=(a*b)5可得，a4*b4=(b*a)4。于是(a3*b3)*(b*a)=(b*a)4=a4*b4,即b4*a=a*b4。同理可得，(a2*b2)*(b*a)=(b*a)3=a3*b3,即TOC\o"1-5"\h\zb3*a=a*b3。 \由于(a*b)*b3=a*b4=b4*a=b*(b3*a)=b*(a*b3)=(b*a)*b3,故a*b=b*a。 \八、(15分)(1)证明在n个结点的连通图G中，至少有n-1条边。证明