离散数学试题(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 (2) ?E?(A∧?B)
P P
P
(3) (C∨D)?(A∧?B) T(1)(2)，I (4) (A∧?B)?(R∨S) (5) (C∨D)?(R∨S) (6) C∨D
T(3)(4)， I
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={
解：R={
S*R={
七、设R={，
解：r(R)={，
2
2
-1
2
-1
2
R= R={，
t(R)={，
八、证明整数集I上的模m同余关系R={
证明：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）=fg（10分）。
-1
-1-1
43
25
证明：因为f、g是双射，所以gf：A→C是双射，所以gf有逆函数（gf）：C→A。同理可推fg：C→A是双射。
因为
-1
-1
-1-1
-1-1
-1
-1
-1-1
-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(c)) T(3)，ES (5)B(b)?C(c) T(4)，US (6)A(a)?B(b) T(2)，US (7)A(a)?C(c) T(5)(6)，I (8)?xA(x)?C(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={
七、设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>} R=R={<2,2>,<2,4>,<3,4>,<4,4>,<5,1>,<5,5>,<5,4>} R={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<5,4>} R={<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满足：<
证明 对任意的
对任意的
432
5