1离散数学考试试题(A卷及答案)一、(10分)求(PQ)(P∧(Q∨R))的主析取范式解:(PQ)(P∧(Q∨R))((P∨Q))∨(P∧Q∧R))(P∨Q)∨(P∧Q∧R))(P∨Q∨P)∧(P∨Q∨Q)∧(P∨Q∨R)(P∨Q)∧(P∨Q∨R)(P∨Q∨(R∧R))∧(P∨Q∨R)(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)0M∧1M2m∨3m∨4m∨5m∨6m∨7m二、(10分)在某次研讨会的休息时间,3名与会者根据王教授的口音分别作出下述判断:甲说:王教授不是苏州人,是上海人。乙说:王教授不是上海人,是苏州人。丙说:王教授既不是上海人,也不是杭州人。王教授听后说:你们3人中有一个全说对了,有一人全说错了,还有一个人对错各一半。试判断王教授是哪里人?解设设P:王教授是苏州人;Q:王教授是上海人;R:王教授是杭州人。则根据题意应有:甲:P∧Q乙:Q∧P丙:Q∧R王教授只可能是其中一个城市的人或者3个城市都不是。所以,丙至少说对了一半。因此,可得甲或乙必有一人全错了。又因为,若甲全错了,则有Q∧P,因此,乙全对。同理,乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为:((P∧Q)∧((Q∧R)∨(Q∧R)))∨((Q∧P)∧(Q∧R))(P∧Q∧Q∧R)∨(P∧Q∧Q∧R)∨(Q∧P∧Q∧R)(P∧Q∧R)∨(P∧Q∧R)P∧Q∧RT因此,王教授是上海人。三、(10分)证明tsr(R)是包含R的且具有自反性、对称性和传递性的最小关系。证明设R是非空集合A上的二元关系,则tsr(R)是包含R的且具有自反性、对称性和传递性的关系。若'R是包含R的且具有自反性、对称性和传递性的任意关系,则由闭包的定义知r(R)'R。则2sr(R)s('R)='R,进而有tsr(R)t('R)='R。综上可知,tsr(R)是包含R的且具有自反性、对称性和传递性的最小关系。四、(15分)集合A={a,b,c,d,e}上的二元关系R为R={a,a,a,b,a,c,a,d,a,e,b,b,b,c,b,e,c,c,c,d,c,e,d,d,d,e,e,e},(1)写出R的关系矩阵。(2)判断R是不是偏序关系,为什么?解(1)R的关系矩阵为:1000011000101001011011111)(RM(2)由关系矩阵可知,对角线上所有元素全为1,故R是自反的;ijr+jir≤1,故R是反对称的;可计算对应的关系矩阵为:)(1000011000101001011011111)(2RMRM由以上矩阵可知R是传递的。五、(10分)设A、B、C和D为任意集合,证明(A-B)×C=(A×C)-(B×C)。证明:因为x,y∈(A-B)×Cx∈(A-B)∧y∈C(x∈A∧xB)∧y∈C(x∈A∧y∈C∧xB)∨(x∈A∧y∈C∧yC)(x∈A∧y∈C)∧(xB∨yC)(x∈A∧y∈C)∧(x∈B∧y∈C)x,y∈(A×C)∧x,y(B×C)x,y∈(A×C)-(B×C)所以,(A-B)×C=(A×C-B×C)。六、(10分)设f:AB,g:BC,h:CA,证明:如果hgf=IA,fhg=IB,gfh=IC,则f、g、h均为双射,并求出f-1、g-1和h-1。解因IA恒等函数,由hgf=IA可得f是单射,h是满射;因IB恒等函数,由fhg=IB可得g是单射,f是满射;因IC恒等函数,由gfh=IC可得h是单射,g是满射。从而f、g、h均为双射。由hgf=IA,得f-1=hg;由fhg=IB,得g-1=fh;由gfh=IC,得h-1=gf。3七、(15分)设G,*是一代数系统,运算*满足交换律和结合律,且a*x=a*yx=y,证明:若G有限,则G是一群。证明因G有限,不妨设G={1a,2a,…,na}。由a*x=a*yx=y得,若x≠y,则a*x≠a*y。于是可证,对任意的a∈G,有aG=G。又因为运算*满足交换律,所以aG=G=Ga。令e∈G使得a*e=a。对任意的b∈G,令c*a=b,则b*e=(c*a)*e=c*(a*e)=c*a=b,再由运算*满足交换律得e*b=b,所以e是关于运算*的幺元。对任意a∈G,由aG=G可知,存在b∈G使得a*b=e,再由运算*满足交换律得b*a=e,所以b是a的逆元。由a的任意性知,G中每个元素都存在逆元。故G是一群。八、(20分)(1)证明在n个结点的连通图G中,至少有n-1条边。证明不妨设G是无向连通图(若G为有向图,可略去边的方向讨论对应的无向图)。设G中结点为1v、2v、…、nv。由连通性,必存在与1v相邻的结点,不妨设它为2v(否则可重新编号),连接1v和2v,得边1e,还是由连通性,在3v、4v、…、nv中必存在与1v或2v相邻的结点,不妨设为3v,将其连接得边2e,续行此法,nv必与1v、2v、…、1nv中的某个结点相邻,得新边1ne,由此可见G中至少有n-1条边。(2)给定简单无向图G=V,E,且|V|=m,|E|=n。试证:若n≥21mC+2,则G是哈密尔顿图。证明若n≥21mC+2,则2n≥m2-3m+6(1)。若存在两个不相邻结点u、v使得d(u)+d(v)<m,则有2n=Vwwd)(<m+(m-2)(m-3)+m=m2-3m+6,与(1)矛盾。所以,对于G中任意两个不相邻结点u、v都有d(u)+d(v)≥m。由定理10.26可知,G是哈密尔顿图。4离散数考试试题(B卷及答案)一、(10分)使用将命题公式化为主范式的方法,证明(PQ)(P∧Q)(QP)∧(P∨Q)。证明:因为(PQ)(P∧Q)(P∨Q)∨(P∧Q)(P∧Q)∨(P∧Q)(QP)∧(P∨Q)(Q∨P)∧(P∨Q)(P∧Q)∨(Q∧Q)∨(P∧P)∨(P∧Q)(P∧Q)∨P(P∧Q)∨(P∧(Q∨Q))(P∧Q)∨(P∧Q)∨(P∧Q)(P∧Q)∨(P∧Q)所以,(PQ)(P∧Q)(QP)∧(P∨Q)。二、(10分)证明下述推理:如果A努力工作,那么B或C感到愉快;如果B愉快,那么A不努力工作;如果D愉快那么C不愉快。所以,如果A努力工作,则D不愉快。解设A:A努力工作;B、C、D分别表示B、C、D愉快;则推理化形式为:AB∨C,BA,DCAD(1)A附加前提(2)AB∨CP(3)B∨CT(1)(2),I(4)BAP(5)ABT(4),E(6)BT(1)(5),I(7)CT(3)(6),I(8)DCP(9)DT(7)(8),I(10)ADCP三、(10分)证明xy(P(x)Q(y))(xP(x)yQ(y))。xy(P(x)Q(y))xy(P(x)∨Q(y))x(P(x)∨yQ(y))xP(x)∨yQ(y)xP(x)∨yQ(y)(xP(x)yQ(y))四、(10分)设A={,1,{1}},B={0,{0}},求P(A)、P(B)-{0}、P(B)B。解P(A)={,{},{1},{{1}},{,1},{,{1}},{1,{1}},{,1,{1}}}P(B)-{0}={,{0},{{0}},{0,{0}}-{0}={,{0},{{0}},{0,{0}}5P(B)B={,{0},{{0}},{0,{0}}{0,{0}}={,0,{{0}},{0,{0}}五、(15分)设X={1,2,3,4},R是X上的二元关系,R={1,1,3,1,1,3,3,3,3,2,4,3,4,1,4,2,1,2}(1)画出R的关系图。(2)写出R的关系矩阵。(3)说明R是否是自反、反自反、对称、传递的。解(1)R的关系图如图所示:(2)R的关系矩阵为:0111011100000111)(RM(3)对于R的关系矩阵,由于对角线上不全为1,R不是自反的;由于对角线上存在非0元,R不是反自反的;由于矩阵不对称,R不是对称的;经过计算可得)(0111011100000111)(2RMRM,所以R是传递的。六、(15分)设函数f:R×RR×R,f定义为:f(x,y)=x+y,x-y。(1)证明f是单射。(2)证明f是满射。(3)求逆函数f-1。(4)求复合函数f-1f和ff。证明(1)对任意的x,y,x1,y1∈R,若f(x,y)=f(x1,y1),则x+y,x-y=x1+y1,x1-y1,x+y=x1+y1,x-y=x1-y1,从而x=x1,y=y1,故f是单射。(2)对任意的u,w∈R×R,令x=2wu,y=2wu,则f(x,y)=2wu+2wu,2wu-2wu=u,w,所以f是满射。(3)f-1(u,w)=2wu,2wu。(4)f-1f(x,y)=f-1(f(x,y))=f-1(x+y,x-y)=2yxyx,2)(yxyx=x,yff(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,6试证G,*是Abel群。证明对G中任意元a和b。因为a3*b3=(a*b)3,所以1a*a3*b3*1b=1a*(a*b)3*1b,即得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,即b3*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条边。证明不妨设G是无向连通图(若G为有向图,可略去边的方向讨论对应的无向图)。设G中结点为1v、2v、…、nv。由连通性,必存在与1v相邻的结点,不妨设它为2v(否则可重新编号),连接1v和2v,得边1e,还是由连通性,在3v、4v、…、nv中必存在与1v或2v相邻的结点,不妨设为3v,将其连接得边2e,续行此法,nv必与1v、2v、…、1nv中的某个结点相邻,得新边1ne,由此可见G中至少有n-1条边。(2)试给出|V|=n,|E|=21(n-1)(n-2)的简单无向图G=V,E是不连通的例子。解下图满足条件但不连通。