离散数学习题解答(耿素云屈婉玲)北京大学出版社 下载本文

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

主析取范式法:

?p?q???p??q???p?q???p??q?(??p??p???q??p?)??q??p??q?p??q?M1?m0?m2?m3,从而可知不是重言式,故推理不正确。

(5)设p:今天是星期一,q:明天是星期二,r:明天是星期三。推理的形式结构为p?q?r。

p?(q?r)??p?q?r?M4?m0?m1?m2?m3?m4?m5?m6?m7,由此可知p?(q?s)不为重言式,

故推理不正确。

显然该式不是重言式,所以推理不正确。

(6)设p:今天是星期一,r:明天是星期三,推理的形式结构为(p?r)??p??r。

(p?r)??p??r??((p?r)?(r?p)??p)??r??(?p?r)??(?r?p)?p??r?(p??r)?(?p?r)?p??r?p?(?p?r)??r?p?m4?m5?m6?m7

7.在下面各推理中没给出结论。请对于每个推理前提给出两个结论,使其中之一是有效的,而另一个不是有效的:

(1)前提:p?q,q?r (2)前提:(p?q)?r,?r,q (3)前提:p?(q?r),p,q

解:(1)结论1:p?r为有效的(假言三段论) 结论2:p为无效的。

(2)结论1:??p?q?是有效的(拒取式)

结论2:p是无效的

,由此可知不为重言式,故推理不正确。

(3)结论1:(q?r)是有效的(假言三段论)

结论2:r是无效的

8.在下面各推理中没给出结论,请对于每个推理前提给出两个结论,使其中之一是有效的,而另一个不是有效的。

(1)只有天气热,我才去游泳。我正在游泳,所以??

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

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

(2)只有天气热,我就去游泳。我没去游泳,所以??

(3)除非天气热并且我有时间,我才去游泳。天气不热或我没时间,所以?? 解:

(1)设p:天气热,q:我去游泳 前提:q?p,q

结论1:p,有效结论(假言推理) 结论2:?p,无效结论

(2)设p:天气热,q:我去游泳。 前提:p?q,?q

结论1:?p,有效结论(拒取式) 结论2:p,无效结论

(3)设p:天气热,q:我有时间,r:我去游泳。

前提:r??p?q?,?p??q 结论1:?r,有效结论(拒取式) 结论2:r,无效结论。

9.用三种方法(真值表法,等值演算法,主析取范式法)证明下面推理是正确的:

若a是奇数,则a不能被2整除。若a是偶数,则a能被2整除。因此,如果a是偶数,则a不是奇数。

解:设p:a是奇数,q:a能被2整除,r:a是偶数。

推理的形式结构为?p??q???r?q???r??p?(*)。下面用三种方法证明该式为重言式:

(1) 真值表法:

p q r 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 (p??q)?(r?q) 0 1 0 0 0 1 1 1 (r??p) 1 1 1 1 1 0 1 0 * 1 1 1 1 1 1 1 1 由真值表可知(*)为重言式,故推理是正确的。

(2) 等值演算法:

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

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

?p??q???r?q???r??p????p??q????r?q????r??p???p?q????q?r???p??r???p?q???p?????q?r???r?(交换律,结合律) ???p?q????q??r???p??q??q???r?1

(3) 构造证明法:

前提:?p??q?,?r?q? 结论:?r??p?

证明:

①p??q 前提引入 ②q??p ①置换 ③r?q 前提引入

④r??p ③②假言三段论 主析取范式法

由方法2可以得知推理的形式结构(*)的主析取范式为

(*)?m0?m1?m2?m3?m4?m5?m6?m7,则(*)为重言式,推理正确。

10.用两种方法(真值表法,主析取范式法)证明下面推理不正确:

如果a,b两数之积是负数,则a,b之中恰有一个是负数。a,b两数之积不是负数,所以a,b中无负数。

真值表法:

(q??r)?(?q?r) p?(q??r)?(?q?r) ?q??r p q r A 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 0 1 1 0 0 1 1 0 1 1 1 1 0 1 1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 1 1 推理不正确

主析取范式法:

(p?((q??r)?(?q?r))?(?q?r))??p)?(?q??r)?(?p?(q??r)?(?q?r)??p?(?q??r))??p?(?q??r)?p?(?q??r)?m0?m4?m5?m6?m7文章来源:http://www.7zhao.net

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

由于主析取范式只含有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:

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