山大研究生招生信息网-兰亭集序原文

离散数学习题解答
数理逻辑习题
1. 将下列命题符号化：
（1）要是明天不下雨且我有时间，那么我去步行街购物。
设p：明天下雨 q：我有时间 r：我去步行街购物
(pq)r

（2）如果小王和小张是一个组，那么这次英语竞赛一定取胜。
设p：小王和小张是一个组 q：这次英语竞赛一定取胜
pq

（3）除非天下雨，否则他不乘出租车上班。
设p：天下雨 q：他乘出租车上班
qp

（4）我反悔，仅当太阳从西边出来。
设p：我反悔 q：太阳从西边出来
pq

（5）如果
f(x)
在点
x
0
处 可导，则
f(x)
在点
x
0
处可微。反之亦然。
设p：
f(x)
在点
x
0
处可导 q：
f(x)
在点
x
0
处可微
pq

（6）明天既不是晴天也不是下雨天。
设p：明天是晴天 q：明天是雨天
pq


4、用真值表判断下列公式的类型。
（2）
(pq)r

p

0
0
0
0
1
1
1
1
公式是可满足式。

q

0
0
1
1
0
0
1
1
r

0
1
0
1
0
1
0
1
(pq)r

0
1
1
1
1
1
0
1
1

5、证明下列等值式
方法：等值演算、主范式、真值表
（2）
(p(qr))(pq)(pr)

(pq)(p r)
(pq)(pr)
(pq)pr
((pp) (qp))r

(qp)r
pqr
p( qr)
p(qr)
6、使用恒等式证明下列各式，并写出它们的对偶公式。
（3）
q((pq)p)T

q((pq)p)q((pq)p)
q((pp)(qp))
q(q p)
qqp
T
q((pq)p)T
的对偶公式：
q((pq)p)F


7、证明下列蕴涵式
（1）
pq(pq)

(pq)(pq)
(pq )(pq)
pqpq
T


2

8、
（1）
pqrs

（2）
m
3
m
8
m
10
m
12
m
14

（3）
M
0
M
1
M
2
M
4
M
5
M
6
M
7
M
9
M
11
M
13
M
15

（4）可满足式
9、求下列公式的主析取范式和主合取范式。

（1） < br>(pq)(qp)
(pq)qp
(pq)qp< br>pq
M
1
m
0
m
2
m
3
真值表法也很简单：00，10，11时是1，01时是0。

10、将下列公式化成与之等值且仅含
{,}
中联结词的公式。
（1）
(pq)r

(pq)r
((pq) r)
((pq)r)
((pq)r)

14、构造下面推理的证明。

（1）如果今天是星期六，我们就要到独秀峰或象鼻山 去玩，如果独秀峰人太多，我们就不
去独秀峰。今天是星期六。独秀峰游人太多，所以我们去象鼻山玩。
解：
设p：今天是星期六。q：我们到独秀峰玩。r：我们到象鼻山玩。s：独秀峰游人多。
前提：
p(qr)
，
sq
，
p
。
结论：
sr

证明：
①
p
前提引入

3

②
p(qr)
前提引入
③
qr
①②假言推理
④
s
附加前提引入
⑤
sq
前提引入
⑥
q
④⑤假言推理
⑦
r
③⑥析取三段论

（2）如果马会飞或羊吃草，则母鸡就会是飞鸟。如果母鸡是飞鸟，那么烤熟的鸭子还会跑。
烤 熟的鸭子不会跑。所以，羊不吃草。
设p：马会飞。q：羊吃草。r：母鸡是飞鸟。s：烤熟的鸭子会跑。
前提：
(pq)r
，
rs
，
s

结论：
q

证明：
①
rs
前提引入
②
s
前提引入
③
r
①②拒取式
④
(pq)r
前提引入
⑤
(pq)
③④拒取式
⑥
pq
⑤等值演算
⑦
q
⑥化简规则
17、符号化下列语句。
（1）有会说话的机器人。
设：
F(x)
：x是机器人。
G(x)
：x会说话。
符号化为：
x(F(x)G(x))

（2）尽管有人很聪明，但未必一切人都聪明。
设：
F(x)
：x是人。
G(x)
：x很聪明。
符号化为：
x(F(x)G(x))x(F(x)G(x))

（3）并不是所有的汽车都比火车快。
设：
F(x)
：x是汽车。
G(y)
：y是火车。
L(x,y)
：x比y快。
符号化为：
x(F(x)y(G(y)L(x,y)))

（4）有的人不吃萝卜，但人都要喝水。

4

设：
F(x)
：x是人。
G(x)
：x吃萝卜。
H(x)
：x要喝水。
符号化为：
x(F(x)G(x))x(F(x)H(x))

（5）男人一定比女人高，是不对的。
设：
F(x)
：x是男人。
G(y)
：y是女人。
L(x,y)
：x比y高。
符号化为：
x(F(x)y(G(y)L(x,y)))

（6）某些汽车慢于所有的火车，但至少有一火车快于每一汽车。
设：
F(x)：x是汽车。
G(y)
：y是火车。
L(x,y)
：x比y慢。
符号化为：
xy(F(x)G(y)L(x,y))yx(F(x)G(y)L( x,y))

（7）两个不相等的实数间，必存在第三个实数。
设：
F(x )
：x是实数。
G(x,y)
：x和y相等。
L(x,y,z)
：z 在x和y之间。
符号化为：
xyz(F(x)F(y)F(z)G(x,y) L(x,y,z))

19、
（1）x是任意自然数，2x=x。真值为假。
（2）x和y是任意自然数，若x+2=y，那么y+2=x。真值为假。
（3）x和y是任意自然数，存在自然数z，使得x+y=z。真值为真。

20、
（1）命题公式的代换实例。永真式
（3）个体域：自然数。
F(x,y)
：x=y。真命题。
F(x,y)
：x>y。假命题。可满足式。

24、
（1）
xF(x)yG(x,y)
xF(x)yG(t,y)
x(F(x)yG(t,y))
xy(F(x)G(t,y))



5

（2）
xy(z(p(x,z)p(y,z ))uQ(x,y,z))
xy(z(p(x,z)p(y,z))uQ(x,y, t))
xyz((p(x,z)p(y,z))uQ(x,y,t))
x yzu((p(x,z)p(y,z))Q(x,y,t))


25、 < br>设
F(x)
：x是无理数。
G(x)
：x是有理数。
H(x)
：x能表示成分数。
前提：
x(F(x)H(x))
，
x (G(x)H(x))

结论：
x(G(x)F(x))

证明：
①
x(F(x)H(x))
前提引入
②
x(F(x)H(x))
①量词等值式
③
x(F(x)H(x))
②等值式
④
x(H(x)F(x))
③等值式
⑤
H(y)F(y)
④全称量词消去规则
⑥
x(G(x)H(x))
前提引入
⑦
G(y)H(y)
⑥全称量词消去规则
⑧
G(y)F(y)
⑤⑦假言三段论
⑨
x(G(x)F(x))
⑧全称量词引入规则

6

集合论与关系习题
2、集合应用题
文氏图求解，答案是5人。

5、已知
A{,{}}
，求
AP(A)
。
解：
P(A){,{},{{}},A}

AP(A){, ,,{},,{{}},,A,
{},,{},{}, {},{{}},{},A}


7、
解：R的关系矩阵为
0 0 1

1

0

0 0 0



1 1 0 1


0 0 1 0

R的关系图为：

9、
dom(A)={1,2,3}， dom(B)={1,2,4}，ran(A)={2,3,4}，ran(B)={2,3,4}。

11、

R
1
R
2

，
R
2
R
1
{a,d,a,c}
，
R
1< br>{a,a,a,b,a,d}
，
2
R
2
< br>


7
3

12、
（1）自反
（2）反对称、传递
（3）自反、对称、传递
（4）自反
（5）对称
（6）对称

13、
RR{0,2,0,3,1,3}

R
1
{ 1,0,2,0,3,0,2,1,3,1,3,2}

R{0,1}{0,1,0,2,0,3,1,2,1,3}

R[{1,2}]{2,3}


14、
[a]=[b]={a,b}，[c]=[d]={c,d}。

15、
（1）证明：
1）
x,yAA
，
xyx yx,yRx,y
，所以R自反。
2）
u,v,x,yAA
，
u,vRx,yuyx vxvuyx,yRu,v
，
所以R对称。
3）u,v,x,yAA
，
x,y,s,tAA
，

u,vRx,yuyxv
，
x,yRs,txtsy
，

8

由
u,vRx,yuyxv
和
x,yRs,txt sy
可得
uyxtxvsy
。
uyxtxv syutvssvu,vRs,t
。所以R
传递。
由1），2），3）可证R是A×A上的等价关系。
（2）
1,1,2,2,3,3,4,4
具有R关系，
1,2,2,3,3,4
具有R关系，
2,1,3,2,4,3
具有R关系，
1,3,2,4
具有R关系，
3,1,4,2
具有R关系，
由R确定的划分为{{
1,1,2,2,3,3,4,4
},
{
1,2,2,3,3,4
},
{
2,1,3,2,4,3
},
{
1,3,2,4
},
{
3,1,4,2
},
{
1,4
},
{


4,1
}}
19、
（1）必要性
R循环，由
aRb,bRb,
则
bRa
，所以R对称，
由
aRb,bRc,
则
cRa
，因为R对称，由
cRa，可得
aRc
，所以R传递，
因R自反，所以综上所述，R是等价关系。
（2）充分性
R是等价关系，所以R自反；

9

R是等价关系，
aRb,bRc,
则
aRc
，因为R对称，所以可得
cRa
，故R是循环的。

22、哈斯图：

极大元：7，8，9，10，11，12；
极小元：1
最小元：1
最大元：无

24、
上界：12，下界：1，最小上界：12，最大下界：1。

27、
（1）单射，不是满射
（2）不是满射，也不是单射
（3）不是满射，也不是单射
（4）是满射，不是单射
（5）是单射，不是满射
（6）不是单射，也不是满射

29、
（1）计算
f(Z)
。
{0,1,2,...,n1}

（2）确定商集
ZR
。

10

{{nk0},{nk1},{nk2},...{nk,n1}kZ}


11