山西储备物资管理局-光盘面

离散数学试题(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))

五、已知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}，S={| x,yN∧y=x+1}。求R、R*S、S*R、
R{1,2}、S[{1,2}]（10分）
解：R={| x,yN∧y=x}，R*S={| x,yN∧y=x+1}，S*R={| x,yN∧y=（x+1）}，
七、若f:A→B和g:B→C是双射，则（gf）=fg（10分）。
证明：因为f、g是 双射，所以gf：A→C是双射，所以gf有逆函数（gf）：C→A。同理可推fg：C→A是双射。
因为∈fg存在z（∈g∈f）存在z（∈f ∈g）∈gf∈（gf）,
-1-1-1-1-1
-1-1-1-1-1-1
-1222
2-1
证明（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))

所以（gf）=fg。
R{1,2}={<1,1>,<2,4>}，S[{1,2}]={1,4}。

离散数学试题(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)M1m0∨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

五、已知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
1< br>，A
2
，…，A
n
}是集合A的一个划分，定义R={|a 、b∈A
i
，I=1，2，…，n}，则R是A上的等价关系（15分）。
证明：a∈A必有i使得a∈A
i
，由定义知aRa，故R自反。
a,b∈A，若aRb ，则a,b∈A
i
，即b,a∈A
i
，所以bRa，故R对称。
a,b,c∈A，若aRb 且bRc，则a,b∈A
i
及b,c∈A
j< br>。因为i≠j时A
i
∩A
j
=，故i=j，即a,b,c∈A
i
，所以aRc，故R传递。
总之R是A上的等价关系。
七、若f:A→B是双射，则f:B→A是双射（15分）。
证明: 对任意的x∈A，因为 f是从A到B的函数，故存在y∈B，使∈f，∈f。所以,f是满射。
对任意 的x∈A，若存在y
1
,y
2
∈B，使得1
,x>∈f 且2
,x>∈f,则有1
>∈f且2
>∈f。因为f是函数，则y
1
=y
2
。所
以，f是单射。 因此f是双射。

-1-1
-1-1
-1-1
-1
-1-1-1
(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
一、 选择题.(每小题2分，总计30)

1. 给定语句如下：
（1）15是素数（质数）
（2）10能被2整除，3是偶数。
（3）你下午有会吗？若无会，请到我这儿来！
（4）2x+3>0.
（5）只有4是偶数，3才能被2整除。
(6)明年5月1日是晴天。
以上6个语句中，是简单命题的为（A）,是复合命题的为（B ）,是真命题的为（C）,是假命题的是（D）,真值待定的命题是（E）
A: ①(1)(3)(4)(6) ②(1)(4)(6) ③(1)（6） B: ①(2)(4) ②(2)(4)(6) ③(2)(5)
C: ①(1)(2)(5)(6) ②无真命题 ③（5） D: ①(1)(2) ②无假命题 ③(1)(2)(4)(5)
E: ①(4)(6) ②（6） ③ 无真值待定的命题
2. 将下列语句符号化：
（1）4是偶数或是奇数。（A）设p：4是偶数，q：4是奇数
（2）只有王荣努力学习，她才能取得好成绩。（B）设p：王荣努力学习，q：王荣取得好成绩 （3）每列火车都比某些汽车快。（C）设F(x):x是火车，G(y):y是汽车，H(x,y):x比 y快。
A: ① p∨q ② p∧q ③ p→q B: ① p→q ② q→p ③ p∧q
C: ①
x

y
((F(x) ∧G(y)) → (H(x,y))②
x
(F(x) →
y
(G(y)∧H(x,y)))③
x
(F(x) ∧
y
(G(y)∧H(x,y)))
3. 设S={1,2,3},下图给出了S 上的5个关系,则它们只具有以下性质:R
1
是（A）,R
2
是(B),R< br>3
是(C)。

A B C:①自反的，对称的，传递的 ②反自反的，对称的 ③自反的
反对称的 ⑤对称的 ⑥自反的，对称的，反对称的，传递的
4. 设S={Ф，{1}，{1，2}}，则有
（1）（A）S （2） (B) S
（3） P(S)有（C）个元数。 （4）（D）既是S的元素，又是S的子集
A: ① {1,2} ② 1 B: ③{{1,2}} ④{1}
C: ⑤ 3 ⑥ 6 ⑦ 7 ⑧ 8 D: ⑨ {1} ⑩Ф
二、证明（本大题共2小题，第1小题10分，第2小题10分，总计20分）
1、用等值演算算法证明等值式 (p∧q)∨(p∧q)p
2、构造下面命题推理的证明
如果今天是星期三，那么我有一次英语或数学测验；如果数学老 师有事，那么没有数学测验；今天是星期三且数学老师有事，
所以我有一次英语测验。
三、计算（本大题共4小题，第1小题5分，第2小题10分，第3小题15分，
总计30分）
1、设
P

x,y

为x整除y， Q

x

为x2，个体域为

1，2

，求公式：

x

y

P

x ,y

Q

x

的真值。
2、设集合
3、设
A
A

1,2,3,4

,A
上的关 系
R

1,1,1,2,2,1,2,3,3,4

，求出它的 自反闭包，对称闭包和传递闭包。

1,2,4,8,12,24,

上的 整除关系
R

a
1
,a
2
a
1
,a
2
A,a
1
整除a
2

，
R
是否为
A
上的偏序关系？若是，则：

1、画出
R
的哈斯图；（10分）
2、求它的极小元，最大元，极大元，最大元。（5分）
四、用推导法求公式
答案：
一、 选择题
1. A:③ B: ③ C:③ D:① E:② 2.A:① B: ② C:②
3.A:③ B: ④ C:⑥ 4.A:① B: ③ C:⑧ D:⑩
二、证明题
1. 证明 左边（(p∧q)∨p）∧（(p∧q)∨q)） （分配律）
 p∧（(p∧q)∨q)） (吸收律)
 p∧（(p∨q) ∧ (q∨q)） （分配律）
 p∧（(p∨q)∧1） （排中律）
 p∧ (p∨q) （同一律）
 p （吸收律）
2.解：p：今天是星期三。
q：我有一次英语测验。
r：我有一次数学测验。
s：数学老师有事。
前提：p(q∨r) , sr , p∧s
结论：q
证明：①p∧s 前提引入
②p ①化简
③p(q∨r) 前提引入
④q∨r ②③假言推理
⑤s ①化简
⑥sr 前提引入
⑦r ⑤⑥假言推理
⑧q ④⑦析取三段论
推理正确。
三、计算

pq

p

的主析取范式和主合取范式。（本大题10分）

x

y


P

x,y

Q

x


1.

y



P

1,y

Q

1




P

2,y
< br>Q

2







P

1,1

Q

1



P

2,1

Q

2






P

1,2
Q

1




P

2, 2

Q

2




P

1,1

1,P

1,2

1,P

2,1

0,P

2,2

1,Q

1

1,Q

2

0



11



00





11



10


1
该公式的真值是1，真命题。

x

y

P

x,y

Q

x



x

P

x,1

Q
x



P

x,2

Q

x



P

1,1

Q

1



P

1, 2

Q

1



P

2,1

Q

2



P< br>
2,2

Q

2

或者


TT



TT



FF



TF


TT



TF

TTT

< br>2、
r(R)

1,1,1,2,2,1,2,3,3,4,2,2,3,3 ,4,4


s(R)

1,1,1,2,2,1,2,3,3, 4,3,2,4,3


t(R)

1,1,1,2,2,1,2 ,3,3,4,1,3,2,2,2,4,1,4


3、（1）
R
是
A
上的偏序关系。





（2）极小元、最小元是1,极大元、 最大元是24。
四、


pq

p





 pq

p




pq

p

p
p

qq


< br>
pq



pq


< br>
2，3

主合取范式


0，1
