离散数学试题(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[{1,2}]（10
N∧y=x}，R*S={
2
2
N∧y=x+1}，
2
N∧y=（x+1）}，
-1
-1
-1
七、若f:A→B和g:B→C是双射，则（gf）=fg（10分）。
证明：因为f、g是双射，所以gf：A→C是双射，所以gf有逆函数（gf）：C→A。同理可推fg：C→A是双射。
因为
-1-1
-1
-1-1
存在z（
-1
-1
-1
-1-1
-1
R{1,2}={<1,1>,<2,4>}，S[{1,2}]={1,4}。
八、（15分）设
b*a，证明：
(1)对A中每个元a，有a*a＝a。 (2)对A中任意元a和b，有a*b*a＝a。 (3)对A中任意元a、b和c，有a*b*c＝a*c。 证明 由题意可知，若a*b＝b*a，则必有a＝b。 (1)由(a*a)*a＝a*(a*a)，所以a*a＝a。
(2)由a*(a*b*a)＝(a*a)*(b*a)＝a*b*(a*a)＝(a*b*a)*a，所以有
a*b*a＝a。
(3)由(a*c)*(a*b*c)＝(a*c*a)*(b*c)＝a*(b*c)＝(a*b)*c＝(a*b)*(c*a*c)＝(a*b*c)*(a*c)，所以有a*b*c＝a*c。
2九、给定简单无向图G＝
2，则G是哈密尔顿图
2证明 若n≥Cm。 ?1＋2，则2n≥m－3m＋6 （1）
2
若存在两个不相邻结点u、v使得d(u)＋d(v)＜m，则有2n＝?d(w)＜m＋(mw?V－2)(m－3)＋m＝m－3m＋6，与（1）矛盾。所以，对于G中任意两个不相邻结点u、v都有d(u)＋d(v)≥m，所以G是哈密尔顿图。 离散数学试题(B卷及答案） 一、证明题（10分）
2