离散数学屈婉玲版课后答案.doc

(完整版)离散数学屈婉玲版课后答案
For personal use only in study and research； not for commercial use

3

习题一

1。1． 略

1。2． 略

1。3． 略

1。4． 略

1。5． 略

1.6． 略

1.7． 略

1。8． 略

1。9． 略

1。10．
1。11．
1.12．
略
略
将下列 命题符号化， 并给出各命题的 真值：

(1)2+2＝4当且仅当3+3＝6。

(2)2+2＝4的充要条件是3+3≠6。

（3）2+2≠4与3+3＝6互为充要条件.

(4)若2+2≠4, 则3+3≠6, 反之亦然。

（1）p↔q, 其中， p： 2+2＝4， q: 3+3＝6, 真值为1.

（2）p↔¬q, 其中, p： 2+2＝4, q： 3+3＝6， 真值为0.

（3) ¬p↔q, 其中， p: 2+2＝4， q: 3+3＝6， 真值为0.

(4) ¬p↔¬q, 其中， p: 2+2＝4, q： 3+3＝6， 真值为1。

将下列命题符号化, 并给出各命题的真值:

（1)若今天是星期一， 则明天是星期二.

（2)只有今天是星期一, 明天才是星期二。

(3）今天是星期一当且仅当明天是星期二。

(4)若今天是星期一， 则明天是星期三.

令 p: 今天是星期一; q： 明天是星期二； r： 明天是星期三.

(1) p→q ⇔ 1.

（2) q→p ⇔ 1.

(3） p↔q ⇔ 1.

(4) p→r当p ⇔ 0时为真; p ⇔ 1 时为假.

将下列 命题符号化。

(1） 刘晓月跑得快, 跳得高。

（2)老王是山东人或河北人。

（3）因为天气冷, 所以我穿了羽绒服.

(4)王欢与李乐组成一个小组。

（5)李辛与李末是兄弟。

（6）王强与刘威都学过法语。

(7)他一面吃饭， 一面听音乐.

(8)如果天下大雨, 他就乘班车上班.

(9）只有天下大雨， 他才乘班车上班。

（10)除非天下大雨, 他才乘班车上班。

（11)下雪路滑, 他迟到了.

(12)2与4都是素数， 这是不对的.

（13)“2或4是素数, 这是不对的”是不对的.

4

(1)p∧q, 其中， p: 刘晓月跑得快， q: 刘晓月跳得高。

(2）p∨q， 其中， p: 老王是山东人， q: 老王是河北人。

(3）p→q， 其中， p: 天气冷, q： 我穿了羽绒服。

（4)p, 其中, p： 王欢与李乐组成一个小组， 是简单命题。

（5)p， 其中, p： 李辛与李末是兄弟。

(6）p∧q, 其中, p: 王强学过法语， q： 刘威学过法语。

（7)p∧q, 其中， p: 他吃饭， q： 他听音乐.

（8)p→q, 其中, p: 天下大雨， q： 他乘班车上班。

（9）p→q, 其中, p: 他乘班车上班， q: 天下大雨。

（10）p→q， 其中, p: 他乘班车上班， q: 天下大雨.

（11）p→q， 其中, p: 下雪路滑， q： 他迟到了。

（12） ¬ (p∧q）或¬p∨¬q, 其中, p: 2是素数, q: 4是素数.

(13） ¬¬ (p∨q）或p∨q， 其中, p: 2是素数， q： 4是素数.

设p： 2+3=5。

q： 大熊猫产在中国。

r： 复旦大学在广州.

求下列复合命题的真值：

(1)(p↔q） →r

(2）（r→ （p∧q）) ↔ ¬p

(3) ¬r→ (¬p∨¬q∨r)

（4）（p∧q∧¬r) ↔ （（ ¬p∨¬q） →r)

（1)真值为0.

（2）真值为0。

(3)真值为0.

(4)真值为1。

注意： p， q是真命题, r是假命题。

1。16．
1.17．
1.18．
1。19．
略
略
略
用真值表判断下列公式的类型：

(1）p→ （p∨q∨r)

（2）（p→¬q） →¬q

（3) ¬ (q→r) ∧r

（4)（p→q) → （¬q→¬p)

（5）（p∧r） ↔ （ ¬p∧¬q）

（6）(（p→q) ∧ (q→r)) → (p→r)

（7）（p→q) ↔ （r↔s)

5

(1）， (4)， (6)为重言式.

(3）为矛盾式.

(2）， （5), （7）为可满足式.

1。20．
1.21．
1.22．
1.23．
1.24．
1。25．
1.26．
1。27．
1.28．
1。29．
1。30．
1。31．
略
略
略
略
略
略
略
略
略
略
略
将下列 命题符号化， 并给出各命题的 真值:

(1)若3+＝4， 则地球是静止不动的.

(2)若3+2＝4, 则地球是运动不止的。

（3)若地球上没有树木, 则人类不能生存.

(4）若地球上没有水, 则3是无理数.

（1）p→q， 其中, p： 2+2＝4, q: 地球静止不动, 真值为0。

（2）p→q, 其中, p: 2+2＝4， q： 地球运动不止， 真值为1。

（3) ¬p→¬q, 其中， p： 地球上有树木， q： 人类能生存, 真值为1.

（4) ¬p→q， 其中， p: 地球上有水, q: 3是无理数, 真值为1。

6

习题二

2。1。 设公式 A = p→q, B = p¬∧q， 用真值表验证公式 A 和 B 适合德摩根律：

¬（A∨B） ⇔ ¬A¬∧B。

A =p→q B =p¬∧q ¬（A∨B） ¬A¬∧B

0

0

1

1
0

1

0

1
1

1

0

1
0

0

1

0
0

0

0

0
0

0

0

0

因为¬（A∨B)和¬A¬∧B的真值表相同, 所以它们等值.

2.2。 略

2。3. 用等值演算法判断下列公式的类型, 对不是重言式的可满足式, 再用真值表法求出成真赋值.

（1） ¬ (p∧q→q）

（2）(p→ (p∨q）) ∨ （p→r)

（3）（p∨q） → （p∧r)

（1) ¬ （p∧q→q)⇔ ¬ （¬（p∧q） ∨ q） ⇔ ¬ （¬p ∨ ¬q ∨ q） ⇔ p∧q∧¬q ⇔ p∧0 ⇔ 0 ⇔ 0. 矛盾式。

(2)重言式。

(3) （p∨q） → (p∧r） ⇔ ¬(p∨q) ∨ （p∧r） ⇔ ¬p¬∧q ∨ p∧r易见, 是可满足式， 但不是重言式。 成真赋值为： 000,

001， 101, 111

¬p ∧ ¬q ∨ p∧r

1
1
1
1
0
0
0
0
1
1
0
0
0
0
0
0
1
1
0
0
1
1
0
0
1
1
0
0
0
1
0
1
0
0
0
0
0
1
0
1

2。4. 用等值演算法证明下面等值式:

(1) p⇔ （p∧q) ∨ (p∧¬q)

(3) ¬ (p↔q） ⇔ (p∨q） ∧¬ （p∧q）

(4) （p∧¬q） ∨ （¬p∧q） ⇔ (p∨q） ∧¬ (p∧q）

（1） （p∧q) ∨ （p∧¬q) ⇔ p ∧ (q¬∨q) ⇔ p ∧ 1 ⇔ p。

（3) ¬ (p↔q) p q r
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

7

⇔¬ （（p→q) ∧ （q→p)）

⇔¬ （(¬p∨q） ∧ (¬q∨p）)

⇔ (p∧¬q） ∨ (q∧¬p）

⇔ （p∨q） ∧ (p∨¬p) ∧ （¬q∨q) ∧ (¬p∨¬q）

⇔ （p∨q） ∧¬ （p∧q)

(4) （p∧¬q） ∨ （¬p∧q)

⇔ (p∨¬p） ∧ (p∨q） ∧ (¬q∨¬p） ∧ （¬q∨q）

⇔ （p∨q） ∧¬ (p∧q)

2。5. 求下列公式的主析取范式, 并求成真赋值：

(1)（ ¬p→q） → (¬q∨p）

(2） ¬ （p→q） ∧q∧r

（3)（p∨ （q∧r)） → (p∨q∨r）

（1)（¬p→q） → (¬q∨p)

⇔ ¬（p∨q） ∨ （¬q∨p)

⇔ ¬p∧¬q ∨ ¬q ∨ p⇔ ¬p∧¬q ∨ ¬q ∨ p(吸收律）⇔ (p¬∨p）¬∧q ∨ p∧(q¬∨q）

⇔ p¬∧q ¬∨p¬∧q ∨ p∧q ∨ p¬∧q

⇔ m10 ∨ m00 ∨ m11 ∨ m10

⇔ m0 ∨ m2 ∨ m3

⇔ ∑(0， 2, 3).

成真赋值为 00, 10, 11.

（2）主析取范式为0， 无成真赋值, 为矛盾式.

（3)m0∨m1∨m2∨m3∨m4∨m5∨m6∨m7 , 为重言式。

2.6。 求下列公式的主合取范式， 并求成假赋值:

(1） ¬ （q→¬p） ∧¬p

(2）(p∧q） ∨ （¬p∨r)

（3）(p→ （p∨q）) ∨r

(1） ¬ (q¬→p） ∧ ¬p

⇔ ¬（¬q¬∨p） ∧ ¬p

⇔ q∧p ∧ ¬p

⇔ q∧0

⇔ 0

⇔ M0∧M1∧M2∧M3

这是矛盾式。 成假赋值为 00， 01， 10, 11。

(2)M4 ， 成假赋值为100。

(3）主合取范式为1, 为重言式。

8

2.7。 求下列公式的主析取范式, 再用主析取范式求合取范式：

（1）（p∧q） ∨r

(2)(p→q) ∧ (q→r)

（1）m1∨m3∨m5∨m6∨m7⇔M0∧M2∧M4

（2）m0∨m1∨m3∨m7⇔M2∧M4∧M5∧M6

2。8。 略

2。9. 用真值表求下面公式的主析取范式。

（2) (p→q) → （p¬↔q)

(2）从真值表可见成真赋值为01, 10. 于是(p → q) → (p¬ ↔ q） ⇔ m1 ∨ m2 。

2。10。 略

2。11。 略

2.12. 略

2.13。 略

2.14。 略

2.15。 用主析取范式判断下列公式是否等值:

（1） (p→q） →r与q→ (p→r)

（2）(p→q） →r

⇔ ¬（¬p∨q） ∨ r

⇔ ¬(¬p∨q) ∨ r

⇔ p¬∧q ∨ r

⇔ p¬∧q∧(r¬∨r） ∨ (p¬∨p） ∧ (q¬∨q）∧r

⇔ p¬∧q∧r ∨ p¬∧q∧¬r ∨

p∧q∧r ∨ p∧¬q∧r ∨ ¬p∧q∧r ∨ ¬p∧¬q∧r

= m101 ∨ m100 ∨ m111 ∨ m101 ∨ m011 ∨ m001

⇔ m1 ∨ m3 ∨ m4 ∨ m5 ∨ m7

= ∑(1, 3, 4, 5， 7）.

而 q→（p→r）

⇔ ¬q ∨ （¬p∨r）

⇔ ¬q ∨ ¬p ∨r

⇔ (¬p∨p)¬∧q∧(¬r∨r) ∨ ¬p∧（¬q∨q）∧（¬r∨r）

∨ （¬p∨p)∧（¬q∨q）∧r

⇔ (¬p¬∧q∧¬r)∨（¬p¬∧q∧r）∨（p¬∧q∧¬r）∨（p¬∧q∧r)

∨(¬p∧¬q∧¬r）∨（¬p∧¬q∧r）∨(¬p∧q∧¬r）∨（¬p∧q∧r） p q
( p → q ) → ( p ¬ ↔ q )
0 0
0 1
1 0
1 1
1 0 0 1
1 1 1 0
0 1 1 1
1 0 0 0

9

∨（¬p∧¬q∧r）∨（¬p∧q∧r）∨(p∧¬q∧r）∨(p∧q∧r）

= m0 ∨ m1 ∨ m4 ∨ m5

∨ m0 ∨ m1 ∨ m2 ∨ m3

∨ m1 ∨ m3 ∨ m5 ∨ m7

⇔ m0 ∨ m1 ∨ m2 ∨ m3 ∨ m4 ∨ m5 ∨ m7

⇔ ∑（0, 1， 2, 3, 4, 5, 7).

两个公式的主吸取范式不同， 所以（p→q） →r

2.16. 用主析取范式判断下列公式是否等值:
(1)(p→q) →r与q→ (p→r)
(2) ¬ （p∧q）与¬ （p∨q）

(1）
(p→q） →r） ⇔m1∨m3∨m4∨m5∨m7
q→ (p→r) ⇔m0∨m1∨m2∨m3∨m4∨m5∨m7
所以(p→q) →r) q→ (p→r)
（2）
¬ (p∧q） ⇔m0∨m1∨m2
¬ （p∨q） ⇔m0
所以¬ （p∧q) ¬ （p∨q）

2。17。 用主合取范式判断下列公式是否等值:
（1）p→ （q→r)与¬ (p∧q) ∨r
（2）p→ (q→r)与(p→q) →r

（1)
p→ (q→r） ⇔M6
¬ （p∧q） ∨r⇔M6
所以p→ (q→r） ⇔ ¬ (p∧q） ∨r
(2）
p→ （q→r) ⇔M6
(p→q) →r⇔M0∧M1∧M2∧M6
所以p→ （q→r） （p→q） →r

2.18. 略
2.19。 略
q→ (p→r）。

2.20. 将下列公式化成与之等值且仅含 ｛¬, →} 中联结词的公式.

（3） (p∧q）↔r。

注意到A↔B ⇔ (A→B)∧（B→A)和 A∧B ⇔ ¬（¬A¬∨B) ⇔ ¬(A¬→B)以及 A∨B ⇔ ¬A→B。

（p∧q)↔r

10

⇔ (p∧q → r） ∧ （r → p∧q)

⇔ （¬(p¬→q) → r） ∧ (r → ¬(p¬→q)）

⇔ ¬（(¬（p¬→q) → r） → ¬(r → ¬（p¬→q)））

注联结词越少， 公式越长。

2.21. 证明：

（1) （p↑q) ⇔ （q↑p）, （p↓q) ⇔ （q↓p).

(p↑q） ⇔ ¬（p∧q） ⇔ ¬（q∧p) ⇔ （q↑p)。

(p↓q) ⇔ ¬（p∨q) ⇔ ¬(q∨p） ⇔ （q↓p).

2。22. 略

2.23. 略

2。24. 略

2.25。 设A， B， C为任意的命题公式。

（1)若A∨C⇔B∨C， 举例说明 A⇔B不一定成立。

(2)已知A∧C⇔B∧C， 举例说明A⇔B不一定成立.

（3）已知¬A⇔¬B, 问： A⇔B一定成立吗?

（1) 取 A = p， B = q， C = 1 (重言式）, 有

A∨C ⇔ B∨C， 但 A B.

(2） 取 A = p, B = q， C = 0 （矛盾式), 有

A∧C ⇔ B∧C, 但 A B。

好的例子是简单， 具体， 而又说明问题的。

（3)一定。

2.26. 略

2.27。 某电路中有一个灯泡和三个开关A，B,C. 已知在且仅在下述四种情况下灯亮：

(1）C的扳键向上, A,B的扳键向下。

（2）A的扳键向上， B，C的扳键向下.

（3)B,C的扳键向上， A的扳键向下.

（4）A，B的扳键向上， C的扳键向下.

设F为1表示灯亮， p，q,r分别表示A,B,C的扳键向上。

（a）求F的主析取范式.

（b）在联结词完备集{¬， ∧｝上构造F.

（c）在联结词完备集{¬, →，↔}上构造F.

（a）由条件（1）—(4）可知, F的主析取范式为

F⇔ (¬p∧¬q∧r） ∨ （p∧¬q∧¬r) ∨ （¬p∧q∧r) ∨ (p∧q∧¬r)

⇔m1∨m4∨m3∨m6

⇔m1∨m3∨m4∨m6

11

（b）先化简公式

F⇔ （¬p∧¬q∧r） ∨ (p∧¬q∧¬r） ∨ (¬p∧q∧r) ∨ （p∧q∧¬r）

⇔¬q∧ （（¬p∧r） ∨ (p∧¬r）) ∨q∧ （(¬p∧r) ∨ （p∧¬r））

⇔ (¬q∨q) ∧ （(¬p∧r) ∨ (p∧¬r))

⇔ (¬p∧r） ∨ (p∧¬r)

⇔¬ (¬ （¬p∧r) ∧¬ (p∧¬r）) (已为{¬, ∧｝中公式)

（c)

F⇔ (¬p∧r) ∨ (p∧¬r)

⇔¬¬ (¬p∧r) ∨ （p∧¬r)

⇔¬ （¬p∧r) → （p∧¬r）

⇔ (p∨¬r) →¬ （¬p∨r）

⇔ （r→p） →¬ (p→r） (已为｛¬， →，↔｝中公式）

2.28。 一个排队线路, 输入为A，B，C， 其输出分别为F A,F B,F C. 本线路中, 在同一时间内只能有一个信号通过，

若同时有两个和两个以上信号申请输出时, 则按A,B，C的顺序输出. 写出F A，F B,F C在联结词完备集{¬, ∨｝

中的表达式.

根据题目中的要求， 先写出F A，F B,F C的真值表(自己写）

由真值表可先求出他们的主析取范式, 然后化成{¬， ∧｝中的公式

F A⇔m4∨m5∨m6∨m7

⇔p
F B⇔m2∨m3
⇔¬p∧q
F C⇔m1
⇔¬p∧¬q∧r

2.29. 略
2.30. 略
(已为{¬， ∧}中公式)

(已为{¬, ∧}中公式）

(已为{¬, ∧｝中公式）

12

习题三

3.1. 略

3.2. 略

3.3. 略

3。4. 略

3.5。 略

3。6. 判断下面推理是否正确。 先将简单命题符号化, 再写出前提， 结论, 推理的形式结构（以蕴涵式的形式给

出)和判断过程（至少给出两种判断方法）：

(1)若今天是星期一， 则明天是星期三；今天是星期一. 所以明天是星期三。

(2)若今天是星期一， 则明天是星期二；明天是星期二. 所以今天是星期一.

(3)若今天是星期一， 则明天是星期三；明天不是星期三. 所以今天不是星期一.

(4）若今天是星期一, 则明天是星期二；今天不是星期一. 所以明天不是星期二。

（5）若今天是星期一, 则明天是星期二或星期三.

（6）今天是星期一当且仅当明天是星期三;今天不是星期一。 所以明天不是星期三。

设p： 今天是星期一, q： 明天是星期二, r: 明天是星期三。

(1）推理的形式结构为

(p→r) ∧p→r

此形式结构为重言式， 即

（p→r） ∧p⇒r

所以推理正确.

(2）推理的形式结构为

(p→q) ∧q→p

此形式结构不是重言式， 故推理不正确。

(3)推理形式结构为

（p→r) ∧¬r→¬p

此形式结构为重言式， 即

(p→r） ∧¬r⇒¬p

故推理正确。

（4)推理形式结构为

（p→q） ∧¬p→¬q

此形式结构不是重言式, 故推理不正确.

(5)推理形式结构为

p→ (q∨r)

它不是重言式, 故推理不正确.

（6）推理形式结构为

（p⇒r） ∧¬p→¬r

13

此形式结构为重言式, 即

（p⇒r） ∧¬p⇒¬r

故推理正确.

推理是否正确， 可用多种方法证明。 证明的方法有真值表法, 等式演算法. 证明推理正确还可用构造证明法.

下面用构造证明法证明(6)推理正确.

前提： p⇒r， ¬p

结论： ¬r

证明： ①p⇒r
②(p→r） ∧ (r→p）
③ r→p
④¬p
⑤¬r
所以， 推理正确。

3。7。 略
3.8。 略
前提引入
①置换
②化简律
前提引入
③④拒取式

3。9。 用三种方法(真值表法, 等值演算法, 主析取范式法)证明下面推理是正确的：

若 a 是奇数， 则 a 不能被2 整除。 若 a 是偶数, 则 a 能被 2 整除。 因此, 如果 a 是偶数， 则 a 不是奇数.

令 p： a 是奇数; q： a 能被2 整除; r: a 是偶数.

前提: p → ¬q, r → q。

结论: r → ¬p。

形式结构： (p → ¬q） ∧ （r → q) → (r → ¬p）.

……

3。10。略

3.11。略

3。12.略

3.13。略

3。14.在自然推理系统P中构造下面推理的证明:

(1）前提: p→ （q→r）, p, q

结论： r∨s

（2）前提: p→q， ¬ （q∧r）， r

结论: ¬p

(3）前提: p→q

结论: p→ (p∧q）

(4)前提： q→p, q⇒s， s⇒t, t∧r

结论: p∧q

(5）前提: p→r， q→s， p∧q

14

结论: r∧s

（6)前提： ¬p∨r， ¬q∨s， p∧q

结论: t→ (r∨s)

(1）证明：

p→(q→r）

② p
q→r ③
④ q
⑤ r
r∨s ⑥

(2）证明:

¬ (q∧r） ①
¬q∨¬r ②
③ r
¬q ④
p→q ⑤
¬p ⑥

(3）证明:

p→q ①
¬p∨q ②
前提引入
①②假言推理
前提引入
③④假言推理
⑤附加律

前提引入
①置换
前提引入
②③析取三段论
前提引入
④⑤拒取式

前提引入
①置换

（¬p∨q） ∧ （¬p∨p）

¬p∨ （p∧q）

p→ （p∧q）

也可以用附加前提证明法， 更简单些.

(4）证明：

s⇒t

(s→t) ∧ (t→s)

t→s

t∧r

⑤ t
⑥ s
q⇒s ⑦
(s→q） ∧ （q→s） ⑧
s→q ⑨
⑩ q
④化简
③⑤假言推理
前提引入
⑦置换
⑧化简
⑥⑥假言推理

15

q →p

○
12 p
p∧q ○
13

(5）证明：

p→r ① 前提引入
q→s ② 前提引入
p∧q ③ 前提引入
④ ③化简 p
⑤ ③化简 q
⑩○假言推理
11
⑩○合取
12

⑥ r
⑦ s
r∧s ⑧

(6)证明：

① t
¬p∨r ②
p∧q ③
④ p
⑤ r
r∨s ⑥
①④假言推理
②⑤假言推理
⑥⑦合取

附加前提引入
前提引入
前提引入
③化简
②④析取三段论
⑤附加

说明： 证明中， 附加提前t， 前提¬q∨s没用上。 这仍是正确的推理。

3。15。在自然推理系统P中用附加前提法证明下面各推理:

（1)前提： p→ （q→r)， s→p, q

结论: s→r

(2)前提: (p∨q） → (r∧s）， (s∨t） →u

结论： p→u

(1)证明：

① s
s→p ②
③ p
p→ (q→r) ④
q→r ⑤
⑥ q
⑦ r
附加前提引入
前提引入
①②假言推理
前提引入
③④假言推理
前提引入
⑤⑥假言推理

16

（2）证明：

① P

p∨q ②

（p∨q) → （r∧s） ③

r∧s ④

⑤ S

s∨t ⑥

(s∨t) →u ⑦

⑧ u
附加前提引入

①附加

前提引入

②③假言推理

④化简

⑤附加

前提引入

⑥⑦假言推理

3。16.在自然推理系统P中用归谬法证明下面推理:

(1)前提： p→¬q, ¬r∨q， r∧¬s

结论: ¬p

（2)前提： p∨q， p→r， q→s

结论: r∨s

（1)证明:

① P
p→¬q ②
¬q ③
¬r∨q ④
¬r ⑤
r∧¬s ⑥
⑦ r
¬r∧r ⑧
结论否定引入
前提引入
①②假言推理
前提引入
③④析取三段论
前提引入
⑥化简
⑤⑦合取

⑧为矛盾式， 由归谬法可知， 推理正确。

(2）证明：

¬ （r∨s）

p∨q

p→r

q→s

r∨s

¬ (r∨s） ∧ (r∨s）

17

⑥为矛盾式， 所以推理正确.

3.17.P53 17. 在自然推理系统 P 中构造下面推理的证明：

只要 A 曾到过受害者房间并且11点以前没用离开, A 就犯了谋杀罪. A 曾到过受害者房间. 如果 A 在

11点以前离开， 看门人会看到他. 看门人没有看到他。 所以 A 犯了谋杀罪.

令 p： A 曾到过受害者房间; q: A 在11点以前离开了; r: A 就犯了谋杀罪; s：看门人看到 A.

前提： p¬∧q → r， p, q → s， ¬s。

结论: r。

前提: p¬∧q → r, p, q → s， ¬s；
证明:
① ¬s 前提引入
② q → s 前提引入
③ ¬q ①②拒取
前提引入 ④ p
⑤ p¬∧q ③④合取
⑥ p¬∧q → r 前提引入
⑦ r ⑤⑥假言推理
结论： r.

3.18.在自然推理系统P中构造下面推理的证明.

(1)如果今天是星期六, 我们就要到颐和园或圆明园去玩。 如果颐和园游人太多， 我们就不去颐和园玩.

今天是星期六。 颐和园游人太多。 所以我们去圆明园玩.

(2)如果小王是理科学生， 他的数学成绩一定很好. 如果小王不是文科生, 他必是理科生。 小王的数学成

绩不好. 所以小王是文科学生.

(3)明天是晴天, 或是雨天;若明天是晴天, 我就去看电影；若我看电影， 我就不看书. 所以， 如果我看书,

则明天是雨天。

（1)令 p： 今天是星期六； q： 我们要到颐和园玩； r： 我们要到圆明园玩； s:颐和园游人太多。

前提: p→ （q∨r), s → ¬q, p， s.

结论: r。

① p

p→q∨r ②

q∨r ③

④ s

s → ¬q ⑤

¬q ⑥

⑦ r
前提引入
p→q∨r
s → ¬q
p
s
前提引入

q∨r ¬q ①②假言推理

前提引入
r
前提引入

(1)的证明树 ④⑤假言推理

③⑥析取三段论

18

（2) 令p： 小王是理科生， q: 小王是文科生, r： 小王的数学成绩很好.

前提： p→r, ¬q→p， ¬r

结论： q

证明：

p→r

¬q
¬r ② 前提引入
¬p ③ ①②拒取式
¬p
¬q→p ④ 前提引入
(2）的证明树
⑤ ③④拒取式 q

(3)令p: 明天是晴天, q: 明天是雨天, r: 我看电影, s： 我看书。
前提： p∨q， p→r, r→¬s
结论: s→q
证明：

① 附加前提引入 s
r→¬s ② 前提引入
¬r ③ ①②拒取式
p→r ④ 前提引入
¬p ⑤ ③④拒取式
p∨q ⑥ 前提引入
⑦ ⑤⑥析取三段论 q
p→q

¬r→p

r

19

习题四

4。1. 将下面命题用0元谓词符号化:

（1)小王学过英语和法语。

（2）除非李建是东北人, 否则他一定怕冷.

(1) 令 F(x）： x 学过英语; F(x）： x 学过法语； a： 小王。 符号化为

F(a)∧F（b).

或进一步细分, 令 L(x, y）： x 学过 y; a: 小王; b1 ： 英语； b2 ： 法语. 则符号化为

L（a, b1 )∧L（a， b2 ）。

(2) 令 F（x）: x 是东北人; G(x）： x 怕冷; a: 李建. 符号化为

¬F（a)→G(a） 或 ¬G（a)→F(a)。

或进一步细分, 令 H（x， y）: x 是 y 地方人; G(x)： x 怕冷； a： 小王； b: 东北。 则符号化为

¬H(a， b）→G(a） 或 ¬G（a）→ H（a, b）.

4。2. 在一阶逻辑中将下面命题符号化， 并分别讨论个体域限制为(a)，(b)时命题的真值:

(1）凡有理数都能被2整除.

(2)有的有理数能被2整除.

其中(a)个体域为有理数集合, （b）个体域为实数集合。

（1)(a)中， ∀xF（x)， 其中, F(x)： x能被2整除, 真值为0.

（b)中， ∀x(G（x） ∧F(x））， 其中， G(x): x为有理数, F(x）同(a)中， 真值为0.

(2)（a）中， ∃xF（x）， 其中, F(x）： x能被2整除， 真值为1.

（b）中， ∃x(G(x) ∧F（x）), 其中， F(x)同(a）中, G（x）： x为有理数, 真值为1.

4.3. 在一阶逻辑中将下面命题符号化, 并分别讨论个体域限制为(a),(b）时命题的真值:

（1）对于任意的x， 均有x2−2=(x+ 2 )（x−2 ）。

(2)存在x， 使得x+5=9.

其中(a）个体域为自然数集合， (b)个体域为实数集合.

(1)（a)中， ∀x（x2−2=(x+ 2 )(x−2 ）), 真值为1.

（b)中, ∀x（F(x) → （x2−2=(x+ 2 )(x−2 )))), 其中, F(x): x为实数， 真值为1。

(2)（a)中, ∃x（x+5=9）, 真值为1。

（b)中, ∃x(F（x) ∧ （x+5=9）), 其中, F（x): x为实数, 真值为1.

4.4. 在一阶逻辑中将下列命题符号化:

（1)没有不能表示成分数的有理数.

(2)在北京卖菜的人不全是外地人.

20

（3)乌鸦都是黑色的。

(4）有的人天天锻炼身体。

没指定个体域， 因而使用全总个体域.

（1） ¬∃x（F（x) ∧¬G（x）)或∀x（F(x） →G(x)）， 其中, F（x)： x为有理数， G(x）： x能表示成分数.

(2) ¬∀x(F（x) →G(x)）或∃x(F（x） ∧¬G（x)), 其中, F（x)： x在北京卖菜， G（x）: x是外地人.

（3） ∀x（F(x) →G(x))， 其中， F(x）： x是乌鸦， G(x): x是黑色的。

（4) ∃x(F(x) ∧G(x)), 其中, F(x)： x是人, G（x): x天天锻炼身体.

4.5. 在一阶逻辑中将下列命题符号化：

(1）火车都比轮船快。

（2）有的火车比有的汽车快.

（3）不存在比所有火车都快的汽车。

(4)“凡是汽车就比火车慢”是不对的。

因为没指明个体域， 因而使用全总个体域

（1） ∀x∀y（F（x） ∧G(y） →H（x,y)）, 其中, F（x）： x是火车， G（y): y是轮船， H(x,y)：x比y快。

(2) ∃x∃y(F（x) ∧G(y） ∧H（x,y）), 其中， F(x)： x是火车， G(y）： y是汽车, H(x，y):x比y快。

(3） ¬∃x(F(x) ∧∀y(G（y） →H(x，y))）

或∀x（F（x) →∃y(G(y） ∧¬H(x,y）))， 其中， F(x）: x是汽车， G(y）： y是火车， H(x，y)：x比y快.

（4） ¬∀x∀y（F（x) ∧G（y） →H(x，y))

或∃x∃y（F（x） ∧G（y） ∧¬H(x，y） )， 其中， F(x): x是汽车， G（y)： y是火车, H（x,y）：x比y慢。

4.6。 略

4。7。 将下列各公式翻译成自