离散数学考试试题(A、B卷及答案)
离散数学考试试题(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再反用分配律
GAGGAGAGGAFFFFAFAF
( 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分）。
主析取范式与析取范式的区别：主析取范式里每个括号里都必须有全部的变元。
主析取范式可由析取范式经等值演算法算得。
GAGGAGAGGAFFFFAFAF
证明：
公式法：因为(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)
M∧5M∧6M使（非P析取Q析取R）为0
4
GAGGAGAGGAFFFFAFAF
所赋真值，即100，二进制为4
GAGGAGAGGAFFFFAFAF
m∨1m∨2m∨3m∨7m
所以，公式(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 11
1
1
1
1
1
1
1
1
1
1
1
1
1
GAGGAGAGGAFFFFAFAF
GAGGAGAGGAFFFFAFAF
1
可满足式，其相应的成真赋值为000、001、010、011、111：成假赋值为：100、101、110。
三、推理证明题（10分）
1）P∨Q，Q∨R，R S P S。
证明：
(1)P附加前提
(2)P∨Q P
(3)Q T(1)(2)，I（析取三段论）
GAGGAGAGGAFFFFAFAF
(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))
GAGGAGAGGAFFFFAFAF
(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分）
证明：因为
GAGGAGAGGAFFFFAFAF
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={
证明：1）x∈I，因为（x-x）/m=0，所以x x(mod m)，
GAGGAGAGGAFFFFAFAF
即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分）。
GAGGAGAGGAFFFFAFAF
证明：
因为f、g是双射，所以gf：A→C是双射，所以gf 有逆函数（gf）-1：C→A 。同理可推f-1g -1：C→A 是双射。
因为
离散数学考试试题(B卷及答案）
一、证明题（10分）
1)((P∨Q)∧(P∧(Q∨R)))∨(P∧Q)∨(P ∧R)T
证明: 左端((P∨Q)∧(P∨(Q∧R)))∨((P∨Q)∧
GAGGAGAGGAFFFFAFAF
(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)
x P(x)∨yQ(y)
GAGGAGAGGAFFFFAFAF
(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
GAGGAGAGGAFFFFAFAF
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
GAGGAGAGGAFFFFAFAF
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)
GAGGAGAGGAFFFFAFAF
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
四、只要今天天气不好，就一定有考生不能提前进入考场，
当且仅当所有考生提前进入考场，考试才能准时进行。所
GAGGAGAGGAFFFFAFAF
以，如果考试准时进行，那么天气就好（15分）。
解：
设P：今天天气好，Q：考试准时进行，A(e )：e 提前进入考场，个体域：考生的集合，则命题可符号化为：P x A(x)，xA(x)Q Q P。
GAGGAGAGGAFFFFAFAF
(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
GAGGAGAGGAFFFFAFAF
(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={
GAGGAGAGGAFFFFAFAF