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

3.9解： 符号化：

p ：a 是奇数. q ：a 是偶数. r：a 能被2整除 前提：(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

⇔ m 0+ 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（真值法） 证明：

不正确。

方法2（主析取范式法）

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

⇔ m 0+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)

下

(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 合取

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

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)如果今天是星期六, 我们就要到颐和园或圆明园去玩. 如果颐和园游人太多, 我们就不去颐和园玩. 今天是星期六. 颐和园游人太多. 所以我们去圆明园玩.

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

(1)令 p: 今天是星期六; q: 我们要到颐和园玩; r: 我们要到圆明园玩; s:颐和园游人太多. 前提: p→ (q∨r), s→¬ q, p, s. 结论: r. 证明： ① p 前提引入 ② p → (q∨r) 前提引入 ③ q ∨r ①②假言推理 ④ s 前提引入 ⑤ s →¬ q 前提引入 ⑥ ¬ q ④⑤假言推理 ⑦ r ③⑥析取三段论

(2) 令 p: 小王是理科生, q: 小王是文科生, r: 小王的数学成绩很好. 前提: p → r, ¬ q → p, ¬ r 结论: q 证明:

① p → r 前提引入 ② ¬ r 前提引入 ③ ¬ p ①②拒取式 ④ ¬ q → p 前提引入 ⑤ q ③④拒取式