辽宁大学图书馆-退休赠言

离散数学 考试题(后附详细答案)

一、命题符号化（共6小题，每小题3分，共计18分）
1. 用命题逻辑把下列命题符号化
a) 假如上午不下雨，我去看电影，否则就在家里读书或看报。
设P表示命题“上午下雨” ，Q表示命题“我去看电影”，R表示命题“在家里读书”，S表示
命题“在家看报”，命题符号化为： （P⇄Q）(P⇄RS)
b) 我今天进城，除非下雨。
设P表示命题“我今天进城”，Q表示命题“天下雨”，命题符号化为：Q→P或P→Q
c) 仅当你走，我将留下。
设P表示命题“你走”，Q表示命题“我留下”，命题符号化为： Q→P
2. 用谓词逻辑把下列命题符号化
a) 有些实数不是有理数
设R(x)表示“x是实数”，Q(x)表示“x是有理数”，命题符号化为：
x(R(x) Q(x)) 或 x(R(x) →Q(x))

b) 对于所有非零实数x，总存在y使得xy=1。
设R(x)表示“x是实数”，E(x,y)表示“x=y”,f(x,y)=xy, 命题符号化为：
x(R(x) E(x,0) →y(R(y) E(f(x,y),1))))

c) f 是从A到B的函数当且仅当对于每个a∈A存在唯一的b∈B，使得f(a)=b.
设F(f)表示“f是从A到B的函数”, A(x)表示“x∈A”, B(x)表示“x∈B”,E(x,y)表示“x=y”,
命题符号化为：F(f)⇄a(A(a)→b(B(b) E(f(a),b) c(S(c) E(f(a),c) →E(a,b))))

二、简答题（共6道题，共32分）
1. 求命题公式(P→(Q→R))(R→(Q→P) )的主析取范式、主合取范式，并写出所有成真赋
值。（5分）
(P→(Q→R))(R→(Q→P))（PQR）(PQR)
（P(QR）→(PQR)) ((PQR) →（PQR）).
(（PQR） (PQR)) ((PQR) （PQR）)
(PQR)(PQR) 这是主合取范式
公式的所有成真赋值为000,001,010,100,101,111,故主析取范式为
（PQR（PQR（PQR（PQR（PQR
（PQR

2. 设个体域为{1,2,3}，求下列命题的真值（4分）
a) xy(x+y=4)
b) yx (x+y=4)
a) T b) F

3. 求x(F(x)→G(x))→(xF(x)→xG(x))的前束范式。（4分）
x(F(x)→G(x))→(xF(x)→xG(x)) x(F(x)→G(x))→(yF(y)→zG(z))

x(F(x)→G(x))→yz(F(y)→G(z)) xyz((F(x)→G(x))→ (F(y)→
G(z)))

4. 判断下面命题的真假，并说明原因。（每小题2分，共4分）
a) （AB）－C=(A-B) (A-C)
b) 若f是从集合A到集合B的入射函数，则|A|≤|B|
a) 真命题。因为（AB）－C=（AB）~C=（A~C）（B~C）=（A-C）（B-C）
b) 真 命题。因为如果f是从集合A到集合B的入射函数，则|ranf|=|A|，且ranfB,故
命题成 立。

5. 设A是有穷集，|A|=5，问（每小题2分，共4分）
a) A上有多少种不同的等价关系？
b) 从A到A的不同双射函数有多少个？
a) 52 b) 5!=120

6. 设有偏序集，其哈斯图如图1，求子集B={b,d ,e}的最小元，最大元、极大元、
极小元、上界集合、下界集合、上确界、下确界，(5分)
f g

d e

b c

a

图1

B的最小元是b，无最大元、极大元是d和e、极小元是b、上界集合是{g}、下界集合是{a,b} 、
上确界是g、下确界是b.

7. 已知有限集S={a
1
,a
2
,…,a
n
},N为自然数集合，R为实数集合，求下列集合的基数
S;P(S);N,N;P(N);R,R×R,{o,1}（写出即可）(6分)
K[S]=n; K[P(S)]=
2
; K[N]=
,K[{0,1}]=

三、证明题（共3小题，共计40分）
1. 使用构造性证明，证明下面推理的有效性。（每小题5分，共10分）
a) A→(B∧C),(E→F)→C, B→(A∧S)B→E
b) x(P(x)→Q(x)), x(Q(x)∨R(x))，xR(x) xP(x)
a) 证 （1）B P(附加条件)
（2）B→(A∧S) P
(3) A∧S T(1)(2) I
(4) A T(3) I
(5) A→(B∧C) P
N
n
N
n
0
,K[N]=
n
0
, K[P(N)]=; K[R]=, K=[R×R]=

(6) B∧C T(4)(5) I
(7) C T(6) I
(8) (E→F)→C P
(9) (E→F) T(7)(8) I
(10) E∧F T(9) E
(11) E T(10) I
(12) B→E CP
b) 证 (1) xR(x) P
(2) R(c) ES(1)
(3) x(Q(x)∨R(x)) P
(4) Q(c)∨R(c) US(3)
(5) Q(c) T(2)(4) I
(6) x(P(x)→Q(x)) P
(7) P(c)→Q(c) US(6)
(8) P(c) T(5)(7) I
(9) xP(x) EG(8)

2. 设R
1
是A上的等价关系，R
2
是B上的等价关系，A≠且B ≠，关系R满足：
<1
,y
1
>,2
,y
2
>>∈R，当且仅当< x
1
, x
2
>∈R
1
且1
,y
2
>∈R
2
。试证明：R是A×B上 的
等价关系。（10分）
证 任取,
∈A×Bx∈A y∈ B∈R
1
∈R
2
<,>∈R，故 R是自反的
任取<,>,
<,>∈R∈R
1
∈R
2
∈R
1
∈ R
2
<,>∈R.
故R是对称的。
任取<,>,<,>∈R
<,>,<,>∈R∈R
1
∈R
2
∈R
1
∈R
2
(∈R
1
∈R
1
)(∈R
2
∈R
2
) R
1
∈R
2
<,>
∈R, 故R是传递的。
综上所述R是A×B上的等价关系。

3. 用伯恩斯坦定理证明（0,1]和(a,b)等势。（10分）
证 构造函数f：（0,1]→(a,b)，f(x)=
ab
x
,显然f是入射函数
22
xa
,显然g是入射函数，
ba
2
构造函数g: (a,b)→（0,1]，
g(x)
故（0,1]和(a,b)等势。 < br>2
m
1
2
m
2


m
r
2

m
1
m
2


mr

sn
2
由于


，所以
2

r
r
rr


4. 设R是集合A上的 等价关系，A的元素个数为n，R作为集合有s个元素，若A关于R

的商集AR有r个元 素，证明：rs≥n
2
。（10分）
证 设商集AR的r个等价类的元素个数分别 为m
1
,m
2
,…,m
r
，由于一个划分对应一个等价关系，m
1
+m
2
+…+m
r
=n，
m1
m
2


m
r
s

2
m
1
2
m
2


m
r2

m
1
m
2


m
r

由于


（r个数的平方的平均值大于等于这
rr
2
222
sn
2
2
r个数的平均值的平方），所以

2
，即
rsn

r
r

四、应用题（10分）
在一个道路上连接有8个城市，分别标记为a,b,c,d,e,f, g,h。城市之间的直接连接的道路是单
向的，有a→b, a→c, b→g, g→b, c→f, f→e, b→d, d→f.对每一个城市求出从它出发
所能够到达的所有其他城市。
解 把8个城市作为集合A的元素，即A={a,b,c,d,e,,f,g,h}，在A上定义二元关系R，
∈R当且仅当从x到y有直接连接的道路，即
R={,,,,,,,}
那么该问题即变为求R的传递闭包。

0

0


0

0
利用Warshal算法，求得t(R)=

< br>0


0

0



0< br>1111110

0011110


0001100


0001100



0000000
< br>0001000

1011110


0000000


那么从城市x出发能到达的城市为
(t(R)I
A
)[{x }]{y|x,yt(R)xy}
，
故有
(t(R)I
A
)[{a}]{b,c,d,e,f,g}

(t(R)I
A
)[{b}]{d,e,f,g}

(t(R)I
A
)[{c}]{e,f}

(t(R)I
A
)[{d}]{e,f}

(t(R)I
A
)[{f}]{e}

(t(R)I
A
)[{g}]{b,d,e,f}

(t(R) I
A
)[{e}](t(R)I
A
)[{e}]


离散数学 考试题答案
一、命题符号化（共6小题，每小题3分，共计18分）
1. 用命题逻辑把下列命题符号化
a) 设P表示命题“上午下雨”，Q表示命题“我去看电影”，R表示命题“在家里读书”，S
表示命题“在家看报”，命题符号化为：（P⇄Q）(P⇄RS)
b) 设P表示命题“我今天进城”，Q表示命题“天下雨”，命题符号化为：Q→P或P→
Q
c) 设P表示命题“你走”，Q表示命题“我留下”，命题符号化为： Q→P
2. 用谓词逻辑把下列命题符号化
a) 设R(x)表示“x是实数”，Q(x)表示“x是有理数”，命题符号化为：
x(R(x) Q(x)) 或 x(R(x) →Q(x))
b) 设R(x)表示“x是实数”，E(x,y)表示“x=y”,f(x,y)=xy, 命题符号化为：
x(R(x) E(x,0) →y(R(y) E(f(x,y),1))))

c) 设F(f)表示“f是从A到B的函数”, A(x)表示“x∈A”, B(x)表示“x∈B”,E(x,y)表示
“x=y”, 命题符号化为：
F(f)⇄a(A(a)→b(B(b) E(f(a),b) c(S(c) E(f(a),c) →E(a,b))))
二、简答题（共6道题，共32分）
1. (P→(Q→R))(R→(Q→P))（PQR）(PQR)
（P(QR）→(PQR)) ((PQR) →（PQR）).
(（PQR） (PQR)) ((PQR) （PQR）)
(PQR)(PQR) 这是主合取范式
公式的所有成真赋值为000,001,010,100,101,111,故主析取范式为
（PQR（PQR（PQR（PQR（PQR
（PQR
2. a) T b) F
3. x(F(x)→G(x))→(xF(x)→xG(x)) x(F(x)→G(x))→(yF(y)→zG(z))
x(F(x)→G(x))→yz(F(y)→G(z)) xyz((F(x)→G(x))→ (F(y)→
G(z)))
4. a) 真命题。因为（AB）－C=（AB）~C=（A~C）（B~C）=（A-C）
（B-C）
b) 真命题。因为如果f是从集合A到集合B的入射函数，则|ranf|=|A|，且ranfB, 故
命题成立。
5. a) 52 b) 5!=120
6. B的最小元是 b，无最大元、极大元是d和e、极小元是b、上界集合是{g}、下界集合
是{a,b}、上确界是g 、下确界是b.
7. K[S]=n; K[P(S)]=
2
; K[N]=
,K[{0,1}]=
三、证明题（共3小题，共计40分）
N
n
0
,K[N]=
n
0
, K[P(N)]=; K[R]=, K=[R×R]=

1. a) 证 （1）B P(附加条件)
（2）B→(A∧S) P
(3) A∧S T(1)(2) I
(4) A T(3) I
(5) A→(B∧C) P
(6) B∧C T(4)(5) I
(7) C T(6) I
(8) (E→F)→C P
(9) (E→F) T(7)(8) I
(10) E∧F T(9) E
(11) E T(10) I
(12) B→E CP
b) 证 (1) xR(x) P
(2) R(c) ES(1)
(3) x(Q(x)∨R(x)) P
(4) Q(c)∨R(c) US(3)
(5) Q(c) T(2)(4) I
(6) x(P(x)→Q(x)) P
(7) P(c)→Q(c) US(6)
(8) P(c) T(5)(7) I
(9) xP(x) EG(8)
2. 证 任取,
∈A×Bx∈A y∈B∈R
1
∈R
2
<,>∈R，故R是自反的
任取<,>,
<,>∈R∈R
1
∈R
2
∈R
1
∈R
2
<,>∈R.
故R是对称的。
任取<,>,<,>∈R
<,>,<,>∈R∈R
1
∈R
2
∈R
1
∈R
2
(∈R
1
∈R
1
)(∈R
2
∈R
2
) R
1
∈R
2
<,>
∈R, 故R是传递的。
综上所述R是A×B上的等价关系。
3. 证 构造函数f：（0,1]→(a,b)，f(x)=
ab
x
,显然f是入射函数
22
xa
,显然g是入射函数，
ba
2
构造函数g: (a,b)→（0,1]，
g(x)
故（0,1]和(a,b)等势。 < br>2
m
1
2
m
2


m
r
2

m
1
m
2


mr

sn
2
由于


，所以
2

r
r
rr

4. 证 设商集AR的r个等价 类的元素个数分别为m
1
,m
2
,…,m
r
，由于一个划分 对应一个等
价关系，m
1
+m
2
+…+m
r
=n，
m
1
m
2


m
r
s
222

2
m
1
2
m
2

m
r
2

m
1
m
2


m
r

由于


（r个 数的平方的平均值大于等于这
rr

2
sn
2
2
r个数的平均值的平方），所以

2
，即
rsn

r
r
四、应用题（10分）
解 把8个城市作为集合A的元素，即A={a ,b,c,d,e,,f,g,h}，在A上定义二元关系R，
∈R当且仅当从x到y有直接 连接的道路，即
R={,,,,, ,,}
那么该问题即变为求R的传递闭包。

0

0


0

0
利用Warshal算法，求得t( R)=


0


0

0


0
1111110

0011110


0001100


0001100



0000000

0001000

1011110


0000000


那么从城市x出发能到达的城市为
(t(R) I
A
)[{x}]{y|x,yt(R)xy}
，
故有
(t(R)I
A
)[{a}]{b,c,d,e,f,g}

(t(R)I
A
)[{b}]{d,e,f,g}

(t(R)I
A
)[{c}]{e,f}

(t(R)I
A
)[{d}]{e,f}

(t(R)I
A
)[{f}]{e}

(t(R)I
A
)[{g}]{b,d,e,f}

(t(R) I
A
)[{e}](t(R)I
A
)[{e}]
