. . . . .
离散数学试题(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))
.
word . .
. . . . .
证明(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={
.
word . .
2
2
-1
2
-1
2
. . . . .
七、设R={,,
解:r(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
432
5
证明:因为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)
.
word . .
离散数学期末考试试题及答案



