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

由天下分享时间：2024/11/15 11:39:43 加入收藏我要投稿点赞

⑨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矛盾。 ⑩○

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如下。

（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；