离散数学考试试题(A卷及答案）
一、证明题（10分）
1) (P∧Q∧A?C)∧(A?P∨Q∨C)? (A∧(P?Q))?C。P<->Q=(p->Q)合取（Q->p）
证明: (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
??( A∧((P∧Q)∨(?P∧?Q)))∨C再反用分配律 ??( A∧(P?Q))∨C ?(A∧(P?Q))?C
2) ?(P?Q)? ?P??Q。
证明：?(P?Q)??(?(P∧Q))??(?P∨?Q))??P??Q。
二、分别用真值表法和公式法求(P?(Q∨R))∧(?P∨(Q?R))的主析取范式与主合取范式，并写出其相应的成真赋值和成假赋值（15分）。
主析取范式与析取范式的区别：主析取范式里每个括号里都必须有全部的变元。 主析取范式可由 析取范式经等值演算法算得。 证明：
公式法：因为(P?(Q∨R))∧(?P∨(Q?R))
?(?P∨Q∨R)∧(?P∨(Q∧R)∨(?Q∧?R))
?(?P∨Q∨R)∧(((?P∨Q)∧(?P∨R))∨(?Q∧?R))分配律
?(?P∨Q∨R)∧(?P∨Q∨?Q)∧(?P∨Q∨?R)∧(?P∨R∨?Q)∧(?P
∨R∨?R)
?(?P∨Q∨R)∧(?P∨Q∨?R)∧(?P∨?Q∨R)
?M4∧M5∧M6使（非P析取Q析取R）为0所赋真值，即100，二进制
为4
?m0∨m1∨m2∨m3∨m7
所以，公式(P?(Q∨R))∧(?P∨(Q?R))为可满足式，其相应的成真赋值为000、001、010、011、111：成假赋值为：100、101、110。
1 / 6
真值表法：
P Q R 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 Q?R 1 0 0 1 1 0 0 1 P?(Q∨R) 1 1 1 1 0 1 1 1 ?P∨(Q?R) 1 1 1 1 1 0 0 1 (P?(Q∨R))∧(?P∨(Q?R)) 1 1 1 1 0 0 0 1 由真值表可知，公式(P?(Q∨R))∧(?P∨(Q?R))为可满足式，其相应的成真赋值为000、001、010、011、111：成假赋值为：100、101、110。 三、推理证明题（10分）
1）?P∨Q，?Q∨R，R?SP?S。
证明：
(1)P 附加前提 (2)?P∨Q P
(3)Q T(1)(2)，I（析取三段论） (4)?Q∨R P
(5)R T(3)(4)，I（析取三段论） (6)R?S P
(7)S T(5)(6)，I（假言推理） (8)P?S CP
2) ?x(P(x)?Q(y)∧R(x))，?xP(x)?Q(y)∧?x(P(x)∧R(x))
证明（1）?xP(x) (2)P(a)
(3)?x(P(x)?Q(y)∧R(x)) (4)P(a)?Q(y)∧R(a) (5)Q(y)∧R(a) (6)Q(y) (7)R(a) (8)P(a) (9)P(a)∧R(a)
2 / 6
(10)?x(P(x)∧R(x)) (11)Q(y)∧?x(P(x)∧R(x))
五、已知A、B、C是三个集合，证明(A∪B)－C＝(A－C)∪(B－C) （10分）
证明：因为
x∈(A∪B)－C?x∈(A∪B)－C
?x∈(A∪B)∧x?C ?(x∈A∨x∈B)∧x?C
?(x∈A∧x?C)∨(x∈B∧x?C) ?x∈(A－C)∨x∈(B－C) ?x∈(A－C)∪(B－C)
所以，(A∪B)－C＝(A－C)∪(B－C)。
八、证明整数集I上的模m同余关系R={
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
证明：
因为f、g是双射，所以gf：A→C是双射，所以gf有逆函数（gf）：C→A。同理可推fg：C→A是双射。
因为
-1
-1
-1-1
-1-1
-1
-1
-1-1
-1
离散数学考试试题(B卷及答案）
一、证明题（10分）
1)((P∨Q)∧?(?P∧(?Q∨?R)))∨(?P∧?Q)∨(?P∧?R)?T
3 / 6