离散数学试卷及答案.doc

离散数学试题（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)
Û∧
Û∨∨∨∨∨
二、（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上的二元关系，则由定理4.19知，tsr(R)是包含R的且具有自反性、对称性和传递性的关系。
若是包含R的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r(R)Í。由定理4.15和由定理4.16得sr(R)Ís()＝，进而有tsr(R)Ít()＝。
综上可知，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的关系矩阵为：

(2)由关系矩阵可知，对角线上所有元素全为1，故R是自反的；＋≤1，故R是反对称的；可计算对应的关系矩阵为：

由以上矩阵可知R是传递的。
五、（10分）设A、B、C和D为任意集合，证明(A－B)×C＝(A×C)－(B×C)。
证明：因为
<，>∈(A－B)×CÛ∈(A－B)∧∈C
Û(∈A∧ÏB)∧∈C
Û(∈A∧∈C∧ÏB)∨(∈A∧∈C∧ÏC)
Û(∈A∧∈C)∧(ÏB∨ÏC)
Û(∈A∧∈C)∧Ø(∈B∧∈C)
Û<，>∈(A×C)∧<，>Ï(B×C)
Û<，>∈(A×C)－(B×C)
所以，(A－B)×C＝(A×C－B×C)。
六、（10分）设f：A®B，g：B®C，h：C®A，证明：如果hogof＝IA，fohog＝IB，gofoh＝IC，则f、g、h均为双射，并求出f－1、g－1和h－1。
解 因IA恒等函数，由hogof＝IA可得f是单射，h是满射；因IB恒等函数，由fohog＝IB可得g是单射，f是满射；因IC恒等函数，由gofoh＝IC可得h是单射，g是满射。从而f、g、h均为双射。
由hogof＝IA，得f－1＝hog；由fohog＝IB，得g－1＝foh；由gofoh＝IC，得h－1＝gof。
七、（15分）设<G，*>是一代数系统，运算*满足交换律和结合律，且a*x＝a*yÞx＝y，证明：若G有限，则G是一群。
证明 因G有限，不妨设G＝{，，…，}。由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中结点为、、…、。由连通性，必存在与相邻的结点，不妨设它为（否则可重新编号），连接和，得边，还是由连通性，在、、…、中必存在与或相邻的结点，不妨设为，将其连接得边，续行此法，必与、、…、中的某个结点相邻，得新边，由此可见G中至少有n－1条边。
（2）给定简单无向图G＝<V，E>，且|V|＝m，|E|＝n。试证：若n≥＋2，则G是哈密尔顿图。
证明 若n≥＋2，则2n≥m2－3m＋6 （1）。
若存在两个不相邻结点、使得d()＋d()＜m，则有2n＝＜m＋(m－2)(m－3)＋m＝m2－3m＋6，与（1）矛盾。所以，对于G中任意两个不相邻结点、都有d()＋d()≥m。由定理10.26可知，G是哈密尔顿图。

离散数学试题（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∨C P
(3)B∨C T(1)(2)，I
(4)B®ØA P
(5)A®ØB T(4)，E
(6)ØB T(1)(5)，I
(7)C T(3)(6)，I
(8)D®ØC P
(9)ØD T(7)(8)，I
(10)A®ØD CP
三、（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}}
P(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的关系矩阵为：

(3)对于R的关系矩阵，由于对角线上不全为1，R不是自反的；由于对角线上存在非0元，R不是反自反的；由于矩阵不对称，R不是对称的；
经过计算可得
，所以R是传递的。
六、（15分）设函数f：R×R®R×R，f定义为：f(<x，y>)＝<x＋y，x－y>。
(1)证明f是单射。
(2)证明f是满射。
(3)求逆函数f－1。
(4)求复合函数f－1of和fof。
证明 (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＝，y＝，则f(<x，y>)＝<＋，－>＝<u，w>，所以f是满射。
(3)f－1(<u，w>)＝<，>。
(4)f－1of(<x，y>)＝f－1(f(<x，y>))＝f－1(<x＋y，x－y>)＝<，>＝<x，y>
fof(<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和b。
因为a3*b3＝(a*b)3，所以*a3*b3*＝*(a*b)3*，即得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中结点为、、…、。由连通性，必存在与相邻的结点，不妨设它为（否则可重新编号），连接和，得边，还是由连通性，在、、…、中必存在与或相邻的结点，不妨设为，将其连接得边，续行此法，必与、、…、中的某个结点相邻，得新边，由此可见G中至少有n－1条边。
（2）试给出|V|＝n，|E|＝(n－1)(n－2)的简单无向图G＝<V，E>是不连通的例子。
解 下图满足条件但不连通。

9