离散试卷及答案
离散数学（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) ?M0∧M1
?m2∨m3∨m4∨m5∨m6∨m7
二、（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
因此，王教授是上海人。
第 1 页 共 26 页
离散试卷及答案
三、（10分）证明tsr(R)是包含R的且具有自反性、对称性和传递性的最小关系。
证明 设R是非空集合A上的二元关系，则由定理4.19知，tsr(R)是包含R的且具有自反性、对称性和传递性的关系。
若R是包含R的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r(R)?R。由定理4.15和由定理4.16得sr(R)?s(R)＝R，进而有tsr(R)?t(R)＝R。 综上可知，tsr(R)是包含R的且具有自反性、对称性和传递性的最小关系。
四、（15分）集合A＝{a，b，c，d，e}上的二元关系R为R＝{，，，，，
(1)写出R的关系矩阵。
(2)判断R是不是偏序关系，为什么？
解 (1) R的关系矩阵为：
''''''?1??0M(R)??0??0?0?1111??1101?0101?
?0011?0001??(2)由关系矩阵可知，对角线上所有元素全为1，故R是自反的；rij＋rji≤1，故R是反对称的；可计算对应的关系矩阵为：
?1??0M(R2)??0??0?0?由以上矩阵可知R是传递的。
1111??1101?0101??M(R)
?0011?0001??五、（10分）设A、B、C和D为任意集合，证明(A－B)×C＝(A×C)－(B×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) ?
第 2 页 共 26 页
离散试卷及答案
?
所以，(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、g和h。
解 因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＝h?g；由f?h?g＝IB，得g＝f?h；由g?f?h＝IC，得h＝g?f。
七、（15分）设
证明 因G有限，不妨设G＝{a1，a2，?，an}。由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中结点为v1、v2、?、vn。由连通性，必存在与v1相邻的结点，不妨设它为v2（否则可重新编号），连接v1和v2，得边e1，还是由连通性，在v3、v4、?、vn中必存在与v1或v2相邻的结点，不妨设为v3，将其连接得边e2，续行此法，vn必与v1、v2、?、vn?1中的某个结点相邻，得新边en?1，由此可见G中至少有n－1条边。
2（2）给定简单无向图G＝
2
－1
－1
－1
－1
－1
－1
若存在两个不相邻结点u、v使得d(u)＋d(v)＜m，则有2n＝
w?V?d(w)＜m＋(m－2)(m－3)＋m＝m－3m
2
＋6，与（1）矛盾。所以，对于G中任意两个不相邻结点u、v都有d(u)＋d(v)≥m。由定理10.26可知，G是哈密尔顿图。
第 3 页 共 26 页
离散试卷及答案
离散数考试试题（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))
第 4 页 共 26 页
离散试卷及答案
四、（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的关系矩阵为：
?1??0M(R)??1??1?自反的；由于矩阵不对称，R不是对称的；
经过计算可得
101110110??0? ?0?0??(3)对于R的关系矩阵，由于对角线上不全为1，R不是自反的；由于对角线上存在非0元，R不是反
?1??02M(R)??1??1?
101110110??0??M(R)，所以R是传递的。 ?0?0??六、（15分）设函数f：R×R?R×R，f定义为：f(
(1)证明f是单射。 (2)证明f是满射。 (3)求逆函数f。
(4)求复合函数f?f和f?f。
证明 (1)对任意的x，y，x1，y1∈R，若f(
(2)对任意的
－1－1
u?wu?wu?wu?wu?wu?w
，y＝，则f(
第 5 页 共 26 页
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库离散试卷有答案 (4)在线全文阅读。
相关推荐：