离散数学期末考试试题及答案.doc

离散数学试题(B卷答案1）
一、证明题（10分）
1)(ØP∧(ØQ∧R))∨(Q∧R)∨(P∧R)ÛR
证明: 左端Û(ØP∧ØQ∧R)∨((Q∨P)∧R)
Û((ØP∧ØQ)∧R))∨((Q∨P)∧R)
Û(Ø(P∨Q)∧R)∨((Q∨P)∧R)
Û(Ø(P∨Q)∨(Q∨P))∧R
Û(Ø(P∨Q)∨(P∨Q))∧R
ÛT∧R(置换)ÛR
2) $x (A(x)®B(x))Û "xA(x)®$xB(x)
证明 ：$x(A(x)®B(x))Û$x(ØA(x)∨B(x))
Û$xØA(x)∨$xB(x)
ÛØ"xA(x)∨$xB(x)
Û"xA(x)®$xB(x)
二、求命题公式(P∨(Q∧R))®(P∧Q∧R)的主析取范式和主合取范式（10分）。
证明：(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∧R)∨(ØP∧ØQ∧ØR)∨(ØP∧Q∧ØR))∨(ØP∧ØQ∧ØR))∨(P∧Q∧R)
Ûm0∨m1∨m2∨m7
ÛM3∨M4∨M5∨M6
三、推理证明题（10分）
1） C∨D， (C∨D)® ØE， ØE®(A∧ØB)， (A∧ØB)®(R∨S)ÞR∨S
证明：(1) (C∨D)®ØE P
(2) ØE®(A∧ØB) P
(3) (C∨D)®(A∧ØB) T(1)(2)，I
(4) (A∧ØB)®(R∨S) P
(5) (C∨D)®(R∨S) T(3)(4)， I
(6) C∨D P
(7) R∨S T(5)，I
2) "x(P(x)®Q(y)∧R(x))，$xP(x)ÞQ(y)∧$x(P(x)∧R(x))
证明(1)$xP(x) P
(2)P(a) T(1)，ES
(3)"x(P(x)®Q(y)∧R(x)) P
(4)P(a)®Q(y)∧R(a) T(3)，US
(5)Q(y)∧R(a) T(2)(4)，I
(6)Q(y) T(5)，I
(7)R(a) T(5)，I
(8)P(a)∧R(a) T(2)(7)，I
(9)$x(P(x)∧R(x)) T(8)，EG
(10)Q(y)∧$x(P(x)∧R(x)) T(6)(9)，I
四、某班有25名学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。而6个会打网球的人都会打另外一种球，求不会打这三种球的人数（10分）。
解：A，B，C分别表示会打排球、网球和篮球的学生集合。则|A|=12，|B|=6，|C|=14，|A∩C|=6，|B∩C|=5，|A∩B∩C|=2。
先求|A∩B|。
∵6=|（A∪C）∩B|=|（A∩B）∪（B∩C）|=|（A∩B）|+|（B∩C）|-|A∩B∩C|=|（A∩B）|+5-2，∴|（A∩B）|=3。
于是|A∪B∪C|=12+6+14-6-5-3+2=20。不会打这三种球的人数25-20=5。
五、已知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）
六、已知R、S是N上的关系，其定义如下：R={<x，y>| x，yÎN∧y=x2}，S={<x，y>| x，yÎN∧y=x+1}。求R-1、R*S、S*R、R{1，2}、S[{1，2}]（10分）。
解：R-1={<y，x>| x，yÎN∧y=x2}
R*S={<x，y>| x，yÎN∧y=x2+1}
S*R={<x，y>| x，yÎN∧y=（x+1）2}，R{1，2}={<1，1>，<2，4>}，S[{1，2}]={1，4}。
七、设R={<a，b>，<b，c>，<c，a>}，求r(R)、s(R)和t(R) （15分）。
解：r(R)={<a，b>，<b，c>，<c，a>，<a，a>，<b，b>，<c，c>}
s(R)={<a，b>，<b，c>，<c，a>，<b，a>，<c，b>，<a，c>}
R2= R5={<a，c>，<b，a>，<c，b>}
R3={<a，a>，<b，b>，<c，b>}
R4={<a，b>，<b，c>，<c，c>}
t(R)={<a，b>，<b，c>，<c，a>，<a，c>，<b，a>，，<a，a>，<b，b>，<c，b>，<c，c>}
八、证明整数集I上的模m同余关系R={<x，y>|xºy(mod m)}是等价关系。其中，xºy(mod m)的含义是x-y可以被m整除（15分）。
证明：1）"x∈I，因为（x-x）/m=0，所以xºx(mod m)，即xRx。
2）"x，y∈I，若xRy，则xºy(mod m)，即（x-y）/m=k∈I，所以（y - x）/m=-k∈I，所以yºx(mod m)，即yRx。
3）"x，y，z∈I，若xRy，yRz，则（x-y）/m=u∈I，（y-z）/m=v∈I，于是（x-z）/m=（x-y+y-z）/m=u+v ∈I，因此xRz。
九、若f:A→B和g:B→C是双射，则（gf）-1=f-1g-1（10分）。
证明：因为f、g是双射，所以gf：A→C是双射，所以gf有逆函数（gf）-1：C→A。同理可推f-1g-1：C→A是双射。
因为<x，y>∈f-1g-1Û存在z（<x，z>∈g-1Ù<z，y>∈f-1）Û存在z（<y，z>∈fÙ<z，x>∈g）Û<y，x>∈gfÛ<x，y>∈（gf）-1，所以（gf）-1=f-1g-1。
离散数学试题(B卷答案2）
一、证明题（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"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))
二、求命题公式(Ø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
(3)P
(4)P®(Q®S)
(5)Q®S
(6)Q
(7)S
(8)R®S
2) $x(A(x)®"yB(y))，"x(B(x)®$yC(y))"xA(x)®$yC(y)。
证明：(1)$x(A(x)®"yB(y)) P
(2)A(a)®"yB(y) T(1)，ES
(3)"x(B(x)®$yC(y)) P
(4)"x(B(x)®C()) T(3)，ES
(5)B()®C() T(4)，US
(6)A(a)®B() T(2)，US
(7)A(a)®C() T(5)(6)，I
(8)"xA(x)®C() T(7)，UG
(9)"xA(x)®$yC(y) T(8)，EG
四、只要今天天气不好，就一定有考生不能提前进入考场，当且仅当所有考生提前进入考场，考试才能准时进行。所以，如果考试准时进行，那么天气就好（15分）。
解 设P：今天天气好，Q：考试准时进行，A(e)：e提前进入考场，个体域：考生的集合，则命题可符号化为：ØP®$xØA(x)，"xA(x)«QQ®P。
(1)ØP®$xØA(x) P
(2)ØP®Ø"xA(x) T(1)，E
(3)"xA(x)®P T(2)，E
(4)"xA(x)«Q P
(5)("xA(x)®Q)∧(Q®"xA(x)) T(4)，E
(6)Q®"xA(x) T(5)，I
(7)Q®P T(6)(3)，I
五、已知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）
六、A={ x1,x2,x3 }，B={ y1,y2}，R={<x1, y1>,<x2, y2>,<x3, y2>}，求其关系矩阵及关系图（10分）。
七、设R={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>}，求r(R)、s(R)和t(R)，并作出它们及R的关系图（15分）。
解：r(R)={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,1>,<2,2>,
<3,3>,<4,4>,<5,5>}
s(R)={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,2>,<4,2>,<4,3>}
R2=R5={<2,2>,<2,4>,<3,4>,<4,4>,<5,1>,<5,5>,<5,4>}
R3={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<5,4>}
R4={<2,2>,<2,4>,<3,4>,<4,4>,<5,1>,<5,5>,<5,4>}
t(R)={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<2,2>,<5,1>,<5,4>,<5,5>}
八、设R1是A上的等价关系，R2是B上的等价关系，A≠Æ且B≠Æ。关系R满足：<<x1，y1>，<x2，y2>>∈RÛ<x1，x2>∈R1且<y1，y2>∈R2，证明R是A×B上的等价关系（10分）。
证明 对任意的<x，y>∈A×B，由R1是A上的等价关系可得<x，x>∈R1，由R2是B上的等价关系可得<y，y>∈R2。再由R的定义，有<<x，y>，<x，y>>∈R，所以R是自反的。
对任意的<x，y>、<u，v>∈A×B，若<x，y>R<u，v>，则<x，u>∈R1且<y，v>∈R2。由R1对称得<u，x>∈R1，由R2对称得<v，y>∈R2。再由R的定义，有<<u，v>，<x，y>>∈R，即<u，v>R<x，y>，所以R是对称的。
对任意的<x，y>、<u，v>、<s，t>∈A×B，若<x，y>R<u，v>且<u，v>R<s，t>，则<x，u>∈R1且<y，v>∈R2，<u，s>∈R1且<v，t>∈R2。由<x，u>∈R1、<u，s>∈R1及R1的传递性得<x，s>∈R1，由<y，v>∈R2、<v，t>∈R2及R2的传递性得<y，t>∈R1。再由R的定义，有<<x，y>，<s，t>>∈R，即<x，y>R<s，t>，所以R是传递的。
综上可得，R是A×B上的等价关系。
九、设f：A®B，g：B®C，h：C®A，证明：如果hogof＝IA，fohog＝IB，gofoh＝IC，则f、g、h均为双射，并求出f－1、g－1和h－1（10分）。
解 因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。
离散数学试题(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(<x，y>)=<x+y，x-y>。1)证明f是双射。
解：1）"<x1，y1>，<x2，y2>∈R×R，若f(<x1，y1>)=f(<x2，y2>)，即<x1+y1，x1-y1>=<x2+y2，x2-y2>，则x1+y1=x2+y2且x1-y1=x2-y2得x1=x2，y1=y2从而f是单射。
2）"<p，q>∈R×R，由f(<x，y>)=<p，q>，通过计算可得x=(p+q)/2；y=(p-q)/2；从而<p，q>的原象存在，f是满射。
八、（10分）<G，*>是个群，u∈G，定义G中的运算“D”为aDb=a*u-1*b，对任意a，b∈G，求证：<G， D>也是个群。
证明：1）"a，b∈G，aDb=a*u-1*b∈G，运算是封闭的。
2）"a，b，c∈G，（aDb）Dc=（a*u-1*b）*u-1*c=a*u-1*（b*u-1*c）=aD（bDc），运算是可结合的。
3）"a∈G，设E为D的单位元，则aDE=a*u-1*E=a，得E=u，存在单位元u。
4）"a∈G，aDx=a*u-1*x=E，x=u*a-1*u，则xDa=u*a-1*u*u-1*a=u=E，每个元素都有逆元。
所以<G， D>也是个群。
九、（10分）已知：D=<V，E>，V={1，2，3，4，5}，E={<1，2>，<1，4>，<2，3>，<3，4>，<3，5>，<5，1>}，求D的邻接距阵A和可达距阵P。
解：1）D的邻接距阵A和可达距阵P如下：

0
1
0
1
0

1
1
1
1
1

0
0
1
0
0

1
1
1
1
1
A=
0
0
0
1
1

P=
1
1
1
1
1

0
0
0
0
0

0
0
0
0
0

1
0
0
0
0

1
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）
六、p={A1，A2，…，An}是集合A的一个划分，定义R={<a，b>|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=F，故i=j，即a,b,c∈Ai，所以aRc，故R传递。
总之R是A上的等价关系。
七、若f:A→B是双射，则f-1:B→A是双射（15分）。
证明:对任意的x∈A，因为f是从A到B的函数，故存在y∈B，使<x,y>∈f，<y,x>∈f-1。所以,f-1是满射。
对任意的x∈A，若存在y1,y2∈B，使得<y1,x>∈f-1且<y2,x>∈f-1,则有<x,y1>∈f且<x,y2>∈f。因为f是函数，则y1=y2。所以，f-1是单射。
因此f-1是双射。
八、设<G，*>是群，<A，*>和<B，*>是<G，*>的子群，证明：若A∪B＝G，则A＝G或B＝G（10分）。
证明 假设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-1ÎA，从而a-1 * (a*b)＝b ÎA，所以矛盾，故a*bÏA。同理可证a*bÏB，综合有a*bÏA∪B＝G。
综上所述，假设不成立，得证A＝G或B＝G。
九、若无向图G是不连通的，证明G的补图是连通的（10分）。
证明 设无向图G是不连通的，其k个连通分支为、、…、。任取结点、∈G，若和不在图G的同一个连通分支中，则[，]不是图G的边，因而[，]是图的边；若和在图G的同一个连通分支中，不妨设其在连通分支（1≤≤）中，在不同于的另一连通分支上取一结点，则[，]和[，]都不是图G的边，，因而[，]和[，]都是的边。综上可知，不管那种情况，和都是可达的。由和的任意性可知，是连通的。
离散数学试题（B卷答案5）
一、（10分）求命题公式Ø(P∧Q)«Ø(ØP®R)的主合取范式。
解：Ø(P∧Q)«Ø(ØP®R)Û（Ø(P∧Q)®Ø(ØP®R)）∧（Ø(ØP®R)®Ø(P∧Q)）
Û（(P∧Q)∨(ØP∧ØR)）∧（(P∨R)∨(ØP∨ØQ)）
Û(P∧Q)∨(ØP∧ØR)
Û(P∨ØR)∧（Q∨ØP）∧（Q∨ØR）
Û(P∨Q∨ØR)∧(P∨ØQ∨ØR)∧（ØP∨Q∨R）∧（ØP∨Q∨ØR）
ÛM1∧M3∧M4∧M5
二、（8分）叙述并证明苏格拉底三段论
解：所有人都是要死的，苏格拉底是人，所以苏格拉底是要死的。
符号化：F（x）：x是一个人。G（x）：x要死的。A：苏格拉底。
命题符号化为"x（F（x）®G（x）），F（a）ÞG（a）
证明：
（1）"x(F(x)®G(x)) P
（2）F(a)®G(a) T(1),US
（3）F(a) P
（4）G(a) T(2)(3),I
三、（8分）已知A、B、C是三个集合，证明A∩(B∪C)=(A∩B)∪(A∩C)
证明：∵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）
四、（10分）已知R和S是非空集合A上的等价关系，试证：1）R∩S是A上的等价关系；2）对a∈A，[a]R∩S=[a]R∩[a]S。
解："x∈A，因为R和S是自反关系，所以<x,x>∈R、<x,x>∈S，因而<x,x>∈R∩S，故R∩S是自反的。
"x、y∈A，若<x,y>∈R∩S，则<x,y>∈R、<x,y>∈S，因为R和S是对称关系，所以因<y,x>∈R、<y,x>∈S，因而<y,x>∈R∩S，故R∩S是对称的。
"x、y、z∈A，若<x,y>∈R∩S且<y,z>∈R∩S，则<x,y>∈R、<x,y>∈S且<y,z>∈R、<y,z>∈S，因为R和S是传递的，所以因<x,z>∈R、<x,z>∈S，因而<x,z>∈R∩S，故R∩S是传递的。
总之R∩S是等价关系。
2）因为x∈[a]R∩SÛ<x,a>∈R∩SÛ
<x,a>∈R∧<x,a>∈SÛ x∈[a]R∧x∈[a]SÛ x∈[a]R∩[a]S
所以[a]R∩S=[a]R∩[a]S。
五、(10分) 设A＝{a，b，c，d}，R是A上的二元关系，且R＝{<a，b>，<b，a>，<b，c>，<c，d>}，求r(R)、s(R)和t(R)。
解 r(R)＝R∪IA＝{<a，b>，<b，a>，<b，c>，<c，d>，<a，a>，<b，b>，<c，c>，<d，d>}
s(R)＝R∪R-1＝{<a，b>，<b，a>，<b，c>，<c，d>，<c，b>，<d，c>}
R2＝{<a，a>，<a，c>，<b，b>，<b，d>}
R3＝{<a，b>，<a，d>，<b，a>，<b，c>}
R4＝{<a，a>，<a，c>，<b，b>，<b，d>}＝R2
t(R)＝＝{<a，b>，<b，a>，<b，c>，<c，d>，<a，a>，<a，c>，<b，b>，<b，d>，<a，d>}
六、(15分) 设A、B、C、D是集合，f是A到B的双射，g是C到D的双射，令h：A×C®B×D且"<a,c>∈A×C，h(<a,c>)＝<f(a),g(c)>。证明h是双射。
证明：1）先证h是满射。
"<b,d>∈B×D，则b∈B，d∈D，因为f是A到B的双射，g是C到D的双射，所以存在a∈A，c∈C，使得f(a)=b，f(c)=d，亦即存在<a,c>∈A×C，使得h(<a,c>)＝<f(a),g(c)>＝<b,d>，所以h是满射。
2）再证h是单射。
"<a1,c1>、<a2,c2>∈A×C，若h(<a1,c1>)＝h(<a2,c2>)，则<f(a1),g(c1)>＝<f(a2),g(c2)> ，所以f(a1)＝f(a2)，g(c1)＝g(c2)，因为f是A到B的双射，g是C到D的双射，所以a1＝a2，c1＝c2，所以<a1,c1>＝<a2,c2>，所以h是单射。
综合1）和2），h是双射。
七、(12分)设<G，*>是群，H是G的非空子集，证明<H，*>是<G，*>的子群的充要条件是若a，bÎH，则有a*b-1ÎH。
证明：Þ "a,b∈H有b-1∈H，所以a*b-1∈H。
Ü"a∈H，则e=a*a-1∈H
a-1=e*a-1∈H
∵a,b∈H及b-1∈H，∴a*b=a*（b-1）-1∈H
∵HÍG且H≠F,∴*在H上满足结合律
∴<H，*>是<G，*>的子群。
八、（10分）设G=<V，E>是简单的无向平面图，证明G至少有一个结点的度数小于等于5。
解：设G的每个结点的度数都大于等于6，则2|E|=Sd(v)≥6|V|，即|E|≥3|V|，与简单无向平面图的|E|≤3|V|-6矛盾，所以G至少有一个结点的度数小于等于5。
九.G=<A,*>,A={a,b,c},*的运算表为：(写过程，7分)

（1）G是否为阿贝尔群？
（2）找出G的单位元；（3）找出G的幂等元（4）求b的逆元和c的逆元
解：（1）(a*c)*(a*c)=c*c=b=a*b=(a*a)*(c*c)
(a*b)*(a*b)=b*b=c=a*c=(a*a)*(b*b)
(b*c)*(b*c)=a*a=a=c*b=(b*b)*(c*c)
所以G是阿贝尔群
（2）因为a*a=a a*b=b*a=b a*c=c*a=c 所以G的单位元是a
（3）因为a*a=a 所以G的幂等元是a
（4）因为b*c=c*b=a，所以b的逆元是c且c的逆元是b
十、(10分)求叶的权分别为2、4、6、8、10、12、14的最优二叉树及其权。
解：最优二叉树为

权＝148
离散数学试题（B卷答案6）

一、（20分）用公式法判断下列公式的类型：
(1)(ØP∨ØQ)®(P«ØQ)
(2)(P¯Q)®(P∧Ø(Q∨ØR))
解：（1）因为(ØP∨ØQ)®(P«ØQ)ÛØ(ØP∨ØQ)∨(P∧ØQ)∨(ØP∧Q)
Û(P∧Q)∨(P∧ØQ)∨(ØP∧Q)
Û∨∨
Û
所以，公式(ØP∨ØQ)®(P«ØQ)为可满足式。
（2）因为(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)
Û∧
Û∨∨∨∨∨
所以，公式(P¯Q)®(P∧Ø(Q∨ØR))为可满足式。
二、（15分）在谓词逻辑中构造下面推理的证明：每个科学家都是勤奋的，每个勤奋又身体健康的人在事业中都会获得成功。存在着身体健康的科学家。所以，存在着事业获得成功的人或事业半途而废的人。
解：论域：所有人的集合。()：是勤奋的；()：是身体健康的；()：是科学家；()：是事业获得成功的人；()：是事业半途而废的人；则推理化形式为：
(()®())，(()∧()®())，(()∧())(()∨())
下面给出证明：
(1)(()∧()) P
(2)()∧() T(1)，ES
(3)(()®()) P
(4)()®() T(1)，US
(5)() T(2)，I
(6)() T(4)(5)，I
(7)() T(2)，I
(8)()∧() T(6)(7)，I
(9)(()∧()®()) P
(10)()∧()®() T(9)，Us
(11)() T(8)(10)，I
(12)() T(11)，EG
(13)(()∨()) T(12)，I
三、（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分）设R和S是集合A上的任意关系，判断下列命题是否成立？
(1)若R和S是自反的，则R*S也是自反的。
(2)若R和S是反自反的，则R*S也是反自反的。
(3)若R和S是对称的，则R*S也是对称的。
(4)若R和S是传递的，则R*S也是传递的。
(5)若R和S是自反的，则R∩S是自反的。
(6)若R和S是传递的，则R∪S是传递的。
解 (1)成立。对任意的∈，因为R和S是自反的，则<，>∈R，<，>∈S，于是<，>∈R*S，故R*S也是自反的。
(2)不成立。例如，令＝{1，2}，R＝{<1，2>}，S＝{<2，1>}，则R和S是反自反的，但R*S＝{<1，1>}不是反自反的。
(3)不成立。例如，令＝{1，2，3}，R＝{<1，2>，<2，1>，<3，3>}，S＝{<2，3>，<3，2>}，则R和S是对称的，但R*S＝{<1，3>，<3，2>}不是对称的。
(4)不成立。例如，令＝{1，2，3}，R＝{<1，2>，<2，3>，<1，3>}，S＝{<2，3>，<3，1>，<2，1>}，则R和S是传递的，但R*S＝{<1，3>，<1，1>，<2，1>}不是传递的。
(5)成立。对任意的∈，因为R和S是自反的，则<，>∈R，<，>∈S，于是<，>∈R∩S，所以R∩S是自反的。
五、（15分）令X＝{x1，x2，…，xm}，Y＝{y1，y2，…，yn}。问
(1)有多少个不同的由X到Y的函数？
(2)当n、m满足什么条件时，存在单射，且有多少个不同的单射？
(3)当n、m满足什么条件时，存在双射，且有多少个不同的双射？
解 (1)由于对X中每个元素可以取Y中任一元素与其对应，每个元素有n种取法，所以不同的函数共nm个。
(2)显然当|m|≤|n|时，存在单射。由于在Y中任选m个元素的任一全排列都形成X到Y的不同的单射，故不同的单射有m!＝n(n－1)(n―m