离散数学习题解答耿素云屈婉玲北京大学出版社(供参考)

文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

主析取范式法：

由于主析取范式只含有5个极小项，所以（3.8）不是重言式，推理不正确。 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） 证明：

结论1： 结论2： 结论3：

（2） 证明：

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

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

文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

（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 结论：t?(r?s) （1） 证明

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

r （5）

r?s （6）

（2） 证明

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

r （3） （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 （3） （2）置换 (?p?q)?(?p?p) （4） （3）置换 ?p?(q?p)

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

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

t?s （2）

t?r （3）

t?r （4）

t （5）

s （6） （7） q?s

（1）置换 （2）换件 前提引入 （4）化简 （3）（5）假言推理 前提引入

文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

（8） (q?s)?(s?q) （9） s?q （10） q （11） q?p （12） p （13） p?q

（5） 证明

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

（7）置换 （8）化简 （6）（9）假言推理 前提引入 （10）（11）假言推理 （10）（12）合取 前提引入 （1）化简 （1）化简 前提引入

（2）（4）假言推理 前提引入

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

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

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

r （5） （6） q?s

s （7）

r?s （8）

（6） 证明

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

r （5） （6） ?q?s

s （7）

r?s （8） （9） ?t?(r?s) （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） 证明

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

r （7）

（2） 证明

（1） p （2） p?q

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

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

文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

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

r?s （4）

s （5） s?t （6） （7） (s?t)?u

前提引入

（2）（3）假言推理

（4）化简 （5）附加 前提引入

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

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

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

结论：r?s （1） 证明

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

?r （5）

r??s （6）

r （7） ?r?r （8）

（2） 证明

（1） ?(r?s)

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

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

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

?r （3） （2）化简 ?s （4） （2）化简 （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）

q?s 前提引入