离散数学习题解答（耿素云屈婉玲）北京大学出版社

去找 QQ头像 http://www.7zhao.net

(?(p?q)?q)?(p?q)?(r?s)?r??p??q?q???p?q???r?s??r?0??p?q???r?s??r?0?r?1结论2：

(?(p?q)?q)?(p?q)?(r?s)?s??p??q?q???p?q???r?s??s?0??p?q???r?s??s?0?s?1结论3：

(?(p?q)?q)?(p?q)?(r?s)?r?s??p??q?q???p?q???r?s??r?s?0??p?q???r?s??r?s?0?r?s?1（2） 证明：

设任何可能的结论为*, 则：

(?(p?q)?q)?(p?q)?(r?s)?*??p??q?q???p?q???r?s??*?0??p?q???r?s??*?0?*?1

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

（2）前提：p?q，?(q?r)，r 结论：?p （3）前提：p?q 结论：p?(p?q)

（4）前提：p?q，q?s，s?t，t?r 结论：p?q

（5）前提：p?r，q?s，s?tt?r 结论：r?s

（6）前提：?p?r，?q?sp?q

文章来源：http://www.7zhao.net

去找 QQ头像 http://www.7zhao.net

结论：t?(r?s)

（1） 证明

（1） p?(q?r) （2） p （3） q?r （4） q

（5） r （6） r?s

（2） 证明

?(q?r) （1） （2） ?q??r

（3） r （4） ?q （5） p?q （6） ?p

前提引入 前提引入 （1）（2）假言推理 前提引入 (3)(4)假言推理 （5）附加 前提引入 （1）置换

前提引入 （2）（3）析取三段论 前提引入 （4）（5）拒取式

（3） 证明

（1） p?q 前提引入 （2） （1）置换 ?p?q

(?p?q)?(?p?p) （3） （2）置换 ?p?(q?p) （4） （3）置换 （5） p?(p?q) （4）置换 （4） 证明

(s?t)?(t?s) 前提引入 （1）

（2） （1）置换 t?s （3） （2）换件 t?r （4） 前提引入 t?r （5） （4）化简 t （6） （3）（5）假言推理 s （7） 前提引入 q?s

(q?s)?(s?q) （7）置换 （8） （9） （8）化简 s?q

（10） q （6）（9）假言推理 （11） q?p 前提引入 （12） p （10）（11）假言推理 （13） p?q （10）（12）合取

（5） 证明

（1） p?q （2） p （3） q （4） p?r

（5） r

前提引入 （1）化简 （1）化简 前提引入

（2）（4）假言推理

文章来源：http://www.7zhao.net

去找 QQ头像 http://www.7zhao.net

（6） q?s

（7） s （8） r?s

（6） 证明

（1） p?q （2） p （3） q （4） ?p?r

前提引入

（3）（6）假言推理 （5）（7）合取 前提引入 （1）化简 （1）化简 前提引入

（2）（4）析取三段论 前提引入

（3）（6）析取三段论 （5）（7）合取 （8）附加 （9）置换

（5） r （6） ?q?s

（7） s （8） r?s

?t?(r?s) （9）

（10） t?(r?s)

15.在自然推里系统p中用附加前提法证明下面各推理： （1）前提：p?(q?r)，s?p，q 结论：s?r

（2）前提：(p?q)?(r?s)，(s?t)?u 结论：p?u

（1） 证明

（1） s （2） s?p （3） p （4） p?(q?r) （5） q?r （6） q （7） r

（2） 证明

（1） p （2） p?q

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

（4） r?s （5） s （6） s?t

(s?t)?u （7）

附加前提引入 前提引入 （1）（2）假言推理 前提引入 （3）（4）假言推理 前提引入

（5）（6）假言推理 附加前提引入 （1）附加 前提引入

（2）（3）假言推理 （4）化简 （5）附加 前提引入

（8） （6）（7）假言推理 u

16.在自然推理系统p中用归谬法证明下面推理： （1）前提：p??q，?r?qr??s 结论：?p

（2）前提：p?q，p?r，q?s 结论：r?s

文章来源：http://www.7zhao.net

去找 QQ头像 http://www.7zhao.net

（1） 证明

（1） p （2） p??q （3） ?q （4） ?r?q （5） ?r （6） r??s （7） r （8） ?r?r

（2） 证明

?(r?s) （1）

结论否定引入 前提引入 （2）（1）假言推理 前提引入

（3）（4）析取三段论 前提引入 （6）化简 （5）（7）合取 结论否定引入

（2） (1)置换 ?r??s

（3） （2）化简 ?r （4） （2）化简 ?s

（5） p?r 前提引入 （6） （3）（5）拒取式 ?p （7） 前提引入 q?s （8） （4）（7）拒取式 ?q （9） （9）置换 ?p??q

（10） q?p 前提引入 （11） ?(p?q)?(p?q) （10）（11）合取

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 证明

（1）

（2） （3） （4） （5） （6） （7）

q?s

?s ?q

前提引入 前提引入 （2）（1）拒取式 前提引入 （3）（4）合取 前提引入

（5）（6）假言推理

(p??q)?r r

p

p??q

18.在自然系统p中构造下面各推理的证明：

(1)如果今天是星期六，我们就要去颐和园或圆明园玩。如果颐和园游人太多，我们就不去颐和园玩。今天是星期六，颐和园游人太多，所以我们去圆明园玩。

文章来源：http://www.7zhao.net