离散数学试题(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 的整数倍
证明 设1a ，2a ，…，1+m a 为任取的m ＋1个整数，用m 去除它们所得余数只能是0，1，…，m －1，由抽屉原理可知，
1a ，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=x 2
}，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=x 2
}，R*S={| x,y
N ∧y=x 2
+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≥21-m
C＋2，则G是哈密尔顿图
证明若n≥21-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
证明左端((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(P(x)Q(x))∧xP(x)x(P(x)∧Q(x))
证明x(P(x)Q(x))∧xP(x)x((P(x)Q(x)∧P(x))x((P(x)∨Q(x)∧P(x))x(P(x)∧Q(x))xP(x)∧xQ(x)x(P(x)∧Q(x))
二、求命题公式(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)M1m0∨m2∨m3
三、推理证明题（10分）
1)(P (Q S))∧(R∨P)∧Q R S
证明：（1）R 附加前提
(2)R∨P P
(3)P T(1)(2),I
(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(P(x)∨Q(x))，x P(x)x Q(x)
证明：(1)x P(x) P
(2)P(c) T(1),US
(3)x(P(x)∨Q(x)) P
(4)P(c)∨Q(c) T(3),US
(5)Q(c) T(2)(4),I
(6)x Q(x) T(5),EG
四、例5在边长为1的正方形内任意放置九个点，证明其中必存在三个点，使得由它们组成的三角形（可能是退化的）面积不超
