离散数学习题解
此形式结构为重言式, 即 (p?r) ??p??r 故推理正确.
11
推理是否正确, 可用多种方法证明. 证明的方法有真值表法, 等式演算法. 证明推理正确还可用构造证明法.
下面用构造证明法证明(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
离散数学习题解
结论: r?s
(6)前提: ?p?r, ?q?s, p?q 结论: t??(r?s) (1)证
明:
12
① ② ③ ④ ⑤ ⑥
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
⑤附加
说明: 证明中, 附加提前 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
⑤⑥假言推理
13
离散数学习题解
(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)
①⑤合取
14
离散数学习题解
⑥为矛盾式, 所以推理正确.
15
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 p?q?r
s s ???q ?q
q?r
r
(1)的证明树
④⑤假言推理
③⑥析取三段论