2024年4月5日发(作者：琴书桃)

1.14． 将下列命题符号化.

(1) 刘晓月跑得快, 跳得高.

(2)老王是山东人或河北人.

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

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

(5)李辛与李末是兄弟.

(6)王强与刘威都学过法语.

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

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

(9)只有天下大雨, 他才乘班车上班.

(10)除非天下大雨, 他才乘班车上班.

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

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

,

”是不对的.

(13)“2

或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是素数.

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)

(1), (4), (6)为重言式.

(3)为矛盾式.

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

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) ∧ (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.7. 求下列公式的主析取范式, 再用主析取范式求合取范式:

(1)(p∧q) ∨r

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

(1)m

1

∨m

3

∨m

5

∨m

6

∨m

7

⇔M

0

∧M

2

∧M

4

(2)m

0

∨m

1

∨m

3

∨m

7

⇔M

2

∧M

4

∧M

5

∧M

6

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)

⇔m

1

∨m

4

∨m

3

∨m

6

⇔m

1

∨m

3

∨m

4

∨m

6

(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) (已为{¬, →,↔}中公式)

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

结论: r∧s

(6)前提: ¬p∨r, ¬q∨s, p∧q

结论: t→ (r∨s)

4

离散数学习题解

(1)证明:

①

②

③

④

⑤

⑥

①

②

③

④

⑤

⑥

p→(q→r)

p

q→r

q

r

r∨s

¬ (q∧r)

¬q∨¬r

r

¬q

p→q

¬p

前提引入

前提引入

①②假言推理

前提引入

③④假言推理

⑤附加律

前提引入

①置换

前提引入

②③析取三段论

前提引入

④⑤拒取式

前提引入

①置换

②置换

③置换

④置换

5

(2)证明:

(3)证明:

①

p→q

②

③

④

⑤

¬p∨q

(¬p∨q) ∧ (¬p∨p)

¬p∨ (p∧q)

p→ (p∧q)

也可以用附加前提证明法

, 更简单些.

(4)证明:

① 前提引入

s⇒t

②

③

④

⑤

⑥

⑦

⑧

⑨

⑩

11

○

12

○

13

○

(s→t) ∧ (t→s)

t→s

t∧r

t

s

q⇒s

(s→q) ∧ (q→s)

s→q

q

q →p

p

①置换

②化简

前提引入

④化简

③⑤假言推理

前提引入

⑦置换

⑧化简

⑥⑥假言推理

前提引入

11

假言推理

⑩○

12

合取

⑩○

p∧q

(5)证明:

①

p→r

②

③

q→s

p∧q

p

q

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

附加前提引入

前提引入

①②假言推理

前提引入

③④假言推理

前提引入

⑤⑥假言推理

6

(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)

结论否定引入

前提引入

前提引入

前提引入

②③④构造性二难

①⑤合取

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

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.

证明:

① ¬s 前提引入

前提引入

7

② q → s

③ ¬q ①②拒取

④ p

前提引入

③④合取

前提引入

⑤⑥假言推理

⑤ p¬∧q

⑥ p¬∧q → r

⑦ r

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

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

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

(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.9. 给定解释I如下:

(a)个体域D

I

为实数集合.

(b)D

I

中特定元素⎯a =0.

(c)特定函数⎯f (x,y)=x−y, x,y∈D

I

.

(d)特定谓词⎯F(x,y): x=y,⎯G(x,y): x

I

.

(1) ∀x∀y(x

(2) ∀x∀y((x−y=0) →x

(3) ∀x∀y((x

(4) ∀x∀y((x−y<0) → (x=y)), 真值为0.

说明下列公式在I下的含义, 并指出各公式的真值:

(1) ∀x∀y(G(x,y) →¬F(x,y))

(2) ∀x∀y(F(f(x,y),a) →G(x,y))

(3) ∀x∀y(G(x,y) →¬F(f(x,y),a))

(4) ∀x∀y(G(f(x,y),a) →F(x,y))

离散数学习题解

4.11.判断下列各式的类型:

(1) F(x, y) → (G(x, y) → F(x, y)).

(3) ∀x∃yF(x, y) → ∃x∀yF(x, y).

(5) ∀x∀y(F(x, y) → F(y, x)).

(1) 是命题重言式 p → (q → p) 的代换实例, 所以是永真式.

(3) 在某些解释下为假(举例), 在某些解释下为真(举例), 所以是非永真式的可满足式.

(5) 同(3).

5.8. 在一阶逻辑中将下列命题符号化, 要求用两种不同的等值形式.

(1) 没有小于负数的正数.

(2) 相等的两个角未必都是对顶角.

(1) 令 F(x): x 小于负数, G(x): x 是正数. 符合化为:

∃¬x((F(x) ∧ G(x)) ⇔ ∀x(G(x) → ¬G(x)).

(2) 令 F(x): x 是角, H(x, y): x 和 y 是相等的, L(x, y): x 与 y 是对顶角. 符合化为:

¬∀x∀y(F(x) ∧ F(y) ∧ H(x, y) → L(x, y))

⇔ ∃x∃y(F(x) ∧ F(y) ∧ H(x, y) ∧ ¬L(x, y))

⇔ ∃x(F(x) ∧ (∃y(F(y) ∧ H(x, y) ∧ ¬L(x, y))).

8

5.12.求下列各式的前束范式.

(1) ∀xF(x) → ∀yG(x, y);

(3) ∀xF(x, y) ↔ ∃xG(x, y);

(5) ∃x

1

F(x

1

, x

2

) → (F(x

1

) → ∃¬x

2

G(x

1

, x

2

)).

前束范式不是唯一的.

(1) ∀xF(x) → ∀yG(x, y)

⇔ ∃x(F(x) → ∀yG(x, y))

⇔ ∃x∀y(F(x) → G(x, y)).

(3) ∀xF(x, y) ↔ ∃xG(x, y)

⇔ (∀xF(x, y) → ∃xG(x, y)) ∧ (∃xG(x, y) → ∀xF(x, y))

⇔ (∀x

1

F(x

1

, y) → ∃x

2

G(x

2

, y)) ∧ (∃x

3

G(x

3

, y) → ∀x

4

F(x

4

, y))

⇔ ∃x

1

∃x

2

(F(x

1

, y) → G(x

2

, y)) ∧ ∀x

3

∀x

4

(G(x

3

, y) → F(x

4

, y))

⇔ ∃x

1

∃x

2

∀x

3

∀x

4

((F(x

1

, y) → G(x

2

, y)) ∧ (G(x

3

, y) → F(x

4

, y))).

5.15.在自然推理系统F中构造下面推理的证明:

(1) 前提: ∃xF(x) → ∀y((F(y) ∨ G(y)) → R(y)), ∃xF(x)

结论: ∃xR(x).

(2) 前提: ∀x(F(x) → (G(a) ∧R(x))), ∃xF(x)

结论: ∃x(F(x) ∧R(x))

(3) 前提: ∀x(F(x) ∨G(x)), ¬∃xG(x)

结论: ∃xF(x)

(4) 前提: ∀x(F(x) ∨G(x)), ∀x(¬G(x) ∨¬R(x)), ∀xR(x)

结论: ∀xF(x)

5.24.在自然推理系统 F 中, 构造下面推理的证明:

每个喜欢步行的人都不喜欢骑自行车

. 每个人或者喜欢骑自行车或者喜欢乘汽车

. 有的人不喜欢乘汽车,

所以有的人不喜欢步行. (个体域为人类集合)

离散数学习题解

令 F(x): x 喜欢步行, G( x): x喜欢骑自行车, H(x): x 喜欢乘汽车.

前提: ∀x(F(x) → ¬G(x)), ∀x(G(x) ∨ H(y)), ∃x¬H(x).

结论: ∃x¬F(x).

① ∀x(G(x) ∨ H(y)) 前提引入

9

② G(c) ∨ H(c) ①UI

③ ∃x¬H(x)

前提引入

④ ¬H(c)

⑤ G(c)

③UI

②④析取三段

前提引入 ⑥ ∀x(F(x) → ¬G(x))

⑦ F(c) → ¬G(c) ⑥UI

⑧ ¬F(c) ⑤⑦拒取

⑨ ∃x¬F(x) ⑧EG

8.5. 设X = {a, b, c, d}, Y = {1, 2, 3}, f = {〈a, 1〉, 〈b, 2〉, 〈c, 3〉}, 判断以下命题的真假

(1)f是从X到Y的二元关系, 但不是从X到Y的函数;

(2) f是从X到Y的函数, 但不是从满射, 也不是单射

(3) f是从X到Y的满射, 但不是从单射;

(4) f是从X到Y的双射.

8.12.设f: S→T, 证明

(1)f (A∩B) ⊆ f (A) ∩ f (B), 其中A, B ⊆ S.

(2)举出反例说明等式f (A∩B) = f (A) ∩ f (B)不是永远为真的.

(3)说明对于什么函数, 上述等式为真.

8.16.16.设A={a, b, c}. R为A上的等价关系, 且

 R={〈a, b〉, 〈b, a〉}∪I

A

求自然映射g: A→A/R.

8.21.21.设f :

2024年4月5日发(作者：琴书桃)

1.14． 将下列命题符号化.

(1) 刘晓月跑得快, 跳得高.

(2)老王是山东人或河北人.

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

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

(5)李辛与李末是兄弟.

(6)王强与刘威都学过法语.

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

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

(9)只有天下大雨, 他才乘班车上班.

(10)除非天下大雨, 他才乘班车上班.

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

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

,

”是不对的.

(13)“2

或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是素数.

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)

(1), (4), (6)为重言式.

(3)为矛盾式.

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

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) ∧ (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.7. 求下列公式的主析取范式, 再用主析取范式求合取范式:

(1)(p∧q) ∨r

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

(1)m

1

∨m

3

∨m

5

∨m

6

∨m

7

⇔M

0

∧M

2

∧M

4

(2)m

0

∨m

1

∨m

3

∨m

7

⇔M

2

∧M

4

∧M

5

∧M

6

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)

⇔m

1

∨m

4

∨m

3

∨m

6

⇔m

1

∨m

3

∨m

4

∨m

6

(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) (已为{¬, →,↔}中公式)

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

结论: r∧s

(6)前提: ¬p∨r, ¬q∨s, p∧q

结论: t→ (r∨s)

4

离散数学习题解

(1)证明:

①

②

③

④

⑤

⑥

①

②

③

④

⑤

⑥

p→(q→r)

p

q→r

q

r

r∨s

¬ (q∧r)

¬q∨¬r

r

¬q

p→q

¬p

前提引入

前提引入

①②假言推理

前提引入

③④假言推理

⑤附加律

前提引入

①置换

前提引入

②③析取三段论

前提引入

④⑤拒取式

前提引入

①置换

②置换

③置换

④置换

5

(2)证明:

(3)证明:

①

p→q

②

③

④

⑤

¬p∨q

(¬p∨q) ∧ (¬p∨p)

¬p∨ (p∧q)

p→ (p∧q)

也可以用附加前提证明法

, 更简单些.

(4)证明:

① 前提引入

s⇒t

②

③

④

⑤

⑥

⑦

⑧

⑨

⑩

11

○

12

○

13

○

(s→t) ∧ (t→s)

t→s

t∧r

t

s

q⇒s

(s→q) ∧ (q→s)

s→q

q

q →p

p

①置换

②化简

前提引入

④化简

③⑤假言推理

前提引入

⑦置换

⑧化简

⑥⑥假言推理

前提引入

11

假言推理

⑩○

12

合取

⑩○

p∧q

(5)证明:

①

p→r

②

③

q→s

p∧q

p

q

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

附加前提引入

前提引入

①②假言推理

前提引入

③④假言推理

前提引入

⑤⑥假言推理

6

(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)

结论否定引入

前提引入

前提引入

前提引入

②③④构造性二难

①⑤合取

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

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.

证明:

① ¬s 前提引入

前提引入

7

② q → s

③ ¬q ①②拒取

④ p

前提引入

③④合取

前提引入

⑤⑥假言推理

⑤ p¬∧q

⑥ p¬∧q → r

⑦ r

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

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

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

(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.9. 给定解释I如下:

(a)个体域D

I

为实数集合.

(b)D

I

中特定元素⎯a =0.

(c)特定函数⎯f (x,y)=x−y, x,y∈D

I

.

(d)特定谓词⎯F(x,y): x=y,⎯G(x,y): x

I

.

(1) ∀x∀y(x

(2) ∀x∀y((x−y=0) →x

(3) ∀x∀y((x

(4) ∀x∀y((x−y<0) → (x=y)), 真值为0.

说明下列公式在I下的含义, 并指出各公式的真值:

(1) ∀x∀y(G(x,y) →¬F(x,y))

(2) ∀x∀y(F(f(x,y),a) →G(x,y))

(3) ∀x∀y(G(x,y) →¬F(f(x,y),a))

(4) ∀x∀y(G(f(x,y),a) →F(x,y))

离散数学习题解

4.11.判断下列各式的类型:

(1) F(x, y) → (G(x, y) → F(x, y)).

(3) ∀x∃yF(x, y) → ∃x∀yF(x, y).

(5) ∀x∀y(F(x, y) → F(y, x)).

(1) 是命题重言式 p → (q → p) 的代换实例, 所以是永真式.

(3) 在某些解释下为假(举例), 在某些解释下为真(举例), 所以是非永真式的可满足式.

(5) 同(3).

5.8. 在一阶逻辑中将下列命题符号化, 要求用两种不同的等值形式.

(1) 没有小于负数的正数.

(2) 相等的两个角未必都是对顶角.

(1) 令 F(x): x 小于负数, G(x): x 是正数. 符合化为:

∃¬x((F(x) ∧ G(x)) ⇔ ∀x(G(x) → ¬G(x)).

(2) 令 F(x): x 是角, H(x, y): x 和 y 是相等的, L(x, y): x 与 y 是对顶角. 符合化为:

¬∀x∀y(F(x) ∧ F(y) ∧ H(x, y) → L(x, y))

⇔ ∃x∃y(F(x) ∧ F(y) ∧ H(x, y) ∧ ¬L(x, y))

⇔ ∃x(F(x) ∧ (∃y(F(y) ∧ H(x, y) ∧ ¬L(x, y))).

8

5.12.求下列各式的前束范式.

(1) ∀xF(x) → ∀yG(x, y);

(3) ∀xF(x, y) ↔ ∃xG(x, y);

(5) ∃x

1

F(x

1

, x

2

) → (F(x

1

) → ∃¬x

2

G(x

1

, x

2

)).

前束范式不是唯一的.

(1) ∀xF(x) → ∀yG(x, y)

⇔ ∃x(F(x) → ∀yG(x, y))

⇔ ∃x∀y(F(x) → G(x, y)).

(3) ∀xF(x, y) ↔ ∃xG(x, y)

⇔ (∀xF(x, y) → ∃xG(x, y)) ∧ (∃xG(x, y) → ∀xF(x, y))

⇔ (∀x

1

F(x

1

, y) → ∃x

2

G(x

2

, y)) ∧ (∃x

3

G(x

3

, y) → ∀x

4

F(x

4

, y))

⇔ ∃x

1

∃x

2

(F(x

1

, y) → G(x

2

, y)) ∧ ∀x

3

∀x

4

(G(x

3

, y) → F(x

4

, y))

⇔ ∃x

1

∃x

2

∀x

3

∀x

4

((F(x

1

, y) → G(x

2

, y)) ∧ (G(x

3

, y) → F(x

4

, y))).

5.15.在自然推理系统F中构造下面推理的证明:

(1) 前提: ∃xF(x) → ∀y((F(y) ∨ G(y)) → R(y)), ∃xF(x)

结论: ∃xR(x).

(2) 前提: ∀x(F(x) → (G(a) ∧R(x))), ∃xF(x)

结论: ∃x(F(x) ∧R(x))

(3) 前提: ∀x(F(x) ∨G(x)), ¬∃xG(x)

结论: ∃xF(x)

(4) 前提: ∀x(F(x) ∨G(x)), ∀x(¬G(x) ∨¬R(x)), ∀xR(x)

结论: ∀xF(x)

5.24.在自然推理系统 F 中, 构造下面推理的证明:

每个喜欢步行的人都不喜欢骑自行车

. 每个人或者喜欢骑自行车或者喜欢乘汽车

. 有的人不喜欢乘汽车,

所以有的人不喜欢步行. (个体域为人类集合)

离散数学习题解

令 F(x): x 喜欢步行, G( x): x喜欢骑自行车, H(x): x 喜欢乘汽车.

前提: ∀x(F(x) → ¬G(x)), ∀x(G(x) ∨ H(y)), ∃x¬H(x).

结论: ∃x¬F(x).

① ∀x(G(x) ∨ H(y)) 前提引入

9

② G(c) ∨ H(c) ①UI

③ ∃x¬H(x)

前提引入

④ ¬H(c)

⑤ G(c)

③UI

②④析取三段

前提引入 ⑥ ∀x(F(x) → ¬G(x))

⑦ F(c) → ¬G(c) ⑥UI

⑧ ¬F(c) ⑤⑦拒取

⑨ ∃x¬F(x) ⑧EG

8.5. 设X = {a, b, c, d}, Y = {1, 2, 3}, f = {〈a, 1〉, 〈b, 2〉, 〈c, 3〉}, 判断以下命题的真假

(1)f是从X到Y的二元关系, 但不是从X到Y的函数;

(2) f是从X到Y的函数, 但不是从满射, 也不是单射

(3) f是从X到Y的满射, 但不是从单射;

(4) f是从X到Y的双射.

8.12.设f: S→T, 证明

(1)f (A∩B) ⊆ f (A) ∩ f (B), 其中A, B ⊆ S.

(2)举出反例说明等式f (A∩B) = f (A) ∩ f (B)不是永远为真的.

(3)说明对于什么函数, 上述等式为真.

8.16.16.设A={a, b, c}. R为A上的等价关系, 且

 R={〈a, b〉, 〈b, a〉}∪I

A

求自然映射g: A→A/R.

8.21.21.设f :