一、证明题（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)
∧∧使（非P析取Q析取R）为0所赋真值，即100，二进制为4
∨∨∨∨
所以，公式(P (Q∨R))∧( P∨(Q R))为可满足式，其相应的成真赋值为000、001、010、011、111：成假赋值为：100、101、110。
真值表法：
P Q R | Q R | P (Q∨R) | P∨(Q R) | (P (Q∨R))∧( 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 | 1 0 0 1 1 0 0 1 | 1 1 1 1 0 1 1 1 | 1 1 1 1 1 0 0 1 | 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)
(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分）
证明：因为
∈(A∪B)－C ∈(A∪B)－C
∈(A∪B)∧ C
(∈A∨∈B)∧ C
(∈A∧ C)∨(∈B∧ C)
∈(A－C)∨∈(B－C)
∈(A－C)∪(B－C)
所以，(A∪B)－C＝(A－C)∪(B－C)。
八、证明整数集I上的模m同余关系R={<x,y>|x y(mod m)}是等价关系。其中，x y(mod m)的含义是x-y可以被m整除（15分）。X(modm)=y(modm)
证明：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卷及答案）
一、证明题（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析取要使之为假，即赋真值001，即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）析取三段论
(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(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提前进入考场，个体域：考生的集 合，则命题可符号化为：PxA(x)，xA(x)QQP。
(1)PxA(x) P
(2)PxA(x) T(1)E
(3)xA(x)P T(2)E
(4)xA(x)Q P
(5)(xA(x)Q)∧(QxA(x)) T(4)E
(6)QxA(x) T(5)I
(7)QP 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分）。有就是1，没就是0
七、设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><5,5>}（自反闭包）
s(R)={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,2>,<4,2>,<4,3>}（对称闭包）
t(R)={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<2,2>,<5,1>,<5,4>,<5,5>}（传递闭包）
九、设f：A B，g：B C，h：C A，证明：如果hgf＝IA，fhg＝IB，gfh＝IC，则f、g、h均为双射，并求出f－1、g－1和h－1（10分）。
解 因IA恒等函数，由hgf＝IA可得f是单射，h是满射；因IB恒等函数，由fhg＝IB可得g是单射，f是满射；因IC恒等函数，由gfh＝IC可得h是单射，g是满射。从而f、g、h均为双射。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议