离散数学试题（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)⇔M∧1M⇔m∨3m∨4m∨5m∨6m∨7m2二、（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 (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 ＝{<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)(R M(2)由关系矩阵可知，对角线上所有元素全为1，故R 是自反的；ij r ＋ji r ≤1，故R 是反对称的；可计算对应的关系矩阵为：)(1000011000101001011011111)(2R M R M =⎪⎪⎪⎪⎪⎪⎭⎫⎝⎛=由以上矩阵可知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 ＝I A ，f h g ＝I B ，g f h ＝I C ，则f 、g 、h 均为双射，并求出f －1、g －1和h －1。

解 因I A 恒等函数，由h g f ＝I A 可得f 是单射，h 是满射；因I B 恒等函数，由f h g ＝I B 可得g 是单射，f 是满射；因I C 恒等函数，由g f h ＝I C 可得h 是单射，g 是满射。

从而f 、g 、h 均为双射。

由h g f ＝I A ，得f －1＝h g ；由f h g ＝I B ，得g －1＝f h ；由g f h ＝I C ，得h －1＝g f 。

七、（15分）设<G ，*>是一代数系统，运算*满足交换律和结合律，且a *x＝a*y⇒x＝y，证明：若G有限，则G是一群。

证明因G有限，不妨设G＝{1a，2a，…，n a}。

由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、…、n v。

由连通性，必存在与1v相邻的结点，不妨设它为2v（否则可重新编号），连接1v和2v，得边1e，还是由连通性，在3v、4v、…、nv中必存在与1v或2v相邻的结点，不妨设为3v，将其连接得边2e，续行此法，n v必与1v、2v、…、1-n v中的某个结点相邻，得新边1-n e，由此可见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是哈密尔顿图。

离散数学试题（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→⌝C A→⌝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 的关系矩阵为：⎪⎪⎪⎪⎪⎭⎫⎝⎛=0111011100000111)(R M(3)对于R 的关系矩阵，由于对角线上不全为1，R 不是自反的；由于对角线上存在非0元，R 不是反自反的；由于矩阵不对称，R 不是对称的；经过计算可得)(0111011100000111)(2R M R M =⎪⎪⎪⎪⎪⎭⎫⎝⎛=，所以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是满射。