《离散数学期末试题》由会员分享，可在线阅读，更多相关《离散数学期末试题（6页珍藏版）》请在金锄头文库上搜索。
1、离散数学考试试题(卷及答案)一、（10分）求（PQ)(P(R)）的主析取范式解：(P)（P(QR)（( P）)（PQ）(PQ)(QR)）(PQP)(PQQ)(QR)（Q）(QR)(P（)）(PR)(QR)(PQ)(PQ）二、（分)在某次研讨会的休息时间,3名与会者根据王专家的口音分别作出下述判断:甲说：王专家不是苏州人，是上海人。乙说:王专家不是上海人,是苏州人。丙说：王专家既不是上海人，也不是杭州人。王专家听后说:你们人中有一种全说对了，有一人全说错了,尚有一种人对错各一半。试判断王专家是哪里人?解 设设：王专家是苏州人；:王专家是上海人；R：王专家是杭州人。则根据题意应有:甲:PQ乙:QP
2、丙:QR王专家只也许是其中一种都市的人或者个都市都不是。因此，丙至少说对了一半。因此，可得甲或乙必有一人全错了。又由于，若甲全错了，则有Q,因此，乙全对。同理,乙全错则甲全对。因此丙必是一对一错。故王专家的话符号化为：(PQ)(（Q)(QR)(（QP)（QR）)(PQQR)(PQR)(QQR)(PQ)(QR)T因此,王专家是上海人。三、(0分)证明tsr(R)是涉及R的且具有自反性、对称性和传递性的最小关系。证明 设R是非空集合A上的二元关系,则r(）是涉及R的且具有自反性、对称性和传递性的关系。若是涉及R的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知(）。则r（R）s()，进而有
3、r(R）()=。综上可知，tsr()是涉及R的且具有自反性、对称性和传递性的最小关系。四、(分)集合A=a，b,c，d,e上的二元关系R为R=a,a,，,a，,e,，,d,d，d,e,(1)写出R的关系矩阵。(2）判断是不是偏序关系，为什么?解 (1)R的关系矩阵为：（2）由关系矩阵可知，对角线上所有元素全为1，故R是自反的;+1,故R是反对称的;可计算相应的关系矩阵为:由以上矩阵可知是传递的。五、（10分)设、B、C和D为任意集合，证明(A-B)C=(A)-（C)。证明：由于(-)(B)C（AB)C(AC)(C）()(BC)（A)(BC）(AC)，(BC),(AC)-(B）因此，(A-)(A
4、CBC)。六、(1分)设:A，g:BC,h:CA,证明：如果hogofIA，fohogI,go=I，则f、g、h均为双射,并求出f-、g-和h1。解 因IA恒等函数，由ho可得f是单射，h是满射；因IB恒等函数，由fohog=IB可得g是单射,f是满射；因I恒等函数，由ofoh=IC可得h是单射,g是满射。从而f、h均为双射。由hg=I,得f1hg；由fooIB,得-1fo;由goh=,得h-1=gof。七、（1分）设是一代数系统,运算*满足互换律和结合律，且a*xa*yxy，证明:若G有限,则G是一群。证明 因G有限，不妨设=，,。由axa*yx=y得，若xy，则a*xay。于是可证，对任意
5、的aG,有aGG。又由于运算*满足互换律，因此aG=G。令eG使得*e=a。对任意的bG，令ca=，则b*e(c*)*e=*(a*e)=c*=b,再由运算*满足互换律得e*b=b,因此e是有关运算*的幺元。对任意G，由G=可知，存在bG使得a*b=e，再由运算*满足互换律得b*ae,因此是a的逆元。由的任意性知，G中每个元素都存在逆元。故G是一群。八、（2分)（1)证明在n个结点的连通图中,至少有1条边。证明不妨设G是无向连通图(若为有向图,可略去边的方向讨论相应的无向图)。设G中结点为、。由连通性,必存在与相邻的结点,不妨设它为(否则可重新编号），连接和,得边,还是由连通性，在、中必存在与或
6、相邻的结点，不妨设为,将其连接得边,续行此法，必与、中的某个结点相邻，得新边，由此可见G中至少有n1条边。(2)给定简朴无向图GV，E，且|m,|E|。试证：若n2，则是哈密尔顿图。证明 若n+2，则2nm2-3 （1)。若存在两个不相邻结点、使得d()+()m,则有n=m+（m2)(3)+mm23,与（）矛盾。因此,对于G中任意两个不相邻结点、均有d()+d()m。由定理10.6可知，G是哈密尔顿图。离散数考试试题（卷及答案）一、(分)使用将命题公式化为主范式的措施，证明（Q)(Q)（QP)(PQ)。证明：由于（PQ)（P)（P)（P）（PQ)(P)(QP)(P)（Q)（PQ）(PQ)(Q)
7、(P)(Q）(PQ)(Q)(P(Q)(PQ)(P)（Q)(PQ）(Q) 因此,（Q）（Q)(QP)(PQ)。二、（10分)证明下述推理： 如果A努力工作，那么B或C感到快乐；如果B快乐,那么A不努力工作；如果D快乐那么C不快乐。因此,如果努力工作，则D不快乐。解 设A：努力工作;B、C、D分别表达B、D快乐;则推理化形式为：AB,A,CAD(1)A 附加前提()AB P(3)B T(1)(2)，I（4)BA P(5)AB T（4),E(6)B T(1)(5)，I(7)C T（3)(6)，I(8)D P（9)D T（）(8),I（1)AD CP三、（10分）证明xy(P(x)Q(y)）($xP(
8、x)yQ(y)。x(P(x)Q(y)xy(P（x)（)）(x)yQ(y)xP(x)Q(y)$P(x）yQ(y)($xP（x)(）)四、（分）设A，1,1，B=0,0，求P(）、P（B)-0、P(B）B。解 P（A)=,，1，1,1，1,1，1，1，1P(B）-0，0，0,0，0，0,0,(B）,0，0，0，00,0,0，,0，五、(1分）设，2，3,4，R是X上的二元关系，=，1，,3,3，3,2，,，)=。(1)证明f是单射。(2）证明f是满射。()求逆函数f1。(4)求复合函数f-1f和ff。证明 (1）对任意的x,y，x，1R，若()=(x，y)，则y，x-yRR，令x=,y,则f()，
9、-=，,因此f是满射。（3)f-()。(4）1of()=f(）x，yfof（)=f（f(x,)f(）=。七、（5分)给定群，若对G中任意元和b，有a3*3=(*）3，a4*b(b)4,a5*=(a*b)5，试证是bel群。证明对G中任意元a和。由于*b3(a*b)3，因此*3*b3*(b）3*，即得a2b2(*a)2。同理,由a4b4=(a*b)4可得,a3*3=(*a)3。由a*b5=（a*)5可得，a*b4(*)。于是(a33)*（b*a)=（a)=a4*b4,即4*a=ab4。同理可得，（a*b2)(b*a)(ba）3=a3b，即b3*aa*。由于(a)*b3ab=b4a=b*(b3*)b*(*b)=(*a)*b3,故*b=b*a。八、(15分）（)证明在个结点的连通图G中，至少有n1条边。证明 不妨设G是无向连通图(若G为有向图，可略去边的方向讨论相应的无向图）。设中结点为、。由连通性,必存在与相邻的结点，不妨设它为（否则可重新编号),连接和，得边，还是由连通性，在、中必存在与或相邻的结点，不妨设为,将其连接得边,续行此法，必与、中的某个结点相邻,得新边,由此可见中至少有-1条边。(2)试给出|V|=n，=（n1)(n2)的简朴无向图GV，E是不连通的例子。解 下图满足条件但不连通。
