离散数学试题(A卷及答案）
一、证明题（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
2)
x(A(x)
B(x))
B(x))xA(x)
xA(x)
x(xB(x)
(P∧Q∧R)的主析取范式和主合取范式（10
T∧R(置换)xB(x) A(x)∨B(x))
x
A(x)∨xB(x)R
证明 ：x(A(x)xA(x)∨xB(x)
二、求命题公式(P∨(Q∧R))分）
证明：(P∨(Q∧R))
（((
∨(
P∧
Q∧
P∧(P∧P∧
(P∧Q∧R)Q∨Q)∨(
(P∨(Q∧R))∨(P∧Q∧R))
R)）∨(P∧Q∧R) P∧
R))∨(P∧Q∧R) P∧
Q∧
R)∨(
P∧Q∧
R))
Q∧R)∨(
R))∨(P∧Q∧R) m0∨m1∨m2∨m7 M3∨M4∨M5∨M6
三、推理证明题（10分） 1）
C∨D, (C∨D)(A∧R∨S
证明：(1) (C∨D)
E
(5) (C∨D)
(R∨S)
B), (A∧
B)
E,
E
(2)
E
(A∧(A∧B)
B) B)
(R∨S)(3) (C∨D)(4) (A∧
(R∨S)
(6) C∨D (7) R∨S 2) xP(x)
x(P(x)Q(y)∧
Q(y)∧R(x))，x(P(x)∧R(x)) xP(x)
(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))
x(P(x)∧R(x))
证明（1）(2)P(a) (3)
x(P(x)Q(y)∧R(x)) (11)Q(y)∧
(4)P(a)Q(y)∧R(a)
四、设m是一个取定的正整数，证明：在任取m＋1个整数中，至少有两个整数，它们的差是m的整数倍
证明 设a1，a2，…，am?1为任取的m＋1个整数，用m去除它们所得余数只能是0，1，…，m－1，由抽屉原理可知，a1，a2，…，am?1这m＋1个整数中至少存在两个数as和at，它们被m除所得余数相同，因此as和at的差是m的整数倍。
五、已知A、B、C是三个集合，证明A-(B∪C)=(A-B)∩(A-C) （15分） 证明 ∵x∧xx
A-（B∪C）
A∧x
x
A∧x
（B∪C） x A∧x
C）
x A∧（x
B
C） （x（A-C）
x
B）∧（x（A-B）∧
（A-B）∩（A-C）∴A-（B∪C）=（A-B）∩（A-C）
N∧y=x}，
2
六、已知R、S是N上的关系，其定义如下：R={
解：R={
-1
-1
N∧y=x+1}。求R、R*S、S*R、R{1,2}、S[{