离散数学习题三

11、填充下面推理证明中没有写出的推理规则。 前提：?p?q,?q?r,r?s,p 结论：s

证明：① p 前提引入 ②?p?q 前提引入

③ q （①②析取三段论） ④?q?r 前提引入

⑤ r （③④析取三段论） ⑥r?s 前提引入

⑦ s （⑤⑥假言推理）

12、填充下面推理证明中没有写出的推理规则。 前提：p?(q?r),q?(r?s) 结论：(p?q)?s

证明：①(p?q) （附加前提） ② p （①化简规则） ③ q （①化简规则） ④p?(q?r) 前提引入 ⑤q?r （②④假言推理） ⑥ r （③⑤假言推理） ⑦q?(r?s) 前提引入 ⑧(r?s) （③⑦假言推理） ⑨ s （⑥⑧假言推理） 13、前提：?(p?q)?q,p?q,r?s

结论1：r 结论2：s 结论3：r?s

（1）证明从此前提出发，推出结论1，结论2，结论3的推理都是正确的。 （2）证明从此前提出发，推任何结论的推理都是正确的。 证明：（1）①((?(p?q)?q)?(p?q)?(r?s))?r

②((?(p?q)?q)?(p?q)?(r?s))?s ③((?(p?q)?q)?(p?q)?(r?s))?(r?s)

即结论

1，结论2，结论3的推理都是正确的。

（2）(?(p?q)?q)?(p?q)?(r?s)

即推任何结论的推理都是正确的。

14、在自然推理系统P中构造下面推理的证明： （1）前提：p?(q?r)，p,q 结论：r?s

证明：①p?(q?r) 前提引入 ② p 前提引入 ③ (q?r) ① ②假言推理

④ q 前提引入 ⑤ r ③ ④假言推理 ⑥ r?s ⑤ 附加律

15、在自然推理系统P中用附加前提法证明下面的推理： 前提：p?(q?r)，s?p,q

结论：s?r 证明：

① s 附加前提引入 ② s?p 前提引入 ③ p ① ②假言推理 ④ p?(q?r) 前提引入 ⑤ q?r ③ ④假言推理 ⑥ q 前提引入

⑦ r ⑤ ⑥假言推理 即根据附加前提证明法，推理正确。

16、在自然推理系统P中用归谬法证明下面的推理： 前提：p?q，q?r,q?s 结论：r?s 证明：

① ?(r?s) 结论否定引入 ② p?q 前提引入

③ q?r 前提引入 ④ q?s 前提引入

⑤ r?s ② ③ ④构造性二难 ⑥ ?(r?s)?(r?s) ① ⑤ 合取

因为⑥为矛盾式即推理正确

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

证明：① q?s 前提引入 ② ?s 前提引入 ③ ?q ① ②拒取式 ④ p 前提引入 ⑤ p??q ③ ④合取 ⑥ (p??q)?r 前提引入 ⑦ r ⑤ ⑥假言推理

张梦婷