离散数学试题(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⇔T∧R(置换)⇔R
2)∃x(A(x)→B(x))⇔∀xA(x)→∃xB(x)
证明：∃x(A(x)→B(x))⇔∃x(⌝A(x)∨B(x))⇔∃x⌝A(x)∨∃xB(x)⇔⌝∀xA(x)∨∃xB(x)⇔∀xA(x)→∃xB(x)
二、求命题公式(P∨(Q∧R))→(P∧Q∧R)的主析取范式和主合取范式（10分）
证明：(P∨(Q∧R))→(P∧Q∧R)⇔⌝(P∨(Q∧R))∨(P∧Q∧R))
⇔（⌝P∧(⌝Q∨⌝R)）∨(P∧Q∧R)
⇔(⌝P∧⌝Q)∨(⌝P∧⌝R))∨(P∧Q∧R)
⇔(⌝P∧⌝Q∧R)∨(⌝P∧⌝Q∧⌝R)∨(⌝P∧Q∧⌝R))∨(⌝P∧⌝Q∧⌝R))∨(P∧Q∧R)
⇔m0∨m1∨m2∨m7
⇔M3∨M4∨M5∨M6
三、推理证明题（10分）
1）C∨D, (C∨D)→⌝E, ⌝E→(A ∧⌝B), (A∧⌝B)→(R∨S)⇒R∨S
证明：(1) (C∨D)→⌝E (2) ⌝E→(A∧⌝B)
(3) (C∨D)→(A∧⌝B)
(4) (A∧⌝B)→(R∨S)
(5) (C∨D)→(R∨S)
(6) C∨D
(7) R∨S
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))
四、设m是一个取定的正整数，证明：在任取m＋1个整数中，至少有两个整数，它们的差是m的整数倍
证明设
1
a，2a，…，1+m a为任取的m＋1个整数，用m去除它们所得余数
只能是0，1，…，m－1，由抽屉原理可知，
1
a，2a，…，1+m a这m＋1个整
数中至少存在两个数
s
a和t a，它们被m除所得余数相同，因此s a和t a的差是m的整数倍。
五、已知A、B、C是三个集合，证明A-(B∪C)=(A-B)∩(A-C) （15分）证明∵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）
六、已知R、S是N上的关系，其定义如下：R={| x,y∈N∧y=x2}，S={| x,y∈N∧y=x+1}。求R-1、R*S、S*R、R{1,2}、S[{1,2}]（10分）
解：R-1={| x,y∈N∧y=x2}，R*S={| x,y∈N∧y=x2+1}，S*R={| x,y∈N∧y=（x+1）2}，
七、若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是双射。
因为∈f-1g-1⇔存在z（∈g-1∧∈f-1）⇔存在z（∈f∧∈g）⇔∈gf⇔∈（gf）-1,所以（gf）-1=f-1g-1。
R{1,2}={<1,1>,<2,4>}，S[{1,2}]={1,4}。
八、（15分）设是半群，对A中任意元a和b，如a≠b必有a*b≠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。
九、给定简单无向图G＝，且|V|＝m，|E|＝n。试证：若n≥2
1-
m
C＋2，则G是哈密尔顿图
证明若n≥2
1-
m
C＋2，则2n≥m2－3m＋6 （1）。
若存在两个不相邻结点u、v使得d(u)＋d(v)＜m，则有2n＝∑
∈V
w
w
d)
(＜m＋(m
－2)(m－3)＋m＝m2－3m＋6，与（1）矛盾。所以，对于G中任意两个不相邻结点u、v都有d(u)＋d(v)≥m，所以G是哈密尔顿图。
离散数学试题(B卷及答案）
一、证明题（10分）
1)((P∨Q)∧⌝(⌝P∧(⌝Q∨⌝R)))∨(⌝P∧⌝Q)∨(⌝P∧⌝R)⇔T
