离散数学期末试题

1离散数学考试试题（A卷及答案）一、（10分）求(PQ)(P∧(Q∨R))的主析取范式解：(PQ)(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∧1M2m∨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∧RT因此，王教授是上海人。三、（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)×Cx∈(A－B)∧y∈C(x∈A∧xB)∧y∈C(x∈A∧y∈C∧xB)∨(x∈A∧y∈C∧yC)(x∈A∧y∈C)∧(xB∨yC)(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：AB，g：BC，h：CA，证明：如果hgf＝IA，fhg＝IB，gfh＝IC，则f、g、h均为双射，并求出f－1、g－1和h－1。解因IA恒等函数，由hgf＝IA可得f是单射，h是满射；因IB恒等函数，由fhg＝IB可得g是单射，f是满射；因IC恒等函数，由gfh＝IC可得h是单射，g是满射。从而f、g、h均为双射。由hgf＝IA，得f－1＝hg；由fhg＝IB，得g－1＝fh；由gfh＝IC，得h－1＝gf。3七、（15分）设G，*是一代数系统，运算*满足交换律和结合律，且a*x＝a*yx＝y，证明：若G有限，则G是一群。证明因G有限，不妨设G＝{1a，2a，…，na}。由a*x＝a*yx＝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、…、1nv中的某个结点相邻，得新边1ne，由此可见G中至少有n－1条边。（2）给定简单无向图G＝V，E，且|V|＝m，|E|＝n。试证：若n≥21mC＋2，则G是哈密尔顿图。证明若n≥21mC＋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分）使用将命题公式化为主范式的方法，证明(PQ)(P∧Q)(QP)∧(P∨Q)。证明：因为(PQ)(P∧Q)(P∨Q)∨(P∧Q)(P∧Q)∨(P∧Q)(QP)∧(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)所以，(PQ)(P∧Q)(QP)∧(P∨Q)。二、（10分）证明下述推理：如果A努力工作，那么B或C感到愉快；如果B愉快，那么A不努力工作；如果D愉快那么C不愉快。所以，如果A努力工作，则D不愉快。解设A：A努力工作；B、C、D分别表示B、C、D愉快；则推理化形式为：AB∨C，BA，DCAD(1)A附加前提(2)AB∨CP(3)B∨CT(1)(2)，I(4)BAP(5)ABT(4)，E(6)BT(1)(5)，I(7)CT(3)(6)，I(8)DCP(9)DT(7)(8)，I(10)ADCP三、（10分）证明xy(P(x)Q(y))(xP(x)yQ(y))。xy(P(x)Q(y))xy(P(x)∨Q(y))x(P(x)∨yQ(y))xP(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×RR×R，f定义为：f(x，y)＝x＋y，x－y。(1)证明f是单射。(2)证明f是满射。(3)求逆函数f－1。(4)求复合函数f－1f和ff。证明(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－1f(x，y)＝f－1(f(x，y))＝f－1(x＋y，x－y)＝2yxyx，2)(yxyx＝x，yff(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，所以1a*a3*b3*1b＝1a*(a*b)3*1b，即得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、…、1nv中的某个结点相邻，得新边1ne，由此可见G中至少有n－1条边。（2）试给出|V|＝n，|E|＝21(n－1)(n－2)的简单无向图G＝V，E是不连通的例子。解下图满足条件但不连通。