离散数学第三章习题详细答案

文档可能无法思考全面，请浏览后下载!

1 / 7 3.9解：

符号化：

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

前提：(p→¬r),(q→r)

结论：(q→¬p)

证明：

方法1（真值法）

p q r p→¬r q→r (p→¬r)∧(q→r) q→¬p

0 0 0 1 1 1 1

0 0 1 1 1 1 1

0 1 1 1 0 0 1

1 0 0 1 1 1 1

1 0 1 0 1 0 1

0 1 1 1 1 1 1

1 1 0 1 0 0 0

1 1 1 0 1 0 0

由上表可知，没有出现合取式(p→¬r)∧(q→r)为真，结论(q→¬p)为假的情况，因此推论正确。

方法2（等值演算法）

(p→¬r)∧(q→r) →(q→¬p)

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

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

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

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

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

⇔ 1

即证得该式为重言式，则原结论正确。

方法3（主析取范式法）

(p→¬r)∧(q→r) →(q→¬p)

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

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

⇔ m0+ m1+ m2+ m3+ m4+ m5+ m6+ m7

可知该式为重言式，则结论推理正确。

3.10. 解：

符号化：p：a是负数. q：b是负数. r：a、b之积为负

前提： r→(p∧¬q) ∨(¬p∧q)

结论：¬r→(¬p∧¬q)

方法1（真值法）

证明：

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

0 0 0 0 1 1 1 文档可能无法思考全面，请浏览后下载!

2 / 7 0 0 1 0 1 0 1

0 1 0 1 0 1 0

1 0 0 1 0 1 0

1 1 0 0 0 1 0

1 0 1 1 0 1 1

0 1 1 1 0 1 1

1 1 1 0 0 0 1

由上表可知，存在r→(p∧¬q) ∨(¬p∧q)为真，结论¬r→(¬p∧¬q)为假的情况，因此推理不正确。

方法2（主析取范式法）

证明：(r→(p∧¬q) ∨(¬p∧q)) →(¬r→(¬p∧¬q))

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

⇔ r∨(¬p∧¬q)

⇔ m0+m2+m4+m6+m7

只含5个极小项，课件原始不是重言式，因此推理不正确

3.11.填充下面推理证明中没有写出的推理规则。

解：

③：①②析取三段论

⑤：③④析取三段论

⑦：⑤⑥假言推理

3.12. 填充下面推理证明中没有写出的推理规则。

解：

②：①化简规则

③：①化简规则

⑤：②④假言推理

⑥：③⑤假言推理

⑧：③⑦假言推理

⑨：⑥⑧假言推理

3.13.证明：

∵前提¬(p→q)∧q ⇔ ¬(¬ p∨q)∧q ⇔p∧¬q∧q ⇔0为矛盾式

∴以(¬(p→q)∧q)∧(p∨q)∧(r→s) →B.(B为任何结论)的推理的前件在任何赋值

下均为假

∴无论结论如何，推理总正确

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

(1)前提: p → (q → r), p, q

结论: r ∨ s

(2)前提: p → q, ¬ (q ∧ r), r

结论: ¬ p

(3)前提: p → q

结论: p → (p ∧ q) 文档可能无法思考全面，请浏览后下载!

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

(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 ⑥⑨假言推理

11 q→p 前提引入

12 p ⑩11 假言推理

13 p ∧ q ⑩○12 合取文档可能无法思考全面，请浏览后下载!

4 / 7

(5)证明:

① p → r 前提引入

② q → s 前提引入

③ p ∧ q 前提引入

④ p ③化简

⑤ q ③化简

⑥ r ①④假言推理

⑦ s ②⑤假言推理

⑧ r ∧ s ⑥⑦合取

(6)证明:

① t 附加前提引入

② ¬ p ∨ r 前提引入

③ p ∧ q 前提引入

④ p ③化简

⑤ r ②④析取三段论

⑥ r ∨ 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 ⑤⑥假言推理

(2)证明:

① P 附加前提引入

② p∨q ①附加

③ (p∨q)→(r∧s)前提引入

④ r ∧ s ②③假言推理

⑤ s ④化简

⑥ s ∨ t ⑤附加

⑦ (s ∨ t) → u 前提引入

⑧ u ⑥⑦假言推理 文档可能无法思考全面，请浏览后下载!

5 / 7 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. 在自然推理系统 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 前提引入

② q→s 前提引入

③ ¬ q ②拒取

④ p 前提引入

⑤ p∧¬q ③④合取

⑥ (p∧¬q)→r 前提引入

⑦ r ⑤⑥假言推理

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

(1)如果今天是星期六, 我们就要到颐和园或圆明园去玩. 如果颐和园游人太多, 我们就不文档可能无法思考全面，请浏览后下载!

6 / 7 去颐和园玩