离散数学习题解
○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)的证明树
④⑤假言推理
③⑥析取三段论
离散数学习题解
(2) 令 p: 小王是理科生, q: 小王是文科生, r: 小王的数学成绩很好. 前提: p?r, ?q?p, ?r 结论: q 证明:
16
① ② ③ p?r ?r ?p 前提引入 前提引入 ①②拒取式 ?q ?p p?q
?r?p
④ ?q?p 前提引入 ⑤
q
③④拒取式
(2)
的证明树
(3)令 p: 明天是晴天, q: 明天是雨天, r: 我看电影, s: 我看书. 前提: p?q, p?r, r??s 结论: s?q 证明:
① s 附加前提引入 ② r??s 前提引入 ③ ?r ①②拒取式 ④ p?r 前提引入 ⑤ ?p ③④拒取式 ⑥ p?q 前提引入 ⑦
q
⑤⑥析取三段论
r