离散数学与应用数理逻辑部分课后习题答案

.

证明：（1）真值表法：

p q r ?p ?r p??r q?r (p??r)?(q?r)?q 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 0 1 1 0 1 1 1 0 1 0 0 0 1 0 0 0 0 (p??r)?(q?r)?q??p 1 1 1 1 1 1 1 1 所以(p??r)?(q?r)?q??p为永真式；推理(p??r)?(q?r)?q??p是正确的。

（2）等值演算：

(p??r)?(q?r)?q??p?(?p??r)?(?q?r)?q??p??((?p??r)?(?q?r)?q)??p?((p?r)?(q??r)??q)??p?(p?r)?(q??r)??q??p?((p?r)??p)?((q??r)??q)?((p??p)?(r??p))?((q??q)?(?r??q))?(1?(r??p))?(1?(?r??q))?(r??p)?(?r??q)?(r??p)?(?r??q)?r??r??p??q?1（3）主析取范式

(p??r)?(q?r)?q??p?(?p??r)?(?q?r)?q??p??((?p??r)?(?q?r)?q)??p?((p?r)?(q??r)??q)??p?(p?r)?(q??r)??q??p?(p?(?q?q)?r)?((?p?p)?q??r)?((?p?p)??q?(?r?r))?(?p?(?q?q)?(?r?r))........?m0?m1?m2?m3?m4?m5?m6?m7

word范文

.

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

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

结论：?p 证明： ①?(q?r) ②?q??r ③r

前提引入 ①置换 前提引入 ②③析取三段论 前提引入 ④⑤拒取式

④?q ⑤p?q ⑥?p

（4）前提：q?p,q?s,s?t,t?r

结论：p?q 证明： ①t?r ②t ③r

前提引入 ①化简 ①化简 前提引入

④s?t

⑤(s?t)?(t?s) ④置换 ⑥t?s ⑦q?s

⑤化简 前提引入

⑧(q?s)?(s?q) ⑦置换

word范文

.

⑨s?q ⑩t?q

11q ○

⑧化简 ⑥⑨假言三段论

②⑩假言推理

前提引入

11○12假言推理 ○12○13合取 ○

12q?p ○13p ○

⑨p?q

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

结论：s?r 证明： ①s

附加前提引入 前提引入 ①②假言推理 前提引入 ③④假言推理 前提引入 ⑤⑥假言推理

②s?p ③p

④p?(q?r) ⑤q?r ⑥q ⑦r

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

结论：r?s 证明： ①?(r?s) ②?r??s ③?s ④?r ⑤p?r ⑥q?s ⑦?p ⑧?q

结论否定引入 ①置换 ②化简 ②化简 前提引入 前提引入 ④⑤拒取式 ③⑥拒取式 ⑦⑧合取 ⑨置换 前提引入

⑨?p??q ⑩?(p?q)

11p?q ○

11矛盾。 ⑩○

word范文

.

17：在自然推理系统P中构造下面推理的证明：

只要A曾到过受害者房间并且11点以前没有离开，A就是谋杀嫌疑犯。A曾到过受害者房间。如果A在11点以前离开，看门人会看见过他。看门人没有看见他。所以，A是谋杀嫌疑犯。 解答：

（1） 命题符号化：p:A曾到过受害者房间；q:A在11点以前离开；

r: A就是谋杀嫌疑犯；s:看门人会看见过A；

（2） 推理的形式结构：

前提：(p??q)?r;p;q?s;?s 结论：r （3） 证明

①?s ②q?s ③?q ④p

前提引入 前提引入 ①②拒取式 前提引入 ③④合取 前提引入 ⑤⑥假言推理。

⑤p??q

⑥(p??q)?r ⑦r

P63:习题四

5、在一阶逻辑中讲下列命题符号化。 （3）不存在比所有火车都快的汽车。 （4）凡是汽车就比火车慢是不对的。

解答：F(x):x为火车；G(y)：y为汽车；H(x,y)：y比x快。

（3）?(?y?x(G(y)?F(x)?H(x,y))) （4）??y?x(G(y)?F(x)?H(y,x))

6、将下列命题符号化，个体域为实数集合R，并指出各命题的真值。 （1）对所有的x，都存在y使得x?y?0。 （3）对所有的x，都存在y使得y?x?1。 解答：F(x,y):x?y?0;G(x,y):y?x?1 （1）?x?yF(x,y)，真值为1； （3）?x?yG(x,y)，真值为1； 9、给定解释I如下。

word范文

.

（a）个体域为实数集合R。 （b）特定元素a?0。

（c）函数f(x,y)?x?y,x,y?R

（d）谓词F(x,y):x?y,G(x,y):x?y,x,y?R。 给出下列公式在I下的解释，并指出它们的真值。 （1）?x?y(G(x,y)??F(x,y)) （3）?x?y(G(x,y)??F(f(x,y),a))

解答：（1）对任意的x和y，如果x?y,那么x?y。真值为1；

11、判断下列各式的类型。

（2）?x(F(x)?F(x))??y(G(y)??G(y)) （4）?x?yF(x,y)??y?xF(x,y)

解答：（2）?x(F(x)?F(x))真值为1；?y(G(y)??G(y))真值为0；

所以?x(F(x)?F(x))??y(G(y)??G(y))真值为0，所以为永假式。 （4）?x?yF(x,y)与?y?xF(x,y)真值相同，所以为永真式。

13、给出下列各公式的一个成真解释和一个成假解释。 （1）?x(F(x)?G(x)) （2）?x(F(x)?G(x)?H(x)) （3）?x(F(x)??y(G(y)?H(x,y)) 解答：

（1）成真解释：F(x):x为偶数；G(x):x为奇数

成假解释：F(x):x为偶数；G(x):x为素数

（3）对任意的x和y，如果x?y,那么x?y?0。真值为1；

（2）成真解释：F(x):x能被2整除；G(x):x能被3整除；H(x):x能被5整除。

成假解释：F(x):x为偶数；G(x):x为奇数，H(x):x为素数

（3）成真解释：F(x):x为正数；G(x):x负数；H(x，y):x?y。

成假解释：F(x):x为正数；G(x):x负数；H(x，y):x?y。欢迎您的光临，word文档下载后可以修改编辑。双击可以删除页眉页脚。谢谢！单纯的课本内容，并不能满足学生的需要，通过补充，达到内容的完善

word范文