对任意的
综上可得，R是A×B上的等价关系。
九、设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（10分）。
解 因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。
－1
－1
－1
－1
－1
－1
离散数学试题(B卷答案3）
一、（10分）判断下列公式的类型（永真式、永假式、可满足式）？(写过程) 1)P?(P∨Q∨R) 2)?((Q?P)∨?P)∧(P∨R) 3)((?P∨Q)?R)?((P∧Q)∨R)
解：1)重言式；2)矛盾式；3)可满足式
二、（10分）求命题公式（P∨(Q∧R))?(P∨Q∨R)的主析取范式，并求成真赋值。
解：（P∨(Q∧R))?(P∨Q∨R)??(P∨(Q∧R))∨P∨Q∨R
??P∧(?Q∨?R)∨P∨Q∨R
?(?P∧?Q)∨(?P∧?R)∨(P∨Q)∨R ?(?(P∨Q)∨(P∨Q))∨(?P∧?R)∨R ?1∨((?P∧?R)∨R)?1 ?m0∨m1∨m2∨m3∨m4∨m5∨m6∨m7
该式为重言式，全部赋值都是成真赋值。
三、（10分）证明 ((P∧Q∧A)?C)∧(A?(P∨Q∨C))?(A∧(P?Q))?C
证明：((P∧Q∧A)?C)∧(A?(P∨Q∨C))?(?(P∧Q∧A)∨C)∧(?A∨(P∨Q∨C))
?((?P∨?Q∨?A)∨C)∧((?A∨P∨Q)∨C) ?((?P∨?Q∨?A)∧(?A∨P∨Q))∨C
??((?P∨?Q∨?A)∧(?A∨P∨Q))?C ?(?(?P∨?Q∨?A)∨?(?A∨P∨Q))?C ?((P∧Q∧A)∨(A∧?P∧?Q))?C ?(A∧((P∧Q)∨(?P∧?Q)))?C ?(A∧((P∨?Q)∧(?P∨Q)))?C ?(A∧((Q?P)∧(P?Q)))?C ?(A∧(P?Q))?C
四、（10分）个体域为{1，2}，求?x?y（x+y=4）的真值。
解：?x?y（x+y=4）??x（（x+1=4）∨（x+2=4））
?（（1+1=4）∨（1+2=4））∧（（2+1=4）∨（2+2=4）） ?（0∨0）∧（0∨1）?0∧1?0
五、（10分）对于任意集合A，B，试证明：P(A)∩P(B)=P(A∩B)
解：?x?P(A)∩P(B)，x?P(A)且x?P(B)，有x?A且x?B，从而x?A∩B，x?P(A∩B)，由于上述过程可逆，故P(A)∩P(B)=P(A∩B)
六、（10分）已知A={1，2，3，4，5}和R={<1，2>，<2，1>，<2，3>，<3，4>，<5，4>}，求r(R)、s(R)和t(R)。
解：r(R)={<1，2>，<2，1>，<2，3>，<3，4>，<5，4>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>}
s(R)={<1，2>，<2，1>，<2，3>，<3，4>，<5，4>，<3，2>，<4，3>，<4，5>} t(R)={<1，2>，<2，1>，<2，3>，<3，4>，<5，4>，<1，1>，<1，3>，<2，2>，<2，4>，<1，4>}
七、（10分）设函数f：R×R?R×R，R为实数集，f定义为：f(
解：1）?
2）?
八、（10分）
-1
∈G，求证：
证明：1）?a，b∈G，a?b=a*u*b∈G，运算是封闭的。
2）?a，b，c∈G，（a?b）?c=（a*u*b）*u*c=a*u*（b*u*c）=a?（b?c），运算是可结合的。
3）?a∈G，设E为?的单位元，则a?E=a*u*E=a，得E=u，存在单位元u。 4）?a∈G，a?x=a*u*x=E，x=u*a*u，则x?a=u*a*u*u*a=u=E，每个元素都有逆元。
所以
九、（10分）已知：D=
解：1）D的邻接距阵A和可达距阵P如下：
A=
0 1 0 1 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0
1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1
1 1 1 0 1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
P= 1 1 1 1
十、（10分）求叶的权分别为2、4、6、8、10、12、14的最优二叉树及其权。
解：最优二叉树为
权＝(2+4)×4+6×3+12×2+(8+10)×3+14×2＝148
离散数学试题(B卷答案4）
一、证明题（10分）
1)((P∨Q)∧?(?P∧(?Q∨?R)))∨(?P∧?Q)∨(?P∧?R)?T
证明: 左端?((P∨Q)∧(P∨(Q∧R)))∨?((P∨Q)∧(P∨R))(摩根律) ? ((P∨Q)
∧(P∨Q)∧(P∨R))∨?((P∨Q)∧(P∨R))(分配律) ? ((P∨Q)∧(P∨R))∨?((P∨Q)∧(P∨R)) (等幂律) ?T
(代入)
2)?x(P(x)?Q(x))∧?xP(x)??x(P(x)∧Q(x))
证明：?x(P(x)?Q(x))∧?xP(x)??x((P(x)?Q(x)∧P(x))??x((?P(x)∨Q(x)∧P(x))??x(P(x)∧Q(x))??xP(x)∧?xQ(x)??x(P(x)∧Q(x))
二、求命题公式(?P?Q)?(P∨?Q) 的主析取范式和主合取范式（10分）
解：(?P?Q)?(P∨?Q)??(?P?Q)∨(P∨?Q)??(P∨Q)∨(P∨?Q)?(?P∧?Q)∨(P∨?Q) ?(?P∨P∨?Q)∧(?Q∨P∨?Q)?(P∨?Q)?M1?m0∨m2∨m3 三、推理证明题（10分）
1)(P?(Q?S))∧(?R∨P)∧Q?R?S
证明：（1）R 附加前提 (2)?R∨P P (3)P T(1)(2),I (4)P?(Q?S) P (5)Q?S T(3)(4),I (6)Q P
(7)S T(5)(6),I (8)R?S CP
2) ?x(P(x)∨Q(x))，?x?P(x)??x Q(x)
证明：(1)?x?P(x) P (2)?P(c) T(1),US (3)?x(P(x)∨Q(x)) P (4)P(c)∨Q(c) T(3),US (5)Q(c) T(2)(4),I (6)?x Q(x) T(5),EG
四、例5在边长为1的正方形内任意放置九个点，证明其中必存在三个点，使得由它们组成的三角形（可能是退化的）面积不超过1/8（10分）。
证明：把边长为1的正方形分成四个全等的小正方形，则至少有一个小正方形内有三个点，它们组成的三角形（可能是退化的）面积不超过小正方形的一半，即1/8。 五、已知A、B、C是三个集合，证明A∩(B∪C)=(A∩B)∪(A∩C) （10分）
证明：∵x? A∩（B∪C）? x? A∧x?（B∪C）? x? A∧（x?B∨x?C）?（ x? A∧x?B）∨（x? A∧x?C）? x?（A∩B）∨x? A∩C? x?（A∩B）∪（A∩C）∴A∩（B∪C）=（A∩B）∪（A∩C）
六、?={A1，A2，?，An}是集合A的一个划分，定义R={|a、b∈Ai，I=1，2，?，n}，则R是A上的等价关系（15分）。
证明：?a∈A必有i使得a∈Ai，由定义知aRa，故R自反。 ?a,b∈A，若aRb ，则a,b∈Ai，即b,a∈Ai，所以bRa，故R对称。
?a,b,c∈A，若aRb 且bRc，则a,b∈Ai及b,c∈Aj。因为i≠j时Ai∩Aj=?，故i=j，即a,b,c∈Ai，所以aRc，故R传递。
总之R是A上的等价关系。
七、若f:A→B是双射，则f:B→A是双射（15分）。
证明:对任意的x∈A，因为f是从A到B的函数，故存在y∈B，使
对任意的x∈A，若存在y1,y2∈B，使得
因此f是双射。
八、设
证明 假设A≠G且B≠G，则存在a?A，a?B，且存在b?B，b?A（否则对任意的a?A，a?B，从而A?B，即A∪B＝B，得B＝G，矛盾。）
对于元素a*b?G，若a*b?A，因A是子群，a?A，从而a * (a*b)＝b ?A，所以矛盾，故a*b?A。同理可证a*b?B，综合有a*b?A∪B＝G。 综上所述，假设不成立，得证A＝G或B＝G。
九、若无向图G是不连通的，证明G的补图G是连通的（10分）。
证明 设无向图G是不连通的，其k个连通分支为G1、G2、?、Gk。任取结点u、
v∈G，若u和v不在图G的同一个连通分支中，则[u，v]不是图G的边，因而[u，v]
-1
-1
-1
-1
-1
-1
-1
-1
-1
是图G的边；若u和v在图G的同一个连通分支中，不妨设其在连通分支Gi（1≤i≤k）中，在不同于Gi的另一连通分支上取一结点w，则[u，w]和[w，v]都不是图G的边，，因而[u，w]和[w，v]都是G的边。综上可知，不管那种情况，u和v都是可达的。由u和v的任意性可知，G是连通的。